МІНІСТЕРСТВО освіти и науки України
Національний технічний університет України "КПІ"
Кафедра МЕДИЧНОЇ кібернетики та телемедицини
Лабораторна робота № 2
Тема: динамічні структури даніх
Варіант № 16 (задача 17.16).
Виконала:
студент ІМ-81
Плахтій Артур Миколайович
Перевірів:
старший викладач
Зінченко Ніна Павлівна
Київ 2009
Зміст
1. Теоретична частина
Деякі лінійні списки
Побудова складних структур у динамічній пам'яті
Бінарні дерева
2. Умови завдання
Текст програми
Екран результату
Контрольні Розрахунки
Висновок
Список літературніх джерел
1. Теоретична частина
Деякі лінійні списки
Стек створюється як лінійний список. Нехай Top - покажчик на початок стека. Стек зручно будувати в зворотному порядку. Наступний фрагмент програми демостріруєт основні операції роботи зі стеком:
Type ukaz = stak, stak = record inf: integer, next: ukaz, end, Var Top, Tek: ukaz; value: integer Procedure DobavS;
Begin new (Tek) readln (Tek. inf) Tek. next: = Top Top: = Teк End Procedure UdalS Begin Top: = Top. next if Top = 0 then writeln ('брак елементів ') End
Для організація черзі можна використовувати аналогічний контрольний тип, при цьому необхідно мати покажчики на початковий nach та кінцевий kon елементи. Черга зручно будувати в прямому порядку (рис.1).
Рис.1. Приклад побудови черзі в прямому порядку
Циклічно зв'язаний список (циклічний список) - такий список, в якому зв'язок від останнього вузла йде до першого елементу списку. На рис.2 зображено односвязного циклічний список. У ньому можна отримати доступ до будь-якого елементу списку, вирушаючи від будь-якої точки.
Рис.2. Приклад циклічного списку
Найбільш важливі операції для односвязного циклічних списків:
1. включити елемент зліва
2. включити елемент праворуч
3. виключити вузол зліва
Якщо nach1 і nach2 вказують на два різних списку L1 і L2 (див. рис.3), то можна включити праворуч в список L1 весь список L2 , для чого потрібно виконати присвоювання, використовуючи проміжну змінну PP типу pointer :
Var PP: pointer {... } PP: = nach1. link nach1. link: = nach2. link nach2. link: = PP
Рис.3. Циклічний список L1 + L2
Кожен елемент списку з двома зв'язками містить два покажчика: на сусідні ліворуч і праворуч елементи (див. рис.4). За таким списком зручно рухатися вперед і назад, так як він містить два входи в список. Для створення двозв'язним списку можна використовувати наступний тип:
Type ptr = element element = record d: integer right, left: ptr end
Рис.4. Приклад списку з двома зв'язками (двонаправлений список)
Важливе перевага двозв'язним списку полягає в тому, що для того щоб видалити елемент tek, досить знати тільки адресу цього вузла, так як адреси попереднього і наступного елементів зберігаються в tek. left і tek. right :
tek. left. right: = tek. right tek. right. left: = tek. left
Тут ви можете перевірити, як ви навчилися працювати з двонаправленим списком.
Списки з півтора зв'язками являють собою чергування елементів з одного і двома зв'язками. Їх перевага: вимагають менше пам'яті, ніж двозв'язним, але ходити по списку можна вперед і назад.
Рис.5. Приклад списку з півтора зв'язками
Побудова складних структур у динамічній пам'яті
За допомогою покажчиків можна створювати найрізноманітніші структури, в тому числі більше складні, ніж прості лінійні списки. Це обумовлено тим, що:
1) будь вузол може бути початком іншого списку;
2) один і той же вузол може бути включений в кілька різних списків.
Застосування покажчиків додає пам'яті гнучкість, необхідну для представлення структур, при цьому може знадобитися комбінація елементів з однією і двома зв'язками. На рис.1 можна бачити приклад структури, яка містить чергування елементів з 1 і 2 зв'язками.
Рис.1. Чергування елементів з 1 і 2 зв'язками.
Для реалізації складної структури слід описати два типи елементів:
Type ptr1 = element1 element1 = record info: string link: ptr1 end ptr2 = element2 element2 = record info: integer rlink, dlink: ptr2 end
Оскільки елемент з одного зв'язком приєднується до елемента з двома зв'язками (тобто елементу іншого типу), при спробі прямого побудови зв'язку компілятор видає повідомлення про помилку на несумісність типів. Цю складність можна обійти, використовуючи проміжну змінну типу pointer .
Нехай є наступні описи:
Var E1: ptr1 E2: ptr2 p: pointer
Тоді щоб приєднати елемент Е1 до елементу Е2 , слід виконати:
p: = E1 E2. dlink: = P
У приватному випадку, коли адресна частина елемента Е2 посилається завжди тільки на адресу елемента одного і того ж типу, можна користуватися описом:
Type ptr2 = element2 element2 = record info: integer rlink: ptr2 dlink: ptr1 {Тут посилання на елемент типу ptr1} end
і тоді можна виконувати присвоювання: Е2. dlink: = E1.
Бінарні дерева
Дерева відносяться до розряду структур, які зручно будувати в динамічної пам'яті з використанням покажчиків. Найбільш важливий тип дерев - двійкові (бінарні) дерева, в яких кожен вузол має найбільше два піддерева: ліве і праве. Детальніше, якщо маємо дерево виду (ріс.1a), то йому може відповідати в динамічній пам'яті структура (рис.1б).
Рис.1. Двійкове дерево і його уявлення за допомогою облікових структур пам'яті а - двійкове дерево, б - представлення дерева за допомогою списків з використанням ланок однакового розміру
Для побудови такого бінарного дерева використовується наступний контрольний тип:
Type Ptr = Node Node = record Info = Char Llink, Rlink = Ptr End
Для роботи з деревами є безліч алгоритмів. До найбільш важливих відносяться завдання побудови і обходу дерев. Нехай в програмі дано опис змінних:
var t: ptr; s: integer; c: char; b: boolean;
Тоді двійкове дерево можна побудувати за допомогою наступної рекурсивної процедури:
procedure V (var t: ptr) var st: string begin readln (st) if st <> '. 'Then begin new (t) t. info: = st V (t. Llink) V (t. Rlink) end else t: = nil end
Структура дерева відбивається у вхідному потоці даних: кожній вводиться порожній зв'язку відповідає умовний символ (в даному випадку точка). Для прикладу на рис.1 вхідний потік має вигляд:
A B D. G. .. C E. F H. J. ..
Існує три основних способи обходу дерев [1]: у прямому порядку, зворотному і кінцевому. Обхід дерева може бути виконаний рекурсивної процедурою та процедурою без рекурсії (стековий обхід). У наведеній нижче рекурсивної процедурою виконується обхід дерева в зворотному порядку.
Рrocedure PR (T: ptr) {рекурсивний обхід дерева} begin if t <> nil then begin PR (t. Llink) {Обійти ліве піддерево} writeln (t. info) {потрапити в корінь} PR (t. Rlink) {обійти праве піддерево} end end
нерекурсівние алгоритм обходу дерева в прямому порядку:
Нехай T - Покажчик на бінарне дерево; А - стек, в який заносяться адреси ще не пройдених вершин; TOP - вершина стека; <...
