Организация списка с помощью двоичного дерева
Федеральное
Агентство по образованию РФ
Рязанский
радиотехнический университет
Кафедра
«АИТП»
Практическая
работа
по
дисциплине «Программирование и основы алгоритмизации»
Выполнили: Рогачиков А. Е.,
Попов Б.С.
Проверила: Кузьмина Е.М
1. Описание процедуры выбора структуры хранения
данных
Для программной реализации задания №12 мы
выбрали линейную структуру данных фиксированного размера - одномерный
неоднородный массив.(вектор)
Каждый элемент массива - это запись, состоящая
из полей . При обращении к элементу вектора в программе задается значение его
индекса i.
=record //Эталон для массива записей
Number: integer; //номер
зачетки
Surename:string[10]; //фамилия
NameGroup: string[10]; //номер группы
Максимальное число записей в списке 100 - это
означает , в памяти ЭВМ может храниться информация о 100 студентах.
. Описание структуры двоичного
дерева
Бинарное дерево можно
представить в виде динамической структуры данных, состоящей из узлов, каждый из
которых содержит кроме данных не более двух ссылок на правое и левое бинарное
дерево.
На каждый узел имеется одна
ссылка. Начальный узел называется корнем.
По аналогии с элементами
списков, узлы дерева удобно представить в виде записей, хранящих информацию и
два указателя:
T = Integer; { это будет номером зачетки }=
^TNode; //указатель на запись
TNode = record //сама запись
value: T; //значение записи
Left, Right: TTree; //левые и правые ветки(для
дерева)
Здесь поля Left,
Right (левые и правые
ветки) будут содержать указатели для последующих полей.
Изобразим схематично пример
дерева, организованного в виде динамической структуры данных:
Данное дерево организовано
таким образом, что для каждого узла все ключи (значения узлов) его левого
поддерева меньше ключа этого узла, а все ключи его правого поддерева больше.
Такой способ построения дерева называется деревом поиска или двоичным
упорядоченным деревом.
С помощью дерева поиска можно
организовать эффективный способ поиска, который значительно эффективнее поиска
по списку.
Поиск в упорядоченном дереве
выполняется по следующему рекурсивному алгоритму:
· Если дерево не
пусто, то нужно сравнить искомый ключ с ключом в корне дерева:
если ключи совпадают, поиск
завершен;
если ключ в корне больше
искомого, выполнить поиск в левом поддереве;
если ключ в корне меньше
искомого, выполнить поиск в правом поддереве.
· Если дерево пусто,
то искомый элемент не найден.
Словесное описание работы программы.
Нами был реализован список студентов, записи
которого состоят из следующих полей: номер зачетки, фамилия, и номер группы.
Эти данные считываются в оперативную память из внешнего файла (base.txt)
при каждом запуске в начале работы программы. Эти действия выполняются в
процедуре инициализации, которая так же подсчитывает количество записей о
студентах.
Далее, проходя по всем записям, программа строит
двоичное дерево по ключевому полю - номеру зачетки.
Программа включает в себя функции поиска записи
в базе по фамилии, либо по номеру зачетки, добавление новых записей в базу
данных, и поиск элементов в дереве.
Поиск по списку организован путем сравнения
заданного значения (Фамилии или номера зачетки) с соответствующими полями
записи при прохождении записи от первого до последнего элементов.
программный бинарный дерево массив
3. Содержание базы данных (внешний файл)
иванов 334
попов 3372
рогачиков 337
орлов 112
. Блок-схемы алгоритмов и тексты программ
Program Kursach;crt;
SimplyRecord=record //Эталон
для
массива
записей
Number: integer; //номер
зачетки
Surename:string[10]; //фамилия
NameGroup: string[10]; //номер
группы
end;
T = Integer; { это будет номером зачетки }
TTree = ^TNode; //указатель на запись= record
//сама запись: T; //значение записи, Right: TTree; //левые и правые ветки(для
дерева)
end;
input:text; //входной
файл
base:array[1..100] of SimplyRecord;
{Массив
из
100 записей}
r, i, NumberOfRecords, numberBook:
integer;
MyTree:TTree; //непосредственно
дерево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) //если дерево еще не
создано,то создаем его
with Root^ do begin //проходим по всей записи
if value < X then
Insert(Right, X) //если значение меньше, то
вставляем ветку слева
else if value > X Then
Insert(Left, X); //если
больше,
то
справа
end;
end;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; //иначе
ложь;initializate:integer;
//иннициализация
s:string; //считываемая
строка
i,x,bufer1:integer;
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;FindInBase; //функция
найти
в
базе
Counter,operation,number:integer;
s:string;
i: integer;
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);
end;
if counter=0 then writeln('Запись
не
найдена');
//если
ничего
не
найдено
readln;counter:=0; //обнуляем
все
end;;FindINTREE; // процедура вывода на экран
результата функции поиска
var
numberbook:integer;
begin
writeln('Введите
номер
зачетки');
readln(numberbook);
if FindInTree(MyTree,numberBook) //поиск
в
дереве
then writeln ('Данный элемент в дереве найден')
else writeln ('Данный элемент в дереве не
найден');
readln;;AddInBase; //процедура
добавления
в
базу
m:integer;
s:string[50];
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);:=initializate();
For i:=1 to NumberOfRecords do
Insert(MyTree,Base[i].Number);;
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;;//ТЕЛО
ПРОГРАММЫ:=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(r); //чтение действия
case r of
: FindInBase; //запуск функции поиска в базе
2: addinbase; //запуск функции добавления в базу
3: FindINTREE; //поиск в дереве
5: obhod(mytree); // симметричный обход
end;
end;.
БЛОК-СХЕМЫ АЛГОРИТМОВ
)Основной программы
2) Процедура Insert
)Функция FindInTree
- поиск в дереве.
4) Процедура FindINTREE-
процедура вывода на экран результата функции поиска
5) Функция Initialisate
- инициализация. Функция переносит записи из внешнего файла в оперативную
память и подсчитывает количество записей.
6) Процедура FindInBase
- процедура поиска элемента в базе данных
)Процедура AddInBase
- добавление новых элементов.
8) Процедура Print
- печать содержимого базы данных
) Процедура Obhod
- симметричный обход дерева с печатью его элементов.
Симметричный обход . Сначала в
симметричном порядке посещаются все узлы левого поддерева, затем корень n ,
после чего в симметричном порядке все узлы правого поддерева.
Работа программы на разных режимах
) Поиск существующего элемента в базе двумя
способами
- по номеру зачетки
по фамилии
Поиск в базе несуществующего элемента
- по номеру зачетки
по фамилии
Добавление элемента в базу
Поиск в дереве существующего элемента
Поиск в дереве несуществующего элемента
Печать содержимого базы
Печать содержимого дерева
Выход
