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

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

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

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

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 позволяют выходить на любое звено ссылки на любой список. Сами списки для удобства работы с ними лучше делать в виде цепочек, очередей, стеков, хотя они также могут быть организованы в виде дека. В результате имеем такую схему:

Для реализации этой структуры необходимо задать два типа данных: 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 (конец очереди).

Похожие работы

Основы программирования на языке Паскаль

Скачать

168304

7

26

... .....-46.780 Program Prim24; Var r1,r2:real; BEGIN r1:=-46.78; r2:=-46.78; writeln('r1=',r1:12:3,' r2=',r2:9:4); writeln('_______________________________'); readln; END. 6. Массивы   6. 1. Описание массивов В языке Паскаль можно обрабатывать не только отдельные переменные, но и их совокупности. Одной из таких совокупностей (структурированных) данных является массив. ...

Алгоритмические языки и программирование Системное программное обеспечение Технология программирования"

Скачать

112819

0

0

... . Объясните, для чего служат разрешения и привилегии в Windows NT. Зав. кафедрой --------------------------------------------------   Экзаменационный билет по предмету СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ Билет № 22 Перечислите возможности и инструменты системы программирования Microsoft Developer Studio. Укажите для чего предназначается буфер в системах ввода-вывода, ...

Основные понятия алгоритмического языка

Скачать

91405

0

0

... с внешнего устройства (из входного файла) в основную память ЭВМ, операция вывода - это пересылка данных из основной памяти на внешнее устройство (в выходной файл). Файлы на внешних устройствах часто называют физическими файлами. Их имена определяются операционной системой. В программах на языке Паскаль имена файлов задаются с помощью строк. Например, имя файла на диске может иметь вид: ...