Лабораторная работа №1. Указатели и связные списки
Указатель – это переменная, в которой хранится адрес другой переменной. Иными словами, это переменная, указывающая на место в памяти, в котором хранится значение другой переменной.
С помощью указателей программист может создавать связные списки и более сложные структуры данных и выделять для них память динамически, т. е. при выполнении программы. Используя указатели, можно легко добавлять или удалять данные из любой части структуры данных.
Связный список – это структура данных в виде списка, элементы которой связаны друг с другом с помощью указателей.
В Object Pascal указатели используются в любом типе данных, требующем динамического выделения больших блоков памяти. Например, длинные строки и объекты классов являются неявными указателями. Указатели всегда неявно присутствуют как бы «за кадром» исходного кода, даже если явно их в коде нет. Понимание указателей и операций с указателями необходимо для работы с Object Pascal. Более того: во многих приемах программирования указатели используются явно.
Использование указателей позволяет экономнее расходовать память, потому что с их помощью память для переменных можно выделять динамически. Однако динамическое выделение памяти в то же время является и недостатком использования указателей. Программист должен постоянно помнить о необходимости удаления неиспользуемых динамических объектов, иначе в программе произойдет утечка памяти. Интенсивная утечка памяти может вызвать крах программы, причем обнаружить источник утечки довольно трудно.
В Object Pascal символ «крышечка» (^) используется как для обозначения указателя, так и для его разадресации. Синтаксис определения типа указателя имеет вид
type
имя_типа_указателя = ^тип;
Например, оператор
type
IntPointer = ^Integer;
определяет тип указателя IntPointer. Переменная этого типа является указателем на целое значение, т. е. переменная типа IntPoiner содержит адрес ячейки памяти, в которой хранится значение типа Integer.
Если определен тип указателя, то можно объявить указатель этого типа. Например, оператор
intptr:IntPointer;
объявляет указатель intPtr типа IntPointer.
Если символ ^ расположен после указательной переменной, то он разадресует указатель, т. е. выражение возвращает значение, хранящееся по адресу, хранящемуся в указателе. Таким образом, выражение
имя_указателя^
разадресует указатель. Например, если переменная intptr имеет тип IntPointer, то выражение intptr^ возвращает целое значение.
В Object Pascal есть зарезервированное ключевое слово nil, обозначающее специальную константу, значение которой можно присвоить любой указательной переменной. Если указателю присвоено значение nil, то это означает, что указатель не ссылается ни на какой объект. Поэтому рекомендуется всегда инициализировать указатели значением nil.
Для создания и уничтожения динамических переменных в Object Pascal используются встроенные процедуры New() и Dispose(). Процедура New() выделяет память для новой динамической переменной и присваивает указателю значение адреса выделенной области памяти. Когда созданная процедурой New() динамическая переменная больше не нужна, ее следует удалить с помощью процедуры Dispose(), т. е. освободить память, выделенную для этой переменной. Синтаксис процедур New() и Dispose() имеет вид
New(имя_указателя);
Dispose(имя_указателя);
После вызова процедуры Dispose() значение указателя становится неопределенным.
Внутри записей указатели используются для создания связных списков и других сложных структур данных. Например, приведенный ниже фрагмент кода создает, выводит на экран и уничтожает связный список целых значений от 1 до 10.
type
IntPointer = ^IntRecord;
IntRecord = record
value: Integer;
next: IntPointer;
end;
var
top, temp: IntPointer;
count: Integer;
begin
New(top);
temp := top;
{Создание связного списка}
for count := 1 to 10 do begin
temp^.value := count;
if (count < 10) then begin
New(temp^.next);
temp := temp^.next;
end
else begin
temp^.next := nil;
end;
end;
{Вывод}
temp := top;
while (temp <> nil) do begin
Writeln(temp^.value);
temp := temp^.next;
if (temp <> nil) then begin
writeln('');
writeln('|');
writeln('V');
writeln('');
end;
end;
{Уничтожение}
while (top <> nil) do begin
temp := top;
top := top^.next;
Dispose(temp);
end;
readln;
end.
В следующем примере указатели используются для создания связного списка имен. Программа LinkedList содержит процедуры инициализации списка, добавления в список узлов, удаления узлов из списка, вывода содержимого списка на экран и уничтожения списка. Обратите внимание: цикл while в процедуре Remove() содержит булево выражение, требующее режима неполного вычисления, так как при list, равном nil, объекта list^.name не существует.
program LinkedList;
{$APPTYPE CONSOLE}
uses
SysUtils;
type
NameType = String[20];
ListPointer = ^ListType;
ListType = record
name: NameType;
next: ListPointer;
end;
{Инициализация связного списка}
procedure InitializeList(var top: ListPointer);
begin
top := nil;
end;
{Добавление в связный список узла, содержащего имя}
procedure Add(var top: ListPointer; name: NameType);
var
list: ListPointer;
begin
if (top = nil) then begin
New(top);
list := top;
end
else begin
list := top;
while (list^.next <> nil) do begin
list := list^.next;
end;
New(list^.next);
list := list^.next;
end;
list^.name := name;
list^.next := nil;
end;
{Удаления из связного списка узла, содержащего имя}
procedure Remove(var top: ListPointer; name: NameType);
var
list, prev: ListPointer;
begin
list := top;
prev := list;
while (list <> nil) and (list^.name <> name) do begin
prev := list;
list := list^.next;
end;
if (list <> nil) then begin
if (prev = list) then begin {Удаление первого узла}
prev := prev^.next;
top := prev;
end
else begin {Удаление второго, или}
prev^.next := list^.next; {последующео узла}
end;
Dispose(list);
end;
end;
{Вывод связного списка}
procedure DisplayList(top: ListPointer);
var
lineOut: String;
begin
lineOut := '';
while (top <> nil) do begin
lineOut := lineOut + top^.name;
top := top^.next;
if (top <> nil) then begin
lineOut := lineOut + ' --> ';
end;
end;
frmLinkedList. memOutput. Lines. Add(lineOut);
end;
{Уничтожение связного списка}
procedure DestroyList(var top: ListPointer);
var
temp: ListPointer;
begin
while (top <> nil) do begin
temp := top;
top := top^.next;
Dispose(temp);
end;
end;
var
list: ListPointer;
begin
InitializeList(list);
Add(list, 'Jack');
Add(list, 'Bill');
Add(list, 'Tom');
Add(list, 'Harry');
DisplayList(list);
Remove(list, 'Jack');
DisplayList(list);
Remove(list, 'Harry');
DisplayList(list);
Add(list, 'Sally');
DisplayList(list);
Remove(list, 'Tom');
DisplayList(list);
Add(list, 'Lucy');
DisplayList(list);
DestroyList(list);
readln;
end.
Операции с указателями и указатель pointer
Для указателей определены только операции присваивания и проверки на равенство и неравенство. В Object Pascal запрещается любые арифметические операции с указателями, их ввод-вывод и сравнение на больше-меньше.
Нетипизированный указатель не связан с каким-либо конкретным типом данных. Для нетипизированного указателя служит зарезервированное слово Pointer. Нетипизированные указатели используют в тех случаях, когда в процессе работы программы тип и структура данных изменяются. Для работы с не типизированными указателями существуют следующие процедуры:
Процедура GetMem(P,Size), где P – переменная-указатель, Size – размер выделяемой памяти в байтах, позволяет выделить в динамической памяти область размера Size, при этом адрес выделенной области присваивается переменной P.
Процедура FreeMem(P,Size), где P – переменная-указатель, Size – размер памяти в байтах, освобождает область в памяти, адрес которой задается указателем P, а размер равен Size
Указателям можно присваивать значения друг друга, если они указывают на один и тот же тип. Нетипизированные указатели являются исключением из этого правила - они совместимы с любыми типизированными указателями. Для того чтобы записать значение по адресу, на который ссылается нетипизированный указатель необходимо использовать операции приведения типа.
В Object Pascal определены стандартные функции для работы с указателями:
– add(x):pointer – возвращает адрес x (аналогично операции @).
– ptr(x):pointer – по заданному сегменту и смещению формирует адрес типа poiner.
– seg(x):word – возвращает адрес сегмента для x.
– ofs(x):word – возвращает смещение для x.
При работе с динамической памятью часто применяются вспомогательные функции:
– Maxavail:longint – возвращает длину в байтах самого длинного свободного участка динамической памяти.
– Memavail:longint – возвращает полный объем свободной динамической памяти в байтах.
– Sizeof(x):word – возвращает объем в байтах, занимаемый х.
Списки, стеки, очереди и очереди с двухсторонним доступом
Список – это упорядоченный набор данных. Первый узел списка называется называется головой, а последний – хвостом. Списки, стеки, очереди и очереди с двухсторонним доступом представляют собой специальные виды списков, добавление и удаление данных из которых регулируется определенными правилами. Реализация этих структур на основе статических массивов работает удовлетворительно только при относительно небольшом объеме данных. Динамические массивы более гибкие, с их помощью можно обрабатывать данные произвольного объема. Указатели позволяют создавать наиболее быстродействующие коды на основе оптимальных решений. Обычно указатели используются для обработки особенно больших объемов данных, однако при этом программисту приходится брать на себя дополнительную задачу управления памятью.
Наглядно стек можно представить себе как стопку тарелок, стоящих на столе. Когда рабочий в кафе моет посуду, он ставит каждую вымытую тарелку на самый верх стопки чистых тарелок. Когда в кафе заходит клиент, чистая тарелка для него снимается с верха стопки. Таким образом, последняя тарелка, поставленная в стопку, оказывается первой, извлеченной из стопки. Говорят, что стек работает по принципу LIFO (last-in first-out, т. е. последним зашел – первым вышел).
Процессы добавления и чтения данных из стека называются занесением в стек и извлечением из стека (иногда используются термины «заталкивание в стек» и «выталкивание из стека»). Механизм работы стека напоминает магазин автомата, в который солдат заталкивает один патрон за другим. Во время стрельбы механизм автомата извлекает патроны тоже один за другим. Когда очередной патрон извлечен, на его место немедленно подается новый.
В компьютерном программировании используются термины вершина и дно стека. Вершиной стека является элемент данных, подлежащий извлечению. Между магазином автомата и стеком есть существенное отличие. В магазине автомата двигаются патроны, а в стеке элементы данных остаются неподвижными (данные не переписываются из ячейки в ячейку), вместо этого передвигается указатель на вершину стека, т. е. изменяется значение указателя. С этой точки зрения стек больше похож все же на стопку тарелок. Продемонстрируем работу стека с помощью следующего примера. Код программы StackEx реализует стек целых чисел на основе статического массива. Указателем на вершину стека является переменная topOf Stack. Как видно из программы, при инициализации указателю стека присваивается значение nil, т. е. если значение указателя равно nil, значит, стек пуст.
Для занесения и извлечения данных из стека предназначены процедуры Pop() и Push(). Статический массив стека stack типа stackType и относящиеся к нему переменные имеют глобальную область видимости.
program StackEx;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
STACKSIZE = 50; {Максимальный размер стека}
type
StackType = array[1..STACKSIZE] of Integer; {Тип стека целых чисел}
var
stack: StackType;
topOfStack: Integer;
function Rus(mes: string):string;
// В ANSI русские буквы кодируются числами от 192 до 255,
// в ASCII - от 128 до 175 (А..Я, а..п) и от 224 до 239 (р..я)
var
i: integer; // номер обрабатываемого символа
begin
for i:=1 to length(mes) do
case mes[i] of
'А'..'п' : mes[i] := Chr(Ord(mes[i]) - 64);
'р'..'я' : mes[i] := Chr(Ord(mes [i]) - 16);
end;
rus := mes;
end;
{Инициализация стека}
procedure Initialize;
begin
topOfStack := 0;
end;
{Функция IsEmpty возвращает True, если стек пуст}
function IsEmpty: Boolean;
begin
IsEmpty := (topOfStack = 0);
end;
{Функция IsFull возвращает True, если стек заполнен}
function IsFull: Boolean;
begin
IsFull := (topOfStack = STACKSIZE);
end;
{Извлечение целого числа с вершины стека}
procedure Pop(var value: Integer);
begin
if IsEmpty then begin
writeln(rus('Недопустимая операция извлечения -- стек пуст!'));
end
else begin
value := stack[topOfStack];
Dec(topOfStack);
end;
end;
{Занесение целого числа в стек}
procedure Push(value: Integer);
begin
if IsFull then begin
writeln(rus('Недопустимая операция занесения -- стек заполнен!'));
end
else begin
Inc(topOfStack);
stack[topOfStack] := value;
end;
end;
{Тестирование стека}
var
value, count: Integer;
begin
Initialize;
for count := 1 to 10 do begin
Push(count);
Writeln(rus('Занесено: ') + IntToStr(count));
end;
for count := 1 to 5 do begin
Pop(value);
Writeln(rus('Извлечено: ') + IntToStr(value));
end;
for count := 30 to 33 do begin
Push(count);
Writeln(rus('Занесено: ') + IntToStr(count));
end;
for count := 1 to 9 do begin
Pop(value);
Writeln(rus('Извлечено: ') + IntToStr(value));
end;
readln;
end.
Принцип действия очереди противоположен принципу действия стека. Стек похож на стопку тарелок, стоящую на столе, в то время как очередь напоминает живую очередь клиентов кафе. Первый клиент в очереди всегда обслуживается первым. Таким образом, очередь работает по принципу FIFO (fist-in fist-out, первым вошел – первым вышел). Когда данные добавляются в конец очереди, говорят, что они ставятся очередь. Термины «добавление» или «занесение в очередь» – синонимы термин «постановка в очередь». В программировании используются также термины начало и конец очереди. В начале очереди находится элемент данных, предназначенный для извлечения из очереди на следующем шаге.
В программе Queue реализована очередь целых чисел на основе динамического массива. Процедуры Enqueue() и Dequeue() используются для постановки чисел в очередь и извлечения из очереди. Используемая в модуле QueueEx методика реализации очереди широко применяется в реальных задачах компьютерного моделирования, требующих высокого быстродействия программы.
program Queue;
{$APPTYPE CONSOLE}
uses
SysUtils;
function Rus(mes: string):string;
// В ANSI русские буквы кодируются числами от 192 до 255,
// в ASCII - от 128 до 175 (А..Я, а..п) и от 224 до 239 (р..я)
var
i: integer; // номер обрабатываемого символа
begin
for i:=1 to length(mes) do
case mes[i] of
'А'..'п' : mes[i] := Chr(Ord(mes[i]) - 64);
'р'..'я' : mes[i] := Chr(Ord(mes [i]) - 16);
end;
rus := mes;
end;
type
QueueType = array of Integer; {Тип очереди целых чисел}
var
queue: QueueType;
{Инициализация очереди}
procedure Initialize;
begin
SetLength(queue, 0);
end;
{Функция IsEmpty возвращает True, если очередь пустая}
function IsEmpty: Boolean;
begin
IsEmpty := (Length(queue) = 0);
end;
{Извлечение целого числа из начала очереди}
procedure Dequeue(var value: Integer);
var
count: Integer;
begin
if IsEmpty then begin
value := 0;
Writeln(rus('Недопустимая операция извлечения -- Очередь пустая!'));
end
else begin
value := queue[Low(queue)];
for count := Low(queue) to (High(queue) - 1) do begin
queue[count] := queue[count + 1];
end;
SetLength(queue, Length(queue) - 1);
end;
end;
{Добавление целого значения в конец очереди}
procedure Enqueue(value: Integer);
begin
SetLength(queue, Length(queue) + 1);
queue[High(queue)] := value;
end;
{Тестирование очереди}
var
value, count: Integer;
begin
Initialize;
for count := 1 to 10 do begin
Enqueue(count);
Writeln(rus('Добавлено: ') + IntToStr(count));
end;
for count := 1 to 5 do begin
Dequeue(value);
Writeln(rus('Извлечено: ') + IntToStr(value));
end;
for count := 30 to 33 do begin
Enqueue(count);
Writeln(rus('Добавлено: ') + IntToStr(count));
end;
for count := 1 to 9 do begin
Dequeue(value);
Writeln(rus('Извлечено: ') + IntToStr(value));
end;
readln;
end.
Очередь с двусторонним доступом (двусторонняя очередь) обладает свойствами как стека, так и простой очереди. Данные в нее могут добавляться в любой конец и извлекаться из любого конца. Сравните: как в стек, так и в одностороннюю очередь данные могут добавляться только в конец. Обычно в программах, реализующих двустороннюю очередь, предусмотрены процедуры добавления данных в начало и в конец очереди, а также извлечения из начала и из конца.
Рассмотрим пример реализации на Object Pascal двусторонней очереди целых чисел. В коде программы DequeEx, реализующем двустороннюю очередь, используется двусвязный список, т. е. связный список, в котором каждый узел содержит два указателя: одни из них указывает на предыдущий узел, а другой – на следующий.
program DequeEx;
{$APPTYPE CONSOLE}
uses
SysUtils;
function Rus(mes: string):string;
// В ANSI русские буквы кодируются числами от 192 до 255,
// в ASCII - от 128 до 175 (А..Я, а..п) и от 224 до 239 (р..я)
var
i: integer; // номер обрабатываемого символа
begin
for i:=1 to length(mes) do
case mes[i] of
'А'..'п' : mes[i] := Chr(Ord(mes[i]) - 64);
'р'..'я' : mes[i] := Chr(Ord(mes [i]) - 16);
end;
rus := mes;
end;
type
NodePointer = ^NodeType;
NodeType = record
value: Integer;
next: NodePointer;
last: NodePointer;
end;
DequeType = record
front: NodePointer;
rear: NodePointer;
end;
{Инициализация двусторонней очереди}
procedure Initialize(var deque: DequeType);
begin
deque. front := nil;
deque. rear := nil;
end;
{Функция IsEmpty возвращает True, если очередь пустая}
function IsEmpty(deque: DequeType): Boolean;
begin
IsEmpty := (deque. front = nil) or (deque. rear = nil);
end;
{Добавление целого значения в начало двусторонней очереди}
procedure AddFront(var deque: DequeType; value: Integer);
var
temp: NodePointer;
begin
New(temp);
temp^.value := value;
temp^.next := deque. front;
temp^.last := nil;
if IsEmpty(deque) then begin
deque. rear := temp;
end
else begin
deque. front^.last := temp;
end;
deque. front := temp;
end;
{Добавление целого значения в конец двусторонней очереди}
procedure AddRear(var deque: DequeType; value: Integer);
var
temp: NodePointer;
begin
New(temp);
temp^.value := value;
temp^.last := deque. rear;
temp^.next := nil;
if IsEmpty(deque) then begin
deque. front := temp;
end
else begin
deque. rear^.next := temp;
end;
deque. rear := temp;
end;
{Извлечение целого значения из конца двусторонней очереди}
procedure RemoveFront(var deque: DequeType;
var value: Integer);
var
temp: NodePointer;
begin
if IsEmpty(deque) then begin
value := 0;
Writeln(rus('Недопустимый вызов функции RemoveFront() -- двусторонняя очередь пустая!'));
end
else begin
temp := deque. front;
value := temp^.value;
deque. front := temp^.next;
Dispose(temp);
if IsEmpty(deque) then begin
deque. rear := nil;
end
else begin
deque. front^.last := nil;
end;
end;
end;
{Извлечение целого значения из конца двусторонней очереди}
procedure RemoveRear(var deque: DequeType;
var value: Integer);
var
temp: NodePointer;
begin
if IsEmpty(deque) then begin
value := 0;
Writeln(rus('Недопустимый вызов функции RemoveRear() -- Двусторонняя очередь пустая!'));
end
else begin
temp := deque. rear;
value := temp^.value;
deque. rear := temp^.last;
Dispose(temp);
if IsEmpty(deque) then begin
deque. front := nil;
end
else begin
deque. rear^.next := nil;
end;
end;
end;
{Тестирование двусторонней очереди}
var
deque: DequeType;
count, value: Integer;
begin
Initialize(deque);
for count := 1 to 10 do begin
AddRear(deque, count);
Writeln(rus('Добавлено в конец: ') + IntToStr(count));
end;
for count := 5 downto 1 do begin
AddFront(deque, count);
Writeln(rus('Добавлено в начало: ') + IntToStr(count));
end;
for count := 1 to 10 do begin
RemoveFront(deque, value);
Writeln(rus('Извлечено из начала: ') + IntToStr(value));
end;
for count := 1 to 5 do begin
RemoveRear(deque, value);
Writeln(rus('Извлечено из конца: ') + IntToStr(value));
end;
readln
end.
Очереди с приоритетами, кучи и деревья
Очередь с приоритетами — это очередь, с каждым элементом которой ассоциирован некоторый приоритет. Обычно для очереди с приоритетами предусмотрены две операции: добавление нового элемента и извлечение элемента, имеющего самый низкий приоритет. Обратите внимание: в этом примере в первую очередь извлекаются элементы с низким приоритетом, т. е. значение термина "приоритет" инвертировано. В реальных задачах этот термин может применяться как в прямом, так и в инвертированном значении.
В программе PriorityQueueEx очередь с приоритетами реализована на основе статического массива. В данном примере реализована так называемая кольцевая очередь с приоритетами, т. е. очередь обладает способностью переходить из одного конца массива в другой. Процедура Insert() предназначена для вставки в очередь нового элемента соответственно его приоритету. Таким образом, элементы очереди всегда располагаются в массиве таким образом, что с увеличением значения индекса увеличивается приоритет элементов (в восходящем порядке). Процедура DeleteMin() извлекает из очереди первый элемент, всегда имеющий минимальный приоритет.
Кольцевая очередь с приоритетами реализуется на основе статического массива. Кольцевая очередь может переходить из одного конца массива в другой. Например, при 50 элементах массива и 15 элементах очереди начало очереди front может располагаться в 46-м элементе, а конец rear – в 10-м. Процедура CheckBounds корректирует значения front и rear для реализации правильного перехода из конца массива в начало.
В программе для задания приоритета элементов используется генератор псевдослучайных чисел. Процедура Randomize() инициализирует встроенный в Delphi генератор значением, полученным от системных часов. Функция Random(x) возвращает случайное число целого типа, равномерно распределенное в диапазоне от 0 до х.
program PriorityQueueEx;
{$APPTYPE CONSOLE}
uses
SysUtils;
function Rus(mes: string):string;
// В ANSI русские буквы кодируются числами от 192 до 255,
// в ASCII - от 128 до 175 (А..Я, а..п) и от 224 до 239 (р..я)
var
i: integer; // номер обрабатываемого символа
begin
for i:=1 to length(mes) do
case mes[i] of
'А'..'п' : mes[i] := Chr(Ord(mes[i]) - 64);
'р'..'я' : mes[i] := Chr(Ord(mes [i]) - 16);
end;
rus := mes;
end;
const
PQ_MIN = 1; {Начальный индекс}
PQ_MAX = 50; {Конечный индекс}
PQ_SIZE = PQ_MAX - PQ_MIN + 1; {Максимальная длина
очереди с приоритетами}
type
PQRec = record
task: String[20];
priority: Integer;
end;
PQArray = array[PQ_MIN..PQ_MAX] of PQRec;
PQType = record
pq: PQArray; {Очередь с приоритетами}
front: Integer; {Начальный индекс очереди}
rear: Integer; {Конечный индекс очереди}
size: Integer; {Длина очереди с приоритетами}
end;
procedure Initialize(var pqueue: PQType);
begin
with pqueue do begin
front := PQ_MIN;
rear := PQ_MIN;
size := 0;
end;
end;
{Функция IsEmpty возвращает True, если очередь с приоритетами пустая}
function IsEmpty(pqueue: PQType): Boolean;
begin
IsEmpty := (pqueue. size = 0);
end;
{Функция IsFull возвращает True, если очередь с приоритетами заполнена}
function IsFull(pqueue: PQType): Boolean;
begin
IsFull := (pqueue. size = PQ_SIZE);
end;
{Проверка допустимости индекса массива}
procedure CheckBounds(var index: Integer);
begin
if (index < PQ_MIN) then begin
index := PQ_MAX;
end
else if (index > PQ_MAX) then begin
index := PQ_MIN;
end;
end;
{Вставка элемента в очередь с приоритетами}
procedure Insert(var pqueue: PQType; data: PQRec);
var
loc, prev: Integer;
found: Boolean;
begin
if IsFull(pqueue) then begin
writeln(rus('Ошибка при вызове Insert() -- очередь заполнена!'));
end
else begin
Inc(pqueue. size);
if (pqueue. size = 1) then begin
pqueue. front := pqueue. rear;
pqueue. pq[pqueue. rear] := data;
end
else begin
Inc(pqueue. rear);
CheckBounds(pqueue. rear);
found := False;
loc := pqueue. rear;
repeat
prev := loc - 1;
CheckBounds(prev);
if (data. priority < pqueue. pq[prev].priority) then begin
pqueue. pq[loc] := pqueue. pq[prev];
loc := prev;
end
else begin
found := True;
end;
until found or (loc = pqueue. front);
pqueue. pq[loc] := data;
end;
end;
end;
{Извлечение из очереди с приоритетами элемента с наименьшим приоритетом}
procedure DeleteMin(var pqueue: PQType; var data: PQRec);
begin
if IsEmpty(pqueue) then begin
data. task := '';
data. priority := 0;
Writeln(rus('Ошибка при вызове DeleteMin() -- очередь пустая!'));
end
else begin
data := pqueue. pq[pqueue. front];
Inc(pqueue. front);
CheckBounds(pqueue. front);
Dec(pqueue. size);
end;
end;
var
pqueue: PQType;
data: PQRec;
count: Integer;
begin
Writeln(rus('ВСТАВКА ЭЛЕМЕНТОВ:'));
Randomize;
Initialize(pqueue);
for count := 1 to 20 do begin
data. task := 'Задача ' + IntToStr(count);
data. priority := Random(10);
Insert(pqueue, data);
Writeln(rus('Вставлено: ') + rus(data. task) +
Rus(', Приоритет ') +
IntToStr(data. priority));
end;
Writeln('');
Writeln(Rus('ИЗВЛЕЧЕНИЕ ЭЛЕМЕНТОВ:'));
for count := 1 to 20 do begin
DeleteMin(pqueue, data);
Writeln(rus('Извлечено: ') + rus(data. task) +
Rus(', Приоритет ') +
IntToStr(data. priority));
end;
readln;
end.
Куча (или бинарная куча, binary heap) – это очередь с приоритетами, структурированная как бинарное дерево. Чтобы понять, что такое кучи, необходимо сначала ознакомиться с древовидными структурами. Дерево – это набор узлов, между которыми установлены родительско-дочерние отношения. В древовидной структуре каждый узел может быть соединен с произвольным количеством дочерних узлов и только с одним родительским. Кроме того, каждое дерево содержит единственный узел, называющийся корневым узлом или корнем.
Бинарным называется дерева, каждый узел которого соединен не более чем с двумя дочерними узлами.
Рассмотрим следующий пример. В программе BinaryTreeEx для создания бинарного дерева, состоящего из 20 целых случайных чисел в диапазоне от 0 до 99, используй указатели. Программа выводит минимальное и максимальное целые значения, хранящиеся в дереве. Дерево организовано таким образом, что для каждого узла его левый дочерний узел содержит меньшее значение, чем родительский, а правый – большее или равное значению в родительском узле.
program BinaryTreeEx;
{$APPTYPE CONSOLE}
uses
SysUtils;
function Rus(mes: string):string;
// В ANSI русские буквы кодируются числами от 192 до 255,
// в ASCII - от 128 до 175 (А..Я, а..п) и от 224 до 239 (р..я)
var
i: integer; // номер обрабатываемого символа
begin
for i:=1 to length(mes) do
case mes[i] of
'А'..'п' : mes[i] := Chr(Ord(mes[i]) - 64);
'р'..'я' : mes[i] := Chr(Ord(mes [i]) - 16);
end;
rus := mes;
end;
type
NodePointer = ^NodeType;
NodeType = record
value: Integer;
left: NodePointer;
right: NodePointer;
end;
{Инициализация дерева}
procedure Initialize(var tree: NodePointer);
begin
tree := nil;
end;
{Вставка узла в дерево}
procedure Insert(var tree: NodePointer; data: Integer);
var
temp, loc, prev: NodePointer;
begin
New(temp);
temp^.value := data;
temp^.left := nil;
temp^.right := nil;
if (tree = nil) then begin
tree := temp;
end
else begin
loc := tree;
while (loc <> nil) do begin
prev := loc;
if (data < loc^.value) then begin
loc := loc^.left;
end
else begin
loc := loc^.right;
end;
end;
if data < prev^.value then begin
prev^.left := temp;
end
else begin
prev^.right := temp;
end;
end;
end;
{Получение минимального значения в дереве}
function GetMin(tree: NodePointer): Integer;
var
prev: NodePointer;
begin
prev := nil;
while (tree <> nil) do begin
prev := tree;
tree := tree^.left;
end;
if (prev = nil) then begin
GetMin := -1;
Writeln(Rus('Ошибка при вызове GetMin() -- дерево пустое!'));
end
else begin
GetMin := prev^.value;
end;
end;
{Получение максимального значения в дереве}
function GetMax(tree: NodePointer): Integer;
var
prev: NodePointer;
begin
prev := nil;
while (tree <> nil) do begin
prev := tree;
tree := tree^.right;
end;
if (prev = nil) then begin
GetMax := -1;
Writeln(Rus('Ошибка при вызове GetMax() -- дерево пустое!'));
end
else begin
GetMax := prev^.value;
end;
end;
var
tree: NodePointer;
count, value: Integer;
begin
Writeln(Rus('СОЗДАНИЕ ДЕРЕВА:'));
Randomize;
Initialize(tree);
for count := 1 to 20 do begin
value := Random(100);
Insert(tree, value);
Writeln(Rus('Вставлено: ') + IntToStr(value));
end;
Writeln('');
Writeln(Rus('ПОИСК МИНИМАЛЬНОГО И МАКСИМАЛЬНОГО ЗНАЧЕНИЙ:'));
Writeln(Rus('Минимальное значение: ') + IntToStr(GetMin(tree)));
Writeln(Rus('Максимальное значение: ') + IntToStr(GetMax(tree)));
readln;
end.
Как упоминалось раньше, куча – это очередь с приоритетами, структурированная кик бинарное дерево. Программа реализации кучи поддерживает «сбалансированность» бинарного дерева. Это означает, что каждый родительский узел содержит значение, меньшее или равное значению каждого из его дочерних узлов. Таким образом, корневой узел всегда содержит минимальное значение.
Для простейшей реализации кучи достаточно статического массива. Если родительский узел имеет индекс i, то дочерние узлы расположены в элементах с индексами 2i и 2i+1. Пример кучи с такой структурой реализован в программе НеарЕх. Назначение процедур Insert() и DeleteMin() описано в комментариях, содержащихся в исходном коде программы.
program HeapEx;
{$APPTYPE CONSOLE}
uses
SysUtils;
function Rus(mes: string):string;
// В ANSI русские буквы кодируются числами от 192 до 255,
// в ASCII - от 128 до 175 (А..Я, а..п) и от 224 до 239 (р..я)
var
i: integer; // номер обрабатываемого символа
begin
for i:=1 to length(mes) do
case mes[i] of
'А'..'п' : mes[i] := Chr(Ord(mes[i]) - 64);
'р'..'я' : mes[i] := Chr(Ord(mes [i]) - 16);
end;
rus := mes;
end;
const
HEAPSIZE = 50; {Максимальный размер кучи}
SENTINEL = -100; {Контрольное значение в заголовочном узле}
type
HeapRec = record
task: String[20];
priority: Integer;
end;
HeapArray = array[0..HEAPSIZE] of HeapRec;
HeapType = record
data: HeapArray; {Тип кучи}
size: Integer; {Количество элементов в куче}
end;
{Инициализация кучи}
procedure Initialize(var heap: HeapType);
begin
heap. size := 0;
with heap. data[0] do begin
task := Rus('ЗАГОЛОВОЧНЫЙ УЗЕЛ');
priority := SENTINEL;
end;
end;
{Функция IsEmpty возвращает True, если куча пустая}
function IsEmpty(heap: HeapType): Boolean;
begin
IsEmpty := (heap. size = 0);
end;
{Функция IsFull возвращает True, если куча заполнена}
function IsFull(heap: HeapType): Boolean;
begin
IsFull := (heap. size = HEAPSIZE);
end;
{Вставка элемента в кучу}
procedure Insert(var heap: HeapType; data: HeapRec);
var
i: Integer;
begin
if IsFull(heap) then begin
Writeln(rus('Ошибка при вызове Insert() -- куча заполнена!'));
end
else begin
Inc(heap. size);
i := heap. size;
while (heap. data[i div 2].priority > data. priority) do begin
heap. data[i] := heap. data[i div 2];
i := i div 2;
end;
heap. data[i] := data;
end;
end;
{Извлечение из кучи следующего элемента с минимальным приоритетом}
procedure DeleteMin(var heap: HeapType; var data: HeapRec);
var
i, child: Integer;
lastElement: HeapRec;
done: Boolean;
begin
if IsEmpty(heap) then begin
data. task := '';
data. priority := 0;
Writeln(Rus('Ошибка при вызове DeleteMin() -- куча пустая!'));
end
else begin
data := heap. data[1];
lastElement := heap. data[heap. size];
Dec(heap. size);
i := 1;
done := False;
while (i * 2 <= heap. size) and not(done) do begin
{Поиск дочернего узла с меньшим значением}
child := i * 2;
if (child <> heap. size) then begin
if heap. data[child + 1].priority <
heap. data[child].priority then begin
Inc(child);
end;
end;
{Перемещение элементов кучи}
if lastElement. priority > heap. data[child].priority
then begin
heap. data[i] := heap. data[child];
i := child;
end
else begin
done := True;
end;
end;
heap. data[i] := lastElement;
end;
end;
{Тестирование кучи}
var
heap: HeapType;
data: HeapRec;
count: Integer;
begin
Randomize;
Writeln(Rus('ВСТАВКА ЭЛЕМЕНТОВ:'));
Initialize(heap);
for count := 1 to 20 do begin
data. task := Rus('Задача ') + IntToStr(count);
data. priority := Random(10);
Insert(heap, data);
Writeln(Rus('Вставлено: ') + data. task +
Rus(', Приоритет ') +
IntToStr(data. priority));
end;
Writeln('');
Writeln(Rus('ИЗВЛЕЧЕНИЕ ЭЛЕМЕНТОВ:'));
for count := 1 to 20 do begin
DeleteMin(heap, data);
Writeln(Rus('Извлечено: ') + data. task +
Rus(', Приоритет ') +
IntToStr(data. priority));
end;
readln;
end.
Контрольные вопросы.
Что называется указателем? Для чего необходимо значение nil при работе с указателями? Назовите операции, которые допускаются над значениями ссылочного типа? Какие стандартные процедура реализуют основные действия над динамическими переменными? К чему приводит «потеря» указателя на данные, хранимые в динамической памяти? Ограничена ли динамическая память?Задания
Реализуйте операции работы со стеком, построенным на основе динамических структур. Реализуйте операции работы с очередью, построенной на основе динамических структур.
Основные порталы (построено редакторами)