Динамические структуры данных

Міністерство освіти і науки України

Національний технічний університет України "КПІ"

Кафедра медичної кібернетики та телемедицини

Лабораторна робота №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. http://distance. edu. vn. ua/metodic/pascal/

4. Будникова Н.А. Обучающий комплекс по программированию на языке ПАСКАЛЬ http://petrsu.ru/Chairs/IMO/pascal/