Зміст
Вступ
РОЗДІЛ І. ДИНАМІЧНІ СТРУКТУРИ ДАНИХ
1.1 ЗМІННІ-ВКАЗІВНИКИ
1.2. ЗВ’ЯЗАНИЙ СПИСОК. СТЕК
1.3. ЗВ’ЯЗАНИЙ СПИСОК. ЧЕРГА
РОЗДІЛ ІІ. ДЕРЕВА. БІНАРНЕ ДЕРЕВО
2.1. РЕАЛІЗАЦІЯ БІНАРНОГО ДЕРЕВА ЗА ДОПОМОГОЮ ДИНАМІЧНИХ ЗМІННИХ
ВИСНОВКИ
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
/>Вступ
Сучасніалгоритми працюють з великим обсягом інформації, і тому час пошуку у такихалгоритмах є критичним. Таким чином, актуальним є розроблення структур данихдля ефективного зберігання та обробки інформації.
Однієюз таких структур є бінарне дерево. Це динамічна структура даних, розмір якоїобмежується тільки розміром віртуальної пам’яті комп’ютера. Бінарні деревазабезпечують пошук конкретного значення, максимуму, мінімуму, попереднього,наступного, операції вставки та видалення елемента.
Пошуку збалансованому дереві виконується за час O(log2n), але звичайні бінарнідерева можуть вироджуватись у список, при цьому пошук вже триватиме O(n) часу.
Уповсякденному житті ми дуже часто зустрічаємо приклади дерев. Наприклад, людичасто використовують генеалогічне дерево для зображення структури свого роду;як ми побачимо, багато термінів, пов'язаних з деревами, узято саме звідси.
Другийприклад — це структура великої організації; використання деревоподібноїструктури для представлення її "ієрархічної структури" нині широковикористовується в багатьох комп'ютерних завданнях.
Третійприклад — це граматичне дерево; спочатку воно служило для граматичного аналізукомп'ютерних програм, а нині широко використовується і для граматичного аналізулітературної мови.
РОЗДІЛ І. ДИНАМІЧНІ СТРУКТУРИ ДАНИХ
Підчас роботи довільної програми значення деякої статичної змінної можезмінюватися, але власне кількість оголошених статичних змінних не змінюється.Це не завжди зручно. Наприклад, якщо програма призначена для введення таобробки даних про учнів класу, а для збереження цих даних використовуєтьсязвичайний масив, то визначаючи розмір масиву, приходиться орієнтуватися надеяке, як здається програмісту, граничне значення учнів в класі. При цьому якщореально учнів в класі менше цього граничного значення, то пам’ять ПКвикористовується неефективно. Якщо ж учнів більше – то таку програмувикористовувати взагалі неможна.
Втаких задачах зручно використовувати структури (подібні до масивів) в якихкількість елементів може змінюватися. Такими структурами є зв’язані список.Зв’язаний список нагадує масив, в якому кількість елементів змінюється під часроботи програми.
Зв’язанийсписок можна побудувати використовуючи динамічні змінні. Динамічні змінні можнастворювати під час роботи програми («на ходу») за допомогою так званихзмінних-вказівників.1.1 ЗМІННІ-ВКАЗІВНИКИ
/>
Змінну-вказівникможна уявити як звичайну статичну змінну, але таку, в якій зберігається недеяке конкретне значення (наприклад типу integer, real, …), а адресіншої змінної.
Змінна-вказівник(р) нагадує конверт, який містить лише адресу квартири Петрова, а не її вміст.Можна сказати, що змінна-вказівник р вказує на іншу змінну, яка знаходиться заадресою вул… 1-го Травня, 58.
Вмістзмінної-вказівника р:
Вул.1 Травня, 58
Вмістзмінної за адресою «Вул. 1 Травня, 58» (ця змінна не має імені):
КвартираПетрова
Змінна,що містить значення Квартира Петрова не є звичайною статичною змінною –вона динамічна.
:^тип динамічної змінної
Наприклад,a:^integer; b:^real;
Щобзмінити значення динамічній змінній, на яку вказує деяка змінна-вказівник z, необхідновиконати команду:
z^:=(z – це зміннавказівник, а z^ — динамічна змінна, на яку вказує вказівник z).
Щобзмінити значення змінної-вказівника z (направити її на іншу динамічну змінну)необхідно:
z:=
Оскількидинамічна змінна не має імені (а отже не описується в блоці var), то на початкуроботи програми пам’ять під дану змінну не виділяється. А відповідназмінна-вказівник ні нащо не вказує. Коли змінна-вказівник ні нащо не вказує, тоговорять, що вона вказує на nil.
Щобвиділити пам’ять, необхідно виконати процедуру new(x), де х –змінна-вказівник.
Післявиконання даної процедури (new(x)) вказівник x буде вказувати на коміркупам’яті відповідного типу.