Бусыгин Б.С., Коротенко Г.М., Коротенко Л.М. Введение в современную информатику

Подождите немного. Документ загружается.

370

Type

IntPtr = ^Integer; {Ссылка на целое значение}

Var

P : IntPtr; {Ссылочная переменная типа IntPtr, определяющая ссылку

на целое число}

Тогда при вызове в следующем виде:

New(P);

Или:

P:=New(IntPtr);

В куче выделится блок памяти размером SizeOf (Integer) то есть 2

байта и адрес первого байта этого блока запишется в P. После выполнения New

можно уже ссылаться на динамическую переменную P^.

Кроме того, вызов New (P) можно заменить на вызов GetMem (P,

SizeOf (ИмяБазовогоТипа_P)), где SiZeOf (X) – стандартная

функция ТП, возвращающая размер в байтах базового типа.

Процедура GetMem предназначена для выделения памяти указателям:

Var

P : Pointer; {Объявляем указатель}

Begin

GetMem (P, 4*1024); {Теперь P указывает на блок памяти в куче

размером 4 Кб.

P^ не имеет типа, однако содержит 4096

байтов}

. . .

End.

8.27.8. Освобождение динамических переменных. Процедуры

Dispose и FreeMem

Для освобождения памяти, занимаемой динамической переменной P,

используется процедура Dispose (Var P: Pointer). Эта процедура

работает только с типизированными ссылочными переменными (табл.. 53). Для

корректной работы программы Вы всегда должны выполнять вызов Dispose

парными вызовам New. После вызова процедуры значение ссылки P не

определено, как и значение разименованной переменной P^.

371

Таблица 53.

Процедуры освобождения динамических переменных в ТП

Процедуры и функции Назначение

Dispose (Var P: Pointer)

Уничтожает связь, созданную ранее

New, между ссылкой Р и значением,

на которое она ссылается

FreeMem (Var P: Pointer;

Size : Word)

Освобождает Size байт в куче,

начиная с адреса, записанного в

указателе (ссылке Р)

Для освобождения непрерывных участков памяти необходимо

использовать процедуру

FreeMem (Var P : Pointer; Size : Word)

Вызовы FreeMem, так же как и Dispose, должны быть парными вызовам

GetMem. Значения ссылочной переменной Р после вызова FreeMem считаются

неопределёнными.

8.27.9. Объединяем вместе понятия Record и динамических

переменных: решение задачи по созданию

динамических структур типу "очередь"

Наиболее важным аспектом программирования с использованием

динамических структур данных является возможность программной

реализации стековых структур, односвязных и двусвязных списков, очередей,

двоичных деревьев и т.д. Для программной поддержки всех этих структур

можно использовать массивы, но при ближайшем рассмотрении становится

очевидным, что при этом необходимо описывать достаточно большие массивы

с определённой избыточностью, либо, в случае описания заведомо малых

массивов, область прикладного применения программы будет существенно

ограничена. Альтернативой массивам служат указатели в сочетании со

структурой

Record, в которую включают информационную часть и указатель

на следующую структуру

Record. Их преимущество заключается как в том,

что они позволяют создавать динамические структуры необходимой

размерности, так и в том, что мы получаем возможность оперировать

большими объектами с помощью всего лишь 4-байтных указателей.

8.27.10. Логическая структура очереди FIFO

