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

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

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

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

Лабораторна робота №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

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);