СТРУКТУРЫ ПОСЛЕДОВАТЕЛЬНОГО ДОСТУПА. ЛИНЕЙНЫЕ СПИСКИ

14. СТРУКТУРЫ ПОСЛЕДОВАТЕЛЬНОГО ДОСТУПА. ЛИНЕЙНЫЕ СПИСКИ

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

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

14.1 Очередь

Очередь - это линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) - на другом. Очередь иногда называют циклической памятью или списком типа FIFO (от первых букв английской фразы "First Input First Output"): первым включается - первым исключается.

При работе с очередью мы говорим о ее начале и конце – объекты вставляются в конце очереди и удаляются в начале:

Для характеристики работы с очередью необходимо рассмотреть процедуры ее формирования, добавления, исключения элементов.

Условимся в дальнейшем, что будем составлять линейные списки, элементами которых будут числа типа INTEGER. Очевидно, что для организации этих данных необходимо задать описание:

type SS = ^ZVENO;

ZVENO = record

elem: integer;

next: SS;

end.

Рассмотрим сначала алгоритм формирования очереди. Для этого введем три указателя - на начало очереди, на ее конец и текущий указатель:

VAR L: SS; {начало очереди}

R: SS; {конец очереди}

K: SS; {рабочий указатель}

el1,el2: integer;{рабочие элементы}

Алгоритм формирования очереди представлен на следующей схеме:

Запишем теперь полностью процедуру формирования очереди:

procedure FORMIR_OTCHERED_1 (var L, R: SS);

var K: SS; EL: integer;

begin

¦ { Формирование первого звена очереди }

¦ randomize; EL:= random(10);

¦ new(K); L:= K; R:= K;

¦ K^.elem:= EL; K^.next:= nil;

¦ EL:= random(10);

¦ { Помещение очередного элемента в очередь }

¦ while EL <> 0 do

¦ begin

¦ ¦ new(K);

¦ ¦ K^.elem:= EL; K^.next:= nil;

¦ ¦ R^.next:= K; R:= K;

¦ ¦ EL:= random(10);

¦ end;

end.

ЗАМЕЧАНИЕ. Из программы видно, что L всегда хранит начало очереди, а R - ее конец. Процедура имеет два возвращаемых параметра, которые идентифицируют получаемую с ее помощью очередь. Первый параметр L позволяет начать просмотр очереди или удалить из нее элемент, а второй R - добавить новый элемент (согласно правилу работы с очередями).

Заметим также, что эта процедура формирует очередь из однозначных чисел и признаком конца очереди является число 0. Она предполагает формирование пустой очереди, состоящей из одного нулевого звена:

Если пустой очередью считать очередь без единого звена, то процедура принимает вид:

procedure FORMIR_OTCHERED_2 (var L, R: SS);

var K: SS;

EL1, EL2: integer;

begin

¦ {Формирование первого звена очереди }

¦ randomize; EL1:= random(10);

¦ if EL1= 0 then begin L:= nil; R:= L end

¦ else begin new(K);

¦ L:= K; R:= K; K^.next:= nil;

¦ K^.elem:= EL1;

¦ { Помещение очередного элемента в очередь }

¦ EL2:=random(10);

¦ while EL2<>0 do

¦ begin

¦ new(K);

¦ K^.elem:= EL2; K^.next:= nil;

¦ R^.next:= K; R:= K; EL2:= random(10);

¦ end; end;

end.

Одним из приемов работы с очередями является доступ к ее элементу, в частности, сравнение элемента с каким-то числом или вывод его на печать. Исходя из идеологии построения очереди видно, что выборка любого элемента, как и в файле последовательного доступа, возможна только путем просмотра всех элементов очереди, начиная с ее начала. Это легко сделать, зная ссылки на начало и конец очереди. Наличие двух ссылок очень удобно для просмотра очереди (поиска нужного элемента или вывода его на печать). Действительно, в этом случае достаточно организовать цикл с изменением некоторой ссылочной переменной от значения L до значения R.

Таким образом, если необходимо обработать очередь, то следует указать для нее две переменные, где хранятся ссылки на начало и конец. Эти переменные берутся либо непосредственно из программы формирования очереди, либо как выходные параметры процедуры формирования, рассмотренной выше. Ниже следует процедура распечатки элементов очереди, сформированной процедурой пункта 14.1.1:

procedure VIVOD_OTCHERED (var L, R: SS);

var K: SS;

begin

¦ if (L^.elem= 0) or (L= nil) then

¦ writeln('Очеpедь пуста ! ')

¦ else begin

¦ ¦ K:= L;

¦ ¦ write('Элементы очереди: ');

¦ ¦ while K <> R^.next do

¦ ¦ begin

¦ ¦ ¦ write (K^.elem, ' ');

¦ ¦ ¦ K:= K^.next;

¦ ¦ end;

¦ end;

end.

ЗАМЕЧАНИЕ. В данной процедуре знание ссылки R на конец очереди совсем не обязательно. Здесь можно обойтись только ссылкой на начало, а в цикле WHILE в качестве условия взять сравнение значения переменной K с NIL: WHILE K <> NIL.

Добавление нового звена EL к очереди происходит справа (используется указатель R). Рассмотрим сначала алгоритм:

Запишем теперь процедуру добавления звена к очереди:

procedure DOBAV_OTCHERED (EL:integer; var L, R: SS);

var K: SS;

begin

¦ if L^.elem = 0 then R^.elem:= EL

¦ else if L = nil then

¦ begin

¦ ¦ new(K);L:= K;

¦ ¦ R:= K;

¦ ¦ K^.next:= nil;

¦ ¦ K^.elem:= EL

¦ end

¦ else begin

¦ ¦ new(K);

¦ ¦ K^.elem:=el;

¦ ¦ K^.next:=nil;

¦ ¦ R^.next:=K;

¦ ¦ R:=K

¦ end;

end.

ЗАМЕЧАНИЕ. В данной процедуре сначала проверяется, является ли очередь пустой. Если пустая очередь имеет нулевое звено,то оно заполняется элементом EL. Если же она не содержит звеньев, то создается одно звено по тем же правилам, как при формировании очереди. В общем случае к последнему звену очереди добавляется новое звено.

Исключение звена из очереди происходит слева – используется указатель L - и осуществляется одним оператором: L:=L^.next. При такой операции, однако, память не освобождается. Для ее освобождения необходимо дополнительно использовать процедуру DISPOSE.

procedure UDALENIE_OTCHERED (var l, r:ss);

begin

¦ if l=nil then writeln('Очеpедь пуста !')

¦ else l:=l^.next

end.

ОБЩЕЕ ЗАМЕЧАНИЕ. В рассмотренных процедурах признаком конца очереди являлось число 0. Если очередь заполняется символами, то для этого нужно выбрать свой признак конца, например, ".". Для ввода символов, как и для ввода чисел, также можно использовать датчик случайных чисел. Но в этом случае он должен генерировать коды ASCII, которые затем с помощью функции преобразования типов CHR трансформировать в сами символы.

Можно элементы очереди вводить с клавиатуры с помощью операторов READLN и READ. При использовании READLN необходимо производить нажатие клавиши ENTER после набора каждого элемента (числа или символа). Оператор же READ позволяет ввести сразу все элементы, заканчивая их набор числом 0 или точкой как признаком конца, причем числа при этом надо отделять друг от друга пробелом. В этом случае для очистки буфера клавиатуры рекомендуется в конце ввода предусмотреть пустой оператор READLN.

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

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

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

Скачать

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

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