Мансуров. Основы программирования в среде Lazarus. 2010
.pdfГлава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
ся программно в зависимости от задачи. Пример автоматического создания де-
рева мы рассмотрим в разделе сортировка и поиск с помощью двоичного дере-
ва.
Теперь попробуйте самостоятельно реализовать другие способы обхода двоичного дерева, т.е. обход сверху и снизу.
Достоинства представления деревьев в виде массивов – относительная простота реализации. Для небольших деревьев, особенно если количество вер-
шин заранее известно, использование массивов может оказаться более эффек-
тивным решением. Но отсюда вытекает и недостаток, если количество вершин дерева заранее неизвестно, то, как и в случае со стеком, приходится резервиро-
вать память по максимуму. А каков этот максимум? Определенных критериев нет. Память расходуется непродуктивно. Еще один существенный недостаток – порядок расположения поддеревьев в массиве не поддается формализации.
Паскаль предоставляет значительно более удобный механизм для пред-
ставления списков и, следовательно, для реализации стека и деревьев. Рассмот-
рим этот механизм.
4.3.4 Указатели
Существует ряд задач, где статические структуры данных неэффективны для реализации алгоритма, поэтому в Паскале предусмотрена возможность ра-
боты с динамическими типами структур. С некоторыми из них, в частности стеками и связанными списками, мы познакомились в предыдущих разделах.
Также мы увидели, что стек можно реализовать, используя массивы.
Эффективным средством построения связанных списков являются указа-
тели.
Об указателях мы уже вели разговор в разделе 3.2.1.6, где шла речь о типе данных – указатель.
Напомним синтаксис объявления типизированных указателей:
361
4.3 Динамические структуры данных
____________________________________________________________________
type
Pint = ^integer;
var |
|
p: ^integer; |
{указатель на переменную целого типа} |
p1: ^ string; |
{указатель на строку символов} |
p2: Pint; |
|
Нетипизированный указатель описывается следующим образом:
var
ptr: pointer; {нетипизированный указатель}
Описание указателей p и p2 эквивалентны, т.е. можно применять тот и другой способ.
Указатель фактически является адресом памяти, по которому осуществля-
ется доступ к значениям динамической переменной.
Над указателями допустимы операции проверки на равенство (=) и нера-
венство (<>), а также возможно выполнение оператора присваивания := . Если список пуст, то значение переменной-указателя равно nil.
Память для динамических структур, реализуемых при помощи указателей,
распределяется в специальной области оперативной памяти компьютера и на-
зывается "кучей" (от англ. heap – куча) или динамически распределяемой памя-
тью (ДРП).
Для работы с динамическими переменными в Паскале предусмотрены процедуры:
New(p) – выделить в динамически распределяемой памяти (ДРП) необхо-
димую память для переменной заданного типа с типизированным указателем p;
Dispose(p) – освободить участок ДРП, занятый переменной с типизиро-
362
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
ванным указателем р.
Getmem(p, size) – второй способ выделить память переменной с указа-
телем p размером size байтов. Этой процедурой можно выделить память как для типизированных, так и для нетипизированных указателей.
Freemem(p, size) ) – освободить память распределенной переменной с указателем p размером size байтов.
Пример:
New(p);{Выделяется память для переменной целого типа} New(p1); {Выделяется память для строки символов}
Getmem(p2, 1000); {Выделяется память размером 1000 байт для пе-
ременной с указателем p2}
Как вы видите, динамические переменные не имеют собственного имени и доступ к значению такой переменной осуществляется через операцию разыме-
нования указателя. Для этого используется тот же символ "^", что использовал-
ся при описании указателей.
Пример:
p^:= 25;
p1^:= 'Это строка символов';
p2^:= 44;
При выделении памяти процедурой Getmem для типизированных указате-
лей и определении размера выделяемой памяти, лучше всего использовать про-
цедуру SizeOf так как, размеры памяти, отводимой под тот или иной тип, мо-
гут разниться в различных версиях компиляторов, например:
Getmem(p2, SizeOf(integer));
Обязательно освобождайте память после использования! Имейте в виду только, что после освобождения памяти значения указателей не изменятся, что
363
4.3 Динамические структуры данных
____________________________________________________________________
может привести к ошибкам. Необходимо присваивать значениям указателей nil после освобождения памяти. Кроме того, нельзя смешивать методы выде-
ления и освобождения памяти. Так, если память была выделена процедурой
New(), то нельзя освобождать память процедурой Freemem() и, наоборот,
если память была выделена процедурой Getmem(), то нельзя освобождать процедурой Dispose().
Теперь давайте построим связанный список, используя указатели. Для это-
го достаточно определить тип данных – запись и указатель на него. Структура записи будет следующей:
type
PMyList = ^TMyList; TMyList = record data: integer; next: PMyList; end;
var
mylist: PMyList;
В поле data находится содержательная часть элемента списка, причем data может быть, в свою очередь, записью достаточно сложной структуры.
Поле next – указатель. В нем содержится ссылка на следующий элемент спи-
ска. Благодаря этому указателю можно передвигаться к следующему элементу списка. В качестве признака окончания списка используют пустой указатель nil. Если необходимо двигаться по списку в прямом и обратном направлении,
то в структуру записи добавляют еще одно поле – указатель, в котором указы-
вают адрес предыдущего элемента списка. Такие списки с двумя указателями называются двусвязными или двунаправленными.
Если в конце списка вместо пустого указателя nil поставить ссылку на
364
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
начало списка, т.е. на первый элемент списка, то получим так называемый
кольцевой список.
Для всех видов списков можно определить стандартные операции, которые производятся над списками и которые должен уметь реализовывать програм-
мист. К таким операциям относятся добавление нового элемента в список, уда-
ление элемента из списка, поиск нужного элемента в списке. Рассмотрим их.
4.3.5 Стандартные операции с линейными списками
Запишем стандартные операции с линейными списками в виде готовых
процедур и функций.
Процедура добавления (вставки) нового элемента в список:
procedure Insert_MyList(Elem: integer;
var pHead, pCurrent: PMyList);
{pHead - указатель на первый элемент списка ("голову" списка)
pCurrent - указатель на текущий элемент списка}
var
p: PMyList; // рабочий указатель
begin |
|
new(p); |
// заводим новый элемент |
p^.data:= |
Elem; // записываем в него данные |
{Если список был пустой, то головой списка становится p} if pHead = nil then
begin
p^.next:= nil; pHead:= p;
end else
365
4.3 Динамические структуры данных
____________________________________________________________________
begin
p^.next:= pCurrent^.next; { в новом элементе делаем ссылку на следующий элемент, который был до вставки} pCurrent^.next:= p; {в текущем элементе делаем
ссылку на новый}
end;
pCurrent:= p; // текущим становится новый элемент
end;
Функция поиска элемента в списке просто проходит все элементы списка по ссылкам от начала до тех пор, пока не будет найден искомый элемент.
function Search_MyList(Elem: integer;
var pHead: PMyList): boolean;
var
p: PMyList; begin
if pHead <> nil then p:= pHead
else begin
writeln(UTF8ToConsole('Список пуст'));
exit;
end;
Search_MyList:= false;
while true do
begin
if p^.data = Elem then
begin
366
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
Search_MyList:= true; break;
end else
if p^.next = nil then break; p:= p^.next;
end;
end;
Функция возвращает true, если требуемый элемент найден.
Процедура удаления элемента из списка:
procedure Delete_MyList(Elem: integer;
var pHead, pCurrent: PMyList);
var
p: PMyList;
pPrev: PMyList; // предыдущий элемент списка find: boolean;
begin
if pHead <> nil then p:= pHead
else begin
writeln(UTF8ToConsole('Список пуст'));
exit;
end;
find:= false;
while true do
begin
if p^.data = Elem then
367
4.3 Динамические структуры данных
____________________________________________________________________
begin |
|
find:= true; |
|
break; |
|
end |
|
else |
|
if p^.next = nil |
then break; |
pPrev:= p; |
|
p:= p^.next; |
|
end; |
|
if find then |
|
begin |
|
if p = pHead then // если удаляется первый элемент |
|
begin |
|
p:= pHead^.next; // запоминаем ссылку на следующий элемент |
|
Dispose(pHead); |
// удаляем первый элемент списка |
pHead:= p; |
// головой списка становится p |
end |
|
else |
|
begin // если удаляется не первый элемент
pPrev^.next:= p^.next; { в предыдущем элементе заменяем ссылку на следующий элемент после удаляемого }
Dispose(p);
pCurrent:= pPrev; // текущим делаем предыдущий элемент
end;
writeln(UTF8ToConsole('Элемент успешно удален'));
end
else writeln(UTF8ToConsole('Элемент не найден'));
end;
Процедура, прежде чем удалить элемент, должна его найти. Эта часть сов-
368
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
падает с функцией поиска. Поскольку код функции поиска небольшой, мы вставили в процедуру непосредственно сам код. В принципе, в процедуре мож-
но вызвать функцию поиска. Для этого необходимо видоизменить функцию та-
ким образом, чтобы она возвращала ссылку на найденный элемент. Если эле-
мента нет, она должна возвращать nil. Предоставляем изменить функцию поис-
ка самому читателю.
Напишем главную программу работы со списком (не забудьте включить в программу процедуры и функции, которые мы только что разобрали):
program operation_list; {$mode objfpc}{$H+} uses
CRT, FileUtil; type
PMyList = ^TMyList; TMyList = record data: integer; next: PMyList; end;
var
pHead, pCurrent: PMyList; Elem, choose: integer;
{Сюда добавьте процедуры и функции, реализующие стандартные операции с линейными списками }
begin
pHead:= nil;
pCurrent:= nil;
repeat
writeln(UTF8ToConsole('Выберите нужное действие:'));
369
4.3 Динамические структуры данных
____________________________________________________________________
writeln(UTF8ToConsole('1-ввод элемента списка')); writeln(UTF8ToConsole('2-поиск элемента списка')); writeln(UTF8ToConsole('3-удаление элемента списка')); writeln(UTF8ToConsole('4-просмотр всего списка')); writeln(UTF8ToConsole('5-выход из программы')); readln(choose);
case choose of
1: begin {ввод элемента списка} writeln(UTF8ToConsole('Введите элемент списка')); readln(Elem);
Insert_MyList(Elem, pHead, pCurrent); end;
2: begin {поиск элемента списка}
writeln(UTF8ToConsole('введите искомый элемент'));
readln(Elem);
if Search_MyList(Elem, pHead)then
writeln(UTF8ToConsole('Элемент найден'))
else
writeln(UTF8ToConsole('Элемент не найден')); end;
3: begin {удаление элемента списка} writeln(UTF8ToConsole('введите элемент')); readln(Elem);
Delete_MyList(Elem, pHead, pCurrent); end;
4: begin {Вывод списка на экран}
writeln(UTF8ToConsole('Элементы списка:'));
writeln;
370