Міністерство освіти і науки України
Національний технічний університет України "КПІ"
Кафедра медичної кібернетики та телемедицини
Лабораторна робота №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 - вершина стека; 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 ('press any key');
readkey;
end;
2: begin
{printtree (tree); } writeln ('Zapisano v file OUTPUT. TXT'); writeln;
assign (output,'c: output. txt');
rewrite (output);
write (output,s);
s: ='';
close (output);
writeln ('press 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 ('press any key');
readkey;
end;
0: goto 2;
end;
goto 1;
2: writeln ('press any key');
readkey;
end.
Екран результату
Контрольні розрахунки
Контрольними розрахунками містяться в самій програмі. Отримані результати легко перевірити, що підтверджує вірність роботи програми.
Висновок
Динамічні структури даних дозволяють гнучкіше та ширше використовувати можливості програмування. Дуже зручним у використанні є тип даних Паскаля Pointer та його комбінація з типом Record, що дає змогу реалізовувати списки та будь-які деревовидні структури даних. Середовище Турбо Паскаль та Делфі дозволяє вільно працювати з цими структурами.
Список літературних джерел
1. Т. Рюттен, Г. Франкен. Турбо Паскаль 6.0. Торгово-издательское бюро BHV. Грифон. - К.: 1992. - 235 с.
2. Т.П. Караванова. Основи алгоритмізації та програмування. Форум. - К.: 2002. - 286 с.
3. І. Скляр. Вивчаємо мову программування PASCAL. distance. edu. vn. ua/metodic/pascal/
4. Будникова Н.А. Обучающий комплекс по программированию на языке ПАСКАЛЬ petrsu/Chairs/IMO/pascal/