- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 2007
- •1. Структуры данных и алгоритмы 6
- •1.2. Информация и ее представление
- •1.2.1. Природа информации
- •1.2.2. Хранение информации
- •1.2.3. Классификация структур данных
- •1.3. Операции над структурами данных
- •1.4. Порядок алгоритма
- •1.5. Структурность данных и технологии программирования
- •Контрольные вопросы
- •2. Простые структуры данных
- •2.1. Порядковые типы
- •2.2. Целочисленный тип
- •2.3. Символьный тип
- •2.4. Перечисляемый тип
- •2.5. Интервальный тип
- •2.6. Логический тип
- •2.7. Битовый тип
- •2.8. Вещественный тип
- •2.9. Указательный тип
- •Контрольные вопросы
- •3. Объектные типы данных
- •3.1. Объявление и реализация классов
- •Interface
- •Implementation
- •3.2. Директивы видимости
- •3.3. Свойства классов
- •3.4. Структурированная обработка ошибок
- •3.5. Применение объектов
- •Контрольные вопросы
- •4. Статические структуры данных
- •4.1. Векторы
- •4.2. Массивы
- •4.3. Множества
- •4.4. Записи
- •4.5. Таблицы
- •4.6. Операции над статическими структурами
- •4.6.1. Алгоритмы поиска
- •4.6.2. Алгоритмы сортировки
- •Самые медленные алгоритмы сортировки
- •Быстрые алгоритмы сортировки
- •Самые быстрые алгоритмы сортировки
- •Сортировка слиянием
- •Контрольные вопросы
- •5. Полустатические структуры данных
- •5.1. Стеки
- •5.1.1. Стеки в вычислительных системах
- •5.2. Очереди fifo
- •5.2.1. Очереди с приоритетами
- •5.2.2. Очереди в вычислительных системах
- •5.3. Деки
- •5.3.1. Деки в вычислительных системах
- •5.4. Строки
- •5.4.1. Операции над строками
- •5.4.2. Представление строк в памяти
- •3 A b d 8 p q r s t u V w
- •V w ptr nil
- •1 8 П р е д с т а в
- •2 7 ? Л е н и е ?
- •1 8 С т р о к и з
- •1 8 В е н ь я м и
- •1 8 С у п р а в л
- •1 8 Я е м о й д л
- •1 4 И н о й ? ? ? ? nil
- •6.2. Связные линейные списки
- •6.2.1. Машинное представление связных линейных списков
- •Inf next
- •Inf next
- •Inf nil
- •6.2.2. Реализация операций над связными линейными списками
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •6.2.3. Применение линейных списков
- •6.3. Нелинейные разветвленные списки
- •6.3.1. Основные понятия
- •6.3.2. Представление списковых структур в памяти
- •6.3.3. Операции обработки списков
- •6.4. Язык программирования lisp
- •6.5. Управление динамически выделяемой памятью
- •Контрольные вопросы
- •7. Нелинейные структуры данных
- •7.1. Графы и деревья
- •(B) (a) (b) (a)
- •V0 v1 v2 v5 v6 v3 v4 v7 v8 v9 v10 (v0) (v1) (v7) (v8) (v9) (v10) (v3) (v2) (v4) (v5) (v6)
- •7.3. Бинарные деревья
- •7.3.1. Представление бинарных деревьев
- •7.3.2. Прохождение бинарных деревьев
- •7.4. Алгоритмы на деревьях
- •7.4.1. Сортировка с прохождением бинарного дерева
- •7.4.2. Сортировка методом турнира с выбыванием
- •7.4.3. Применение бинарных деревьев для сжатия информации
- •7.4.4. Представление выражений с помощью деревьев
- •7.5. Представление сильноветвящихся деревьев
- •Контрольные вопросы
- •8. Методы ускорения доступа к данным
- •8.1. Хеширование данных
- •8.1.1. Функции хеширования
- •8.1.2. Оценка качества хеш-функции
- •8.1.3. Методы разрешения коллизий
- •8.1.4. Переполнение таблицы и рехеширование
- •8.2. Организация данных для поиска по вторичным ключам
- •8.2.1. Инвертированные индексы
- •8.2.2. Битовые карты
- •Контрольные вопросы
- •Листинги рабочих примеров
- •1. Создание и управление списковыми объектами
- •Interface
- •Implementation
- •Interface
- •Implementation
- •3. Моделирование работы стека
- •Interface
- •Implementation
- •Interface
- •Implementation
- •4. Создание и редактирование бинарных деревьев
- •5. Создание и редактирование сильноветвящихся деревьев
- •Задания для самостоятельной работы
- •Литература
- •144Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
4. Создание и редактирование бинарных деревьев
Пример демонстрирует способ создания и элементарные операции по изменению и просмотру структуры бинарного дерева.
program BinTree;
{$APPTYPE CONSOLE}
type
PNode = ^TNode;
TNode = record
Name: string;
Left, Right: Pointer;
end;
var
n: Integer;
s: string;
pnt, Current: PNode;
pnt_s, Current_s, Root: Pointer;
{ Сменить текущий узел }
procedure NodeSearch(pnt_s: Pointer; var Current_s: Pointer);
var pnt_n: PNode;
begin
pnt_n:=pnt_s;
if pnt_n^.Name <> s then
begin
if pnt_n^.Left <> nil then
NodeSearch(pnt_n^.Left,Current_s);
if pnt_n^.Right <> nil then
NodeSearch(pnt_n^.Right,Current_s);
end else
Current_s:=pnt_n;
end;
{ Вывод списка всех узлов дерева }
procedure NodeList(pnt_s: Pointer);
var pnt_n: PNode;
begin
pnt_n:=pnt_s;
WriteLn(pnt_n^.Name);
if pnt_n^.Left <> nil then
NodeList (pnt_n^.Left);
if pnt_n^.Right <> nil then
NodeList(pnt_n^.Right);
end;
{ Удаление узла и всех его потомков в дереве }
procedure NodeDispose(pnt_s: Pointer);
var pnt_n: PNode;
begin
if pnt_s <> nil then
begin
pnt_n:=pnt_s;
WriteLn(pnt_n^.Name);
if pnt_n^.Left <> nil then
NodeDispose(pnt_n^.Left);
if pnt_n^.Right <> nil then
NodeDispose(pnt_n^.Right);
Dispose(pnt_n);
end;
end;
begin
New(Current);
Root:=Current;
Current^.Name:='Root';
Current^.Left:=nil;
Current^.Right:=nil;
repeat
WriteLn('Current node - ',Current^.Name);
WriteLn('1 - Set name for left descendant');
WriteLn('2 - Set name for right descendant');
WriteLn('3 - Change current node');
WriteLn('4 - Show node list');
WriteLn('5 - Delete descendantes of current node');
WriteLn('0 - Exit');
Read(n);
{ Создание левого потомка }
if n = 1 then
begin
if Current^.Left = nil then
New(pnt) else
pnt:=Current^.Left;
WriteLn('Left name ?');
ReadLn;
Read(s);
pnt^.Name:=s;
pnt^.Left:=nil;
pnt^.Right:=nil;
Current^.Left:=pnt;
end;
{ Создание правого потомка }
if n = 2 then
begin
if Current^.Right = nil then
New(pnt) else
pnt:=Current^.Right;
WriteLn('Right name ?');
ReadLn;
Read(s);
pnt^.Name:=s;
pnt^.Left:=nil;
pnt^.Right:=nil;
Current^.Right:=pnt;
end;
{ Сменить текущий узел }
if n = 3 then
begin
WriteLn('New current node ?');
ReadLn;
Read(s);
Current_s:=nil;
NodeSearch(Root, Current_s);
if Current_s <> nil then
Current:=Current_s else
WriteLn('Node '''+s+''' not found');
end;
{ Вывод списка узлов }
if n = 4 then NodeList(Root);
{ Удаление поддерева }
if n = 5 then
begin
WriteLn('l,r ?');
ReadLn;
Read(s);
if (s = 'l') then
{ Удаление левого поддерева }
begin
pnt_s:=Current^.Left;
Current^.Left:=nil;
NodeDispose(pnt_s);
en d else
{ Удаление правого поддерева }
begin
pnt_s:=Current^.Right;
Current^.Right:=nil;
NodeDispose(pnt_s);
end;
end;
until n = 0
end.
5. Создание и редактирование сильноветвящихся деревьев
Пример сильноветвящихся деревьев для чтения структуры заданного каталога или диска, навигации и подсчета места, занимаемого каталогом. Операции по просмотру содержимого каталогов и подсчету занимаемого объема производятся не с физическими каталогами и файлами, а с созданным динамическим списковым представлением их логической структуры в виде сильноветвящегося дерева. В примере для каждого файла или каталога хранится его полное имя.
Для чтения оглавления диска используются стандартные функции FindFirst() и FindNext(), которые возвращают сведения о первом и последующих элементах в оглавлении текущего каталога. В процессе чтения корневого каталога строится первый уровень потомков в списковой структуре дерева. Процедура построения поддерева вызывается для каждого узла в корневом каталоге. Процесс повторяется для всех непустых каталогов до тех пор, пока не будет построена полная структура оглавления.
program dirtree;
{$APPTYPE CONSOLE}
uses SysUtils;
type
TNode = record
name: string[50]; { Имя каталога/файла }
size: LongInt; { Размер файла (байт) }
node_type: Char; { Тип узла (файл - 'f' / каталог-'c') }
up, down: Pointer; { Указатели на предка и список потомков }
last, next: Pointer; { Указатели на соседние узлы }
end;
var
n, i, l, error: Integer;
current_root: Pointer;
pnt, current: ^TNode;
str: string;
{ Отображение физического оглавления диска в логическую структуру }
procedure CreateTree(local_root:Pointer);
var s: TSearchRec; local_node, local_r_node, local_last: ^TNode;
{ Создание нового узла в дереве каталогов и файлов }
procedure NewNode;
begin
New(local_node);
local_node^.last:=local_last;
if local_last <> nil then
local_last^.next:=local_node;
local_node^.next:=nil;
local_node^.down:=nil;
local_node^.up:=local_r_node;
if local_r_node^.down = nil then
local_r_node^.down:=local_node;
local_node^.name:=local_r_node^.name+'\'+s.name;
if faDirectory = 0 then
local_node^.node_type:='f' else
local_node^.node_type:='c';
local_node^.size:=s.size;
local_last:=local_node;
end;
{ Собственно процедура }
begin
local_r_node:=local_root;
local_last:=nil;
error:=FindFirst(local_r_node^.name+'\*.*',faAnyFile,s);
if error = 0 then
begin
if (s.name<>'.') and (s.name<>'..') then NewNode;
while error = 0 do
begin
error:=FindNext(s);
if (error = 0) and (s.name<>'.') and (s.name<>'..') then NewNode;
end;
end;
if local_r_node^.down <> nil then
begin
local_node:=local_r_node^.down;
repeat
{ Рекурсивный вызов }
if local_node^.node_type = 'c' then CreateTree(local_node);
local_node:=local_node^.next
until local_node = nil;
end;
end;
{ Вывод оглавления текущего каталога }
procedure CurrentList;
begin
current:=current_root;
WriteLn('Current directory - ', current^.name);
if current^.node_type = 'c' then
begin
pnt:=current^.down;
i:=1;
{ Проходим каталог в дереве }
repeat
WriteLn(i:4,'-',pnt^.name);
pnt:=pnt^.next;
Inc(i);
until pnt = nil;
end;
end;
{ Навигация в дереве каталогов. Перемещение на один уровень вниз }
procedure MoveDown;
begin
current:=current_root;
if current^.down <> nil then
begin
current:=current^.down;
WriteLn('Id in list');
Read(l);
i:=1;
while (i < l) and (current^.next <> nil) do
begin
current:=current^.next;
Inc(i);
end;
if (current^.node_type = 'c') and (current^.down <> nil)
then current_root:= current;
end;
end;
{ Навигация в дереве каталогов. Перемещение на один уровень вверх }
procedure MoveUp;
begin
current:=current_root;
if current^.up <> nil then
current_root:=current^.up;
end;
{ Подсчет числа файлов и подкаталогов иерархической структуры каталога }
procedure Count;
var n_files, n_cats: Integer;
procedure count_in(local_root: Pointer);
var local_node, local_r_node: ^TNode;
begin
local_r_node:=local_root;
if local_r_node^.down <> nil then
begin
local_node:=local_r_node^.down;
repeat
if local_node^.node_type = 'f' then
Inc(n_files) else
begin
Inc(n_cats);
count_in(local_node);
end;
local_node:=local_node^.next
until local_node = nil;
end;
end;
{ Собственно процедура }
begin
n_files:=0; n_cats:=0;
count_in(current_root);
WriteLn('files : ',n_files, ' directories: ', n_cats);
end;
{ Расчет физического объема иерархической структуры каталога }
procedure CountMem;
var mem: LongInt;
procedure count_m_in(local_root: Pointer);
var local_node, local_r_node: ^TNode;
begin
local_r_node:=local_root;
if local_r_node^.down <> nil then
begin
local_node:=local_r_node^.down;
repeat
if local_node^.node_type = 'f' then
mem:=mem+local_node^.size else
count_m_in(local_node);
local_node:=local_node^.next;
until local_node = nil;
end;
end;
{ Собственно процедура }
begin
mem:=0;
count_m_in(current_root);
WriteLn('mem ', mem, ' bytes');
end;
begin
New(current);
{ Инициализация корня дерева каталогов и указателей для навигации }
current_root:=current;
WriteLn('Directory ?');
Read(str);
WriteLn(str);
current^.name:=str;
current^.last:=nil;
current^.next:=nil;
current^.up:=nil;
current^.down:=nil;
current^.node_type:='c';
{ Создание дерева каталогов }
CreateTree(current);
if current^.down = nil then
current^.node_type:=' ';
repeat
WriteLn('1-List');
WriteLn('2-Down');
WriteLn('3-Up');
WriteLn('4-Files');
WriteLn('5-Volume');
Readln(n);
if n = 1 then CurrentList;
if n = 2 then MoveDown;
if n = 3 then MoveUp;
if n = 4 then Count;
if n = 5 then CountMem;
until n = 0;
end.