Очередью FIFO (First In – First Out – "первым пришёл – первым

исключается") называется такой последовательный список с переменной

длиной, в котором включение элементов выполняется только с одной стороны

списка (эту сторону часто называют концом или хвостом очереди), а

372

исключение – с другой стороны (называемой началом или головой очереди). Те

самые очереди, которые возникают у прилавков и кассс, являются типовым

бытовым примером очереди FIFO.

Основные операции над очередью – это включение и исключение

элементов, определение размера очереди, очистка, не разрушающее чтение.

Очереди строятся на базе линейных списков. Представление очереди с

помощью линейного списка позволяет достаточно просто обеспечить любые

необходимые операции обслуживания очереди. Особенно это удобно, когда

число элементов в очереди сложно предвидеть. Линейные списки также

находят широкое применение в приложениях, где непредсказуемы требования к

размеру памяти, необходимой для сохранения данных; имеется большое число

сложных операций над данными, особенно включений и исключений.

8.27.11. Связанные линейные списки

Списком называется упорядоченное множество, состоящее из переменного

числа элементов, к которым применяемы операции включениня и исключения.

Список, отражающий отношения соседства между элементами, называется

линейным. Если ограничения на длину списка не допускаются, то список

представляется в памяти в виде динамичной связанной структуры. Линейные

связанные списки являются наипростешими динамическими структурами

данных. Графически связи в списках удобно изображать с помощью стрелок.

Если компонент не связан ни с каким другим, то в поле указателя записывают

значение которое не указывает ни на один из элементов. Такая ссылка

обозначается специальным именем –

nil.

На рис. 8.96 приведена упрощённая структура односвязного списка. На нём

поле

INF – это информационное поле, которое может включать разнообразные

данные, как встроенных, так и пользовательских типов данных языка Турбо

Паскаль,

NEXT – указатель на следующий элемент списка. Каждый список

должен иметь особый элемент, называемый указателем начала списка или

головой списка, который естественно по формату отличен от других элементов.

В поле указателя последнего элемента списка находится специальный признак

nil, свидетельствующий о конце списка.

8.27.12. Реализация операций над связными линейными

списками

Для рассмотрения программных примеров определим следующие типы

данных:

INF nil

Голова списка

INF NEXT

•••

Рис 8.96. Логическая структура односвязного списка

373

Type

data = ...; { Любая структура информационной части списка }

Type { Элемент односвязного списка (sll – single linked list):}

sllptr = ^slltype; { указатель в односвязном списке }

slltype = record { элемент односвязного списка }

inf : data; { информационная часть }

next : sllptr; { указатель на следующий элемент }

end;

Для графической формализации описываемых операциями действий, далее

приводятся рисунки, демонстрирующие их применение к связанным линейным

спискам. На них, сплошными линиями показаны связи, имевшиеся до и

сохранившиеся после выполнения операции. Пунктиром показаны связи,

установленные при выполнении операции. Значком "

" отмечены связи,

разорванные при выполнении операции. Для всех описываемых операций

следует отметить чрезвычайную важность задания последовательности

изменения указателей, для обеспечения корректного выполнения операций со

списком, которые не затрагивают другие его элементы. При неправильном

порядке смены указателей легко потерять какую-либо часть из

обрабатываемого списка. Поэтому на рисунках рядом с устанавливаемыми

связями в скобках показаны шаги, на котрых эти связи устанавливаются.

Словесные описания алгоритмов даны в виде комментариев к

реализованным программно примерам.

8.27.13. Перебор элементов списка.

Эту операцию, Вы будете выполнять над линейными списками чаще

других. При её выполнении осуществляется последовательный доступ ко всем

элементам до конца списка, либо находится некоторый определённый элемент.

Procedure LookSll (head : sllptr); { Перебор 1-носвязного списка }

{ head - указатель на начало списка }

Var

cur : sllptr; { адрес текущего элемента }

Begin

cur:=head; { 1-й элемент списка назначается текущим }

while cur <> nil do

begin

< обработка cur^.inf>

{обрабатывается информационная часть (ИЧ) элемента, на который

указывает cur. Обработка может включать: печать содержимого ИЧ;

модификацию полей ИЧ; сравнение полей ИЧ с эталоном при поиске по ключу;

подсчёт итераций цикла при поиске по номеру и т.д.}

cur:=cur^.next; {из текущего элемента выбирается указатель на

следующий элемент и для последующей итерации следующий элемент

становится текущим. Если текущий элемент был последним, то его поле NEXT

содержит пустой указатель и поэтому в cur запишется nil, что приведёт к

выходу из цикла при проверке условия while}

374

end; {while}

End; { Proc LookSll}

8.27.14. Вставка элемента в список.

Прграммная реализация процесса вставки элемента во внутрь

односвязного списка показана в следующем примере кода и на рис.8.97.

{ Вставка элемента в середину односвязного списка }

Procedure InsertSll(prev : sllptr; inf : data);

{prev – адрес предыдущего элемента; inf – данные нового элемента}

Var

cur : sllptr; {Адрес нового элемента}

Begin

New(cur); {Выделение памяти для нового элемента}

cur^.inf:=inf; {Запись в информационную часть элемента}

cur^.next := prev^.next; {Элемент, который шёл за предыдущим

теперь будет идти за новым}

prev^.next := cur; { Новый элемент идёт за предыдущим}

End; {Proc InsertSll}

Следует чётко представлять, что после того, как Вы с помощью процедуры

New получили адрес нового элемента списка cur (current – текущий) и

заполнили его информационную часть inf, необходимо на первом же шаге



(рис. 8.97) перенести в его поле

NEXT адрес из предыдущего элемента. Тогда он

будет указывать на следующий элемент (шаг

). После этого Вы должны

занести адрес cur нового элемента в поле

NEXT предыдущего элемента (шаг

). Тогда, после этого, предыдущий элемент будет указывать на новый

элемент (шаг

).

Таким способом Вы можете сделать вставку в средину списка, но не

сможете сделать вставку в его начало. При этом должен модифицироваться

указатель на начало списка, как показано на рис. 8.98.

Рис. 8.98. Вставка элемента в голову списка

•••

INF NEXT

HEAD











Рис. 8.97. Вставка елемента в середину (вовнутрь) списку

•••

INF NEXT

•••











375

Как Вы видите, данная операция очень похожа на предыдущую (рис. 8.97),

однако тонкости заключаются в средстве сохранения указателя

HEAD. Поэтому,

необходимо разработать процедуру, которая будет выполнять вставку элемента

в любое место односвязного списка:

{ Вставка элемента в любое место односвязного списка }

Procedure InsertSll (Var head : sllptr; { Указатель на начало

списка, который может измениться в процедуре. Если head=nil

– список пуст }

prev : sllptr; {Указатель на элемент, после

которого осуществляется вставка. Если prev=nil – вставка

выполняется перед первым элементом }

inf : data; {Данные нового элемента }

Var cur : sllptr) {Адреса нового элемента}

Begin

New(cur); {Выделение памяти для нового элемента и запись в его

информационную часть}

cur^.inf:=inf;

if prev <> nil then

begin {Если есть предыдущий элемент – вставка во внутрь списка, рис.

рис.8.97}

cur^.next:=prev^.next;

prev^.next:=cur;

end

else

begin {Вставка в начало списка }

cur^.next:=head; {Новый элемент указывает на бывший 1-й

елемент списка. Если head=nil, то новый элемент будет

одновременно и последним элементом списка}

head:=cur; { Новый элемент становится 1-вым в списке, указатель на

начало теперь указывает на него}

end {if}

End; {Proc InsertSll}

8.27.15. Удаление элемента из списка.

Порядок удаления элемента из разных частей односвязного списка, то есть

из середины списка или из его начала несколько различен. Поэтому, давайте

начнём с удаления элемента из середины списка (рис. 8.99).

Рис. 8.99. Удаление элемента из середины списка

•••

INF NEXT

•••









Удаляем

376

На первом этапе данной операции мы должны указатель на следующий

элемент с элемента, который удаляется, перенести в предыдущий (шаг

),

тогда на шаге

 указатель обходит элемент, который удаляется. И на третьем

шаге

 Вы должны удалить сам элемент, чтобы освободить от него память.

В случае удаления элемента с начала списка Вы должны указатель

HEAD

переадресовать на следующий элемент (рис. 8.100).

Здесь, Вы сначала должны взять указатель на следующий элемент и с

элемента, который удаляется, перенести его в указатель

HEAD (шаг ). Тогда

на шаге

 указатель HEAD обходит элемент, который удаляется. А на третьем

шаге

 Вы должны удалить сам элемент, чтобы освободить от него память.

Очевидно, что процедуру удаления легко разработать, если известен адрес

элемента, предшествующего удаляемому. Однако, более универсальной будет

процедура для случая, когда удаляемый элемент, задаётся своим адресом del.

Процедура обеспечивает удаление как из середины, так и с начала списка.

{Удаление элемента из любого места односвзного списка

}

Procedure DeleteSll(var head : sllptr; {Указатель на начало списка,

может измениться в процедуре}

del : sllptr {Указатель на элемент, который удаляется});

var prev : sllptr; {Адрес предыдущего элемента}

Begin

if head=nil then

begin {Попытка удаления из пустого списка расценивается как ошибка (в

следующих примерах этот случай учитываться на будет)}

Writeln('Ошибка!');

Halt;

end;

if del=head then {Если элемент, который удаляется, 1-й в списке, то

следующий за ним становится первым }

head:=del^.next

else

begin { При удалении из середины списка приходится искать элемент,

который предваряет тот, что удаляется; поиск выполняется

перебором списка из самого его начала, пока не будет найден

Рисунок 8.100. Удаление элемента из головы списка

•••

INF NEXT

HEAD









Удаляем

377

элемент, поле next которого хранится с адресом удаляемого

элемента}

prev:=head^.next;

while (prev^.next<>del) and (prev^.next<>nil) do

prev:=prev^.next;

if prev^.next=nil then

begin {Данная ветвь соотвествует случаю, когда перебран весь

список, а элемент не найден. Он отсутствует в списке и это

роасценивается как ошибка (в следующих примерах этот

случай учитываться на будет!)}

Writeln('Ошибка!');

Halt;

end;

prev^.next:=del^.next; {Предыдущий элемент теперь указывает на

следующий за тем, который удаляется}

end;

Dispose(del); {Элемент исключён из списка – теперь можно освободить

занимаемую им память}

End; {Proc DeleteSll}

8.27.16. Перестановка элементов списка.

Изменчивость динамических структур данных допускает не только

изменения размеров структуры, но и изменения связей между элементами. Для

связанных структур изменение связей не требует пересылки данных в памяти, а

только требует изменения указателей в элементах связной структуры.

Давайте попробуем сделать перестановку двух соседних элементов списка.

Однако, сначала попробуем разобратьсь, как проходит этот процесс

(рис. 8.101).

При конструировании и реализации алгоритма перестановки в

односвязном списке (рис. 8.101) будем исходить из предположения, что

известен адрес элемента, предшествующего паре, в которой осуществляется

перестановка. В нижеприведенном коде также не учитывается случай

перестановки первого и второго элементов.

Рис. 8.101. Перестановка двух соседних элементов в середине списка

•••

INF NEXT1

INF

•••















378

{ Перестановка двух соседних элементов в односвязном списке }

Procedure ExchangeSll(prev : sllptr {Указатель на элемент,

предшествующий переставляемой паре});

Var

p1, p2 : sllptr; {Указатели на элементы пары}

Begin

p1:=prev^.next; {Указатель на 1-й елемент пары}

p2:=p1^.next; {Указатель на 2-й елемент пары}

p1^.next:=p2^.next; {1-й элемент пары теперь указывает на следующий за

парой}

p2^.next:=p1; {1-й элемент пары теперь располагается за 2-ым }

prev^.next:=p2; {2-й элемент парытеперь становится 1-ым }

End; {Proc ExchangeSll}

8.27.17. Решение задачи по созданию очереди

и реализация операций с нею

Теперь Вы хорошо себе представляете, что линейные списки можно

применить в приложениях, где существуют непредусмотренные требования к

размерам памяти, необходимой для сохранения данных, а также велико число

сложных операций над даннми и, особенно, включений и исключений.

Стек – это такой последовательный список с переменной длиной,

включение и исключение елементов в котором выполняются только с одной

стороны списка, называемого вершиной стека. Существуют и другие названия

стека – магазин, а также очередь, функционирующая по принципу LIFO (Last-

In-First-Out – "последним пришёл – первым исключается"). Примером стека

может служить обойма в пистолете (рис. 8.102).

В программных приложениях стек широко применяется в операциях

сохранения, передачи и дальнейшого использования фактических параметров

при обращениях к процедурам, функциям, модулям, удалённым объектам и

другим автономно функционирующим программным компонентам (см.

пп. 6.2, 6.6, 6.7)

Основные операции над стеком – это включение нового элемента

(английское название push – заталкивать) и исключение элемента из стека

(англ. pop – выскакивать).

Известно, что стек может быть представлен как линейный список, в

котором включение элементов всегда проводится с начала списка, а

Вершина стека, откуда извлекается

последним поступивший элемент

Первый поступивший элемент,

который уйдёт последним

Рис.8.102 Схема функционирования стека

379

исключения – также с начала. Для представления его Вам достаточно иметь

один показатель – top, который всегда указывает на последний записанный в

стек элемент. В выходном состоянии (при порожнем стеке) показатель top –

пуст. Главные процедуры StackPush и StackPop реализуют соответственно

операции включения элемента в начало списка (стека) и, соответственно,

исключения элемента из начала этого списка.

Обратите внимание на то, что при включении элемента для него

выделяется память, а при исключении – освобождается. Перед включением

элемента проверяется доступное программе пространство в памяти, и если оно

меньше требуемого для включения нового елемента, стек считается

заполненным. При очистке стека последовательно просматривается весь список

и исключаются все его элементы. При списковом представлении стека,

определение его размера представляется непростой задачей, так как при этом

приходится предварительно производить перебор всего списка для подсчёта

числа всех элементов. Чтобы избежать выполнения таких списка Вы должны

ввести дополнительную переменную

stsize, содержащую текущее число

элементов в стеке и корректируется при каждом включении/исключении (см.

программный код).

{Реализация стека на 1-носвязном линейном списке}

unit Stack;

Interface

type data = ...; {Элементы могут иметь любой тип}

Procedure StackInit;

Procedure StackClr;

Function StackPush(a : data) : boolean;

Function StackPop(Var a : data) : boolean;

Function StackSize : integer;

Implementation

type stptr = ^stit; {Указатель на элемент списка}

stit = record {Элемент списка}

inf : data; {Данные}

next: stptr; {Указатель на следующий элемент}

end;

Var top : stptr; {Указатель на вершину стека}

stsize : longint; {Размер стека}

{** Инициализация – список пустой }

Procedure StackInit;

begin top:=nil; stsize:=0; end; {Процедура StackInit

}

{**Очищение – освобождение всей памяти}

Procedure StackClr;

var x : stptr;

begin {Перебор элементов до конца списка и их удаление}

while top<>nil do

begin x:=top; top:=top^.next; Dispose(x); end;

stsize:=0;

end; {Proc StackClr}

Function StackPush(a: data) : boolean; {Ф-ция занесения в стек}