Файл: Лекция 13.doc

Явное использование ссылок позволяет строить более разнообразные структуры, чем те, которые можно задать лишь с помощью рекурсивных определений. Следовательно, нужно ввести типы данных, значениями которых являются указатели (ссылки) на другие данные. Для этого используются такие обозначения:

type

TPtr=^TElement.

Здесь имеется ввиду, что значениями типа TPtr являются ссылки на переменные типа TElement. Стрелка ^ читается как «ссылка на». Существенно, что тип элементов, на которые ссылаются значения типа TPtr, задан в его определении. Это означает, что TPtr связан с TElement. Эта связь отличает ссылки в языках высокого уровня от адресов в языке ассемблера и является очень важным средством увеличения надежности программ. Пусть есть описания

type

Tp1=^TE1;

Tp2=^TE2;

…

var

p1: Tp1;

p2: Tp2

Тогда переменные p1 и p2 – разных типов, так как они ссылаются на переменные разных типов. И это несмотря на то, что и размер памяти, отводимой под p1 и p2, – одинаков, и одинакова сущность их значений: обе эти переменные содержат адреса памяти.

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

• создание переменной;

• удаление переменной.

Значения ссылочных типов создаются всякий раз, когда динамически создается соответствующая переменная. Для динамического создания переменной служит стандартная процедура new. Если дана ссылочная переменная p типа TPtr, то оператор new(p) выделяет память для переменой типа TElement, создает ссылку типа TPtr на эту вновь созданную переменную и присваивает значение этой ссылки (адрес новой переменной) p. Поскольку собственно значение адреса программиста, как правило, не интересует, ссылка на переменную обозначается стрелкой.

Рис. 8.1.

Сама ссылка обозначается как p, значение ее – адрес динамически созданной переменной. Динамически созданная переменная своего имени не имеет, но к ней можно обратиться через ее ссылку, и тогда p^ – динамически созданная переменная.

К множеству значений типа TPtr добавляется еще одно значение – Nil, (от англ. ничего, ноль) которое не ссылается ни на какой элемент. Элемент, содержащий такое значение, является конечным элементом структуры.

Операции, допустимые над ссылочными переменными:

• Присваивание (p:=q). Как и для переменных других типов данных, присваивать одной ссылочной переменной можно значение другой ссылочной переменной только если эти переменные одного и того же типа. Значение Nil можно присваивать любой ссылочной переменной.

• Сравнение (if (p<>Nil) and (p=q) then …). Две переменные ссылочного типа можно сравнивать только на равенство/неравенство. Допустимо сравнение со значением Nil.

• Разыменование (p^). Это унарная операция, ее операнд (p) – указатель, результат – данные по адресу, заданные указателем.

• Оператор @, используется для того, чтобы взять адрес переменной, функции и процедуры. Оператор @ возвращает адрес переменной, функции, процедуры или метода; т.е. @ создает указатель на свой операнд. Следующие правила относятся к операции @:

• Если X — переменная, @X возвращает адрес X. Тип @X – Pointer, если выполнена директива компилятора {$T-} (по умолчанию). В состояние {$T+}, @X — тип ^T, где T — тип X.

• Если F — функция или процедура, @F возвращает точку входа в F. Тип @F — всегда Pointer. При применении операции @ к методу перед идентификатором метода должна идти ссылка на имя класса. Например, @TMyClass.MyShow.

8.2.3. Линейные списки. Основные операции

Самый простой способ соединить, или связать, элементы между собой – это расположить их линейно в списке или в очереди. В этом случае каждый элемент списка содержит только одну ссылку, связывающую его со следующим элементом.

В этом случае рекурсивное описание типов и переменных будет таким:

type

TInfo = integer;

PElement = ^TElement;

TElement = record

Info: TInfo;

Next: PElement;

End;

Переменная типа TElement состоит из двух полей: информационного и поля ссылки. Поле Info может быть любого типа, здесь для простоты выбран целый тип. Поле Next служит для связи со следующим элементом списка. Список элементов показан на рис. 8.2.

Рис. 8.2. Линейный список

Переменная-ссылка p указывает на первую компоненту списка. Последний элемент в поле Next содержит значение Nil.

Самое простое действие, которое можно выполнить со списком, показанным на рис. 8.2, – вставить в его начало новый элемент. Для этого нужно сначала создать этот элемент, используя вспомогательную ссылочную переменную q. Затем ссылкам присвоить новые значения:

New(q); q^.Next:=p; p:=q

Необходимо отметить, что важен порядок следования этих операторов.

Операция включения элемента в начало списка показывает, как можно построить такой список: начиная с пустого списка, последовательно добавлять элементы в его начало. Вот алгоритм, создающий список на рис. 8.2:

p:=nil; // начинаем с пустого списка

n:=5; // число элементов списка

while n>0 do begin

New(q); q^.Next:=p; p:=q;

q^.Info:=n; n:=n-1

