Здесь имеем значения L=1; I=1; J=7; R=7. Цикл WHILE X > M[I] при Х = 2 дает сразу же отказ и значение I остается старым, т.е. I = 1. Цикл WHILE X < M[J] при Х = 2 дает J = 6. Сравнение IF I <= J дает 1 <= 6, т.е. истина, отсюда идет обмен между I-м и J-м элементами - первый элемент 6 меняется местом с шестым элементом 1:

1	2	3	4	7	6	5
1	2	3	4	5	6	7

и индекс I (J) увеличивается (уменьшается):

I:=I+1, т.е. I = 2;

J:=J-1, т.е. J = 5.

Сравнение I > J, т.е. 2 > 5, является ложным, поэтому идет возврат наверх. Циклы WHILE доводят значения переменной I до 2, а значение J становится равным 4. Так как I=2 <= J=4, то идет обмен между 2-м и 4-м элементами:

1	2	3	4	5	6	7
1	2	3	4	5	6	7

и индексы получают значения: I = 3, J = 3.

При таких значениях индексов имеем M[I]=M[J]=3, что в результате работы циклов WHILE дает I=3 и J=2. Сравнение I<=J будет ложным, поэтому обмена элементов нет, кроме того, становится истинным условие проверки окончания работы цикла REPEATE (I>J) и происходит переход на рекурсивное обращение к самой процедуре.

Из двух условий истинным является первое (сравнение L < J дает 1< 2), поэтому идет обращение к процедуре при параметрах L=1 и R=2. Однако для этих праметров упорядочивание уже произошло. Затем формируется отрезок [3,7], где происходит обмен между 5-м и 7-м элементами:

1	2	3	4	5	6	7
1	2	3	4	5	6	7

В результате этой работы массив уже упорядочен, однако затем формируются отрезки [3,6] и [5,6], при которых никаких обменов не происходит, но параметры I, J получают значения: I=6, J=4. Ни одно из сравнений L<J (5<4) и R>I (6>6) не является истинным, поэтому рекурсия завершается и процедура заканчивает свою работу.

ЗАМЕЧАНИЕ. Данная процедура очень медленно обрабатывает уже упорядоченный массив.

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;{рабочие элементы}

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

ОПЕРАТОРЫ			ПОЯСНЕНИЕ

new(K);
el:=random(10);	K	*		el	nil
K^.next:=nil;
K^.elem:=el;

L:=K;	L	*

	K	*		el	nil

R:=K;	R	*


el:=random(10);
while el<>0
do begin	K	*		el	nil
new(K);
K^.elem:=el;
K^.next:=nil;


	L	*		el	*
R^.next:=K;
	R	*	K	el	nil


R:=K;	L	*		el	*


	R	*		el	nil
el:=random(10); end;			K

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

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. Она предполагает формирование пустой очереди, состоящей из одного нулевого звена:

L,R	*		0	nil

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

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). Рассмотрим сначала алгоритм:

ОПЕРАТОРЫ			ПОЯСНЕНИЕ

read(el); new(K);
K^.next:=nil;	K	*		el	nil
K^.elem:=el;


	L	*		el1	*
		…	…	…	…	…
R^.next:=K;	R	*		elN	*

				el	nil
			K

	L	X		el1	*
		…	…	…	…	…
R:=K;				elN	*

	R	X		el	nil
			K

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

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.


L	*	el1	*

				el2	*
					…
R	*					elN	nil

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.

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

14.2 Стек

Стек - это структура данных, которая обеспечивает доступ к списку по принципу LIFO (от первых букв английской фразы "Last Input First Output"): последним вошел, первым вышел. Компонента извлекается из стека таким образом, что первой выбирается та, которая была помещена последней.

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

Значением указателя, представляющего стек как единый объект, является ссылка на ВЕРШИНУ стека. Последнее звено цепочки - стека содержит в поле ссылок значение NIL.

STACK

*

elN

*

…

el2

*

el2

nil

Если стек пуст, то значением указателя является ссылка NIL.

Перед началом заполнения стека его необходимо сделать пустым, т.е. выполнить "обнуление" указателя стека: STACK:= NIL.

Над стеком, как и над очередью, допустимы следующие операции:

1) формирование;

2) занесение нового элемента;

3) удаление элемента;

4) доступ (только для просмотра) к N-му звену стека.

