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

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

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

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

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

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

Обладнання: комп’ютери з встановленими ОС та браузером. У разі нестійкого сполучення з Інтернетом — з встановленим середовищем програмування мовою C#.

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

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

Хід уроку

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

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

1. Дати означення таких понять: масив, елемент масиву, індекс масиву.
2. Перелічити властивості масиву.
3. Описати форми оголошення масиву.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Колекція — засіб мови C# групувати об'єкти.

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

Два основні типи колекцій:

• універсальні колекції є строго типізованими. Вони зазвичай забезпечують вищу продуктивність. Універсальні колекції приймають параметр типу під час створення й не вимагають зведення у тип Object і з нього при додаванні або видаленні елементів. Більшість універсальних колекцій підтримано у застосунках Microsoft Store;

• неуніверсальні колекції зберігають такі елементи, як Object, і вимагають зведення типу. Більшість їх не підтримано для розробки програм Microsoft Store. Але неуніверсальні колекції можна побачити у старих кодах.

Ємність більшості колекцій буде автоматично збільшено, щойно кількість елементів досягне цієї межі. При цьому буде перерозподілено пам'ять: елементи буде скопійовано зі старої колекції до нової. Це зменшує обсяг коду, але погіршує ефективність:

• якщо кількість елементів менша за ємність колекції, додавання елемента має ефективність O(1);

• якщо ємність потрібно збільшити для розміщення нового елемента, додавання елемента має ефективність O(n), де n — кількість елементів.

Найкращий спосіб уникнути такої втрати ефективності — встановити початкову ємність на рівні передбачуваного максимального розміру колекції.

BitArray є особливим випадком: ємність збігається з кількістю елементів.

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

Усі індексовані колекції у просторах назв System.Collections мають нижню межу нуль. Клас Array за як усталено має нижню межу нуль. Але при створенні екземпляра класу Array за допомогою Array.CreateInstance можна задати іншу нижню межу.

Вибір колекції для конкретного завдання легко зробити, маючи таку таблицю — дані запозичено зі сторінки сайту learn.microsoft.com.

Для розв'язання завдань при виробленні практичних навичок достатньо перейти за такими посиланнями: List (1-5, 10), Dictionary (6-7), Stack (8), HashSet (9) — у дужках вказано номери відповідних завдань. На наступних уроках буде виконистано елементи опису Array.

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

Текс упорядкував Олександр Рудик.