Организация списка с помощью двоичного дерева - Программирование, компьютеры и кибернетика практическая работа

Главная

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

Описание процедуры выбора структуры хранения данных. Программная реализация одномерного неоднородного массива. Представление бинарного дерева в виде динамической структуры данных. Изучение способов поиска в упорядоченном дереве. Содержание базы данных.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

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

Федеральное Агентство по образованию РФ
Рязанский радиотехнический университет
по дисциплине «Программирование и основы алгоритмизации»
Выполнили: Рогачиков А. Е., Попов Б.С.
1. Описание процедуры выбора структуры хранения данных
Для программной реализации задания №12 мы выбрали линейную структуру данных фиксированного размера - одномерный неоднородный массив.(вектор)
Каждый элемент массива - это запись, состоящая из полей . При обращении к элементу вектора в программе задается значение его индекса i.
SimplyRecord=record //Эталон для массива записей
NameGroup: string[10]; //номер группы
Максимальное число записей в списке 100 - это означает , в памяти ЭВМ может храниться информация о 100 студентах.
2. Описание структуры двоичного дерева
Бинарное дерево можно представить в виде динамической структуры данных, состоящей из узлов, каждый из которых содержит кроме данных не более двух ссылок на правое и левое бинарное дерево.
На каждый узел имеется одна ссылка. Начальный узел называется корнем.
По аналогии с элементами списков, узлы дерева удобно представить в виде записей, хранящих информацию и два указателя:
T = Integer; { это будет номером зачетки }
TTree = ^TNode; //указатель на запись
Left, Right: TTree; //левые и правые ветки(для дерева)
Здесь поля Left, Right (левые и правые ветки) будут содержать указатели для последующих полей.
Изобразим схематично пример дерева, организованного в виде динамической структуры данных:
Данное дерево организовано таким образом, что для каждого узла все ключи (значения узлов) его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева больше. Такой способ построения дерева называется деревом поиска или двоичным упорядоченным деревом.
С помощью дерева поиска можно организовать эффективный способ поиска, который значительно эффективнее поиска по списку.
Поиск в упорядоченном дереве выполняется по следующему рекурсивному алгоритму:
· Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева:
- если ключи совпадают, поиск завершен;
- если ключ в корне больше искомого, выполнить поиск в левом поддереве;
- если ключ в корне меньше искомого, выполнить поиск в правом поддереве.
· Если дерево пусто, то искомый элемент не найден.
Словесное описание работы программы.
Нами был реализован список студентов, записи которого состоят из следующих полей: номер зачетки, фамилия, и номер группы. Эти данные считываются в оперативную память из внешнего файла (base.txt) при каждом запуске в начале работы программы. Эти действия выполняются в процедуре инициализации, которая так же подсчитывает количество записей о студентах.
Далее, проходя по всем записям, программа строит двоичное дерево по ключевому полю - номеру зачетки.
Программа включает в себя функции поиска записи в базе по фамилии, либо по номеру зачетки, добавление новых записей в базу данных, и поиск элементов в дереве.
Поиск по списку организован путем сравнения заданного значения (Фамилии или номера зачетки) с соответствующими полями записи при прохождении записи от первого до последнего элементов.
3. Содержание базы данных (внешний файл)
4. Блок-схемы алгоритмов и тексты программ
SimplyRecord=record //Эталон для массива записей
NameGroup: string[10]; //номер группы
T = Integer; { это будет номером зачетки }
TTree = ^TNode; //указатель на запись
Left, Right: TTree; //левые и правые ветки(для дерева)
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);
New(p); //выделяем память для корня дерева
p^.value := n; //присваи ваем значение в корень
p^.Left := nil; //иннициализация левой и правой ветки
CreateNode(Root, X) //если дерево еще не создано,то создаем его
with Root^ do begin //проходим по всей записи
Insert(Right, X) //если значение меньше, то вставляем ветку слева
Insert(Left, X); //если больше, то справа
function FindInTree(root:ttree; key:integer) :Boolean; //поиск в дереве
while p<>nil do begin //если ветка не пуста
if key=p^.value then begin //если узел с таким ключом есть
FindInTree:=true; //то присваиваем правда
if key < p^.value then //если меньше то
p := p ^. right ; {иначе спуститься вправо}
function initializate:integer; //иннициализация
assign(input,'base.txt'); //база данных номер фамилия группа
reset(input); //открываем для чтения
while not EOF(input) do //пока не конец файла делаем
val(copy(s,1,x-1),base[i].number,bufer1); //забиваем в iй элемент базы номер зачетки
delete(s,1,x); //удяляем в строке все до пробела
base[i].Surename:=copy(s,1,x-1); //забиваем iю фамилию
base[i].NameGroup:=s; //номер группы
close(input); //закрываем входной файл
initializate:=i; //записываем в функцию количество элементов во входном файле
procedure FindInBase; //функция найти в базе
Writeln('Введите данные для поиска'); //меню
readln(operation); //читаем опреацию
if (operation = 1) then //если опреация 1
Writeln('Введите номер зачетки'); //номер зачетки
readln(number); //читаем этот номер
for i := 1 to NumberOfRecords do if Base[i].Number=number then //от 1 до количества элементов, если
Writeln(Base[i].number,' ',base[i].Surename+' '+base[i].NameGroup);
//выводим на экран элемент полностью
if counter=0 then writeln('Запись не найдена'); //Если счетчик 0, то выводим сообщение с результатом-его отсутствием
readln;counter:=0; //обнуляем счетчик
if (operation = 2) then //если операция 2
Writeln('Введите фамилию студента'); //поиск по фамилии
for i:=1 to NumberOfRecords do if Base[i].surename=s then //если искомая и выбранная равны, то выводим
Writeln(Base[i].number,' ',base[i].Surename+' '+base[i].NameGroup);
if counter=0 then writeln('Запись не найдена'); //если ничего не найдено
procedure FindINTREE; // процедура вывода на экран результата функции поиска
if FindInTree(MyTree,numberBook) //поиск в дереве
then writeln ('Данный элемент в дереве найден')
else writeln ('Данный элемент в дереве не найден');
Procedure AddInBase; //процедура добавления в базу
assign(input,'base.txt'); //присоединяем текстовый файл
append(input); //открываем для добавления записей в конец
writeln(input); //переход на новую строку в файле
Writeln('Пожалуйста, введите номер зачетки');
Writeln('Пожалуйста, введите фамилию студента');
Writeln('Пожалуйста, введите номер группы');
Writeln('Добавление прошло успешно.');
Writeln('Запись добавится в базу после выхода из программы.');
For i:=1 to NumberOfRecords do Insert(MyTree,Base[i].Number);
writeln ('В базе нет ни одной записи')
writeln ('Всего записей в базе :',NumberOfRecords:3);
for i := 1 to NumberOfRecords do begin
writeln(base[i].number, ' ', base[i].Surename, ' ',
NumberOfRecords:=initializate(); //выполняем инициализацию(функция)
For i:=1 to NumberOfRecords do Insert(MyTree,Base[i].Number); //ПОСТРОЙКА ДЕРЕВА
writeln('1 - для поиска элемента в базе'); //ОТРИСОВKА МЕНЮ
writeln('2 - для добавления нового элемента в базу');
writeln('3 - для поиска элемента в дереве');
writeln('4 - для печати содержимого базы данных');
writeln('5 - для печати содержимого дерева');
writeln('6(или другое число) - для выхода из программы');
1: FindInBase; //запуск функции поиска в базе
2: addinbase; //запуск функции добавления в базу
5: obhod(mytree); // симметричный обход
3)Функция FindInTree - поиск в дереве.

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


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

