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

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

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

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

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

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

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

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

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

Хід уроку

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітка. Для виконання практичних завдань уроку достатньо переходити за посиланням для ознайомлення з таким:

• ArrayList (завдання 1-5);
• Map (завдання 6-7);
• LinkedList (завдання 8, 10);
• TreeSet (завдання 9).

На розсуд учителя: обмежитися лише переліченим вище чи вивчати додаткові питання. В останньому випадку обов'язково ознайомитися з інтерфейсами Iterator і Comparator.

Вбудовані структури даних мови Java

• Інтерфейс Enumeration — для переліку елементів.
• Клас BitSet — втілює послідовність бітів.
• Клас Vector — динамічно змінюваний масив.
• Клас Stack — втілює принцип last-in-first-out.
• Клас Dictionary — абстрактний клас для пар (ключ, значення).
• Інтерфейс Map — засіб для опрацювання пар ключ/значення.
• Клас Hashtable — хеш-таблиця.
• Клас Properties — підклас Hashtable для зберігання пар рядків.

Java до версії 2 надавала спеціальні класи (Dictionary, Vector, Stack, Properties) для зберігання та керування групами об'єктів. Але їм не вистачало єдиного спрямування. Тому використання Vector відрізняється від використання Properties.

Колекції Java були створені для задоволення таких вимог:

• висока ефективність;
• різні типи колекцій працюють аналогічно і з високим ступенем сумісності;
• можливість розширювати та/або легко пристосувати.

З цією метою використано набір стандартних інтерфейсів. Стандартні втілення типу LinkedList, HashSet, і TreeSet з цих інтерфейсів можна використовувати "як є". Також є можливість втілити свою власну колекцію.

Склад колекцій:

• iнтерфейси — абстрактні типи даних для подання колекції і керування незалежно від деталей їхнього подання;
• класи — конкретні втілення інтерфейсів колекцій;
• методи — програмно втілені алгоритми опрацювання даних. Поліморфні: метод можна викорис­тати у різних втіленнях інтерфейсу колекцій.

Відображення (Map) не є колекціями у звичайному розумінні, але вони повністю інтегровані з колекціями.

Класи та інтерфейси структури колекцій містить java.util.

Інтерфейси колекцій

• Collection — для роботи з групами об'єктів;
• List — розширює Collection, зберігає впорядкований набір елементів;
• Set — розширює Collection для множин — наборів з унікальними елементами;
• SortedSet — розширює Set для опрацювання упорядкованих наборів;
• Map — прив'язує унікальні ключі до значень;
• Map.Entry — описує пару ключ/значення — внутрішній клас Map;
• NavigableMap — розширює SortedMap і додає методи для навігації між елементами упорякованого відображення;
• SortedMap — розширює Map для розташування ключів у порядку зростання;
• Enumeration — перелічує об'єкти у колекції (замінено на Iterator).

• AbstractCollection — втілює більшу частину інтерфейсу Collection;
• AbstractList — розширює AbstractCollection і втілює більшу частину інтерфейсу List;
• AbstractMap — втілює більшу частинук інтерфейсу Map;
• AbstractSequentialList — розширює AbstractList для колекцій з послідовним доступом;
• AbstractSet — розширює AbstractCollection і втілює більшу частину інтерфейсу Set;
• ArrayList — розширює AbstractList і втілює динамічний масив;
• LinkedList — розширює AbstractSequentialList і втілює зв'язаний список;
• HashSet — розширює AbstractSet для використання у хеш-таблиці;
• LinkedHashSet — розширює HashSet, щоб дозволити ітерації порядку вставки;
• TreeSet — розширює AbstractSet і втілює набір, що зберігають у дереві;
• HashMap — розширює AbstractMap для використання хеш-таблиці;
• LinkedHashMap — розширює HashMap, щоб дозволити ітерацію порядку вставки;
• TreeMap.html — розширює AbstractMap для використання червоно-чорного дерева;
• WeakHashMap — розширює AbstractMap для використання хеш-таблиці із слабкими ключами (слабкі ключі видаляють при невикористанні);
• IdentityHashMap — розширює AbstractMap та використовує посилання-рівність замість об'єктної рівності під час порівняння ключів і значень. Інакше кажучи, в IdentityHashMap два ключі k1 і k2 вважають рівними тоді й лише тоді, коли (k1==k2). У звичайних реалізаціях Map (наприклад, HashMap) два ключі k1 і k2 вважають рівними тоді й лише тоді, коли справджується такий вираз:
  
  (k1==null ? k2==null : k1.equals(k2))

Перші 5 з перелічених класів з назвою Abstract* лише зменшують зусилля, необхідні для втілення інтерфейсів колекцій.

Cтатичні сталі Collection: EMPTY_SET, EMPTY_LIST та EMPTY_MAP.

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

Текс упорядкував Олександр Рудик з використанням матеріалів сторінки http://proglang.su/java/data-structures.