Тема уроку. Лінійні структури даних.
Мета уроку:
допомогти учням засвоїти факти та основні ідеї лінійних структур даних;
формувати вміння виділяти головне, актуалізувати, конспектувати, порівнювати, зіставляти;
забезпечити диференційований підхід. встановити зв'язки між засвоєними та новими знаннями;
формувати вміння робити висновки щодо результатів роботи; формувати вміння застосовувати логічне, алгоритмічне структурне та системне мислення для розв’язування життєвих проблемних ситуацій;
сприяти формуванню вміння організовувати свою діяльність із використанням програмних засобів для планування та структурування роботи;
формувати вміння дотримуватись правил БЖД під час роботи з комп’ютерами.
Тип уроку: засвоєння нових знань; формування вмінь і навичок.
Обладнання та наочність: комп’ютери, підручники, презентація, проектор.
Хід уроку
І. Організаційний етап
ІІ. Мотивація навчальної діяльності
ІІІ. Актуалізація опорних знань
По організації взаємозв'язків між елементами складних структур даних існує наступна класифікація:
Лінійні
Масив
Список
Зв’язний список
Стек
Черга
Хеш-таблиця
Табличні
Таблиця реляційної бази даних
Двовимірний масив
Ієрархічні
Двійкові дерева
N-арні дерева
Ієрархічний список
Мережеві
Простий граф
Орієнтовний граф
ІV. Вивчення нового матеріалу
Структура даних - це спосіб представлення інформації.
В алгоритмізації знання різноманітних структур даних, ефективне їх використання мають неабияке значення. Правильне, коректне визначення структур даних, що використовуються в алгоритмі, - це значна частина успіху.
Деякі структури даних визначаються безпосередньо в мовах програмування, які ми використовуємо для реалізації алгоритмів. Наприклад, ви вже знайомі з простими змінними, масивами. А деякі організовуються самими розробниками алгоритмів. Саме з ними ми маємо ознайомитися в цьому розділі.
Можна сказати, що структури даних є одним з інструментів розробки алгоритмів. Багато відомих методів алгоритмів базуються на тих чи інших структурах.
Ознайомлюючись із структурами даних, ми, в першу чергу, будемо виділяти два такі важливі моменти:
відображення структури даних на пам’ять комп’ютера;
обробка інформації в даній структурі.
Перше питання пов’язане з визначенням принципу збереження даних у пам’яті комп’ютера, а друге - з організацією читання та запису інформації. Слід звернути увагу на те, що в різній літературі читання інформації трактується як її вилучення.
Також не менш важливою є інформація про доступ до елементів кожної структури: прямий чи послідовний.
Якщо до будь-якого елемента заданої структури можна дістатися, не переглядаючи всі, то такий доступ називають прямим. У протилежному випадку - послідовним.
СТЕК
Стеком називається структура даних, що організована за принципом «останнім прийшов — першим пішов».
Ми домовилися розглядати структури даних у відображенні на пам’ять комп’ютера. Тому в першу чергу треба визначитися, яким чином елементи даної структури зберігаються в пам’яті.
Оскільки організація одновимірного масиву аналогічна лінійній структурі пам’яті комп’ютера, то логічним буде представлення стека саме у вигляді одновимірного масиву (мал. 5).
А от організація обробки елементів цього масиву буде такою, що відповідає означенню цієї структури даних. Для простішого розуміння поняття «стек» проведемо аналогію зі стосом книг.
Додаючи нову книжку в стос, ми кладемо її зверху, тобто операція запису нового елемента в стек відбувається в кінець масиву додаванням нового елемента. А для того щоб узяти книжку із середини стосу, нам треба всі верхні книжки по одній зняти у зворотному порядку щодо їх складання. Таким чином, операція читання зі стека відбувається також із кінця масиву, але в зворотному порядку.
Обробляючи елементи масиву, ми вводимо поняття поточного порядкового номера елемента масиву і. В даному випадку нас цікавитиме лише останній елемент: ми його або зчитуємо (↑), або після нього записуємо новий елемент (↓).
Індекс останнього елемента стека називається вершиною. Це означає, що для обробки елементів стека нам достатньо знати значення лише однієї величини і вершини стека. Схематично стек можна зобразити так (мал. 6):
Подвійною стрілкою (↨) ми позначили елемент вершини стека, який доступний як для читання, так і для запису, а сірим кольором - ті елементи масиву, які належать стеку. Нижня стрілка (←→) показує зміну розміру стека в межах визначеного масиву.
Алгоритм запису нового елемента х у стек виглядатиме так:
i += 1;
a[i] = х.
Тобто ми спочатку збільшуємо значення вершини стека на 1, a потім елементу масиву з індексом і присвоюємо значення х.
Алгоритм читання чергового елемента стека буде таким:
x= а[i];
i -=1.
Пояснимо цей алгоритм: спочатку значення елемента стека, що знаходиться на його вершині і, читаємо в х, а потім зменшуємо значення вершини стека на 1.
Тепер, коли ми визначили операції для роботи з елементами і тільки обов’язково треба зауважити таке.
Для швидкодії роботи зі стеком не витрачається час на «знищення» елементів стека, які вже «вичитано». Доступ до цих елементів утрачається лише за рахунок зміни значення вершини стека (і - 1). Таким чином, у масиві лишається «сміття». При наступному «попаданні» на ці елементи в масиві під час виконання операції запису туди будуть записані нові значення.
Нам залишилося ще визначитися з принципом доступу до елементів даної структури. Робота зі стеком зводиться до обробки вершинного елемента, який доступний завжди, а решта елементів - ні. Щоб зробити доступним деякий елемент а[к] (k < і), треба спочатку вичитати зі стека всі елементи, що знаходяться вище від нього, зробивши таким чином даний елемент вершиною стека.
Тому можна зробити висновок: структура даних «стек» є структурою послідовного доступу.
ЧЕРГА
Чергою називається структура даних, організована за принципом «першим прийшов — першим пішов».
Черга, так само як і стек, відображається на пам’ять комп’ютера у вигляді одновимірного масиву (мал. 7).
Принцип обробки елементів черги схожий на звичайне формування черги в магазині. В кожний момент часу обслуговується перший покупець. Після обслуговування він іде з черги і на його місце стає наступний - тепер він перший. Новий покупець стає в кінець черги.
Якщо цю схему перенести на обробку елементів черги, то, на перший погляд, треба знати лише індекс останнього елемента черги, щоб після нього можна було записати новий елемент. Початок черги при цьому завжди буде збігатися з першим елементом масиву (мал. 8).
Але при такій логіці існує один суттєвий недолік: після вибування з черги першого елемента всі решта повинні зсуватися на одну позицію вліво. Тобто потрібно кожний раз при виконанні операції читання виконувати таку послідовність дій:
a[і] += 1 для і = 1, 2, ..., <індекс кінця черги >.
Зрозуміло, що така схема обробки операції читання забирає багато часу. Для його економії застосуємо ідею читання елемента стека. Тобто після читання елемента не будемо намагатися знищити його значення, а просто перемістимо індекс початку черги на наступний елемент. Таким чином ми приходимо до ідеї існування двох індексів: і - початок черги, який ще носить назву «голова» черги, та у - кінець черги, що називається «хвостом» черги. Тепер схематично чергу можна зобразити так (мал. 9):
На схемі сірим кольором позначена та частина масиву, в якій розміщені елементи черги.
Алгоритм запису в чергу елемента х:
j +=1;
a[j] =x;
Тобто ми спочатку збільшуємо значення індексу «хвоста» черги на 1, а потім елементу масиву з індексом j присвоюємо значення х.
Алгоритм читання елемента черги виглядатиме так:
x =a[i];
i += 1;
Тобто значення «голови» черги читаємо в х, а потім збільшуймо індекс «голови» черги на 1.
Тепер можна уявити собі, що наша черга ніби повзає по маcиву, переміщуючись від першого елемента до останнього. Причому елементи черги не розриваються і знаходяться в тій послідовності, в якій записувалися. Можна говорити, що запис y чергу буде неможливий, тобто черга переповнена, коли «хвіст» досягне останнього елемента масиву, а читання стане неможливим, тобто черга порожня, коли «голова» пережене «хвіст».
Залишилося лише визначитися з принципом доступу до елементів черги. Зрозуміло, що в кожний момент часу ми можемо здійснювати операції читання та запису над елементами черги, що знаходяться в «голові» або в «хвості» черги. Дістатися до деякого «внутрішнього» елемента черги ми можемо, лише виконавши відповідну кількість операцій читання з «голови» черги. Тому можна зробити висновок, що черга є структурою послідовного доступу.
ДЕКИ
Деки - це впорядкована лінійна динамічно змінювана послідовність елементів, в якій виконуються такі умови:
1) новий елемент може приєднуватися з обох боків послідовності;
2) вибірка елементів можлива також з обох боків послідовності.
Наприклад, якщо послідовність D = D1,...,Dn зображує дек, то її елементи D1 і Dn вказують одночасно на місце включення і виключення елементів.
Деки називають також реверсивними чергами або чергами з двома кінцями, в яких включення і виключення здійснюються з двох країв послідовності. Деки є найбільш загальною лінійною динамічною структурою даних.
V. Фізкультпауза.
VІ. Інструктаж з БЖД та з санітарно – гігієнічних вимог при роботі з комп’ютерами.
VІІ. Засвоєння нових знань. Формування навичок та вмінь.
Завдання для 1 групи
Що називають структурами даних?
Які основні дії виконуються над елементами структури даних?
Як відбувається читання елементів черги? Запишіть алгоритм читання елемента з черги.
Розробити діалогову меню-орієнтовану програму роботи з елементами стека за такими пунктами:
записати елемент у стек;
прочитати елемент зі стека;
показати вміст стека;
показати вміст масиву;
завершити роботу зі стеком.
Завдання для 2 групи
Яка структура даних називається чергою?
Дайте означення структури даних «стек».
Як структура даних «стек» відображається на пам’ять комп’ютера?
Розробити діалогову меню-орієнтовану програму роботи :і елементами черги за такими пунктами:
записати елемент у чергу;
прочитати елемент із черги;
показати вміст черги;
показати вміст масиву;
завершити роботу з чергою.
ІХ. Підсумок уроку.
Х. Домашнє завдання.
1. Вивчити конспект.