Организация списка с помощью двоичного дерева

Федеральное Агентство по образованию РФ Рязанский радиотехнический университет Кафедра «АИТП»

Практическая работа по дисциплине «Программирование и основы алгоритмизации»

Выполнили: Рогачиков А. Е., Попов Б.С.

Проверила: Кузьмина Е. М

1. Описание процедуры выбора структуры хранения данных Для программной реализации задания № 12 мы выбрали линейную структуру данных фиксированного размера — одномерный неоднородный массив.(вектор)

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

SimplyRecord=record //Эталон для массива записей

Number: integer; //номер зачетки

Surename:string[10]; //фамилия

NameGroup: string[10]; //номер группы Максимальное число записей в списке 100 — это означает, в памяти ЭВМ может храниться информация о 100 студентах.

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

На каждый узел имеется одна ссылка. Начальный узел называется корнем.

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

T = Integer; { это будет номером зачетки }

TTree = ^TNode; //указатель на запись

TNode = record //сама запись

value: T; //значение записи

Left, Right: TTree; //левые и правые ветки (для дерева) Здесь поля Left, Right (левые и правые ветки) будут содержать указатели для последующих полей.

Изобразим схематично пример дерева, организованного в виде динамической структуры данных:

Данное дерево организовано таким образом, что для каждого узла все ключи (значения узлов) его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева больше. Такой способ построения дерева называется деревом поиска или двоичным упорядоченным деревом.

С помощью дерева поиска можно организовать эффективный способ поиска, который значительно эффективнее поиска по списку.

Поиск в упорядоченном дереве выполняется по следующему рекурсивному алгоритму:

· Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева:

— если ключи совпадают, поиск завершен;

— если ключ в корне больше искомого, выполнить поиск в левом поддереве;

— если ключ в корне меньше искомого, выполнить поиск в правом поддереве.

· Если дерево пусто, то искомый элемент не найден.

Словесное описание работы программы.

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

Далее, проходя по всем записям, программа строит двоичное дерево по ключевому полю — номеру зачетки.

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

Поиск по списку организован путем сравнения заданного значения (Фамилии или номера зачетки) с соответствующими полями записи при прохождении записи от первого до последнего элементов.

программный бинарный дерево массив

3. Содержание базы данных (внешний файл)

100 200 иванов 334

100 500 попов 3372

111 222 рогачиков 337

111 333 орлов 112

4. Блок-схемы алгоритмов и тексты программ

Program Kursach;

uses crt;

type

SimplyRecord=record //Эталон для массива записей

Number: integer; //номер зачетки

Surename:string[10]; //фамилия

NameGroup: string[10]; //номер группы

end;

T = Integer; { это будет номером зачетки }

TTree = ^TNode; //указатель на запись

TNode = record //сама запись

value: T; //значение записи

Left, Right: TTree; //левые и правые ветки (для дерева)

end;

var

input:text; //входной файл

base:array[1.100] of SimplyRecord; {Массив из 100 записей}

r, i, NumberOfRecords, numberBook: integer;

MyTree:TTree; //непосредственно дерево

procedure Insert (var Root: TTree; X: T);

{ Дополнительная процедура, создающая и инициализирующая новый узел }

procedure CreateNode (var p: TTree; n: T);

begin

New (p); //выделяем память для корня дерева

p^.value := n; //присваи ваем значение в корень

p^.Left := nil; //иннициализация левой и правой ветки

p^.Right := nil

end;

begin

if Root = nil Then

CreateNode (Root, X) //если дерево еще не создано, то создаем его

else

with Root^ do begin //проходим по всей записи

if value < X then

Insert (Right, X) //если значение меньше, то вставляем ветку слева

else if value > X Then

Insert (Left, X); //если больше, то справа

end;

end;

function FindInTree (root:ttree; key: integer) :Boolean; //поиск в дереве

var p: TTree;

begin

p:=root;

while p<>nil do begin //если ветка не пуста

if key=p^.value then begin //если узел с таким ключом есть

FindInTree:=true; //то присваиваем правда

exit; //выходим

end;

if key < p^.value then //если меньше то

p := p^. left {спуститься влево}

else

p := p^. right; {иначе спуститься вправо}

end;

FindInTree:=false; //иначе ложь

end;

function initializate: integer; //иннициализация

Var

s:string; //считываемая строка

i, x, bufer1:integer;

begin

assign (input,'base.txt'); //база данных номер фамилия группа

reset (input); //открываем для чтения

i:=0;

while not EOF (input) do //пока не конец файла делаем

begin

i:=i+1; //счетчик записей +1

readln (input, s); //читаем строку

x:=pos (' ', s); //поиск пробела

val (copy (s, 1, x-1), base[i]. number, bufer1); //забиваем в iй элемент базы номер зачетки

delete (s, 1, x); //удяляем в строке все до пробела

x:=pos (' ', s); //поиск пробела

base[i]. Surename:=copy (s, 1, x-1); //забиваем iю фамилию

delete (s, 1, x);

x:=pos (' ', s);

base[i]. NameGroup:=s; //номер группы

end;

close (input); //закрываем входной файл

initializate:=i; //записываем в функцию количество элементов во входном файле

end;

procedure FindInBase; //функция найти в базе

var

Counter, operation, number: integer;

s:string;

i: integer;

begin

