- •1. Абстрагирование типов
- •1.1. Понятие типа данных
- •1.1.1. Простые типы
- •1.1.2. Абстрактные типы
- •2. Идентификация объектов
- •2.1. Именование
- •2.2. Указание
- •2.2.1. Организация адресного пространства оперативной
- •2.2.2. Понятие указателя
- •2.2.3. Действия над указателями
- •2.2.4. Связывание идентификатора объекта с его
- •3. Время жизни объекта. Классы памяти
- •3.1. Понятие “времени жизни” объекта
- •3.2. Классы памяти
- •3.2.1. Статическая память
- •3.2.2. Автоматическая память
- •3.2.3. Динамическая память
- •4. Динамические структуры данных
- •4.1. Метод вычисляемого и хранимого адреса.
- •4.2. Понятие динамической структуры данных
- •4.3. Линейные динамические структуры данных (списки)
- •4.3.1. Основные виды списков
- •4.4. Односвязные списки
- •4.4.1. Включение узла в начало списка
- •4.4.2. Создание списка из n узлов за счет добавления
- •4.4.3. Создание списка из n узлов за счет добавления
- •4.4.4. Исключение узла из начала списка
- •4.4.5. Перестановка указателя
- •4.4.6. Поиск в списке узла по заданному условию
- •4.4.7. Включение нового узла в список за тем узлом, на
- •4.4.8. Исключение из списка узла за тем узлом, на
- •4.4.9. Исключение из списка узла, на который предварительно
- •4.4.10. Разрушение списка
- •4.4.11. Программный модуль, реализующий операции
- •4.5. Односвязные циклические списки
- •4.6. Двусвязные списки
- •4.6.1. Включение нового узла в список за тем узлом, на
- •4.6.2. Исключение из списка узла, на который
- •4.7. Ортогональные списки (мультисписки)
- •4.8. Разнородные списки
- •4.9. Управление динамической памятью
- •4.9.1. Администратор кучи
- •4.9.2. Алгоритмы выделения участков памяти по запросу
- •4.9.3. Фрагментация
- •4.9.4. Накопление мусора
- •4.9.5. Висящие ссылки
- •5. Множественная интерпретация объектов
- •5.1. Совместимость типов. Приведение и преобразование типов
- •5.2. Методы совмещения типов
- •5.2.1. Запись с вариантной частью
- •5.2.2. Использование директивы absolute
- •5.2.3. Параметры без типа
- •5.2.4. Открытые массивы
- •5.2.5. Наложение масок с помощью указателей
- •6. Рекурсивные структуры данных
- •6.1. Итерация и рекурсия в программировании
- •6.1.1. Понятие рекурсии
- •6.1.2. Итеративная и рекурсивная схема организации
- •6.2. Задача о “ханойских башнях”
- •6.3. Виды рекурсивных структур данных
- •6.3.1. Арифметические выражения
- •6.3.2. Динамические линейные структуры данных: списки
- •6.3.3. Иерархические линейные структуры данных: наборы
- •6.4. Эффективность рекурсивных вычислений
- •7. ИерархическиеНелинейные структуры данных.Деревья
- •7.1. Деревья общего вида
- •7.2. Бинарные деревья
- •7.3. Представление бинарных деревьев
- •7.3.1. Представление бинарных деревьев на статической
- •7.3.2. Представление бинарных деревьев на
- •7.4. Алгоритмы обхода бинарных деревьев
- •7.5. Виды бинарных деревьев
- •7.5.1. Сбалансированные деревья
- •7.5.2. Дихотомические деревья (деревья поиска)
- •7.5.3. Деревья выражений
- •7.6. Программный модуль, реализующий операции
- •Список рекомендуемой литературы
6.4. Эффективность рекурсивных вычислений
Так как для хранения фреймов активации рекурсивной процедуры используется автоматическая память, при обработке данных нерекурсивной природы следует использовать итеративные алгоритмы, не требующие дополнительного расхода памяти, если только рекурсивные алгоритмы не оказываются более ясными и понятными. Примером алгоритма, обрабатывающего данные нерекурсивной природы, но имеющего гораздо более эффективную рекурсивную реализацию по сравнению с итеративной, яаляется алгоритм решения задачи о “ханойских башнях”. При вычислении же значения факториала натурального числа N несомненно следует предпочесть итеративную процедуру.
Если процедура содержит единственный рекурсивный вызов и он является последним действием процедуры, то говорят, что имеет место задняя рекурсия (tail recursion) (см. процедуру Print_Front). Этот рекурсивный вызов требует затрат на создание фреймов активации и запоминание их в стеке. Когда рекурсивный вычислительный процесс доходит до условия завершения, выполняется серия возвратов, выталкивающих фреймы активации из стека. Если при наличии задней рекурсии фреймы активации не используются для окончательных вычислений, следует предпочесть итеративную реализацию (см. процедуру Print из программного модуля!!! ). Рекурсивная процедура Print_Back, не содержащая задней рекурсии, имеет более эффективную реализацию, чем итеративная процедура, выполняющая те же действия.
7. ИерархическиеНелинейные структуры данных.Деревья
7.1. Деревья общего вида
Нелинейные структуры данных выражают более сложные отношения порядка между объектами, чем отношения предшествования и следования. Наиболее важным видом нелинейных структур являются деревья. Древовидные структуры позволяют определить такие отношения, как предок, потомок, брат и т.п.
Дерево– конечное множество объектов Т, состоящее из одного или более узлов, для которых выполняются следующие условия:
имеется один специально выделенный узел, называемый корнем данного дерева;
остальные узлы (исключая корень) содержатся вmпопарно непересекающихся множествах T1, …,Tm, каждое из которых в свою очередь является деревом. Деревья T1,...,Тm называются поддеревьямиданного корня. Структура дерева общего вида представлена на рис. 63.
Рис. 63. Дерево общего вида
Число поддеревьев данного корня (узла) называется степеньюэтогоузла. Максимальная степень всех узлов дерева называетсястепенью дерева, обозначимd. Узел с нулевой степенью называетсятерминальным узлом или листом.Уровень узла– выраженная в числе ребер длина пути, ведущего из узла в корень дерева плюс единица. Считается, что корень дерева находится на уровне 1. Если некоторый узел А располагается на уровнеi, то находящийся непосредственно ниже его на уровнеi+1узел В называетсянепосредственным потомкомузла А, а узел А называетсянепосредственным предкомузла В. Максимальный уровень всех узлов дерева называетсявысотой или глубиной дерева, обозначимh. Высота пустого дерева равна нулю, высота дерева, состоящего из одного корня, равна 1. Дерево, содержащее максимальное число узлов, называетсяполным. Количество узлов в полном дереве степениdвысотойh вычисляется по формуле (i – номер уровня)
Основные свойствадеревьев общего вида:
корень не имеет предков;
каждый узел, за исключением корня, имеет только одного предка;
каждый узел связан с корнем единственным путем, т.е. в деревьях отсутствуют замкнутые контуры (циклы).
Если в определении дерева имеет значение относительный порядок поддеревьев Т1,…,Тm, дерево являетсяупорядоченным. Поэтому два упорядоченных дерева на рис. 64 – это разные, отличные друг от друга объекты.
Рис. 64. Два различных дерева