Общие приемы работы с линейными списками

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

Процедура печати списка имеет вид:

procedure VIVOD_SPISOK(var Y: SS);

var X: SS;

begin X:= Y;

¦ while X^.next <> nil do

¦ begin

¦ ¦ write(X^.elem,' '); X:=X^.next;

¦ end;

end.

ПОЯСНЕНИЕ. Здесь Y - начало списка, а переменная X введена, чтобы после печати списка значение переменной Y не изменилось (не потерялось начало списка).

Поиск заданного элемента в списке осуществляется чаще всего не для констатации факта присутствия этого элемента, а для его удаления или для вставки после него (перед ним в деке) нового элемента. Именно поэтому возвращаемым параметром этой процедуры должна быть ссылка на данный элемент (если такой факт имеет место). Кроме того, полезно знать и номер найденного звена от начала списка:

procedure POISK_V_SPISKE(var Y,Z: SS; ZNACH: integer;

var N: integer);

var X: SS;

begin

¦ N:= 1; X:= Y;

¦ while (X^.elem <> ZNACH) and (X^.next <> nil) do

¦ begin

¦ ¦ X:= X^.next; Z:= X;

¦ ¦ N:= N+1

¦ end;

¦ if X^.next = nil then

¦ begin N:= 0; Z:= nil; end;

end.

ПОЯСНЕНИЕ. С помощью данной процедуры в списке Y ищется звено с элементом ZNACH. Значение переменной N дает номер искомого звена, а переменная Z - ссылку на это звено. Если такого звена нет, то N = 0 и Z = NIL.

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

procedure SORTSPISOK (var X: SS);

{ X - Ссылка на начало списка }

var X1, Y1:SS; P: integer;

begin

¦ X1:= X; { Выбор элемента для сравнения }

¦ while X1^.next <> nil do { Проход по списку до

¦ предпоследнего элемента}

¦ begin

 ¦ ¦ Y1:=X1^.next;

¦ ¦ while Y1^.next <> nil do { Проход до последнего

¦ ¦ элемента }

¦ ¦ begin

¦ ¦ ¦ { Перестановка местами элементов}

¦ ¦ ¦ if Y1^.elem < X1^.elem then

¦ ¦ ¦ begin

¦ ¦ ¦ ¦ P:= X1^.elem; X1^.elem:= Y1^.elem;

¦ ¦ ¦ ¦ y1^.elem:= P;

¦ ¦ ¦ end;

¦ ¦ ¦ Y1:= Y1^.next; { Сдвиг по списку }

¦ ¦ end;

¦ ¦ X1:= X1^.next; { Сдвиг по списку }

¦ end;

end.

ПОЯСНЕНИЕ. В данной процедуре для сортировки использован метод прямого выбора, т.е. способ поиска минимального элемента и установка его в начало списка.

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

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

Здесь поля NEXT и PRED позволяют выходить на любое звено ссылки на любой список. Сами списки для удобства работы с ними лучше делать в виде цепочек, очередей, стеков, хотя они также могут быть организованы в виде дека. В результате имеем такую схему:

…		*			*			*		…
…		*			*			*		…
		*			*			*
		el			el			el
		*			*			*
		el			el			el
		*			*			*
		…			…			…
		Spi-1			SPi			Spi+1

Для реализации этой структуры необходимо задать два типа данных: SS - для обычных списков, SS1 - для дека суперсписка:

type SS = ^ZVENO;

ZVENO = record

el: integer;

next: SS;

end;

SS1 = ^ZVENO1;

ZVENO1 = record

pred1, next1: SS1;

SP: SS;

end.

ЗАМЕЧАНИЕ. В описании 3-го поля второго списка имеется тип SS из первого списка, что позволяет рассматривать каждое звено второго списка как начальное (очередное) звено первого. Для содержания всей этой структуры в рабочем состоянии достаточно хранить в памяти ссылку на один из указателей дека (начало или конец).

Заметим также, что в случае очереди целесообразно построение звена дека из 4-х полей: PRED1, NEXT1, SPL (начало очереди), SPR (конец очереди).

ДЕРЕВЬЯ