Writeln ('Введите данные для поиска'); //меню

Writeln ('1 — номер зачетки');

Writeln ('2 — фамилию студента');

readln (operation); //читаем опреацию

if (operation = 1) then //если опреация 1

begin

Writeln ('Введите номер зачетки'); //номер зачетки

readln (number); //читаем этот номер

for i := 1 to NumberOfRecords do if Base[i]. Number=number then //от 1 до количества элементов, если

//искомый совпадает с найденным

begin

Writeln (Base[i]. number,' ', base[i]. Surename+' '+base[i]. NameGroup);

//выводим на экран элемент полностью

counter:=counter+1; //счетчик +1

end;

if counter=0 then writeln ('Запись не найдена'); //Если счетчик 0, то выводим сообщение с результатом-его отсутствием

readln;counter:=0; //обнуляем счетчик

end;

if (operation = 2) then //если операция 2

begin

Writeln ('Введите фамилию студента'); //поиск по фамилии

readln (s);

for i:=1 to NumberOfRecords do if Base[i]. surename=s then //если искомая и выбранная равны, то выводим

begin

Writeln (Base[i]. number,' ', base[i]. Surename+' '+base[i]. NameGroup);

counter:=counter+1; //счетчик +1

end;

if counter=0 then writeln ('Запись не найдена'); //если ничего не найдено

readln;counter:=0; //обнуляем все

end;

end;

procedure FindINTREE; // процедура вывода на экран результата функции поиска

var

numberbook:integer;

begin

writeln ('Введите номер зачетки');

readln (numberbook);

if FindInTree (MyTree, numberBook) //поиск в дереве

then writeln ('Данный элемент в дереве найден')

else writeln ('Данный элемент в дереве не найден');

readln;

end;

Procedure AddInBase; //процедура добавления в базу

var

m:integer;

s:string[50];

begin

assign (input,'base.txt'); //присоединяем текстовый файл

append (input); //открываем для добавления записей в конец

writeln (input); //переход на новую строку в файле

Writeln ('Пожалуйста, введите номер зачетки');

readln (m); //читаем номер зачетки

write (input, m);

Writeln ('Пожалуйста, введите фамилию студента');

readln (s); //читаем фамилию

write (input,' '+s+' ');

Writeln ('Пожалуйста, введите номер группы');

readln (s); //читаем номер группы

write (input, s);

Writeln ('Добавление прошло успешно.');

Writeln ('Запись добавится в базу после выхода из программы.');

readln;

close (input);

NumberOfRecords:=initializate ();

For i:=1 to NumberOfRecords do Insert (MyTree, Base[i]. Number);

end;

procedure obhod (p:ttree);

Begin

if p<>nil then

begin

obhod (p^.left);

writeln (p^.value);

obhod (p^.right);

end;

end;

procedure Print;

var

i: integer;

begin

if (NumberOfRecords=0) then

writeln ('В базе нет ни одной записи')

else begin

writeln ('Всего записей в базе :', NumberOfRecords:3);

for i := 1 to NumberOfRecords do begin

writeln (base[i]. number, ' ', base[i]. Surename, ' ',

base[i]. namegroup);

end;

end;

end;

begin //ТЕЛО ПРОГРАММЫ

NumberOfRecords:=initializate (); //выполняем инициализацию (функция)

For i:=1 to NumberOfRecords do Insert (MyTree, Base[i]. Number); //ПОСТРОЙКА ДЕРЕВА

r:=1;

while (r>=1) and (r<=5) do begin

clrscr;

Writeln ('Введите:');

writeln ('1 — для поиска элемента в базе'); //ОТРИСОВKА МЕНЮ

writeln ('2 — для добавления нового элемента в базу');

writeln ('3 — для поиска элемента в дереве');

writeln ('4 — для печати содержимого базы данных');

writeln ('5 — для печати содержимого дерева');

writeln ('6(или другое число) — для выхода из программы');

readln®; //чтение действия

case r of

1: FindInBase; //запуск функции поиска в базе

2: addinbase; //запуск функции добавления в базу

3: FindINTREE; //поиск в дереве

4: print; // печать из базы

5: obhod (mytree); // симметричный обход

end;

end;

end.

БЛОК-СХЕМЫ АЛГОРИТМОВ

1)Основной программы

2) Процедура Insert

3)Функция FindInTree — поиск в дереве.

4) Процедура FindINTREEпроцедура вывода на экран результата функции поиска

5) Функция Initialisate — инициализация. Функция переносит записи из внешнего файла в оперативную память и подсчитывает количество записей.

6) Процедура FindInBase — процедура поиска элемента в базе данных

7)Процедура AddInBase — добавление новых элементов.

8) Процедура Print — печать содержимого базы данных

9) Процедура Obhod — симметричный обход дерева с печатью его элементов.

Симметричный обход. Сначала в симметричном порядке посещаются все узлы левого поддерева, затем корень n, после чего в симметричном порядке все узлы правого поддерева.

Работа программы на разных режимах

1) Поиск существующего элемента в базе двумя способами

— по номеру зачетки

— по фамилии Поиск в базе несуществующего элемента

— по номеру зачетки

— по фамилии

Добавление элемента в базу

Поиск в дереве существующего элемента Поиск в дереве несуществующего элемента Печать содержимого базы

Печать содержимого дерева Выход