- •1.1.2 Классификация структур данных
- •1.1.3 Обозначения и договоренности
- •1.1.4 Множества.
- •1.1.5 Прямоугольные структуры. Массивы
- •Лекция 2
- •2.1 Прямоугольные структуры. Таблицы
- •2.2 Реализация с использованием параллельных массивов (статическое представление таблицы)
- •2.3 Реализация операций для неупорядоченной таблицы с использованием статической памяти
- •2.4 Динамическая память. Куча
- •2.5 Операции над указателями
- •2.6 Геометрическая интерпретация
- •2.7 Динамическая цепочка
- •2.8 Реализация операций для неупорядоченной таблицы с использованием динамической памяти
- •3.2 Обратная польская (постфиксная) запись
- •Лекция 4
- •4.1 Списковые структуры. Линейный список
- •Атом есть линейный список (атомарный);
- •Атом есть линейный список (атомарный);
- •4.2 Об операции "расчленение"
- •4.3 Логическое описание линейного списка.
- •4.4 Вычисление значения арифметического выражения
- •Лекция 5
- •5.1 Деревья
- •5.2 Бинарные деревья
- •5.5 Дерево двоичного поиска
- •7.2 Инструментальные средства. Архивация файлов (пока без сжатия)
- •7.3 Программы хранения и обработки информации
- •7.4 Код Цезаря
- •7.5 Упаковка текста
- •7.6 Код Хаффмана
- •7.7 Код Хемминга
- •7.8 Вектор Айлиффа
- •Вектор Айлиффа
- •Лекция 8
- •8.1 Сортировка – перестановка элементов линейной структуры
- •8.2 Алгоритмы сортировки Три класса алгоритмов сортировки (включением, выбором, обменом)
- •8.2.1 Сортировка простым включением.
- •9.2 Источники погрешностей
- •9.3 Классификация погрешностей
- •9.4 Терминология
- •FoRmula traNslation (станд.66, станд.77(*))
- •10.0 Бланк для записи текста программы на Фортране
- •10.1 Элементы языка
- •10.2 Типы данных и операции
- •10.3 Описание переменных и констант
- •10.4 Арифметические операции
- •11.3 Операторы присваивания
- •11.4 Оператор continue
- •11.5 Оператор безусловной передачи управления
- •11.6 Вычисляемый оператор передачи управления
- •11.7 Оператор передачи управления по предписанию
- •11.8 Арифметический оператор условной передачи управления
- •11.9 Логический оператор условной передачи управления
- •11.10 Структурный оператор условной передачи управления*
- •11.11 Оператор цикла с параметром
- •Лекция 12
- •12.1 Реализация стандартных структур
- •12.2 Операции ввода/вывода
- •12.3 Операторы ввода/вывода
- •12.4 Оператор формата (format)
- •12.5 Логическая запись
- •12.6 Взаимодействие операторов в/в и оператора format.
- •Расширенная форма оператора read
- •12.7 Управляющие символы при печати
- •12.8 Представление целого и действительного в памяти.
- •12.9 Оператор data
- •12.10 Сравнение текстовых данных
- •12.11 Функции для данных типа character
- •Лекция 13
- •13.1 Программные единицы
- •13.2 Библиотечные и встроенные функции
- •13.3 Оператор-функция
- •Правило соответствия: Списки формальных и фактических параметров согласованы по количеству, типу и порядку следования. Пример
- •13.4 Подпрограмма-функция
- •13.5 Подпрограмма-процедура
- •О соответствии фактических и формальных параметров
- •13.6 Операторы external и intrinsic
- •Пример (параметр-переменная и параметр-значение)
- •14.3 Операторы ввода и вывода.
- •14.4 Параметры операторов ввода и вывода
- •Открытие (присоединение) файла.
- •14.5 Операторы open и close
- •14.6 Оператор read
- •14.7 Оператор write
- •14.8 Другие операторы
Лекция 5
5.1 Деревья
Дерево – структура данных, позволяющая смоделировать иерархические отношения. У каждого элемента этой структуры имеется свой единственный «непосредственный начальник» и некоторое количество «подчиненных». Примерами древовидной структуры могут служить подчиненность служащих в армии, структура бюрократического управления производством, почтовый адрес, организация хранения данных в файловой подсистеме системы Windows, и другие.
Термины: корень, узлы, листы, ветки, поддерево, пень, предок, потомок, братья, уровень, высота.
Определение (рекурсивное):
Dn – n-арное дерево (n>=2), Dno – непустое n-арное дерево.
Dn = (либо пусто, либо Dno);
Dno = (i:инф; n штук Dn)
n=2 - бинарное дерево.
5.2 Бинарные деревья
D = (либо пусто, либо Dо);
Dо = (i:инф; лев:D; прав:D).
Операции:
Создать (Создается пустое дерево)
Пусто? (Функция логического типа, истина, если дерево пусто, ложь в противном случае)
Корень? (Функция логического типа, истина, если дерево состоит лишь из корня. Такое дерево можно назвать «пнем»)
Корень (Процедура выделяет из дерева корень, левое и правое поддеревья как самостоятельные деревья)
Левое поддерево (Процедура выделяет из дерева левое поддерево, корень, и правое поддерево как самостоятельные деревья)
Правое поддерево (Процедура выделяет из дерева правое поддерево, корень и левое поддерево как самостоятельные деревья)
Конструирование (Из «пня» и двух деревьев конструируется дерево. Это операция, обратная к предыдущим трем)
Обходы (6 штук! Их названия – ЛКП, ЛПК, ПКЛ, ПЛК, КЛП, КПЛ зависят от порядка обхода)
Пример. Правильное арифметическое выражение (((a+b)*c)/(c+d)).
Представим в виде бинарного дерева
Обходы:
ЛКП – (((a+b)*c)/(c+d)) – исходное выражение.
ЛПК – ab+c*cd+/ – обратная польская запись.
Логическое описание двоичного дерева
pTree=^Tree; Tree=record Корень:Inf; Лев,Прав:pTree end;
Корень |
|
Лев |
Прав |
Арифметическое выражение как линейный список p погрузить в двоичное дерево
Голова(p) – функция с побочным эффектом
(Голова указывает на голову, p на хвост).
Функция Погрузить(р:pElem):pTree;
если атом?(р) то создается пень q,
иначе
q:=Конструирование(Погрузить(Голова(р)), Погрузить(Голова(р)), Погрузить(Голова(р)));
Погрузить=q
5.3 Реализация операций
Конструирование(р1:pTree; i:Inf; p2:pTree):pTree
Var p:pTree;
begin
NEW(p);
p^.Корень:=i;
p^.Лев:=p1;
p^.Прав:=p2;
Конструирование:=p
end
Теперь можно реализовать функцию Погрузить
ЛКП(р)
если р<>NIL то ЛКП(р^.Лев), TRT(p^.Корень), ЛКП(р^.Прав)
(TRT(i:Inf) - процедура обработки данного типа Inf, например печать)
5.4 Программа
ПАВ (строка символов) => LS => Линейный список
ПАВ (строка символов) => Задача! => Двоичное дерево
Линейный список => Погрузить => Двоичное дерево
Линейный список => Val => Значение выражения (число!)
Двоичное дерево => ЛПК => Обратная польская запись
Обратная польская запись => Стек => Значение выражения (число!)
program from_list_and_tree_to_list;
uses crt;
type
pList=^List;
List=record
next:pList;
case R:0..1 of
0: (level:pList);
1: (atom:char);
end;
pTree=^Tree;
Tree=record
root:char;
left:pTree;
right:pTree;
end;
var p:pList; q:pTree;
procedure Input_to_List(var p:pList);
var c:char;
begin
if not eoln then
begin
read(c);
case c of
'(': begin
new(p); p^.R:=0;
Input_to_List(p^.level);
Input_to_List(p^.next);
end;
'a'..'z','+','-','*','/': begin
new(p); p^.R:=1;
p^.atom:=c;
Input_to_List(p^.next);
end;
')': p:=nil
end
end else p:=nil
end;
procedure Print_of_List(p:pList);
var q:pList;
begin
if p<>nil then
begin
if p^.R=1 then write(p^.atom)
else
begin
write('(');
q:=p^.level;
while q<>nil do
begin
Print_of_List(q);
q:=q^.next
end;
write(')');
end
end
end;
function CutHead(var p:pList):pList;
var q:pList;
begin
q:=p^.level;
p^.level:=q^.next;
q^.next:=nil;
CutHead:=q
end;
function List_to_Tree(p:pList):pTree;
var q:pTree;
begin
new(q);
if p^.R=1 then
begin
q^.root:=p^.atom;
q^.left:=nil;
q^.right:=nil
end else
begin
q^.left:=List_to_Tree(CutHead(p));
q^.root:=CutHead(p)^.atom;
q^.right:=List_to_Tree(CutHead(p));
end;
List_to_Tree:=q
end;
procedure Print_of_Tree(p:pTree);
begin
if p<>nil then
begin
if (p^.left<>nil)and(p^.right<>nil)then write('(');
Print_of_Tree(p^.left);
write(p^.root);
Print_of_Tree(p^.right);
if (p^.left<>nil)and(p^.right<>nil)then write(')');
end;
end;
Procedure AddHead(var p:pList; q:pList);
begin
q^.next:=p^.level;
p^.level:=q
end;
function Tree_to_List(p:pTree):pList;
var ps:pList; pright,pleft,proot:pTree;
begin
new(ps);
ps^.next:=nil;
if (p^.left=nil) and (p^.right=nil) then
begin
ps^.R:=1;
ps^.atom:=p^.root;
dispose(p)
end else
begin
ps^.R:=0;
ps^.level:=nil;
{Расчленение p на pleft, pright, proot}
pright:=p^.right;
pleft:=p^.left;
p^.right:=nil;
p^.left:=nil;
proot:=p;
AddHead(ps,Tree_to_List(pright));
AddHead(ps,Tree_to_List(proot));
AddHead(ps,Tree_to_List(pleft));
end;
Tree_to_List:=ps
end;
begin
ClrScr;
Input_to_List(p);
Print_of_List(p);
writeln;
q:=List_to_Tree(p);
print_of_Tree(q);
writeln;
p:=Tree_to_List(q);
Print_of_List(p);
writeln;
repeat until keypressed
end.