Реализация операций по работе с бинарными деревьями. Понятие, сущность и необходимость динамических структур данных. Рекурсивный алгоритм, определяющий высоту дерева. Определение значений информационных полей. Программные операции с бинарными деревьями.
Аннотация к работе
В данной работе рассмотрим тему: «Динамические структуры данных: деревья». В языках программирования (Pascal, C, др.) существует способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью). Работа с динамическими величинами связана с использованием еще одного типа данных - ссылочного типа.Динамические структуры данных в процессе существования в памяти могут изменять не только число составляющих их элементов, но и характер связей между элементами. Такая особенность динамических структур, как непостоянство их размера и характера отношений между элементами, приводит к тому, что на этапе создания машинного кода программа-компилятор не может выделить для всей структуры в целом участок памяти фиксированного размера, а также не может сопоставить с отдельными компонентами структуры конкретные адреса. Динамические структуры данных - это структуры данных, память под которые выделяется и освобождается по мере необходимости. Динамические структуры, по определению, характеризуются отсутствием физической смежности элементов структуры в памяти, непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки. Дескриптор связной структуры содержит один или несколько указателей, позволяющих войти в структуру, далее поиск требуемого элемента выполняется следованием по цепочке указателей от элемента к элементу.В процедуре Add имеется тривиальный случай (когда дерево пустое) и рекурсивные вызовы: добавить в левое и правое поддеревья - Add (NEWDATA,Root^.left) и Add(NEWDATA,Root^.right). Number := 0 {дерево пустое - листов нет} else if (Tree^.left=Nil) and (Tree^.right=Nil) then Просмотр справа налево procedure VIEWRL(Root:PNODE); {LR-> Right - Left} begin if ROOTNIL then begin while neonil do begin if arg<ind^.data then begin if ind^.left=nil then begin ind^.left:=neo; if t then begin if (del^.left=nil) and (del^.right=nil) then begin if del=n then begin n:=nil; dispose(del) end else if ind^.left=del then begin ind^.left:=nil;Деревья являются одними из наиболее широко распространенных структур данных в информатике и программировании, которые представляют собой иерархические структуры в виде набора связанных узлов. Нами выявлено, что дерево является структурой данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов. Каждый элемент дерева называется вершиной (узлом) дерева.
Введение
В данной работе рассмотрим тему: «Динамические структуры данных: деревья».
Актуальность исследуемой проблемы. В языках программирования (Pascal, C, др.) существует способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).
Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера.
Работа с динамическими величинами связана с использованием еще одного типа данных - ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.
Предметом данного исследования являются динамические структуры данных в программировании.
Объектом исследования являются деревья в динамических структурах данных.
Цель данной курсовой работы - это изучить динамические структуры данных, а именно деревья.
Для достижения поставленной цели необходимо решить следующие задачи: - рассмотреть понятие, сущность и необходимость динамических структур данных;
- выявить динамические структуры данных, а именно деревья;
Данная работа состоит из введения, основной части, куда входят две главы, заключения, списка использованной литературы, куда входят одиннадцать наименований.
При написании данной работы использовался метод анализа научной литературы отечественных и зарубежных авторов, таких как Кернигана Б., Ритчи Д., Подбельского В. В., Фомина С. С., Будниковой Н.А., Хабибуллина И.Ш., Абилова К.С., Бабаева М.А., Галагузовой М.А. и др.
Вывод
Итак, можно сказать, что древовидная модель оказывается довольно эффективной для представления динамических данных с целью быстрого поиска информации. Деревья являются одними из наиболее широко распространенных структур данных в информатике и программировании, которые представляют собой иерархические структуры в виде набора связанных узлов.
Нами выявлено, что дерево является структурой данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов. Каждый элемент дерева называется вершиной (узлом) дерева. Вершины дерева соединены направленными дугами, которые называют ветвями дерева. Начальный узел дерева называют корнем дерева, ему соответствует нулевой уровень. Листьями дерева называют вершины, в которые входит одна ветвь и не выходит ни одной ветви.
Деревья особенно часто используют на практике при изображении различных иерархий.
Тексты приведенных алгоритмов очень компактны и просты в понимании. В заключение отметим, что рекурсивные алгоритмы широко используются в базах данных и при построении компиляторов, в частности для проверки правильности записи арифметических выражений, синтаксис которых задается с помощью синтаксических диаграмм.
Список литературы
• Керниган Б., Ритчи Д., Фьюэр А. Язык программирования Си: Задачи по языку Си. М.: Финансы и статистика, 2011 г., стр. 290
• Керниган Б., Ритчи Д. Язык программирования Си. М.: Финансы и статистика, 2012 г., стр. 270
• Подбельский В. В., Фомин С. С. Программирование на языке Си. Учеб.пособие. М.: Финансы и статистика, 2010 г., стр. 600
• Будникова Н.А. Обучающий комплекс по программированию на языке ПАСКАЛЬ, Ростов на Дону, 2011 г., стр. 350
• Хабибуллин И.Ш. Программирование C : Пер. с англ. - 3-е изд. - СПБ.: БХВ-Петербург, 2012 г., стр. 512
• Абилов К.С. Информатика для вузов. Москва, 2011 г., стр. 290
• Бабаев М.А. Программирование и его основы. Уфа, 2010 г., стр. 320
• Галагузова М.А. Информатика. Высшая школа. № 7, 2012 г., стр. 380
• Голант Е.Я. Информатика. М., 2011 г., стр. 250
• Кантарбаев С.Е. Языки программирования. Алма-Ата, 2012 г., стр. 340
• Лордкипанидзе Д.О. Принципы организации и методы программирования. М., 2010 г., стр. 269