Тема: способи реалізації структур даних. Формальні та фактичні параметри, хеш-таблиця (словник), масив, список, стек, черга мовою C++.

Мета: сформувати предметні компетенції щодо способів реалізації структур даних мовою C++.

Учень повинен пояснювати:

• способи реалізації структур даних;
• відмінність між формальними та фактичними параметрами;
• призначення хеш-таблиць;
• призначення масивів, списків, стеків, черг.

Учень повинен вміти:

• використовувати різні способи реалізації структур даних;
• створювати та опрацьовувати масиви;
• створювати хеш-таблиці та працювати з ними;
• використовувати списки та виконувати основні операції в зв'язному списку;
• працювати зі стеками та чергами;

Обладнання: комп’ютери IBM PC з встановленими ОС та браузером.

Структура уроку

1. Організаційний момент.
2. Актуалізація опорних знань.
3. Вивчення нового матеріалу.
4. Інструктаж з ТБ.
5. Вироблення практичних навичок.
6. Підбиття підсумків уроку.
7. Домашнє завдання.

Хід уроку

1. Організаційний момент
Вітання з класом. Перевірка присутності і готовності учнів до уроку. Перевірка виконання домашнього завдання.

2. Актуалізація опорних знань

Принцип модульності у програмуванні формулюють як вимогу подати програму у виді сукупності модулів (функцій):

• розмір модуля повинний бути обмежений;

• модуль має виконувати логічно цілісну і завершену дію;

• модуль має бути по можливості параметричним, тобто усі змінювані характеристики виконуваної дії потрібно передавати через параметри;

• вхідні параметри і результат модуля бажано передавати не через глобальні змінні, а через формальні параметри і результат функції.

У мові С++ модулі реалізують у вигляді функцій. При виконанні функції можуть відбутися зміни в керованій системі, причому як оборотні, так і необоротні.

