Geum.ru

Методические указания для выполнения лабораторных работ и курсовой работы содержание

Вид материалаМетодические указания

Содержание


11Лабораторная работа № 10. Древовидные структуры
2.Цель работы
3. Варианты заданий
Подобный материал:
1   ...   4   5   6   7   8   9   10   11   12

11Лабораторная работа № 10. Древовидные структуры



1.Общие понятия


Дерево по определению - это граф без циклов. Если ребра дерева имеют направление, то граф называется ориентированным. Набор несвязанных деревьев называется лесом. Деревья являются удобным инструментом как для организации иерархических структур хранения информации, так и для решения целого ряда задач.

В качестве элементов древовидных структур удобно выбирать так называемые сложные записи, т.е. такие записи, которые состоят из двух — главной, стоящей на более высоком уровне иерархии, и подчиненной, находящейся на более низком уровне иерархии. Главная запись имеет ссылки на все подчиненные записи.

В бинарных деревьях таких ссылок имеется не более двух. Одна и та же запись в дереве может выступать в качестве главной по отношению к записям, находящимся на более низком уровне иерархии, и подчиненной по отношению к записи на более высоком уровне иерархии. Это обстоятельство дает возможность непрерывного просмотра по маршруту (ветви) от самого высокого уровня иерархии до самого низкого.


2.Цель работы


Целью работы является изучение и отработка приемов и навыков использования деревьев в организации алгоритмических структур и структур хранения информации. Машинная реализация этих структур планируется на языке Турбо Паскаль или С++. При упрощенном варианте выполнение работы должно занимать не более четырех часов времени. При усложненном варианте -6 часов.


3. Варианты заданий


При выполнении заданий следует задействовать стандартные операции работы с деревьями, каждая из которых должна быть оформлена в виде отдельной функции или процедуры. Кроме этих операций должны быть процедуры, позволяющие выполнить конкретное задание. Ниже приведен список заданий на эту работу.

1. Построить бинарное дерево, подсчитать число листьев этого дерева и разработать процедуру модификации элементов.

2. Построить бинарное дерево и разработать процедуру выделения поддерева в отдельное дерево.

3. Построить бинарное дерево и разработать процедуру включения поддерева в дерево.

4. Построить бинарное дерево, все элементы которого дополнительно связаны между собой по горизонтали.

5. Построить два бинарных дерева и объединить их, избегая дублирования элементов в суммарном дереве.

6. Построить два бинарных дерева, одно из которых, являясь деревом поиска, по структуре идентично другому, и использовать это обстоятельство для ускорения поиска нужного элемента в другом дереве.

7. Построить два бинарных дерева и на их основе построить дерево, полученное в результате операции вычитания.

8. Построить дерево, привести к бинарному и использовать его для поиска нужного элемента в исходном дереве.

9. Построить на основе дерева простейшую базу данных.

10. Из древовидной структуры вывести список студентов, получивших на экзамене одинаковые оценки.

11. Разработать процедуру сортировки последовательности элементов, используя дерево поиска.

12. Используя бинарное дерево, разработать процедуру формирования кодов Хаффмана.

13. Используя бинарное дерево, разработать процедуру раскодирования кодов Хаффмана.

14. На основе деревьев разработать автомат для игры в "крестики- -нолики".

15. Составить дерево для грамматического разбора арифметического выражения.

16. Программно реализовать алгоритм пирамидальной сортировки.

17. На основе произвольной последовательности построить дерево поиска и затем сбалансировать его.

18. Разработать алгоритм записи на диск и восстановления в динамической памяти почти полного бинарного дерева.

19. Разработать алгоритм записи на диск и восстановления в динамической памяти произвольного бинарного дерева.

20. Объединить пункт 17 и 18.

21. Объединить пункт 17 и 19.

4. Пояснения к выполнению лабораторной работы


Бинарное дерево, на основе которого построены все вышеперечисленные задания, по сути дела, является специально организованным двухсвязанным списком, в котором каждый элемент потенциально может ссылаться на два других элемента с иерархией на пункт ниже. Это свойство бинарных деревьев, к которым, как известно, можно свести произвольное дерево, широко используется для разработки стандартных процедур для бинарных деревьев. Число этих процедур существенно больше, чем для ранее рассмотренных структур (см. предыдущие лабораторные работы). Особенностью использования деревьев является то обстоятельство, что чаще решение конкретной задачи не требует полного набора стандартных задач. Поэтому один из элементов выполнения вышепредставленных заданий - это определение круга стандартных операций, необходимых для решения данной задачи. Второй особенностью этой лабораторной работы является более сильная зависимость от теоретических знаний, без хорошего знания которых практически невозможно выполнить ни одного задания. Следует также обратить внимание на то, что алгоритмы: построения дерева, поиска нужного элемента, просмотра дерева и др. носят рекурсивный характер и другим образом их построить чрезвычайно трудно. Ниже приведены основные стандартные операции с деревьями:

