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

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

Пусть last -длина списка, а maxlength - максимальный размер массива, причем он выбирается достаточно большим (maxlength >= last), чтобы хранить списки любой длины, которые могут встречаться в данной программе. Разместим список в начале массива, так что индексы элементов списка 1<= i <=last и массива совпадают.

Определим тип данных List как запись с двумя полями:

const maxlength =100;

type elementtype = integer;

list = record

elements: array[1..maxlength] of elementtype;

last: integer

end;

position = integer;

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

1. Insert(x,p,L) – процедура, которая вставляет объект x в позицию p, перемещая элементы из позиций p,p+1,…,last в позиции p+1,p+2,…,last+1;
2. Delete(p,L) – процедура, которая удаляет элемент в позиции p, перемещая элементы из позиций p+1,p+2,..,last в позиции p,p+1,..,last-1;
3. Locate(x,L) – функция, которая возвращает позицию объекта x в списке L, последовательно просматривая массив для поиска заданного элемента;
4. Next(p,L) – функция, которая возвращает следующую позицию от заданной p;
5. Previous(p,L) – функция, которая возвращает предыдущую позицию от заданной p;
6. Retrieve(p,L) – функция, которая возвращает элемент, находящийся в позиции p;
7. First(L)- функция, которая возвращает первую позицию в списке L.

Процедура вставки Insert элемента x в позицию p может выглядеть следующим образом:

function EndL(L:list):possition;

begin

EndL:=L.last+1

end;

procedure Insert(x: elementtype; p: position; var L:list);

var q:position;

begin

with L do

if last >= maxlength then

begin writeln(‘ Список полон’); Exit end

else if (p>End(L)) or (p<1 then)

begin writeln(‘Такой позиции нет’); Exit end

else begin

for q:=last downto p do elements[q+1]:=elements[q];

last:=last+1; elements[p]:=x

end

end;

Дата добавления: 2015-07-19