Организация списка с помощью двоичного дерева
Федеральное Агентство по образованию РФ
Рязанский радиотехнический университет
Кафедра «АИТП»
Практическая работа
по дисциплине «Программирование и основы алгоритмизации»
Выполнили: Рогачиков А. Е., Попов Б.С.
Проверила: Кузьмина Е.М
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) //если дерево еще не создано,то создаем его
else
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);
counter:=counter+1; //счетчик +1
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; //поиск в дереве
4: print; // печать из базы
5: obhod(mytree); // симметричный обход
end;
end;.
БЛОК-СХЕМЫ АЛГОРИТМОВ
)Основной программы
2) Процедура Insert
)Функция FindInTree - поиск в дереве.
4) Процедура FindINTREE- процедура вывода на экран результата функции поиска
5) Функция Initialisate - инициализация. Функция переносит записи из внешнего файла в оперативную память и подсчитывает количество записей.
6) Процедура FindInBase - процедура поиска элемента в базе данных
)Процедура AddInBase - добавление новых элементов.
8) Процедура Print - печать содержимого базы данных
) Процедура Obhod - симметричный обход дерева с печатью его элементов.
Симметричный обход . Сначала в симметричном порядке посещаются все узлы левого поддерева, затем корень n , после чего в симметричном порядке все узлы правого поддерева.
Работа программы на разных режимах
) Поиск существующего элемента в базе двумя способами
- по номеру зачетки
по фамилии
Поиск в базе несуществующего элемента
- по номеру зачетки
по фамилии
Добавление элемента в базу
Поиск в дереве существующего элемента
Поиск в дереве несуществующего элемента
Печать содержимого базы
Печать содержимого дерева
Выход
Больше работ по теме:
Предмет: Информационное обеспечение, программирование
Тип работы: Практическое задание
Новости образования
КОНТАКТНЫЙ EMAIL: [email protected]
Скачать реферат © 2017 | Пользовательское соглашение
ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