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

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

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

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

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

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

Обладнання: комп’ютери IBM PC з встановленими ОС, браузером, XAMPP і/або стійким сполученням з Інтернетом для роботи з online-компіляторами. Останнє бажане для пришвидшення перевірки кожного з поданих кодів.

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

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

Хід уроку

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

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

Дати означення, що таке: масив, елемент масиву, індекс масиву? Порівняти з очікуваним.

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

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

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

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

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

getFirst(4,3);

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

Перелічимо найуживаніші вбудовані методи (функції) PHP для роботи з масивами, які буде використано далі: count, array_key_exists, array_keys, array_merge, array_pop, array_push, array_search, array_shift, array_unshift, array_slice, array_splice, array_values, sort (переходити за посиланнями й ознайомитися з описом і прикладами застосування цих методів).

У повному переліку всі методи, назви яких закінчуються на sort, пов'язані з упорядкуванням масивів різними способами.

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

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

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

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

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

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

Примітка. Є можливість працювати "дослівно" у темінах опису списку й описаних далі стека й черги, використовуючи наявні вбудовані методи current, next, prev, end.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При використанні мови PHP усі проблеми роботи з переліченими вище структурами приховано на етапі написанні PHP мовою С.

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

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

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

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. Використавши код html з формою і код php змоделювати відповідь на повідомлення у формі прізвища:

   • при зверненні уперше: «Спасибі, що вибрали саме нас!»
   • при повторному зверненні: «Раді знову вас бачити!»

   Для цього достатнньо лише доповнити код php щодо пункту 4.

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