-построение хорошо сбалансированного дерева;

-построение дерева поиска;

-построение общего бинарного дерева;

-поиск элемента в дереве поиска;

-последовательный просмотр элементов дерева (правый обход, левый, смешанный);

-включение элемента на нижний уровень иерархии;

-выключение элемента с нижнего уровня иерархии;

-включение элемента в произвольный уровень иерархии;

-выключение элемента из произвольного уровня иерархии;

и т. д.

ПРИЛОЖЕНИЕ 1

Пример программы с использованием дерева


Пусть требуется создать структуру хранения данных о предках персоны по главной линии. Такая структура хорошо вписывается в полное бинарное дерево.

На нулевом уровне этого дерева находится информация о персоне;

на первом уровне - информация о родителях;

на втором уровне - информация о бабушках и дедушках и т.д.

При заданной глубине поиска m число вершин n высчитывается по формуле

m+1

n=2 -1 .

Для того, чтобы указанное дерево было деревом поиска, надо соответствующим образом сформировать значения ключей элементов. Для полного бинарного дерева их можно сформировать автоматически (см. функцию contree). В общем случае это сделать достаточно сложно.

Далее приведен текст на Турбо Паскале.


program tree;

uses crt;

type

indtype=per;

key=integer;

per =record {ЛИЧНОСТЬ}

key: byte;

fam : string[9];

nam : string[9];

left: indtype;

right: indtype;

end;

var

ch:char;

n,m,mm,n0:integer;

glub,lev,kod:byte;

tr,root:indtype;

flag:boolean;


{*****************************************************************

Конструирование хорошо сбалансированного бинарного дерева

******************************************************************}

function kontree(n:integer;var i:integer):indtype;


var

x,nl,nr : integer;

newnode: indtype;

begin

if n=0 then

kontree:=nil

else

begin

nl:=n div 2;

nr:=n-1-nl;

new(newnode);

newnode.fam:=' ';

newnode.nam:=' ';

{формирование ключа производится в данной задаче автоматически: в результате для полного бинарного дерева получаем дерево поиска }

x:=nl+1+i;

newnode.key:=x;

newnode.left:=kontree(nl,i);

i:=i+1;

newnode.right:=kontree(nr,i);

kontree:=newnode;

end;

end;

{****************************************************************

Поиск места элемента дерева по ключу: если элемент с заданным ключом отсутствует, то образуется новый элемент с указателем chtree;

переменная root,передаваемая в функцию-это указатель корня дерева (вершины с самым высоким уровнем иерархии)

***************************************************************}

function chtree(n:integer;root:indtype):indtype;

var chtr:indtype;

begin

chtr:=root;

chtree:=root;

while(chtr<>nil) and (chtr.key<>n) do

if chtr.key
begin

chtr:=chtr.right;

chtree:=chtr;

end

else

chtr:=chtr.left;

chtree:=chtr;

if(chtr=nil) and (chtr.key<>n) then

chtr.key:=n;

end;


{*********************************************************

ввод данных в запись(элемент дерева) с заданным

указателем "d"

*********************************************************}


procedure inptree(var d:indtype);


begin

with d do

begin

writeln('Введите фамилию ');

readln(fam);

writeln('Введите имя ');

readln(nam);

end;

writeln;

end;

{*********************************************************

вывод данных из записи(элемента дерева) с задан-

ным указателем "d"

*********************************************************}


procedure outtree(var d:indtype);


begin

with d do

begin

write(key:2,' ');

write(fam,' ');

writeln(nam,' ');

end;

writeln;

end;

{*****************************************************************

Просмотр заданного уровня иерархии дерева *****************************************************************}

procedure seetree(n,glub,lev:integer;root:indtype);

var

i0,i,nn,m :byte;

begin

writeln('Уровень иерархии : ',lev:1);

{формирование ключа первого элемента(переменная "м")}

nn:=glub-lev;

m:=1;

while nn>0 do

begin

nn:=nn-1;

m:=m*2;

end;

i0:=2*m;{формирование шага между элементами}

while n>=m do {поиск нужного элемента и его просмотр}

begin

tr:=chtree(m,root);

outtree(tr);

m:=m+i0;

end;

end;


{**** программа ******}

BEGIN

clrscr;

{Конструирование дерева}


writeln('Введите глубину поиска родственников: ');

read(glub);

m:=glub+1;

{расчет числа вершин}

mm:=1;

while m>0 do

begin

m:=m-1;

mm:=mm*2;

end;

n:=mm-1;

n0:=0;

root:=kontree(n,n0);

repeat

{просмотр исходного дерева по уровням иерархии}

lev:=0;

