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

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

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

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

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

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

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

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

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

Хід уроку

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

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

Назвати найуживаніші вбудовані методи для роботи з масивами, описати їхнє призначення й порівняти з очікуваним:

• push/pop, shift/unshift, splice — додавання й видалення елементів;
• split/join — перетворення рядка у масив і навпаки;
• slice — копіювання частини масиву;
• sort — упорядкування (сортування) масиву;
• reverse — зміна порядку елементів на зворотній;
• concat — об'єднання масивів і елементів;
• indexOf/lastIndexOf — повернення номера елемента у масиві;
• Object.keys — повернення масиву властивостей об'єкта.

Назвати призначення вбудованих методів Math і порівняти з очікуваним:

• Math.abs — повертає модуль (абсолютну величину) аргумента;
• Math.random — повертає (псевдо) випадкове число з проміжку [0, 1];
• Math.round — округлює до найближчого цілого числа.

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

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

Формальні параметри — це параметри, перелічені в описі функції, процедури чи методу. У прикладі:

function getFirst(a,b) {return a;}

a, b — це формальні параметри функції getFirst.

Фактичні параметри (аргументи) — це ті значення, що було передано у функцію, метод або процедуру згідно з описом виклику функції, методу чи процедури. У прикладі:

getFirst(4,3);

4 і 3 — це фактичні параметри функції getFirst

Типовим інструментом для представлення однорідних даних є масив.

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

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

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

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

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

У мові Javascript тип елементів масиву (усіх чи окремо кожного) можна змінити протягом виконання програми довільним чином. Не у всіх мовах це можливо.

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 — лишок.

Порожній масив описують (створюють) таким чином:

var назва_масиву = new Array();

Після цього до нього можна долучати елементи або вилучати їх, змінюючи довжину. Замість постійного обліку кількості елементів масиву можна у потрібний момент використати метод length:

var назва_змінної = назва_масиву.length;

Також можна описати масив з одночасним заданням значень усіх його елементів. Наприклад, таким чином:

var a = [60, 50, 60, 58, 54, 54, 58, 50, 52, 54];

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

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

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

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

Можливість змінювати розмір масиву й наявні вбудовані методи для роботи з масивами дозволяють втілити ідею зв'язного списку звичайним масивом з використанням індекса елемент, збільшеного чи зменшеного на 1 як вказівника відповідно на наступний чи попередній елемент — див. приклад.

Примітка Цей і наступні приклади використовують виведення даних у середовища розробника, яке для Mozilla Firefox викликають натисканням клавіш Ctrl + Shift + K і далі вводять код у рядок, що починається символами >>. Можливо, доведеться перед кодом ввести allow pasting, щоб мати можливість копіювати код, а не вводити його посимвольно. Для роботи з середовищем online потрібно наприкінці коду замінити вказівки console.log на print.

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

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

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

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

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

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

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

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

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

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

Хеш-таблиця (hash table) — це структура даних для зберігання пар ключ-значення. Мовою Javascript таку структуру реалізують асоціативним масивом.

Асоціативний масив (словник в інших мовах програмування) — це вбудована структура даних для збереження даних у форматі ключ-значення.

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

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

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

У JavaScript є тип даних Array. Але цей тип даних призначено лише для створення масивів, у яких в якості ключів використовуються числа (індекси). В JavaScript починаючи з релізу ECMAScript 2015 (6) для створення асоціативного масиву можна використовувати об'єкт Map. До ECMAScript 2015 не існувало типу даних, призначеного виключно для створення асоціативних масивів. Їх створювали за допомогою об'єктів.

Об'єкт Map призначено для створення асоціативних масив — пар «ключ-значення». Як ключ можна використати дані довільного типу.

Маємо істотну відмінність від втілення асоціативних масивів об'єктами: для об'єктів у якості ключа можна використовувати лише рядки. Саме тому далі не розглянуто подання асоціативних масивів об'єктами, для яких усі перелічені нижче дії здійснені, але іншими засобами і часто з довшим кодом.

Вбудовані методи Map

• size — кількість пар (довжина масиву);
• set('key','value') — додавання пари ['key','value'];
• get('key') — отримання значення, асоційованого з ключем 'key';
• has('key') — встановлення, чи є у масиві ключ 'key';
• delete('key') — видалення пари за ключем 'key';
• clear() — очищення (видалення усіх пар).

Перебір пар об'єкта Map здійснюють за допомогою циклу:

for (let … of назва_об'єкта …);

за ключами, значеннями або парами: замість останньої трикрапки потрібно записати key, values або entries відповідно. Те саме можна зробити за допомогою методу forEach.

Все написане вище про Map можна подати одним прокоментованим кодом, який бажано виконувати по одній вказівці для зручності аналізу дії.

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

Опис (порожньої) множини має такий вигляд:

let назва_множини = new Set();

Множину можна утворити зі значень елементів масиву — див. приклад:

var a = [5,2,4,1,1,2,3,4];
var s = new Set(a);
console.log(s);      // Set [ 5, 2, 4, 1, 3 ]

Методи Set:

• add — додає елемент до множини;
• delete — вилучає елемент з множини;
• has — істинність висловлювання про належності елемента до множини;
• size — повертає кількість елементів множини;
• forEach — перебирає елементи множини, є альтернатива for (… of …).

Перелічені методи Set можна подати прокоментованим кодом.

Примітка Для сумісності с масивами, що також мають метод forEach, у цей метод передано функцію зворотнього виклику з 3 параметрами. Для множини перший і другий параметри (a, b у коді прикладу) — поточний елемент перебору, а третій (set у коді прикладу) — множина, елементи якої перебирають.

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

Примітка. При розв'язуванні задач на використання структур даних вхідні дані, внаслідок їхньої громіздкості, зазвичай подають у текстових файлах. Щоб дотриматися цієї традиції при використанні мови Javascript можна скористатися шаблоном, який дозволяє вибрати довільний файл, зчитати з нього послідовність цілих чисел і записати їх у файл output.txt у зворотньому порядку. Якщо умова завдання не передбачає зчитування даних з файлу, достатньо працювати у середовищі розробника.

Створити програми для розв'язання таких задач:

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

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. Використавши стек, перевірити, чи правильно розставлені дужки у заданому виразі. Програму перевірити, опрацювавши такі рядки:
   '[{([[[<>]]])(<>)(){}}]'
   ']()(){<>}[[()]]'
   '[(sjd),"2"],{2:3} [<>]'
   '{[[[[((()))]]<]>]}'
   і отримавши відповідно: 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. Домашнє завдання
Вивчити навчальний матеріал уроку. Доробити при потребі розв'язання задач.