- •Оглавление
- •Введение
- •Основные понятия и определения
- •Встроенные структуры данных(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/с)
- •Варианты индивидуальных заданий
- •Библиографический список
Принципы размещения бинарного дерева в памяти эвм
1. БД располагается в динамической памяти. Каждая вершина БД представляет собой СД типа «запись», содержащую информационную часть и адреса сыновей. Память под вершину БД выделяется по мере надобности при построении БД и освобождается при исключении вершины. Адрес корня дерева находится в специальной ячейке динамической памяти, адрес которой хранится в статической памяти. БД (см. рис.21)может быть представлено в памяти так, как показано на рис.22.
2. Для хранения вершин БД используется СД типа «массив». Массив может располагаться в статической или динамической памяти. Элементы массива представляют собой СД типа «запись», содержащую информационную часть и адреса сыновей вершины БД. Индекс элемента массива, содержащего корень дерева, находится в специальной ячейке динамической памяти, адрес которой хранится в статической памяти. Элементы массива, не являющиеся вершинами БД, объединяются в список свободных элементов (ССЭ), на первый элемент которого указывает правый сын первого элемента массива. При включении элемента в БД берется первый элемент ССЭ, а исключаемый элемент заносится в начало ССЭ. БД (рис.21) может быть представлено в памяти так, как показано на рис.23. При таком способе в одном массиве может быть размещено несколько БД.
3. Для хранения вершин БД используется СД типа «массив». Массив может располагаться в статической или динамической памяти. Элементы массива представляют собой СД типа «запись», содержащую информационную часть вершны БД и признак использования элемента массива — 1 — если элемент содержит вершину БД, 0 — если элемент свободен. Корнем дерева является элемент массива с индексом 1, индекс левого сына вычисляется по формуле i*2, где i — индекс отца, а правый сын располагается в следующем (i*2 + 1) элементе массива. БД (см. рис.21) может быть представлено в памяти так, как показано на рис.24.
Статическая адрес ячейки, содержащей
память адрес корня дерева
----------------------------------------------------------------
адрес корня дерева
Динамическая
память
Рис.22. Представление БД в памяти
Рис.7.4
Рис.23. Представление БД в памяти
A |
B |
G |
C |
F |
|
H |
D |
E |
|
|
|
|
I |
J |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Рис.24. Представление БД в памяти
Алгоритмы обхода бинарного дерева
Пусть в памяти ЭВМ находится БД. Задача обхода БД состоит в том, чтобы вывести информационную часть каждой вершины БД. Порядок прохождения вершин определяет алгоритм обхода БД. Рассмотрим некоторые алгоритмы обхода БД.