- •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. Программный модуль, реализующий операции
- •Список рекомендуемой литературы
7.5.3. Деревья выражений
Дерево выражений– бинарное дерево, в корневых узлах которого хранятся признаки операций, а в терминальных узлах – операнды выражения (переменные или константы). Дерево выражений представлено на рис. 73.
Рис. 73. Дерево выражений
Различные алгоритмы обхода дерева выражений соответствуют различной структуре представления выражения в виде строки.
Нисходящему обходу соответствует префиксная формапредставления, т. к. в ней знак операции предшествует операнду:
* + А 10. / B 5.2 .
Восходящему обходу соответствует постфиксная форма представления, т. к. в ней знак операции находится после операндов:
A 10. + B 5.2 / * .
Смешанному обходу соответствует инфиксная форма представления, т. к. в ней знак операции находится между операндами:
А + 10. * В / 5.2 .
Для того чтобы задать приоритеты операций, используется абсолютно скобочная форма, в которой каждое подвыражение заключается в круглые скобки:
( ( A + 10. ) * ( B / 5.2)).
На рис. 74 приведено дерево, смешанный обход которого позволяет получить бесскобочную инфиксную форму, эквивалентную дереву рис. 73, а скобочная инфиксная форма задает совсем другие приоритеты операций. Заметим, что подобная проблема не может возникнуть при использовании префиксной или постфиксной формы представления выражения.
(А + ( 10. * ( В / 5.2 ) ) )
Рис. . Дерево выражений
Какой алгоритм обхода необходимо использовать для того, чтобы подсчитать значение арифметического выражения, представленного в виде дерева?
7.6. Программный модуль, реализующий операции
создания, обработки, просмотра содержимого
бинарного дерева (на примере сбалансированного дерева)
Uses Crt; |
| ||||||||
|
| ||||||||
Type |
| ||||||||
PTree = ^ Tree; |
{ тип – указатель на узел сбалансированного дерева } | ||||||||
Tree = record |
{ тип – элемент хранения узла сбалансированного дерева } | ||||||||
info: word; |
| ||||||||
left, right: PTree |
| ||||||||
end; |
| ||||||||
|
| ||||||||
var f: PTree; cod,n: byte; sum: word; |
| ||||||||
|
| ||||||||
Procedure Balance( var root: PTree; |
{ root – указатель на корень дерева, } | ||||||||
n: byte ); |
{ n – количество узлов в дереве } | ||||||||
begin |
| ||||||||
if n = 0 then root:=nil |
{ если n = 0, построить пустое дерево } | ||||||||
else begin |
| ||||||||
new( root ); |
{ создать корень дерева } | ||||||||
write( ‘Значение информационного поля узла дерева = ‘ ); |
| ||||||||
readln( root^.info ); |
{ заполнить информационное поле корня } | ||||||||
Balance( root^.left, n div 2); |
{ построить левое поддерево} | ||||||||
Balance( root^.right, n – n div 2 – 1) |
{ построить правое поддерево } | ||||||||
end |
| ||||||||
end; |
| ||||||||
|
| ||||||||
Procedure Print( root: PTree ); |
{ просмотр информац. полей узлов дерева - } | ||||||||
begin |
{ нисходящий обход } | ||||||||
if root <> nil then begin |
| ||||||||
writeln( ‘Информационное поле узла дерева = ‘, root^.info ); |
| ||||||||
Print( root^.left ); |
{ просмотреть левое поддерево } | ||||||||
Print( root^.right ); |
{ просмотреть правое поддерево } | ||||||||
end; |
| ||||||||
end; |
| ||||||||
|
| ||||||||
Procedure Work( root: PTree; var s: word ); |
{ суммирование значений информ. } | ||||||||
begin |
{ полей узлов дерева – смешанный обход } | ||||||||
if root <> nil then begin |
| ||||||||
Work( root^.left ); |
{ обработать левое поддерево } | ||||||||
s:=s + root^.info; |
{ суммирование значений инф. полей узлов } | ||||||||
Work( root^.right ); |
{ обработать правое поддерево } | ||||||||
end; |
| ||||||||
end; |
| ||||||||
|
| ||||||||
Procedure Destroy( var root: PTree ); |
{ разрушение дерева } | ||||||||
begin |
| ||||||||
. . . |
| ||||||||
end; |
| ||||||||
|
| ||||||||
Procedure Message; |
{ вспомогательная процедура } | ||||||||
begin |
| ||||||||
writeln( ‘Дерево пусто‘ ); write( ‘Нажмите любую клавишу‘ ); readkey |
| ||||||||
end; |
| ||||||||
|
| ||||||||
begin |
| ||||||||
f:=nil; |
{ первоначально дерево пусто } | ||||||||
repeat Clrscr; |
| ||||||||
writeln(‘1-Создание 2-Просмотр 3–Обработка 4–Разрушение 5-Выход‘ ); |
| ||||||||
write( ‘Код действия = ‘ ); readln( cod ); |
| ||||||||
case cod of |
| ||||||||
1: begin |
{ создание сбалансированного дерева } | ||||||||
write( ‘Количество узлов в дереве = ‘ ); readln( n ); |
| ||||||||
Balance( f,n ); write( ‘Нажмите любую клавишу‘ ); readkey |
| ||||||||
end; |
| ||||||||
2: begin |
{ просмотр дерева } | ||||||||
if f=nil then Message |
| ||||||||
else begin |
| ||||||||
Print( f ); write( ‘Нажмите любую клавишу‘ ); readkey |
| ||||||||
end; |
| ||||||||
3: begin |
{ обработка дерева } | ||||||||
if f=nil then Message |
| ||||||||
else begin |
| ||||||||
sum:=0; |
{ инициализация значения глобальной переменной } | ||||||||
Work( f,sum ); writeln( ‘Сумма значений инф. полей = ‘, sum ); |
| ||||||||
write( ‘Нажмите любую клавишу‘ ); readkey |
| ||||||||
end; |
| ||||||||
4: begin |
{ разрушение дерева } | ||||||||
if f=nil then Message |
| ||||||||
else begin |
| ||||||||
Destroy( f ); writeln( ‘Дерево разрушено‘ ); |
| ||||||||
write( ‘Нажмите любую клавишу‘ ); readkey |
| ||||||||
end; |
| ||||||||
5: Destroy( f ) |
{ выход } | ||||||||
end; |
| ||||||||
until ( cod = 5 ); Clrscr |
| ||||||||
end. |
|