МІНІСТЕРСТВО ОСВІТИ І науки України
Національний технічний університет України "КПІ"
Кафедра МЕДИЧНОЇ кібернетики та телемедицини
Лабораторна робота № 2
Тема: динамічні структури даніх
Варіант № 16 (завдання 17.16).
Виконала:
студент ІМ-81
Плахтій Артур Миколайович
Перевірів:
старший викладач
Зінченко Ніна Павлівна
Київ 2009
Зміст
1. Теоретична частина
Деякі лінійні списки
Побудова складних структур у динамічній пам'яті
Бінарні дерева
2. Умови завдання
Текст програми
Екран результату
Контрольні розрахунки
Висновок
Список літературніх джерел
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.
Рис.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 вхідний потік має вигляд:
AB DG .. C E. F HJ ..
Існує три основних способи обходу дерев [1]: у прямому порядку, зворотному і кінцевому. Обхід дерева може бути виконаний рекурсивної процедурою і процедурою, що не рекурсії (стековий обхід). У наведеній нижче рекурсивної процедури виконується обхід дерева в зворотному порядку.
Рrocedure PR (t: ptr) {рекурсивний обхід дерева} begin if t <> nil then begin PR (t. Llink) {обійти ліве піддерево} writeln (t. info) {потрапити в корінь} PR (t. Rlink) {обійти праве піддерево} end end
Нерекурсивний алгоритм обходу дерева в прямому порядку:
Нехай T - покажчик на бінарне дерево; А - стік, в який заносяться адреси ще не пройдених вершин; TOP - вершина стека; P - робоча змінна.
1. Початкова установка: TOP: = 0; P: = T.
2. Якщо P = nil, то перейти на 4. {Кінець гілки}
3. Вивести P. info. Вершину заносимо в стек: TOP: = TOP +1; A [TOP]: = P; крок по лівій гілки: P: = P. llink; перейти на 2.
4. Якщо TOP = 0, то КІНЕЦЬ.
5. Дістаємо вершину з стека: P: = A [TOP]; TOP: = TOP-1;
Крок по правій зв'язку: P: = P. rlink; перейти на 2.
Вважаючи описаними тип дерево (див. вище) і тип файл type файл = file of ТЕД; визначити функцію або процедуру, яка:
а) перевіряє, чи входить елемент Е в дерево пошуку Т;
б) записує у файл f елементи дерева пошуку Т в порядку їх зростання;
в) додає до дерева пошуку Т новий елемент Е, якщо його не було в T;
label 1,2,3;
type
BT = longint;
u = BinTree;
BinTree = Record
inf: BT;
L, R: U;
end;
var
output, input: text;
s, t: string;
Tree, tree2: U;
k, e: BT;
b: byte;
procedure insiter (var T: U; X: BT);
var vsp, A: U;
begin
new (A); A. inf: = X; A. l: = nil; A. R: = nil;
if T = nil then t: = a
else begin vsp: = t;
while vsp <> nil do
if a. inf <vsp. inf
then
if vsp. L = nil then begin vsp. l: = a;
vsp: = a. l end else vsp: = vsp. l
else
if vsp. R = nil then begin vsp. R: = a;
vsp: = a. R end else vsp: = vsp. R;
end
end;
function find (T: u; x: BT): boolean;
begin
if t = nil then find: = false
else if t. inf = x then find: = true
else if x <t. inf
then find: = find (t. L, x)
else find: = find (t. R, x)
end;
begin
clrscr;
s: ='';
b: = 1;
while b <> 0 do begin
clrscr;
writeln ('vvedite el dereva'); readln (e);
t: ='';
str (e, t);
s: = s + t + '';
insiter (tree, e);
writeln ('prodoljut? (Varianti-0)');
readln (b);
end;
1: clrscr;
writeln ('chto vu xotite sdelat?');
writeln ('1 - proverka nayavnosti elementa');
writeln ('2 - zapis v fail elementov dereva');
writeln ('3 - dobavleniye elementa');
writeln ('4 - po faily stroit derevo');
writeln ('0 - vuxod iz programmu');
write ('vash vubor:'); readln (b);
case b of
1: begin
write ('vvedite element:'); readln (e);
writeln ('nayavnost elementa-', find (tree, e));
writeln ('divss any key');
readkey;
end;
2: begin
{Printtree (tree);} writeln ('Zapisano v file OUTPUT. TXT'); writeln;
assign (output, 'c: utput. txt');
rewrite (output);
write (output, s);
s: ='';
close (output);
writeln ('divss any key');
readkey;
end;
3: begin
write ('vvedite element:'); readln (e);
insiter (tree, e);
end;
4: begin
s: ='';
assign (input, 'c: \ input. txt');
reset (input);
read (input, s);
close (input);
writeln (s);
writeln ('divss any key');
readkey;
end;
0: goto 2;
end;
goto 1;
2: writeln ('divss any key');
readkey;
end.
2. Т.П. Караванова. Основи алгорітмізації та програмування. Форум. - К.: 2002. - 286 с.
3. І. Скляр. Вівчаємо мову программування PASCAL. http://distance. edu. vn. ua / metodic / pascal /
4. Будникова Н.А. Навчальний комплекс з програмування на мові ПАСКАЛЬ http://petrsu.ru/Chairs/IMO/pascal/
Національний технічний університет України "КПІ"
Кафедра МЕДИЧНОЇ кібернетики та телемедицини
Лабораторна робота № 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 вхідний потік має вигляд:
AB DG .. C E. F HJ ..
Існує три основних способи обходу дерев [1]: у прямому порядку, зворотному і кінцевому. Обхід дерева може бути виконаний рекурсивної процедурою і процедурою, що не рекурсії (стековий обхід). У наведеній нижче рекурсивної процедури виконується обхід дерева в зворотному порядку.
Рrocedure PR (t: ptr) {рекурсивний обхід дерева} begin if t <> nil then begin PR (t. Llink) {обійти ліве піддерево} writeln (t. info) {потрапити в корінь} PR (t. Rlink) {обійти праве піддерево} end end
Нерекурсивний алгоритм обходу дерева в прямому порядку:
Нехай T - покажчик на бінарне дерево; А - стік, в який заносяться адреси ще не пройдених вершин; TOP - вершина стека; P - робоча змінна.
1. Початкова установка: TOP: = 0; P: = T.
2. Якщо P = nil, то перейти на 4. {Кінець гілки}
3. Вивести P. info. Вершину заносимо в стек: TOP: = TOP +1; A [TOP]: = P; крок по лівій гілки: P: = P. llink; перейти на 2.
4. Якщо TOP = 0, то КІНЕЦЬ.
5. Дістаємо вершину з стека: P: = A [TOP]; TOP: = TOP-1;
Крок по правій зв'язку: P: = P. rlink; перейти на 2.
2. Умови завдання
17.16. Деревом пошуку, або таблицею у вигляді дерева, називається бінарне дерево в якому ліворуч від будь-якої вершини знаходяться вершини з елементами, меншими елементу з цієї вершини, а справа - з великими елементами (передбачається, що всі елементи дерева попарно різні і що їх тип (ТЕД) допускає застосування операцій порівняння); приклад такого дерева показаний на рис.21.Вважаючи описаними тип дерево (див. вище) і тип файл type файл = file of ТЕД; визначити функцію або процедуру, яка:
а) перевіряє, чи входить елемент Е в дерево пошуку Т;
б) записує у файл f елементи дерева пошуку Т в порядку їх зростання;
в) додає до дерева пошуку Т новий елемент Е, якщо його не було в T;
Текст програми
uses crt;label 1,2,3;
type
BT = longint;
u = BinTree;
BinTree = Record
inf: BT;
L, R: U;
end;
var
output, input: text;
s, t: string;
Tree, tree2: U;
k, e: BT;
b: byte;
procedure insiter (var T: U; X: BT);
var vsp, A: U;
begin
new (A); A. inf: = X; A. l: = nil; A. R: = nil;
if T = nil then t: = a
else begin vsp: = t;
while vsp <> nil do
if a. inf <vsp. inf
then
if vsp. L = nil then begin vsp. l: = a;
vsp: = a. l end else vsp: = vsp. l
else
if vsp. R = nil then begin vsp. R: = a;
vsp: = a. R end else vsp: = vsp. R;
end
end;
function find (T: u; x: BT): boolean;
begin
if t = nil then find: = false
else if t. inf = x then find: = true
else if x <t. inf
then find: = find (t. L, x)
else find: = find (t. R, x)
end;
begin
clrscr;
s: ='';
b: = 1;
while b <> 0 do begin
clrscr;
writeln ('vvedite el dereva'); readln (e);
t: ='';
str (e, t);
s: = s + t + '';
insiter (tree, e);
writeln ('prodoljut? (Varianti-0)');
readln (b);
end;
1: clrscr;
writeln ('chto vu xotite sdelat?');
writeln ('1 - proverka nayavnosti elementa');
writeln ('2 - zapis v fail elementov dereva');
writeln ('3 - dobavleniye elementa');
writeln ('4 - po faily stroit derevo');
writeln ('0 - vuxod iz programmu');
write ('vash vubor:'); readln (b);
case b of
1: begin
write ('vvedite element:'); readln (e);
writeln ('nayavnost elementa-', find (tree, e));
writeln ('divss any key');
readkey;
end;
2: begin
{Printtree (tree);} writeln ('Zapisano v file OUTPUT. TXT'); writeln;
assign (output, 'c: utput. txt');
rewrite (output);
write (output, s);
s: ='';
close (output);
writeln ('divss any key');
readkey;
end;
3: begin
write ('vvedite element:'); readln (e);
insiter (tree, e);
end;
4: begin
s: ='';
assign (input, 'c: \ input. txt');
reset (input);
read (input, s);
close (input);
writeln (s);
writeln ('divss any key');
readkey;
end;
0: goto 2;
end;
goto 1;
2: writeln ('divss any key');
readkey;
end.
Екран результату
Контрольні розрахунки
Контрольними розрахунки містяться в самій Програмі. Отрімані результати легко перевіріті, Що підтверджує вірність роботи програми.Висновок
Динамічні структури даніх дозволяють гнучкіше та Ширшев вікорістовуваті Можливості програмування. Дуже зручне у вікорістанні є тип даніх Паскаля Pointer та Його комбінація з типом Record, Що дає змогу реалізовуваті списки та будь-які деревовідні структури даніх. Середовище Турбо Паскаль та Делфі дозволяє вільно працюваті з цімі структурами.Список літературніх джерел
1. Т. Рютте, Г. Франкен. Турбо Паскаль 6.0. Торгово-видавниче бюро BHV. Грифон. - К.: 1992. - 235 с.2. Т.П. Караванова. Основи алгорітмізації та програмування. Форум. - К.: 2002. - 286 с.
3. І. Скляр. Вівчаємо мову программування PASCAL. http://distance. edu. vn. ua / metodic / pascal /
4. Будникова Н.А. Навчальний комплекс з програмування на мові ПАСКАЛЬ http://petrsu.ru/Chairs/IMO/pascal/