end

Это – самый простой способ построения списка. Но при этом полученный порядок элементов обратен порядку их «поступления». В некоторых случаях желательно, чтобы вновь поступающие элементы добавлялись бы в конец списка. Построенный таким образом список называется очередью. Чтобы не проходить каждый раз по списку в поисках его конца, воспользуемся переменной EndList, указывающей на конец списка. Алгоритм приведен в листинге 8.3.

Листинг 8.3. Построение очереди

const

Fin=0; // признак конца последовательности вводимых чисел

type

TInfo = integer;

PElement = ^TElement;

TElement=record

Info: TInfo;

Next: TPtr

end;

var

BegList, // указатель на начало списка

EndList, // указатель на конец списка

p: PElement;

i: integer;//считываем с терминала значение информационного поля

begin

BegList:= Nil; // список пуст

Read(i); // ввод первого элемента списка

while i<>Fin do begin

If BegList = Nil then begin // создание первого элемента списка

New(p); p^.Info:=i; p.Next:=nil;

BegList:=p; EndList:=p

end

else begin // добавляем элемент в конец списка

New(p); p^.Info:=i; p.Next:=nil;

EndList.Next:=p; //присоединяем новый элемент к концу списка

EndList:=p; //смещаем указатель конца на последний

end;

Read(i) // читаем очередное значение

end;

end.

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

Теперь рассмотрим включение в список. Предположим, что элемент, на который указывает q, нужно включить в список после элемента, на который указывает p. Необходимые присваивания ссылок такие:

q^.Next:=p^.Next; p^.Next:=q

Результат показан на рис. 8.3.

Рис. 8.3. Включение в список после заданного элемента.

Если требуется включение перед элементом, а не после него, то кажется, что однонаправленность списка препятствует этому, поскольку нет доступа к предыдущему элементу. Однако простой прием позволяет решить эту проблему. Прием заключается в следующем: новый элемент в действительности вставляется после p^, но затем происходит обмен значениями между новым элементом и p^. С учетом того, что значение нового элемента – x, это выполняется операторами

New(q);

q^.Info:=p^.Info;

p^.Info:=x;

q^.Next:=p^.Next;

p^.Next:=q

и показано на рис. 8.4.

Рис. 8.4. Включение в список перед заданным элементом.

При удалении элемента p^ из списка можно воспользоваться тем же приемом: удалить последующий элемент, предварительно переслав его значение в элемент p^. Однако это можно сделать, только если удаляемый элемент не последний.

Удаление элемента из списка должно состоять из двух действий. Первое – исключение элемента из списка, то есть изменение ссылок. Это показано на рис. 8.5.

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

Теперь исключенный из списка элемент нужно удалить совсем, то есть освободить память, занимаемую этим элементом. Для этого существует процедура Dispose(p), которая освобождает память, занимаемую элементом p^. После выполнения процедуры значение переменной, указанной в качестве параметра, становится неопределенной.

Удаление элемента из списка выполняется следующими операторами:

q:=p^.Next; //вспомогательный указатель ставим на удаляемый элемент

p^.Info:=q^.Info; // переносим информационную часть

p^.Next:=q^.Next; // настраиваем ссылку

Dispose(q) // удаляем элемент

Рассмотрим теперь основную операцию: проход по списку. Ее алгоритм следующий:

while не конец списка do begin

обработать элемент списка;

перейти к следующему элементу

end

Используем этот алгоритм для решения следующей задачи. Найти среднее арифметическое значений информационных полей списка. На начало списка указывает BegList. Описание типов – как в предыдущем листинге.

Листинг 8.4. Найти среднее арифметическое значений

var p : TPtr;

sum : integer; // сумма информационных полей элементов списка

n : integer; // количество элементов списка

SA : real;

begin

sum:=0; n:=0;

p:=BegList;

while p<>Nil do begin // пока не закончился список

sum:=sum+p^.Info; n:=n+1;

p:=p^.Next; // переход к следующему элементу списка

end;

if n<>0 then SA:=sum/n

else writeln(‘list is empty’);

end

В завершение рассмотрим поиск в списке элемента с заданным значением информационного поля – ключом. Поиск в списке может вестись только строго последовательно – как в файле. Поиск заканчивается в двух случаях: либо когда элемент найден, либо когда достигнут конец списка, что означает отсутствие в нем искомого элемента. В листинге 8.5 приведен алгоритм поиска элемента в списке, оформленный в виде функции.

Листинг 8.5. Поиск в списке

function SearchInList (BegList: TPtr; i: integer; var q: TPtr): Boolean;

begin

Result:=false;

q:= BegList;

while not Result and (q <> nil) do

if q^.Info=i then Result:=true else q:=q^.Next;

if not Result then q:=nil;

end;

Параметры функции BegList и i – указатель на начало списка и ключ. Если элемент с заданным ключом найден (значение функции = true), то параметр q будет указывать на найденный элемент.