Тема: cпособи реалізації структур даних. Застосування на практиці різних структур даних. Відмінність між формальними і фактичними параметрами. Поняття масиву, списку, стеку, черги, хеш-таблиці (словника) мовою Pascal.
Учень повинен пояснювати:Учень повинен вміти:
Обладнання: комп’ютери зі встановленими ОС та інтегрованим середовищем програмування мовою Pascal (наприклад, Free Pascal, Lazarus, Pascal ABC) або стійким сполученням з інтернетом для роботи з online-сервісами.
Структура уроку
Хід уроку
1. Організаційний момент
Перевірка присутності та готовності учнів до уроку. Перевірка виконання домашнього завдання.
Мотивація навчання: на цьому уроці ми познайомимося з різними структурами даних і навчимося використовувати їх для розв'язування задач. Ми проаналізуємо переваги їхнього використання. Це сприятиме розвитку логічного мислення і надасть можливість використовувати програми для ефективного розв'язання і навчальних, і практичних задач.
2. Актуалізація опорних знань
Величина — одиниця даних, якими оперує програма. Вона має такі властивості:
назва (ідентифікатор) — послідовність літер латиниці, цифр і нижнього підкреслювання «_», на початку — обов'язково літера;
тип — визначає обсяг відведеної пам'яті, можливі дії, правила тлумачення бітів пам'яті та множину допустимих значень;
розмірність — проста або складена (структурована);
значення — елемент множини допустимих значень величини.
З кожною величиною (або її складовою для структурованої величини) пов'язана ділянка оперативної пам’яті, куди її під час роботи програми заносять та у якій зберегають. Цю ділянку визначено її адресою. Тут під адресою розуміють адресу першого байту з послідовновних щодо адресації байтів, відведених для збереження величини. Назва змінної слугує назвою цієї послідовності байтів під час виконання програми.
Стала — вид даних, значення яких заборонено змінювати протягом виконання програми.
Змінна — вид даних, значення яких дозволено змінювати протягом виконання програми.
У мові Pascal кожна стала чи змінна має тип, який оголошують на початку програми, процедури чи функції в розділі опису змінних чи сталих. Наприклад, таким чином
program own
var
a: integer;
b: boolean;
c: char;
r: real;
s: string;
t: set of byte;
u: array [0..99] of qword;
v: record j: integer;
r: real
end;
w: text;
BEGIN END.
Типи даних мови Pascal поділяють на стандартні (вбудовані у мови програмування) та нестандартні, які потрібно описати в коді.
Стандартні типи даних мови Pascal
Для порядкового типу множина значень скінчена, а кожний її елемент має свій порядковий номер — невід'ємне ціле число.
Всі величини поділяють на:
Підпрограма — логічно незалежний фрагмент коду, оформлений спеціальним чином згідно з правилами мови програмування, до якого можна (багаторазово) звернутися з будь-якого місця програми.
Процедура — підпрограма, призначена лише для виконання певних дій.
Функція — підпрограма, що повертає у місце виклику певне значення, що є результатом її виконання.
В описі підпрограми необхідно:
Синтаксис виклику підпрограми
procedure назва_процедури
( назва_параметра-сталої : тип_параметра-сталої;
var назва_параметра-змінної : тип_параметра-змінної);
{опис локальних змінних при потребі}
begin
{тіло процедури}
end;
function назва_фукції
( назва_параметра-сталої : тип_параметра-сталої;
var назва_параметра-змінної : тип_параметра-змінної):
тип значення функції;
{опис локальних змінних при потребі}
begin
{тіло функції}
end;
Тіло підпрограми функції — вказівки підпрограми, записані між службовими словами begin та end.
Різницю між параметром-сталою і параметром-змінною ілюструє така програма.
var a,b: byte; procedure p(x: byte; var y: byte); begin x:= 1; y:= 1; end; begin a:=0; b:=0; p(a, b); writeln(a,' ',b); end.
Ця програма має таке виведення:
0 1
Побічний ефект функції — будь-яка зміна функцією стану програмного середовища, крім повернення результату (зміна значень глобальних змінних, виділення й звільнення пам'яті, введення-виведення тощо).
Теоретично найправильнішим вважають використання функцій без побічних ефектів. Хоча на практиці доводиться використати функції з побічним ефектом, наприклад, для забезпечення введення-виведення й відображення результатів роботи програми.
3. Вивчення нового матеріалу
Структура даних — це спосіб організації даних і операцій з ними.
Відповідним чином побудовані структури даних надають можливість оптимізувати використання машинного часу й пам’яті комп’ютера. Раніше вже розглянуто вбудовану (тобто описану у стандарті мови програмування) структуру: масив.
Список — це лінійно упорядкована даних, кількість яких можна змінювати під час виконання програми. Така структура даних втілює математичне поняття змінюваної послідовності з цілими індексами (номерами).
Пам’ять для розташування нового елемента буде виділено чи вивільнено динамічно при потребі. Для реалізації такої структури даних необхідно використовувати покажчики (на область пам'яті), тому основним елементом такого списку є запис, що має одне або кілька полів, які є покажчиками на його власний тип. Наприклад,
type
p=^t;
t=record
r: real;
n: p;
end;
У поданому прикладі коду описано тип-запис t. Його поле n (англійською next — наступний) має тип p і є покажчиком на дані типу t. Наявність таких полів у записах дає можливість зв’язувати окремі записи у списки.
Для ефективного використання списків необхідно навчитися виконувати над списками операції створення, заповнення даними, додавання та вилучення запису — див. детально прокоментований приклад з таким виведенням даних.
З цього прикладу видно, що навіть найпростіші операції вимагають уваги до роботи зі списком.
Cтек (stack) — структура даних, що є сукупністю елементів і в якій останній доданий елемент буде вилучено першим.
Інакше кажучи, діє принцип: «останнім увійшов, першим вийшов». Структура даних «стек» є структурою послідовного доступу.
Зазвичай стек подають лінійним (одновимірним) масивом. Індекс останнього додученого елемента стека називають вершиною. Хоча можливі й інші реалізації. Наприклад, з використанням динамічного розподілу пам'яті як у поданій вище реалізації списку.
Для пояснення поняття «стек» проведемо аналогію зі стосом книг. Додаючи нову книжку у стос, ми кладемо її зверху (новий елемент у стек додають до кінця масиву). Для того, щоб узяти книжку із середини стосу, потрібно всі верхні книжки по одній зняти у зворотному порядку щодо їх складання. Таким чином, операція читання зі стека відбувається також із кінця масиву, але у порядку, зворотному до порядку заповнення стека.
Можливі такі критичні ситуації:
при читанні може виникнути ситуація, коли вже читати немає чого, тобто стек порожній. Якщо стек порожній (наприклад, на початку роботи з ним), то вершина стека має значення 0. У цьому випадку дозволено лише операція запису у стек;
при записі стек може бути переповненим, тобто досягнуто останнього елемента масиву
У поданих далі прикладах процедур мовою Pascal стек подано такими глобальними змінними: лінійним масивом a з вершиною i. Передбачено виведення або зчитування значення елемента перед виконанням відповідної дії:
вилучення елемента:
procedure ReadFromStack;
begin
if (і=0)
then writeln(‘Стек порожній!’)
else
begin
writeln(a[i]);
dec(i)
end
end;долучення нового елемента:
procedure WriteToStack;
begin
if (і>=n)
then writeln(‘Стек переповнено!’)
else
begin
inc(i);
readln(a[i]);
end
end;виведення поточного вмісту стека:
procedure PrintStack; var k: word; begin for k:=1 to і do write(a[k],' '); writeln; end;
Черга (queue) — лінійно упорядкована структура даних, у в якій перший доданий елемент буде вилучено першим.
Інакше кажучи, діє принцип: «першим увійшов, першим вийшов». Структура даних «черга» є структурою послідовного доступу.
Зазвичай чергу, так само як і стек, подають лінійним (одновимірним) масивом. Принцип опрацювання елементів черги схожий на роботу з чергою покупців у магазині. В кожний момент часу обслуговують першого у черзі покупця. Після обслуговування він іде з черги і на його місце стає наступний.
Завжди потрібно знати індекс останнього елемента черги, щоб після нього можна було вставити новий елемент. Початок черги при цьому завжди збігається з першим елементом масиву.
Нераціонально дослівно таким чином опрацьовувати елементи черги: після вилучення з черги першого елемента всі інші потрібно зсунути на одну позицію. Така схема опрацювання забирає багато часу. Є простий вихід: після опрацювання елемента черги індекс початку черги має вказувати на наступний елемент.
Наступним елементом після досягнення кінця масиву буде його перший елемент. Без такого зациклення програма зможе опрацювати лише таку кількість елементів, що дорівнює довжині масиву. А з таким зацикленням — довільну кількість елементів за умови, що у довільний момент довжина черги n не перевищує довжину масиву na. Інакше кажучи, черга ніби повзає по колу, вздовж якого розташовано елементи масиву. Для стислості коду доцільно діапазон значень індексів масиву n вибрати таким: 0..(n ‒ 1). Саме так зроблено у поданих нижче прикладах.
Запис y чергу неможливий, коли кількість елементів черги дорівнює кількості елементів масиву. Читання з вилученням елемента черги неможливе, коли черга порожня. У поданих далі прикладах процедур мовою Pascal чергу подано такими глобальними змінними: лінійним масивом a, початком черги j0, кінцем черги j1 та кількістю елементів черги n. Передбачено виведення або зчитування значення елемента перед виконанням відповідної дії:
procedure ReadFromQueue;
begin
if (n=0)
then writeln(‘The queue is empty!’)
else
begin
dec(n);
writeln(a[j0]);
j0:=(j0+1) mod na;
end
end;
procedure WriteToQueue;
begin
if (n=na)
then writeln('The queue is full!’)
else
begin
inc(n);
j1:=(j1+1) mod na;
readln(a[j1])
end
end;procedure WriteQueue; var k: integer; begin for k:=0 to na-1 do writeln(a[(j0+k) mod na]); end;
Чергу використовують у багатьох випадках. Наприклад, при встановленні, які вершини графа можна досягнути з даної вершини за 1, 2, 3, ... кроки. Графом може бути певна транспортна схема з вершинами — населеними пунктами.
Запровадимо теоретичне поняття для опису структур даних, заснованих на геш-таблицях.
Геш-таблиця — структура даних, що дозволяє зберігати пари (ключ, значення) і здійснювати три операції: операцію додавання нової пари, операцію пошуку і операцію видалення за ключем.
Інакше кажучи, геш-таблиця — це звичайний масив з незвичайною адресацією, яку задають геш-функцією.
Ефективні методи пошуку мінімізують число порівнянь. В ідеалі бажано мати організацію таблиці без непотрібних порівнянь. Чи можлива така організація? Розглянемо це на прикладі ведення обліку організації виробництва.
Нехай деяка фірма випускає деталі і вимушена кодувати їх послідовністю з 7 цифр. Для застосування прямої індексації з використанням повного 7-значного ключа потрібно використати масив довжини 107 = 10 000 000. Малоймовірно, що фірма має більше ніж тисячу найменувань виробів. Для оптимального використання пам'яті необхідно перетворювати ключ-код, наприклад, у ціле число всередині істотно меншого діапазону — від 1 до 1000. Тоді для зберігання даних достатньо масиву з 1000 елементів з цілими індексами від 0 до 999 включно. При використанні для індексації тррьох останніх цифр початкового коду хеш-функція h може мати такий вигляд:
h(k): = k mod 1000;
Але може трапитися таке: для двох різних найменувань товару останні 3 їхніх кодів збігаються. Такий збіг називають колізією.
Колізія — збіг значень геш-функції при різних значеннях її аргументів.
Досконала хеш-функція — це хеш-функція, яка не породжує колізій.
Усунути колізії при гешуванні можна двома способами:
Метод відкритої адресації. Найпростішим способом усунення колізій є приміщення запису в наступний вільний елемент масиву. Нехай потрібно внести у масив a значення, що відповідає ключу k за умови, що комірка масиву a з індексои h(k) вже містить запис з іншим ключем. У цьому випадку можна застосувати функцію rh до значення h(k) для переходу до наступної клітини. І застосовувати цю функцію потрібно до тих пір, поки не буде знайдено вільну клітинку, куди можна розташувати запис. Цей підхід проілюструємо наступним кодом для хешування масивом а довжини 10.
const n=10;
c: array[0..n-1] of integer=(0,5,8,15,18,10,20,21,22,32);
var a: array[0..n-1] of integer;
b: array[0..n-1] of boolean; {чи зайнято місце?}
j: integer;
function h(k: integer): integer; begin h := k mod 10; end;
function rh(k: integer): integer; begin rh := (k + 1) mod 10; end;
procedure i(k: integer); {внесення значення k}
var j: integer;
begin
j:=h(k);
while (a[j]<>k) and b[j] do j:= rh(j);
a[j]:=k;
b[j]:=true
end;
Begin
for j:=0 to n-1 do b[j]:=false;
for j:=0 to n-1 do i(c[j]);
for j:=0 to n-1 do write(j:4); writeln;
for j:=0 to n-1 do write(a[j]:4);
End.Ця програма здійснює таке виведення.
0 1 2 3 4 5 6 7 8 9 0 10 20 21 22 5 15 32 8 18
Замість пошуку вільного місця у безпосередній близкості інколи здійснюють багаторазове (зазвичай подвійне) хешування, коли послідовно застосовують набір різних хеш-функцій. Тоді і заповнення хеш-таблиці, і доступ до елементів може виявитися вельми хитромудрим. Хеш-адреса елемента з даними ключем ніби відкрита у тому розумінні, що її поступово уточнюють. При цьому всі операції проводять в одновимірному масиві.
Недоліки методу відкритої адресації
Сталий розмір таблиці. Якщо кількість записів перевищує цей розмір, то їх неможливо вставити без виділення таблиці більшого розміру і повторного обчислення гешування для ключів всіх записів, які вже записано у таблицю. Але використовуючи нову геш-функцію.
З такої таблиці важко видалити запис.
Метод ланцюгів полягає у створенні списку (ланцюга) з усіх пар "над значенням" геш-функції, для якого виявлено колізію.
Розглянемо приклад програмної реалізації цього методу.
const n=10;
c: array[0..n-1] of integer=(0,5,8,15,18,10,20,21,22,32);
v: array[0..n-1] of string=('v0','v1','v2','v3','v4',
'v5','v6','v7','v8','v9');
var j: integer;
s: string;
type
link = ^node;
node = record // вузол для зберігання пари
key: integer; // ключ
val: string; // значення
next: link; // вказівник на наступний вузол
end; // для того самого значення геш-функції
var a: array [0..n-1] of link;
p: link;
function h(k: integer): integer;
begin
h:= (k mod n);
end;
function search (key1: integer; val1: string): link;
// Повернення адреси вузла з ключем key1.
// Якщо такого немає, створення нового вузла
// списку "над значенням геш-функції".
var q, p, s: link;
i: integer;
begin
i:=h(key1);
q := nil;
p := a[i];
while p <> nil do
begin
if (p^.key = key1) then begin search := p; exit; end;
q := p;
p := p^.next;
end;
new (s); {Якщо ключ не знайдено, вставляємо новий запис}
s^.key := key1;
s^.val := val1;
s^.next := nil;
if (q = nil) then a[i] := s
else q^.next := s;
search := s;
end;
Begin
for j:=0 to n-1 do a[j]:=nil; // Оголошення таблиці порожньою
for j:=0 to n-1 do search(c[j], v[j]); // Заповнення таблиці
for j:=0 to n-1 do // Виведення таблиці
begin
writeln('j = ',j);
p := a[j];
while p <> nil do
begin
writeln('key =',p^.key:2,' value =',p^.val);
p := p^.next;
end;
end;
End.Ця програма має таке виведення.
j = 0 key = 0 value =v0 key =10 value =v5 key =20 value =v6 j = 1 key =21 value =v7 j = 2 key =22 value =v8 key =32 value =v9 j = 3 j = 4 j = 5 key = 5 value =v1 key =15 value =v3 j = 6 j = 7 j = 8 key = 8 value =v2 key =18 value =v4 j = 9
Тут після рядка: j = … відображено вміст пар (ключ, значення) з одним і тим самим значенням j геш-функції.
Видалення вузла з таблиці, побудованої методом ланцюгів, полягає у видаленні вузла зі списку. При потребі список можна переупорядкувати для збільшення ефективності пошуку.
ОсновниЙ недолік методу ланцюгів — для вузлів покажчиків потрібно використати додатковий простір.
Вибір хеш-функції. Геш-функція тим краща, чим менше колізій створоено при хешуванні. Не можливо визначити, чи буде конкретна геш-функція розподіляти ключі правильно, якщо ці ключі заздалегідь не відомі. Часто використовують такі геш-функції для цілих ключів.
Лишок від ділення на розмір таблиці — див. приклад вище.
Середні цифри квадрата ключа — див. приклад нижче з піднесенням до квадрату, відкиданням 3 молодших бітів і поверненням 10 молодших бітів.
var j: integer; function h (k: integer): integer; begin h:= (k*k shl 3) mod 1024; end; Begin for j:=111 to 127 do write(j:4); writeln; for j:=111 to 127 do write(h(j):4); writeln; End.Програми має таке виведення аргументів і значень геш-функції.
111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 264 0 776 544 328 128 968 800 648 512 392 288 200 128 72 32 8
Адитивний метод для рядків при розмірі таблиці 256: геш-функція повертає лишок від ділення на 256 кодів (функція ord) всіх символів рядка.
Адитивний метод для рядків з побітним додаванням (xor) випадкової складової" — аналогічний попередньому, але успішно розрізняє схожі слова і анаграми. Звичайний адитивний метод дає однакові значення геш-функції на словах, утворених перестановками одних і тих самих літер. Відмінність методів полягає у тому, що до елементів рядка послідовно застосовують операцію побітного додаванням (xor) випадкової складової для поліпшення результату.
const s0: array[0..7] of string =
('роза','азор','once','upon','a','time','there','lived');
var r: array [0..255] of integer; // випадкова складова
j: integer;
function h(s: string): integer;
var sum: longint;
j: integer;
begin
sum:=0;
for j:= 0 to length(s) do sum:=sum + ord(s[j]) xor r[j];
h:= sum mod 256;
end;
Begin
randomize;
for j:=0 to 255 do r[j]:=random(255);
for j:=0 to 5 do writeln(j:4, h(s0[j]):4,' ',s0[j]);
End.Виведення може бути таким.
0 102 роза 1 32 азор 2 196 once 3 249 upon 4 84 a 5 132 time
Інколи вдається взагалі уникнути колізій. Наприклад, якщо всі ключі елементів відомо заздалегідь. Тоді для них можна знайти деяку досконалу геш-функцію, яка розподілить їх за комірками геш-таблиці без колізій. Геш-таблиці, які використовують подібні геш-функції, не потребують механізму розв'язання колізій. Їх називаються геш-таблицями з прямою адресацією.
Важлива властивість геш-таблиць полягає у тому, що при деяких розумних припущеннях всі три операції (пошук, вставлення і видалення елементів) зазвичай виконують за час O(1). Але при цьому не гарантовано, що час виконання окремої операції малий, з певною імовірністю час може бути сумірним із пошуком у списку. З ростом коефіцієнта заповнення таблиці ця імовірність, і, відповідно, середній час виконання операцій, ростуть. Тому при досягненні деякого значення коефіцієнта заповнення необхідно здійснювати перебудову індексу геш-таблиці: збільшити розмір таблиці і заново додати у порожню геш-таблицю всі пари.
Асоціати́вний маси́в (associative array), словник, хеш (dictionary, hash, associative container, map, mapping, finite map) — абстрактний тип даних (інтерфейс до сховища даних), що дозволяє зберігати дані у вигляді набору пар ключ — значення та доступом до значень за їх ключем.
Втілення асоціативних масивів зазвичай підтримують операції додавання пари, пошуку й видалення пари за ключем. Ці три операції часто доповнюються іншими: видалення всіх записів; перебір усіх наявних пар
знаходження пару з найменшим чи найбыльшим значенням ключа.
Підтримка асоціативних масивів з допомогою вбудованих засобів є в багатьох інтерпретованих мовах програмування високого рівня (наприклад, PHP, Python, Ruby, JavaScript). У C++ асоціативний масив підтримано за допомогою класу
map, реалізованого на основі дерева пошуку. У мовах Ruby й Python використовують хеш-таблиці. Є й інші реалізації.
У Pascal'і не передбачає вбудованих засобів втілення асоціативних словників. У цій навчальній мові їх потрібно втілювати самостійно.
Найпростіше втілення можна здійснити з допомогою звичайного масиву, елементами якого є пари (ключ, значення). Для прискорення операції пошуку можна упорядкувати елементи масиву за зростанням ключа і здійснювати пошук методом поділу навпіл. На жаль, у цьому випадку додавання нової пари вимагатиме багато часу, бо вимагатиме «розсування» елементів масиву, щоб в порожнє місце, що утвориться, розташувати нову пару.
4. Інструктаж з ТБ
5. Вироблення практичних навичок
Завдання 1. Створити програму з описом і викликом таких процедур:
Програми повинна:
Виведення має бути таким:
1 2 3 4 5 6 7 8 9 1 2 3 4 5 0 6 7 8 9 1 2 3 5 0 6 7 8 9
Порівняти створену програму з демонстраційним розв'язанням.
Завдання 2. Створити програму з описом і викликом таких процедур:
Програми повинна:
Виведення має бути таким:
9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 6 5 4 3 2 1
Порівняти створену програму з демонстраційним розв'язанням.
Завдання 3. Дано текстовий файл input.txt. Кожний рядок файлу містить слова, розділені пробілами. За один перегляд файлу вивести у перший рядок файлу output.txt слова, які складаються не більше ніж з 3 літер, а у другий рядок — решту, зберігаючи порядок розташування слів у файлі.
Вказівки до виконання
Зчитувати файл посимвольно, формуючи слова.
Якщо отримано слово довжиною не більше 3 символів, то зразу виводити його у файл. Інакше заносити його до черги.
Чергу реалізувати за допомогою вказівників і динамічного розподілу пам'яті.
Після завершення перегляду файлу, вивести слова з черги на екран.
Порівняти створену програму з демонстраційним розв'язанням.
Завдання 4. Кожний рядок файлу dictionary.txt два непорожніх слова з літер латиниці, розділені пробілом. Кожний рядок файлу query.txt містить по одному слову з літер латиниці.
Створити програму, яка:
за даними файлу dictionary.txt створить словник за допомогою геш-функції з використанням адитивнного методу для рядків з побітним додаванням випадкової складової і усуненням колізій методом ланцюгів. Вважати, що кожний рядоу файлу dictionary.txt задає пару ключ — значення (саме у такому порядку):
Порівняти створену програму з демонстраційним розв'язанням.
6. Підведення підсумків уроку
Виставлення оцінок.
7. Домашнє завдання
Вивчити навчальний матеріал уроку. При потребі доробити розв’язання задач.
Текст упорядкувала Котелевець Наталія Валентинівна, вчитель Броварської спеціалізованої школи І-ІІІ ступенів № 7 міста Бровари Київської області, під час виконання випускної роботи на курсах підвищення кваліфікації з 29.10.2018 по 02.11.2018.