Добавлен: 29.03.2023
Просмотров: 173
Скачиваний: 4
Деревья (как упорядоченные, так и нет) активно используются в программировании, что было уже определено в предыдущем параграфе курсовой работы. По этой причине мы сосредоточимся в основном на рассмотрении процедур работы с ними.
Для описания узла бинарного дерева в программе введем тип, имеющий вид следующей записи[28]:
type
PNode = ^TNode;
TNode = record
Info : string; {поле данных}
Left,Right : PNode; {указатели на левое и правое поддеревья}
end;
Процедура создания нового узла.
{ Создание нового узла со значением информационного поля X.
Возвращается указатель на новый узел}
function NewNode(X:string):PNode;
var
P : PNode;
begin
New(P);
P^.Info := X;
P^.Left := Nil;
P^.Roght := Nil;
NewNode := P;
end;
Процедура создания потомка (поддерева)
procedure SetLeft(P:PNode; X:string);
begin
P^.Left := NewNode(X);
end;
Правила создание бинарного дерева[29]:
- данные (целые числа) заносятся с клавиатуры;
- дубликаты не включаются (но выводятся на экран);
- признаком окончания ввода является ввод числа 0;
- результат - бинарное упорядоченное дерево.
При обработке динамических структур типа «дерево» чаще всего используются рекурсивные алгоритмы.
Рекурсия предполагает определение некоторого понятия с использованием самого этого понятия.
Примером рекурсивного определения является факториал неотрицательного числа:
n! = 1 при n=0
n! = n*(n-1)! при n >0
В Турбо-Паскале рекурсия разрешена: подпрограмма может вызывать сама себя:
program FactDemo;
var
k : integer;
function Factor(n:integer):integer;
begin
if n=0 then
Factor : 1
else
Factor := n * Factor(n-1);
{end if}
end;
begin
write('Введите целое число ');
readln(k);
if k>=0 then
writeln('Факториал ',n:1,' = ', Factor(k));
{end if}
end.
Первое значение Factor вычисляется, когда n=0, оно подставляется в соответствующий экземпляр памяти. Теперь на каждом очередном шаге значения всех членов выражения n*Factor(n-1) известны, и алгоритм подставляет в это выражение значение, полученное на предыдущем шаге. Это происходит в процессе свертывания рекурсии.
Сформулируем два важных свойства рекурсивных алгоритмов[30]:
1. Наличие тривиального случая.
Правильный рекурсивный алгоритм не должен создавать бесконечную последовательность вызовов самого себя.
Для этого он обязательно должен содержать нерекурсивный выход: т.е. при некоторых входных данных вычисления в алгоритме должны производиться без вызовов его самого.
Для функции «факториал» тривиальный случай: «0!=1».
2. Определение сложного случая в терминах более простого.
При любых входных данных нерекурсивный выход должен достигаться за конечное число рекурсивных вызовов.
Для этого каждый новый вызов рекурсивного алгоритма должен решать более простую задачу. Иными словами рекурсивный алгоритм должен содержать определение некоторого сложного случая в терминах более простого случая.
Для функции «факториал» вместо вычисления n! заменяется умножением n*(n-1)!, и при этом с каждым вызовом значение n уменьшается, стремясь к нулю и достигая его за конечное число вызовов.
Из определения структуры типа «дерево» видно, что она рекурсивна по определению, а в силу этого рекурсивными являются и практически все алгоритмы работы с деревьями. Для этого достаточно посмотреть на приведенный выше пример создания бинарного упорядоченного дерева.
В процедуре Add имеется тривиальный случай (когда дерево пустое) и
рекурсивные вызовы: добавить в левое и правое поддеревья - Add (NewData,Root^.left) и Add(NewData,Root^.right).
Алгоритмы работы с деревьями
В приведенных ниже алгоритмах предполагается, что узел (элемент) дерева декларирован следующей записью[31]:
Type
PNode = ^TNode;
TNode = record
Data : integer; {информационное поле}
left,right : PNode;
end.
Анализ приведенных алгоритмов показывает, что для получения ответа в них производится просмотр всех узлов дерева. Ниже будут приведены алгоритмы, в которых порядок обхода узлов дерева отличается. И в зависимости от порядка обхода узлов бинарного упорядоченного дерева, можно получить различные результаты, не меняя их размещения.
Просмотр используется не сам по себе, а для обработки элементов дерева, а просмотр сам по себе обеспечивает только некоторый порядок выбора элементов дерева для обработки. В приводимых ниже примерах обработка не определяется; показывается только место, в котором предлагается выполнить обработку текущего.
Алгоритмы просмотра дерева
Самой интересной особенностью обработки бинарных деревьев является та, что при изменении порядка просмотра дерева, не изменяя его структуры, можно обеспечить разные последовательности содержащейся в нем информации. В принципе возможны всего четыре варианта просмотра: слева-направо, справа-налева, сверху-вниз и снизу-вверх.
Прежде чем увидеть, к каким результатам это может привести, приведем
их[32]. Просмотр дерева слева - направо
procedure ViewLR(Root:PNode); {LR -> Left - Right }
begin
if Root<>Nil then
begin
ViewLR(Root^. left); {просмотр левого поддерева}
{Операция обработки корневого элемента - вывод на печать, в файл и др.}
ViewLR(Root^.right); { просмотр правого поддерева }
end;
end;
Таким образом, в данном разделе курсовой работы мы изучили виды операций, которые могут осуществляться при работе с бинарными деревьями. Мы выделили четыре вида операций:
- обход узлов в определенном порядке;
- добавление некоторого поддерева в дерево;
- исключение некоторого поддерева из дерева;
- примитивные операции над узлами дерева.
Далее, мы более подробно рассмотрели алгоритм операций, которые используются программистами.
В целом, можно сделать вывод, что данный вид динамической структуры данных достаточно актуален и довольно часто используется при создании различных программ. Описание алгоритма программ, который приведен в заключительной части курсовой работы позволит создать бинарное дерево на практике.
ЗАКЛЮЧЕНИЕ
Курсовая работа посвящена динамическим структурам данных, а именно – бинарным деревьям.
В первом разделе работы мы определили, что динамические структуры широко применяют для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки, поскольку упорядочивание динамических структур не требует перестановки элементов, а сводится к изменению указателей на эти элементы.
В современном мире наблюдается процесс постоянного внедрения новейших информационных технологий, что обусловлено развитием общества и повышением качества жизни.
Системы, которые предназначены для хранения, поиска и обработки различного рода информации приобретают всё большее значение, повышается их роль и в технологической части построения эффективной организационной системы учреждений. Вместе с этим увеличивается конкуренция, появляется всё больше попыток взлома и несанкционированных проникновений к важной информации.
С каждым годом информации становится всё больше и больше, оптимизируются способы её хранения, быстрой передачи и различных видов использования.
Также, мы подробно рассмотрели классификацию динамической структуры данных. К таким структурам относят:
- однонаправленные (односвязные) списки;
- двунаправленные (двусвязные) списки;
- циклические списки;
- стек;
- дек;
- очередь;
- бинарные деревья.
Третий параграф первой главы курсовой работы мы посвятили описанию структуры бинарных деревьев. Мы также определили, что бинарное дерево представляет собой динамическую структуру данных, представляющих собой дерево, в котором каждая вершина имеет не более двух потомков. Таким образом, бинарное дерево состоит из элементов, каждый из которых содержит информационное поле и не более двух ссылок на различные бинарные поддеревья.
Второй раздел курсовой работы включает описание программ и алгоритма их выполнения при работе с бинарными деревьями.
Мы выделили четыре вида операций:
- обход узлов в определенном порядке;
- добавление некоторого поддерева в дерево;
- исключение некоторого поддерева из дерева;
- примитивные операции над узлами дерева.
Далее, мы более подробно рассмотрели алгоритм операций, которые используются программистами.
Для того чтобы информационная система была изначально выстроена достаточно безопасно и эффективно, мы выделили несколько рекомендаций, которых необходимо придерживаться при ее создании:
- средства защиты, которые используются в системе, должны быть доступны для персонала технического обслуживания, также они должны быть выражены в понятной для них форме и содержать инструкцию;
- довести систему защиты до автономности;
- при создании информационной системы учитывать тот факт, что сбои могут возникнуть в любое время, что непосредственно повлияет на выполнение работы, поэтому нужно выстроить стратегическую систему разрешения внезапных угроз;
- наличие, содержание и место хранение защитных способов должно быть конфиденциально.
Итак, можно сказать, что древовидная модель оказывается довольно эффективной для представления динамических данных с целью быстрого поиска информации. Деревья являются одними из наиболее широко распространенных структур данных в информатике и программировании, которые представляют собой иерархические структуры в виде набора связанных узлов.
Нами выявлено, что дерево является структурой данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов. Каждый элемент дерева называется вершиной (узлом) дерева. Вершины дерева соединены направленными дугами, которые называют ветвями дерева. Начальный узел дерева называют корнем дерева, ему соответствует нулевой уровень. Листьями дерева называют вершины, в которые входит одна ветвь и не выходит ни одной ветви.
Деревья особенно часто используют на практике при изображении различных иерархий.
Тексты приведенных алгоритмов очень компактны и просты в понимании. В заключение отметим, что рекурсивные алгоритмы широко используются в базах данных и при построении компиляторов, в частности для проверки правильности записи арифметических выражений, синтаксис которых задается с помощью синтаксических диаграмм.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
- Александреску А. Современное проектирование на C++. Обобщенное программирование и прикладные шаблоны проектирования. Перевод с английского – Издательский дом «Вильямс», 2016 г. 336 с.
- Ашарина, И.В. Основы программирования на языках С и С++: Курс лекций для высших учебных заведений / И.В. Ашарина. – М.: Гор. линия-Телеком, 2018. – 208 c.
- Баженова, И.Ю. Языки программирования: Учебник для студентов учреждений высш. проф. образования / И.Ю. Баженова; Под ред. В.А. Сухомлин. – М.: ИЦ Академия, 2018. – 368 c.
- Белоусова, С.Н. Основные принципы и концепции программирования на языке VBA в Excel: Учебное пособие / С.Н. Белоусова, И.А. Бессонова. – М.: БИНОМ. ЛЗ, 2017. – 200 c.
- Бьянкуцци, Ф. Пионеры программирования. Диалоги с создателями наиболее популярных языков программирования / Ф. Бьянкуцци, Ш. Уорден. – СПб.: Символ-плюс, 2018. – 608 c.
- Ваныкина Г.В. Структуры и алгоритмы компьютерной обработки данных / Г.В. Ваныкина, Т.О. Сундукова. – ИНТУИТ. URL: https://intuit.ru/studies/courses/648/504/lecture/11455 (Дата обращения: 03.11.2020)
- Васильев А.Н. Программирование на С++ в примерах и задачах / Васильев А.Н. – 2017г. – 369С. URL: https://t.me/technobooks/376 (Дата обращения 03.11.2020)
- Вершинов Ф.Н. Классификация структур данных. / Ф.Н. Вершинов. URL: https://pandia.ru/text/78/302/22759.php (Дата обращения: 04.11.2020)
- Гергель, В.П. Современные языки и технологии параллельного программирования: Учебник/ предисл.: В.А. Садовничий. / В.П. Гергель. – М.: Изд. МГУ, 2016. – 408 c.
- Голицына, О.Л. Основы алгоритмизации и программирования: Учебное пособие / О.Л. Голицына, И.И. Попов. –М.: Форум; Издание 2-е, 2015. – 432 c.
- Дмитриева М.В. Динамические структуры данных / М.В. Дмитриева. Школа современного программирования. – 2017г. URL: https://cyberleninka.ru/article/n/dinamicheskie-struktury-dannyh/viewer (Дата обращения: 03.11.2020)
- Девис, Т. OpenGL. Руководство по программированию / Т. Девис, Д. Шрайнер, Дж. Нейдер, и др.. – М.: СПб: Питер, 2016. – 624 c
- Дорогов, В.Г. Основы программирования на языке С: Учебное пособие / В.Г. Дорогов, Е.Г. Дорогова; Под общ. ред. проф. Л.Г. Гагарина. – М.: ИД ФОРУМ, НИЦ ИНФРА-М, 2017. – 224 c.
- Керниган, Б.У. Язык программирования С / Б.У. Керниган, Д.М. Ритчи; Пер. с англ. В.Л. Бродовой. – М.: Вильямс, 2016. – 304 c.
- Кнут, Д.Э. Искусство программирования (Том 1. Основные алгоритмы) / Д.Э. Кнут. – М.: РИЦ, 2016. – 853 c.
- Литвиненко Н.А. Технология программирования на С++ / Н.А. Литвиненко – БХВ-Петербург.2015 – 281 С.
- Маслов, В.В. Основы программирования на языке Perl / В.В. Маслов. – М.: Радио и связь, 2016. – 144 c.
- Медведев В.И. Особенности объектно-ориентированного программирования С++/CLI, C# и Java. / В.И. Медведев .:РИЦ «Школа», Казань, 2-е изд. – 2010г. С. – 444.
- Монахов, В.В. Язык программирования Java и среда NetBeans. 3-е изд., пер. и доп. + DVD / В.В. Монахов. – СПб.: BHV, 2017. – 704 c.
- Роберт, С. Сикорд Безопасное программирование на C и C++ / Роберт С. Сикорд. – Москва: РГГУ, 2014. – 496 c.
- Оседлов В.И. Классификация динамической структуры данных. С++./ В.И. Оседлов URL: https://zen.yandex.ru/media/codeblog/dinamicheskie-struktury-dannyh-c-5b06f5e4256d5c1d650b7aa9 (Дата обращения: 04.11.2020)
- Поляков, А. Методы и алгоритмы компьютерной графики в примерах на Visual C++ / А. Поляков, В. Брусенцев. – М.: БХВ-Петербург, 2017. – 560 c.
- Понамарев, В. Программирование на C++/C# в Visual Studio .NET 2003 / В. Понамарев. – М.: БХВ-Петербург, 2015. – 917 c.
- Степаненко О.Е. Visual C++/ NET. Классика программирования / О.Е. Степаненко .:Изд-во: Букинист, Научная книга, 2016 , С. – 766.
- Стивен Прата. Язык программирования C++ (C++11). Лекции и упражнения, 6-е издание – М.: Вильямс, 2016. – 248 с.
- Страуструп Б. Язык программирования С++. Специальное издание. Пер. с англ. – М.: Издательство Бином, 2017 г. – 1136 с.
- Троелсен, Э. Язык программирования С# 5.0 и платформа .NET 4.5 / Э. Троелсен; Пер. с англ. Ю.Н. Артеменко. – М.: Вильямс, 2016. – 1312 c.
- Хейлсберг, А. Язык программирования C#. Классика Computers Science / А. Хейлсберг, М. Торгерсен, С. Вилтамут. – СПб.: Питер, 2016. – 784 c.
- Элджер Дж. C++. Библиотека программиста: Пер. с англ. – СПб.: Питер, 2018. – 320 с.