Функція — логічно самостійна частина програми з назвою (ідентифікатором), за допомогою якої здійснюють виклик функції. Функція може мати список аргументів (параметрів), які передають їй для використання. Цей список параметрів (аргументів) записують у круглих дужках ( ) одразу після назви через кому. При відсутності такого списку функцію називають функцією без параметрів. Може повертати (не обов'язково) деяке значення. У цьому випадку в описі функції перед її назвою вказують тип значення, яке повертають. Інакше замість назви типу використовують слово void.

Загальна форма опису функції

тип назва_функції (список_параметрів) // прототип функції
{ …             // тіло функції
  return вираз; // тіло функції
}

Прототип (оголошення) функції — це повідомлення компілятору про наявність функції з певною назвою.

Прототип функції містить скорочений опис функції без тіла функції. Як правило, прототипи окремо без тіла функції записують перед описом функцій при наявності хоча б 2 функцій, у тілі кожної з яких є виклик іншої. Це роблять з метою уникнення помилки компіляції.

Тіло функції — вказівки функції, записані між фігурними дужками { } після назви.

Побічний ефект функції — будь-яка зміна функцією стану програмного середовища, крім повернення результату (зміна значень глобальних змінних, виділення й звільнення пам'яті, введення-виведення тощо).

Теоретично найправильнішим вважають використання функцій без побічних ефектів. Хоча на практиці доводиться використати функції з побічним ефектом, наприклад, для забезпечення введення-виведення й відображення результатів роботи програми.

Існує специфічна парадигма програмування — функціональне програмування, у якій будь-яка програма є набором вкладених викликів функцій, що не викликають побічних ефектів. Найвідомішою мова програмування, що реалізує цю парадигму, є Лісп. У ній будь-яка операція, будь-який вираз окрім сталої є викликом функції.

Згідно з парадигмою функціонального програмування складну задачу чи громіздкий алгоритм можна реалізувати як сукупніть окремих функціональних блоків. У С++ ці частини реалізують як функції. Окремі функції об'єднують у спільну програму. У відкомпільованому вигляді така програма утворює модуль.

Види функцій мови С++

• головна функція main, яку обов'язково містить кожна програма;
• стандартні функції, наявні (описані) у бібліотеках;
• функція користувача.

3. Вивчення нового матеріалу

Способи передавання параметра у функцію

• за значенням (call by value) — передають копії змінних. Інакше кажучи, зміна значень параметрів у тілі функції не змінює значень змінних, переданих у функцію ззовні при її виклику;

• за адресою змінної — передають копію адреси змінних. Використовуючи такий покажчик, функція здійснює доступ до потрібних комірок пам'яті, де розташовано передану змінну, і може змінювати її значення. Таким чином передають масиви і прості об'єкти, які є вихідними даними або вхідними й вихідними одночасно;

• за посиланням (call by reference) — передають посилання (покажчик) на об'єкт (змінну), що дозволяє використовувати це посилання і як покажчик, і як значення. Зміна у тілі функції значення параметра, переданого за посиланням, змінює вихідну копію параметра за межами викликає функції.

У поданому далі прикладі передано параметри: x — за значенням, y — за адресою (як покажчик), z — за посиланням.

#include <iostream>
using namespace std;
void f (int  x, int* y, int& z)
{ x = 1;
 *y = 1;
  z = 1;
}
int main()
{ int a,b,c;
  a=b=c=0;
  f (a, &b, c);
  cout << a << b << c;
  return 0;
}

У результати виконання цього коду буде виведено таке:

011

Формальний параметр — це ідентифікатор (змінна) в описі параметрів функції. Наприклад, у прикладі вище — це x, y, z.

Область видимості формального параметра функції визначається межами тіла функції.

Фактичний параметр (аргумент) — це значення, передане у функцію для надання цього значення формальному параметру. У поданому вище прикладі 0, 0, 0 — це фактичні параметри функції f. У разі передачі даних за адресою фактичний параметр може бути лише змінною — стала або вираз не мають адреси!

Опис структури даних є важливою складовою розробки програмного забезпечення. Розглянемо кілька найпоширеніших структур даних та їхню реалізацію мовою C++. Типовим інструментом для представлення однорідних даних є масив.

Масив — згруповані за місцем розташування у пам'яті величини, що мають одну назву (ідентифікатор) і різні порядкові номери (індекси). Це поняття програмування відповідає математичним поняттям послідовності й таблиці (матриці).

Елемент масиву — одна з величин, що утворюють масив. Це поняття програмування відповідає математичному поняттю елемента послідовності чи матриці.

Індекс масиву — величина перелічуваного (зазвичай цілого) типу, яка (сукупність яких) вказує на конкретний елемент масиву. Це поняття програмування відповідає математичному поняттю номера елемента послідовності чи номеру рядка/стовпчика таблиці (матриці). У мові C++ найменше значення індексу — 0.

Масив має такі властивості:

• тип (типи) елементів (масиву);
• назва (ідентифікатор) — одна й та сама для всіх елементів масиву;
• розмірність — кількість номерів (індексів), необхідних для визначення розташу­вання елемента у масиві;
• діапазони зміни номерів (індексів).

У мові C++ властивості елементів масиву не можна змінити протягом виконання програми. В деяких інших мовах це можливо.

Cукупність розмірності й діапазонів називають формою масиву.

Звернення до значення елемента масиву у коді програми здійснюють, вказавши після його назви у квадратних дужках індекси у вигляді (арифметичних) виразів, що набувають значень з діапазопу порядкового типу.

Наприклад, а[3] — 3-тій елемент масиву а, с[j] — j-ий елемент масиву с.

Елемент масиву може мати і тип простої (неструктурованої) величини і складений тип (масиву, рядка тощо), тобто може існувати масив масивів, масив рядків тощо. Глибину вкладеності (а значить, і кількість індексів) необмежено, але загальну довжину структури обмежено. У пам'яті ПК всі елементи масиву зберігають послідовно: при переході від молодших до старших адрес першим буде змінено індекс, записаний останнім (праворуч).

Під час розв'язування задач переважно використовують одновимірні та двовимірні масиви.

Одновимірний масив інакше називають лінійним масивом або вектором. Кожному його елементу ставлять у відповідність один індекс. У математиці лінійному масиву відповідає поняття послідовності, а номеру члена послідовності — індекс масиву.

Двовимірний масив інакше називають таблицею або матрицею. Кожному його елементу ставлять у відповідність два індекси: номер рядка та номер стовпчика. Прикладом унаочнення двовимірного масиву є шахівниця.

Примітка. Використання масивів розмірності 2 і більше зумовлено лише міркуваннями зручності для програмістів. Наприклад, існує взаємно однозначна відповідність j = kn + l між індексом j — у межах від 0 до (mn – 1) і парою індексів (k, l) при k — у межах від 0 до (m – 1), l — у межах від 0 до (n – 1). А саме: при діленні j на n маємо: k — частка, l — лишок.

Роботу з масивами описано у наявній розробці.

Зв'язний список — лінійно упорядкована структура (послідовність) даних, елементи якої — вузли — містить два види даних:

Використовують також двічі зв'язні списки, в яких кожен вузол має вказіваник і на наступний, і на попередній елемент списку.

Основні дії зі зв'язним списком:

• додавання елемента у список;
• вилучення елемента зі списку;
• пошук елемента (з певними властивостями) у списку.

Контейнер list (список) у мові С++ задає двонаправлений список. У ці списки можна швидко вставляти, а також видаляти елементи з них. Доступ до елементів списку (як і всіх наступних структур) здійснюють за допомогою вказівників (ітераторів).

• #include <list> — замовлення необхідної бібліотеки;
• list <тип_даних> назва_списку; — опис списку;
• list <тип_даних> :: iterator назва_ітератора; — опис ітератора (вказівника);
• l.begin() — вказівник на початок списку l;
• l.end() — вказівник на кінець списку l;
• l.rbegin() — реверсивний вказівник на кінець списку l;
• l.rend() — реверсивний вказівник на початок списку l;
• l.empty() — істинність висловлювання: «Список l порожній»;
• l.push_back(e) — додати елемент e в кінець списку l;
• l.pop_back() — видалити останній елемент списку l;
• l.front() — перший елемент списку l;
• l.back() — останній елемент списку l;
• l.insert(i,e) — вставлення елемента e в позицію i списку l;
• l.erase(j,k) — видалення зі списку l послідовності елементів від позиції j до позиції k

— див. приклад.

Контейнер vector (вектор) у мові С++ призначено для зберігання послідовності значень одного типу, до елементів якої доступ здійснюють за допомогою вказівників (ітераторів):

• #include <vector> — замовлення бібліотеки для роботи з векторами;
• vector <тип> v; — створення порожнього вектора v;
• v.begin() — вказівник на початковий елемент вектора v;
• v.end() — вказівник на кінцевий елемент вектора v;

Додавання елементів (див. приклад)

• v.push_back(a) — додавання значення a в кінець вектора v;
• v.emplace_back(a) — додавання значення a в кінець вектора v;
• v.emplace(p,a) — вставлення значення a на позицію p вектора v;
• v.insert(p,a) — вставлення значення a на позицію p вектора v;
• v.insert(p,n,a) — вставлення n значень a, починаючи з позиції p вектора v;
• v.insert(p,b,e) — вставлення, починаючи з позиції p, елементи з іншого контейнера з діапазону між вказівниками b і e;
• v.insert(p,l) — вставлення списку значень l, починаючи з позиції p вектора v;

Вилучення елементів (див. приклад)

• v.clear() — вилучення усіх елементів з вектора v;

• v.pop_back() — вилучення останнього елемента з вектора v;

• v.erase(p) — вилучення з вектора v елемента, на який вказує ітератор p, повернення вказівника на елемент, наступний після вилученого або на кінець контейнера, якщо вилучено останній елемент;

• v.erase(b,e) — вилучення елементів вектора v з діапазону, на початок і кінець якого вказують ітератори b і e, повернення вказівника на елемент, наступний після останнього вилученого, або на кінець контейнера, якщо вилучено останній елемент;


Розмір вектора (див. приклад)

• v.size() — повертає кількість елементів вектора v;

• v.resize(n) — залишає n перших елементів у векторі v. Якщо розмір вектора менший ніж n, то доданим елементам буде надано значення як усталено для компілятора;

• v.resize(n,a) — залишає n перших елементів у векторі v. Якщо розмір вектора менший ніж n, то доданим елементам буде надано значення a;

Зміна значень елементів вектора (див. приклад)

• v.assign(…) — надання значення вектору v;
• v.swap(u) — обмін вмістом векторів v і u;

Порівняння векторів (див. приклад)

• == — «дорівнює» (збігається за значенням);
• != — «відмінне» (різниться за значенням);
• < — «менше»;
• > — «більше»;
• <= — «не перевищує» (менше або дорівнює);
• >= — «не менше» (більше або дорівнює);

Стек — лінійно упорядкована структура (послідовність) даних, у яку можна вставити елемент або з якої можна вилучити елемент лише з одного кінця.

Стек нагадує стос аркушів паперу у вузькій шухляді: щоб узяти певний аркуш, потрібно спочатку прибрати всі аркущі над ним. Кажуть, що для стеку діє принцип: «Останній зайшов, перший вийшов» (англій­ською LIFO: Last In First Out).

Основні операції зі стеком:

• вставлення елемента в кінець стеку;
• вилучення елемента з кінця;
• відображення вмісту останнього долученого елемента.

Наявні вбудовані функції для роботи з векторами дозволяють втілити ідею стеку.

Контейнер stack безпосередньо втілює принцип: «Останній зайшов, перший вийшов» (англій­ською LIFO: Last In First Out):

• #include <stack> — замовлення бібліотеки;
• stack <тип_даних> назва; — форма опису стека;
• t.empty() — повертає результат встановлення істинності висловлювання: «Стек t порожній»;
• t.size() — повертає розмір стека t;
• t.top() — повертає посилання на верхній елемент стека t;
• t.push(e) — додає елемент e у верхню частину стека t;
• t.pop() — видаляє самий верхній елемент стека t

Прообразом цієї структури є чергу людей у магазині: того, що став першим, буде обслужено першим. Якщо розглядати чергу щодо доступу до даних, то вона реалізує принцип: «Першим зайшов, перший вийшов» (англій­ською First In First Out, FIFO). Інакше кажучи, після додавання нового елементу всі елементи, які було додано до цього, потрібно вилучити до того, як новий елемент буде вилучено.

Основні операції з чергою:

• вставлення елемента в кінець черги;
• вилучення елемента з початку черги.

Контейнер queue безпосередньо втілює принцип: «Першим зайшов, перший вийшов» (англій­ською First In First Out, FIFO):

• #include <queue> — замовлення бібліотеки;
• queue <тип_даних> назва; — форма опису черги;
• q.empty() — повертає результат встановлення істинності висловлювання: «Черга q порожня»;
• q.size() — повертає розмір черги q;
• q.push(e) — додає елемент e у чергу q;
• q.pop() — видаляє перший елемент черги q;
• q.front() — повертає перший елемент черги q;
• q.back() — повертає останній перший елемент черги q

На відміну від звичайних шаф, в асоціативний масив будь-коли можна додати нові «шухляди» або вилучити вже наявні.

Коллізія — випадок збігу виведення при різних аргументах хеш-функції.

Контейнер map (відображення) призначено для створення асоціативного масиву пар «ключ-значення» такими засобами:

• #include <map> — замовлення бібліотеки для роботи з контейнером map;
• map <<тип_ключа><тип_значення>> назва; — створення порожнього контейнера;
• map <<тип_ключа><тип_значення>> :: iterator назва; — створення вказівника;
• i->firsr — значення ключа пари, на яку вказує ітератор i;
• i->second — значення значення пари, на яку вказує ітератор i;
• i--; — збільшення значення вказівника i;
• i++; — зменшення значення вказівника i;
• advance(i,n); — при натуральному n — n-кратне застосування вказівки i++;
• advance(i,-n); — при натуральному n — n-кратне застосування вказівки i--;

Контейнер map в оперативній пам'яті упорядковано за ключем, що може не збігатися з порядком формування пар — див. приклад.

Вбудовані функції map

• size() — повертає кількість пар;
• insert(…) — долучає нову пару;
• erase(i) — вилучає пару, на яку вказує ітератор i;
• count(…) — кількість з даним ключем (0 або 1);
• find(…) — пошук пари з певним ключем:
  • якщо така є, то повернути вказівник на її місце розташування;
  • якщо такої немає, то повернути вказівник на кінець контейнера;

— див. приклад.

Істотна перевага типу map (відображення) така: ключем може бути змінна довільного типу. За цю перевагу (над масивом і вектором) потрібно заплатити збільшенням використаної пам'яті і тривалості операцій додавання пари, звернення до пари та видалення пари. Ефективність за часом перелічених операцій складає О(log n), де n — це розмір контейнера (кількість пар).

У контейнері multimap (тут не розглянуто) на відміну від контейнера map одному ключу можна задати кілька значень.

Set — контейнер для збереження унікальних значень (кожне не більше одного разу), що втілює математичне поняття множини.

При додаванні нового елемента в даному контейнері буде проведено упорядкування елементів. Повторювані елементи буде вилучено (на відміну від контейнера multiset, яке тут не розглянуто).

• #include <set> — замовлення бібліотеки;
• s.swap(t) — зміна місцями вмісту контейнерів s і t;
• s.insert(a) — долучення елемента a у множину s;
• s.erase(t) — вилучення з s елементів t;
• s.clear() — очищення контейнера s;
• s.count() — кількість елементів у контейнері;
• s.size() — розмір контейнера (кількість елементів);
• s.max_size() — максимальний розмір контейнера;
• s.begin() — вказівник на початок контейнера;
• s.end() — вказівник на кінець контейнера;
• s.rbegin() — реверсивний вказівник на кінець контейнера;
• s.rend() — реверсивний вказівник на початок контейнера.

— приклад, у якому використано функцію copy.

4. Інструктаж з ТБ
5. Вироблення практичних навичок

Створити програми для розв'язання таких задач
(при роботі з файлами: введення з файлу input.txt, виведення у файл output.txt):

1. Зчитати з файлу кількість цілих чисел й самі цілі числа. Всі вхідні дані у межах діапазону значень типу int. Розмістити парні числа на початку списку, непарні — в кінці і записати елементи списку у файл.

2. Заповнити випадковими числами різного знаку масив з 10 елементів. Вивести на консоль масив і список з додатних елементів масиву з непарними індексами.

3. Заповнити випадковими невід'ємними цілими числами від 0 до 5 включно масив з 10 елементів. Внести у список лише елементи масиву, що належать зовні проміжку [2, 4].

4. Заповнити випадковими цілими числами від −15 до 15 включно вектор з 10 елементів. Знайти суму абсолютних величин (модулів) елементів вектора, розташованих після першого від’ємного.

5. Заповнити випадковими цілими числами від 0 до 19 включно вектор з 5 елементів. Обчислити суму всіх цифр елементів вектора.

6. Створити асоціативний масив (словник) з 10 пар такого вигляду:
   
   прізвище (на власний вибір) : оцінка (у початковий момент 0).
   
   Надати оцінкам випадкових значень від 1 до 12 включно. Вивести значення середнього арифметичного оцінок і прізвища тих, у кого середній бал вищій, ніж середній бал по групі.

7. Створити асоціативний масив (словник), зв'язавши його зі змінною s, і наповнити даними, які б відображали кількість учнів в різних класах початкової школи: 1а, 1б, 2а, 2б, … , 4б. Вивести словник. В усіх класах змінити кількість учнів на 1, 2, 3 чи 4 і знову вивести словник. Обчислити загальну кількість учнів у школі й вивести її значення.

8. Використавши стек і функцію s.find(с), що повертає індекс позиції першого входження аргумента-рядка або аргумента-символа с у рядок s, перевірити, чи правильно розставлені дужки у заданому виразі. Програму перевірити, опрацювавши такі рядки:
   "[{([[[<>]]])(<>)(){}}]"
   "]()(){<>}[[()]]"
   "[(sjd),'2'],{2:3} [<>]"
   "{[[[[((()))]]<]>]}"
   і отримавши відповідно 1010, тобто true, false, true, false.

9. Використавши множину, змоделювати відповідь на повідомлення у формі прізвища:
   • при зверненні уперше: «Спасибі, що вибрали саме нас!»
   • при повторному зверненні: «Раді знову вас бачити!»

10. За квитками на прем'єру нового мюзиклу вишикувалася черга з N глядачів, кожний з яких хоче купити один квиток. На всю чергу працює лише одна каса, тому продаж квитків йшов дуже повільно, приводячи глядачів у відчай. Найкмітливіші швидко помітили, що, як правило, декілька квитків в одні руки касир продає швидше, ніж коли ці самі квитки продають по одному. Тому вони запропонували декільком людям, що стоять підряд, віддавати гроші першому з них, щоб він купив квитки на всіх. Але для боротьби із спекулянтами касир продавала не більше 3-х квитків в одні руки. Тому домовитися таким чином між собою могли лише двоє або троє глядачів. Відомо, що на продажу j-ій людині з черги одного квитка касир витрачає A_j секунд, на продаж двох квитків — B_j секунд, трьох квитків — C_j секунд. Написати програму, яка підрахує мінімальний час, за який можна обслужити усіх глядачів. Звернути увагу, що квитки на групу людей, що об'єдналися, завжди купує перший з них. Також ніхто в цілях прискорення не купує зайвих квитків.
    
    Формат файлу вхідних даних: Спочатку вводять число N — кількість глядачів у черзі (3 ≤ N ≤ 5000). Далі йде N трійок натуральних чисел A_j, B_j, C_j. Кожне з цих чисел не перевищує 999 999 999. Людей у черзі нумерують, починаючи з 0, від каси.
    
    Формат файлу вихідних даних. Вивести одне число — мінімальний час у секундах, за який можна обслужити N глядачів.
    
    Вказівка до виконання. Ефективні алгоритми комбінаторики як правило пов'язані з рекурентними співвідношеннями. Немає необхідності запам'ято­вувати всі вхідні дані.

Порівняти отримані розв'язання з демонстраційними: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

6. Підведення підсумків уроку
Виставлення оцінок.

7. Домашнє завдання
Вивчити навчальний матеріал уроку. Доробити при потребі розв'язання задач.