6) Процедура FindInBase - процедура поиска элемента в базе данных
7)Процедура AddInBase - добавление новых элементов.
8) Процедура Print - печать содержимого базы данных

9) Процедура Obhod - симметричный обход дерева с печатью его элементов.
Симметричный обход . Сначала в симметричном порядке посещаются все узлы левого поддерева, затем корень n , после чего в симметричном порядке все узлы правого поддерева.
1) Поиск существующего элемента в базе двумя способами
Поиск в базе несуществующего элемента

Поиск в дереве существующего элемента
Поиск в дереве несуществующего элемента
Рассмотрение нелинейных динамических структур данных в виде бинарного дерева. Построение дерева двоичного поиска. Реализация трех обходов дерева, выведение обходов на экран компьютера. Разработка текста программы. Симметричноправая прошивка дерева. контрольная работа [81,6 K], добавлен 14.12.2011
Организация данных с помощью бинарных деревьев. Определение бинарного дерева. Упорядоченное двоичное дерево поиска и его свойства. Программная реализация добавления данных в упорядоченное двоичное дерево с использованием динамических структур данных. курсовая работа [459,0 K], добавлен 09.08.2012
Общая характеристика организации массива в виде двоичного дерева. Особенности линейного и двоичного поиска заданного элемента массива. Методика упорядочения массива методом сортировки деревом. Инструкции и текст программы для нечисленной обработки данных. курсовая работа [242,3 K], добавлен 12.11.2010
Организация работы базы данных с помощью сбалансированных В-деревьев: принципы, методы добавления, поиска, удаления элементов из структуры. Процедуры, производящие балансировку и слияние записей в блоке. Реализация программы в Научной библиотеке ОрелГТУ. курсовая работа [95,3 K], добавлен 12.08.2011
Разработка программы на языке С#, которая будет заниматься построением бинарного дерева для исходных данных и их редактированием, поиском информации о товарах по заданному ключу. Графические схемы алгоритмов поиска и удаления элемента бинарного дерева. курсовая работа [796,9 K], добавлен 22.02.2016
Алгоритм построения упорядоченного бинарного дерева. Нелинейные списковые структуры данных. Методы ускоренного доступа к данным. Организация записей в соответствии с адресной функцией. Способы организации индексируемого массива. Организация записей. реферат [806,0 K], добавлен 14.01.2014
Организация бинарного дерева. Порядок размещения данных в нелинейных структурах. Организация пользовательского интерфейса. Симметричный обход дерева. Параллельная работа обработчиков исключений. Расширенный графический интерфейс и его возможности. курсовая работа [426,0 K], добавлен 24.06.2013
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Организация списка с помощью двоичного дерева практическая работа. Программирование, компьютеры и кибернетика.
Автореферат На Тему Локальний Вплив Аплікації Прогестерону На Ремієлінізацію Зони Входу Трійчастого Нерва В Експеріменті
Пазин Веряскина Историческое Сочинение Скачать
Сколько Стоит Эссе В Кб
Доклад по теме Эстетика и религия
Контрольная работа по теме Комиссия ООН по праву международной торговли (ЮНСИТРАЛ)
Монтажные приспособления и инструменты
Смешные Истории Из Детства Сочинение
Курсовая Работа Гп Недействительная Сделка
Реферат по теме Осмотр места происшествия
Сочинение На Тему Нравственные Ценности Российского Народа
Историческое Сочинение 1113 1125
Дипломная работа по теме Влияние занятий баскетболом на развитие скоростно–силовой подготовки детей
Реферат по теме Как жили в Древней Руси
Контрольная работа по теме Анализ динамики, состава и структуры источников формирования капитала предприятия
Сочинение На Тему Рожь Шишкин 4
Доклад: Скажи мне, что ты слушаешь...
Дипломная работа по теме Каталитический риформинг
Реферат: Добро и зло в теории и практике социальной работы
Реферат: Handmade Soap Lab Essay Research Paper HANDMADE
Реферат: Huck Finn The Problem With The Human
Роль системного взаимодействия с родителями в организации сопровождения развивающихся способностей учащихся начальной школы - Педагогика реферат
Проблема роста российских коммерческих организаций и ее решение - Менеджмент и трудовые отношения реферат
Брак по римскому праву - Государство и право презентация