- •Оглавление
- •Введение
- •Основные понятия и определения
- •Встроенные структуры данных(Pascal/с)
- •Варианты индивидуальных заданий на Pascal
- •Варианты индивидуальных заданий на c
- •Простые типы данных в Pascal
- •Вещественные типы
- •Вещественные типы языка Pascal
- •Сложный тип
- •Простые типы данных в с Целые типы
- •Целые типы языка c
- •Диапазоны значений целых типов языка c
- •Символьный тип
- •Перечисляемый тип
- •Вещественные типы
- •Вещественные типы языка c
- •Структурированные типы данных в Pascal Массив
- •Структура данных типа «запись»
- •Структура данных типа «множество»
- •Структурированные типы данных в c Структура данных типа «массив»
- •Структура данных типа «структура»
- •Производные структуры данных. Структура данных «строка» (Pascal/c)
- •Задание
- •Варианты индивидуальных заданий
- •Варианты задач
- •Варианты форматов
- •Назначение процедур и функций в модулях реализации сд типа строка в Pascal
- •Назначение процедур и функций в модулях реализации сд типа «строка» в c
- •Сравнительный анализ методов сортировки (Pascal/c)
- •1. Изучить временные характеристики алгоритмов.
- •6. Выводы по работе.
- •1. Выбираем элемент массива в качестве разделителя (например, первый).
- •Массив м
- •Массив м
- •Примеры программной реализации алгоритмов сортировки на языке Pascal
- •Примеры программной реализации алгоритмов сортировки на языке c
- •Сравнительный анализ алгоритмов поиска (Pascal/c)
- •Максимальное количество операций сравнения
- •Среднее количество операций сравнения
- •Алгоритмы поиска в неупорядоченных массивах Алгоритм линейного поиска
- •Алгоритм быстрого линейного поиска
- •Анализ алгоритмов линейного поиска
- •Алгоритмы поиска в упорядоченных массивах Алгоритм быстрого линейного поиска
- •Алгоритм бинарного поиска
- •Анализ алгоритма бинарного поиска
- •Алгоритм блочного поиска
- •Анализ алгоритма блочного поиска
- •Структуры данных «линейные списки» (Pascal/с)
- •Варианты индивидуальных заданий
- •Назначение процедур и функций
- •Структуры данных «стек» и «очередь» (Pascal/с)
- •Результаты работы программы
- •Варианты индивидуальных заданий
- •Варианты задач
- •Модули для реализации стека
- •Модули для реализации очереди
- •Очередь
- •Структуры данных «дерево» (Pascal/с)
- •Варианты индивидуальных заданий
- •Варианты задач
- •Назначение процедур и функций:
- •Принципы размещения бинарного дерева в памяти эвм
- •Алгоритмы обхода бинарного дерева
- •Обход бинарного дерева «в глубину» (в прямом порядке)
- •Обход бинарного дерева «в ширину» (по уровням)
- •Обход бинарного дерева в симметричном порядке
- •Обход бинарного дерева в обратном порядке
- •Алгоритмы формирования бинарного дерева
- •Рекурсивный алгоритм формирования бинарного дерева «в глубину»
- •Итеративный алгоритм формирования бинарного дерева «в глубину»
- •Алгоритм формирования бинарного дерева «в ширину»
- •Алгоритм формирования бинарного дерева «снизу вверх»
- •Рекурсивный алгоритм формирования бинарного дерева
- •Итеративный алгоритм формирования бинарного дерева
- •Алгоритм формирования бинарного дерева минимальной высоты
- •Итеративный алгоритм формирования сбалансированного бинарного дерева
- •Представление алгебраических выражений бинарными деревьями
- •Алгоритм формирования бинарного дерева по прямой польской записи
- •Алгоритм формирования бинарного дерева по обратной польской записи
- •Структуры данных «таблица» (Pascal/с)
- •Варианты индивидуальных заданий
- •Библиографический список
Назначение процедур и функций:
InitTree — инициализация дерева;
CreateRoot — создание корня;
WriteDataTree — запись данных в дерево;
ReadDataTree — чтение элемента дерева;
IsLSon — проверка на наличие левого сына;
IsRSon — проверка на наличие правого сына;
MoveToLSon — переход к левому сыну;
MoveToRSon — переход к правому сыну;
IsEmptyTree — проверка: дерево пусто или нет;
DelTree — удаление листа.
С о д е р ж а н и е о т ч е т а
1. Тема лабораторной работы.
2. Цель работы.
3. Характеристика СД «дерево» (п.1 задания).
4. Индивидуальное задание.
5. Тексты модулей на языках Pascal и С для реализации СД «дерево», тексты программ для отладки модулей, тестовые данные и результат работы программ.
6. Тексты программ на языках Pascal и С для решения задачи с использованием модулей, тестовые данные, результаты работы программ.
Т е о р е т и ч е с к и е с в е д е н и я
Дерево — конечное непустое множество Т, состоящее из одной или более вершин таких, что выполняются следующие условия:
1) Имеется одна специально обозначенная вершина, называемая корнем данного дерева.
2) Остальные вершины (исключая корень) содержатся в m 0 попарно непересекающихся множествах Т1, Т2, …, Тm, каждое из которых в свою очередь является деревом. Деревья Т1, Т2, …, Тm называются поддеревьями данного корня.
Наиболее наглядным способом представления дерева является графический (рис.20), в котором вершины изображаются окружностями с вписанной в них информацией и корень дерева соединяется с корнями поддеревьев Т1, Т2, …, Тm, дугой (линией).
Рис.20. Графический способ представления дерева
Если подмножества Т1, Т2, …, Тm упорядочены, то дерево называют упорядоченным. Если два дерева считаются равными и тогда, когда они отличаются порядком подмножеств Т1, Т2, …, Тm, то такие деревья называются ориентированными деревьями. Конечное множество непересекающихся деревьев называется лесом.
Количество подмножеств для данной вершины называется степенью вершины. Если такое количество равно нулю, то вершина является листом. Максимальная степень вершины в дереве — степень дерева. Уровень вершины — длина пути от корня до вершины. Максимальная длина пути от корня до вершины определяет высоту дерева (количество уровней в дереве).
Бинарное дерево — конечное множество элементов, которое может быть пустым, состоящее из корня и двух непересекающихся бинарных деревьев, причем поддеревья упорядочены: левое поддерево и правое поддерево. В дальнейшем будем рассматривать только СД типа «бинарное дерево» (БД). Корень дерева будем называть «отцом», корень левого поддерева — «левым сыном», а корень правого поддерева — «правым сыном». На рис.21 приведен пример графического представления БД.
уровень 0
уровень 1
уровень 2
уровень 3
Рис.21. Графическое представление БД
БД — динамическая структура. Над СД БД определены следующие основные операции: инициализация, создание корня, запись данных, чтение данных, проверка — есть ли левый сын, проверка — есть ли правый сын, переход к левому сыну, переход к правому сыну, проверка — пустое ли дерево, удаление листа.
Кардинальное число СД БД определяется по формуле
CAR(БД) = ((2i)! / ((i + 1)(i!)2))·CAR(BaseType) + 1 ,i=1…max,
где CAR(BaseType) — кардинальное число элемента БД типа BaseType, max — максимальное количество элементов в БД (не всегда определено, т.к. может зависеть от объема свободной динамической памяти).
На абстрактном уровне БД представляет собой иерархическую структуру — дерево.
На физическом уровне БД реализуется связной схемой хранения. Располагаться БД может в статической или динамической памяти.