Составители:
Рубрика:
О Г Л А В Л Е Н И Е
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.
СПИСКИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Линейный однонаправленный список . . . . . . . . . . . . . . . . . . . . . 4
Л1− список как абстрактный тип данных . . . . . . . . . . . . . . . . .
6
Ссылочная реализация Л1− списка в динамической памяти . . . . .
8
Ссылочная реализация ограниченного Л1
−
списка на базе вектора
11
Линейный двунаправленный список . . . . . . . . . . . . . . . . . . . . . 14
Рекурсивная обработка линейных списков . . . . . . . . . . . . . . . . 17
Иерархические списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.
СТЕКИ И ОЧЕРЕДИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Спецификация стека и очереди . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Реализация стека и очереди . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.
ДЕРЕВЬЯ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Определения дерева, леса, бинарного дерева. Скобочное представле-
ние . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
Спецификация дерева, леса, бинарного дерева . . . . . . . . . . . . . . . . 46
Каноническое соответствие бинарного дерева и леса . . . . . . . . . . . 47
Обходы бинарных деревьев и леса . . . . . . . . . . . . . . . . . . . . . 49
Представления и реализации бинарных деревьев . . . . . . . . . . . 55
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Примечания и библиографические указания . . . . . . . . . . . . . . . . . . . . . 66
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
68
ОГЛАВЛЕНИЕ
Введение .................................................... 3
1. СПИСКИ .............................................. 4
Линейный однонаправленный список . . . . . . . . . . . . . . . . . . . . . 4
Л1− список как абстрактный тип данных ................. 6
Ссылочная реализация Л1− списка в динамической памяти . . . . . 8
Ссылочная реализация ограниченного Л1− списка на базе вектора 11
Линейный двунаправленный список . . . . . . . . . . . . . . . . . . . . . 14
Рекурсивная обработка линейных списков . . . . . . . . . . . . . . . . 17
Иерархические списки ............................... 22
Упражнения ......................................... 32
2. СТЕКИ И ОЧЕРЕДИ .................................... 36
Спецификация стека и очереди . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Реализация стека и очереди .......................... 38
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3. ДЕРЕВЬЯ ......................................... 43
Определения дерева, леса, бинарного дерева. Скобочное представле-
ние . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Спецификация дерева, леса, бинарного дерева ................ 46
Каноническое соответствие бинарного дерева и леса . . . . . . . . . . . 47
Обходы бинарных деревьев и леса ..................... 49
Представления и реализации бинарных деревьев . . . . . . . . . . . 55
Упражнения ......................................... 63
Примечания и библиографические указания ..................... 66
Список литературы ......................................... 67
68