Заметим, кстати, что занесение и удаление происходят в стеке исключительно в его вершине.

ОПЕРАТОРЫ

ПОЯСНЕНИЕ

Var ST:SS;

EL:integer;

K:SS;

ST

*

nil

Begin

New(ST);

ST:=nil;

New(K);

K

*

Randomize;

EL:=random(10);

K^.elem:=el;

K

*

el1

nil

K^.next:=ST;

K

*

el1

nil

ST:=K;

ST

*

New(K);

K

*

EL:=random(10);

K

*

el2

*

K^.elem:=EL;

ST

*

el1

nil

K^.next:=ST;

ST:=K;

K

*

el2

*

ST

*

el1

nil

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

procedure SOZDAN_STACK (var ST: SS);

var K: SS;

EL: integer;

begin

randomize;

EL:= random(10);

new(ST); ST:= nil;

while EL <> 0 do

begin

¦ new(K); K^.elem:= EL;

¦ k^.next:= ST; ST:= K;

¦ EL:= random(10);

end;

end.

ЗАМЕЧАНИЕ. Как видно из процедуры, организация очереди и стека отличается только порядком установления связи: предыдущий элемент очереди указывает на следующий, а следующий элемент стека ссылается на предыдущий.

Известно, что новый элемент всегда вставляется на первое место - в вершину стека. Отсюда получаем схему вставки звена в стек:

ST

*

Eln

*

…

EL1

nil

Eln+1

*

Процедура имеет два параметра: ST - указатель на стек, EL - заносимый элемент:

PROCEDURE VSTAVKA_V_STACK(var ST: SS; EL: integer);

var K: SS;

begin

new(K); K^.elem:= EL;

K^.next:= ST; ST:= K

end.

Схематически процесс удаления можно изобразить так:

ST

*

Eln

*

Eln-1

*

…

EL1

nil

По схеме видно, что удаляется N-е звено (вершина стека), которое надо запомнить в специальной ячейке SKLAD:

procedure UDALENIE_IZ_STACK(var ST: SS; var SKLAD: integer);

begin

¦ SKLAD:= ST^.elem;

¦ ST:= ST^.next

end.

Мы видим, что здесь переменная ST начинает хранить ссылку на N-1 элемент.

Данная процедура имеет недостатки:

1) предполагается, что стек заведомо не пуст, иначе программа зависнет;

2) исключаемое звено не уничтожается, т.к. меняется только ссылка в переменной ST. Если таких удалений несколько, то память будет забита "мусором". Поэтому следует исключить элементы не только из списка, но и из памяти. Для этого можно использовать процедуру DISPOSE.

Указанные недостатки учтены в следующей процедуре:

procedure UDALENIE_MOD(var ST: SS; var SKLAD: integer);

var K: SS;

begin

¦ if ST = nil then writeln('стек пустой')

¦ else begin

¦ ¦ SKLAD:= ST^.elem; K:=ST;

¦ ¦ ST:= ST^.next; dispose(K);

end;

end.

Здесь мы ввели в употребление вспомогательную ссылочную переменную К, т.к. писать DISPOSE (ST) нельзя, ведь ST содержит ссылку на вершину стека.

Для извлечения из стека N-го элемента необходимо поступить так же, как при выборке элемента из файла, - "прокрутить" стек на N-1 позиций и затем извлечь N-й элемент. Для "прокрутки" стека можно воспользоваться процедурой UDALENIE, т.к. удаление в динамических структурах означает не уничтожение звеньев списка, а только передвижение указателя на следующий элемент.

Для написания этой процедуры следует уточнить, что под N-м элементом стека следует понимать элемент, отстоящий на N позиций от вершины стека:

procedure VIBORKA_IZ_STACKA(var ST: SS; var SKLAD: integer;

N: integer);

var K: SS; i: integer;

begin

¦ K:= ST;

¦ for i:= 1 to N-1 do

¦ UDALENIE_IZ_STACK(K, SKLAD);

¦ SKLAD:= K^.elem;

end.

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

14.3 Дек

Дек - это двунаправленная очередь, т.е. линейный список, в котором все включения и исключения (и обычно всякий доступ) достигаются на обоих концах списка:

левый

второй

второй

правый

конец

слева

справа

конец

EL1

EL2

..

..

Eln-1

Eln

включить

включить

или

или

исключить

исключить

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11