while lev
begin

seetree(n,glub,lev,root);

lev:=lev+1;

end;

writeln('ВВедите ключ элемента, для ввода данных ');

readln(kod);

tr:=chtree(kod,root); {поиск элемента с ключом "код"}

inptree(tr); { ввод информации в элемент с ключом "код"}

outtree(tr); { вывод элемента с ключом "код"}

writeln('Для окончания работы нажмите - ESC');

until readkey=#27;

END.


ПРИЛОЖЕНИЕ 2

Пример программы с использованием дерева

на языке С++


В этом приложении на языке С++ приведен текст программы, позволяющий

решить задачу, указанную в Приложении 1.


// !!=========================!!

// !! древовидные структуры !!

// !!=========================!!


#include

#include

#include

#include

#include

#include


typedef

struct tree{

int key;

char fam[10];

char nam[10];

struct tree *left;

struct tree *right;

};

struct tree *kontree(int n,int *i) ;

struct tree *chtree(int n,struct tree *root);

void inptree(struct tree *d);

void outtree(struct tree *d);

void seetree(int n,int glub,int lev,struct tree *root);

// {**** программа ******}


main()

{


char ch;

int n,m,mm,n0,glub,lev,kod;

struct tree *root,*d,*tr;

char flag,syb;

// {Конструирование дерева}

printf("Введите глубину поиска родственников:\n ");

scanf(" %d",&glub);

m=glub+1;

// {расчет числа вершин}

mm=1;

while (m>0)

{

m=m-1;

mm=mm*2;

}

n=mm-1;

n0=0;

syb='0';

root=kontree(n,&n0);

while((syb!='y')&&(syb!='Y'))

{

// {просмотр исходного дерева по уровням иерархии}

lev=0;

while (lev
{

seetree(n,glub,lev,root);

lev=lev+1;

}

printf("ВВедите ключ элемента,для ввода данных \n");

scanf("%d",&kod);

tr=chtree(kod,&*root); //поиск элемента с ключом "код"

inptree(&*tr); // ввод в элемент с ключом "код"

outtree(&*tr); // вывод элемента с ключом "код"

scanf("%c",&syb);

}

}


//****************************************************************

// Конструирование хорошо сбалансированного бинарного дерева //****************************************************************

struct tree *kontree(int n,int *i)//параметр "i"только для дерева поиска

{

int nl,nr ,x,j;

struct tree *newnode;

if (n==0)

return(NULL);

else

{

nl=n / 2;

nr=n-1-nl;

newnode=(struct tree*)malloc(sizeof(struct tree));

for(j=0;j<11;j++)

{ newnode->fam[j]=0;

newnode->nam[j]=0;

}

//{формирование ключа производится в данной задаче автоматически:в результате для полного бинарного дерева получаем дерево поиска }

x=nl+1+*i;//только для построения полного дерева

newnode->key=x;

newnode->left=kontree(nl,&*i);

*i=*i+1; //только для дерева поиска

newnode->right=kontree(nr,&*i);

return(newnode);

}

}

//****************************************************************

// Поиск места элемента дерева по ключу: если элемент с заданным

// ключом отсутствует, то образуется новый элемент с указателем // chtree; переменная root, передаваемая в функцию-это указатель //на корень дерева (вершины с самым высоким уровнем иерархии) //****************************************************************

struct tree *chtree(int n,struct tree *root)

{

struct tree *chtr;

chtr=root;

while((chtr!=NULL)&&(chtr->key!=n))

if (chtr->key
chtr=chtr->right;

else

chtr=chtr->left;

return(chtr);

if((chtr==NULL)&&(chtr->key!=n))

chtr->key=n;

}


//****************************************************************

// ввод данных в элемент дерева с заданным указателем "d"

// **************************************************************


void inptree(struct tree *d)

{ gets(d->fam);

printf("Введите фамилию\n ");

gets(d->fam);

printf("Введите имя\n");

gets(d->nam);

printf("\n");

}

//*********************************************************

//вывод данных из элемента дерева с заданным указателем "d"

*********************************************************} */


void outtree(struct tree *d)


{

printf("%d %s %s",d->key,d->fam,d->nam);

printf("\n");

}

//****************************************************************

// Просмотр заданного уровня иерархии дерева //***************************************************************

void seetree(int n,int glub,int lev,struct tree *root)

{

int i0,i,nn,m;

struct tree *tr;

printf("Уровень иерархии :%d \n",lev);

//формирование ключа первого элемента(переменная "м")}

nn=glub-lev;

m=1;

while (nn>0)

{

nn=nn-1;

m=m*2;

}

i0=2*m; //формирование шага между элементами}

while (n>=m) // {поиск нужного элемента и его просмотр}

{

tr=chtree(m,root);

outtree(tr);

m=m+i0;

}

}