Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

var I,J,X: integer;

begin

¦ for I:=2 to N do

¦ for J:= N downto I do

¦ if MM[J-1] > MM[J] then

¦ begin

¦ ¦ X:= MM[J-1];

¦ ¦ MM[J-1]:= MM[J];

¦ ¦ MM[J]:= X

end;

end.

Работу программы иллюстрирует пример с тем же исходным массивом, что и ранее:

Все остальные обработки при I = 4, 5, 6 идут впустую, т.к. массив уже упорядочен. В других ситуациях может случиться так, что сортировка закончится только на последнем цикле.

13.4 Сравнительная характеристика методов

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

1. Массив уже отсортирован (но мы не знаем об этом).

Здесь самым быстрым и эффективным следует считать метод прямого включения, т.к. никаких передвижек не произойдет (за счет цикла WHILE, который формально просто не будет работать), а останется только проход по внешнему циклу.

2. Исходный массив упорядочен по убыванию.

Здесь самым лучшим методом является прямой выбор, т.к. вся работа будет проделана за половину ходов (проход до середины):

ПРИМЕР:

3. Массив дан случайным образом.

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

13.5 Улучшенный метод сортировки. QUICK – сортировка

Все рассмотренные выше методы сортировки допускают определенное улучшение. Однако наибольший эффект достигается при модификации наиболее быстрого из всех известных методов - метода прямого обмена. Эта модификация получила название QUICK - сортировка.

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

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

1-ый - левый элемент: L,

2-ой - правый элемент: R.

На начало процедуры эти параметры должны получить значения:

L = 1; R = N.

В процедуре используется цикл REPEAT по сближению левой и правой границ.

procedure QUICKSORT (L, R: integer; var M: MAS);

var I,J,W,X: integer;

begin

¦ {Установка границ, от которых идет движение к середине}

¦ I:= L; J:= R;

¦ {Выбор граничного элемента}

X:= M[(L+R) div 2];

¦ repeat

¦ ¦ { Поиск слева элемента, большего X }

¦ ¦ while X > M[I] do I:= I+1;

¦ ¦ { Поиск справа элемента, меньшего X }

¦ ¦ while X < M[J] do J:= J-1;

¦ ¦ if I <= J then

¦ ¦ begin

¦ ¦ ¦ W:= M[I]; {Обмен местами

¦ ¦ ¦ M[I]:= M[J]; I-го и J-го

¦ ¦ ¦ M[J]:= W; элементов,

¦ ¦ ¦ I:=I+1; дальнейшее продвижение

¦ ¦ ¦ J:=J-1; вперед (назад)}

¦ ¦ end;

¦ ¦ {Выход из цикла, если левый край перевалил за правый}

¦ until I > J;

¦ { Повтор обмена для левой части }

¦ if L < J then QUICKSORT (L,J,M);

¦ { Повтор обмена для правой части }

¦ if R > i then QUICKSORT (I,R,M);

¦

end;

ПОЯСНЕНИE. Рассмотрим работу этой процедуры на примере сортировки следующего массива:

Здесь имеем значения 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:

и индекс 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-м элементами:

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

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

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

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

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

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.

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

14.2 Стек

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

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

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

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

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

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

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

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

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

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

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

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

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 - указатель на стек, 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.

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

По схеме видно, что удаляется 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 Дек

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

Более точно следует представить так:

Ôîðìèðîâàíèå äåêà

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

type SS = ^ZVENO;

ZVENO = record

ELEM: integer;

next: SS;

pred: SS;

end.

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

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

procedure FORMIR_DEK_1(var L, R: SS);

var Z: SS; EL: integer;

begin

¦ new(L); read(L^.elem);

¦ L^.pred:= nil; R:= L; Z:= L;

¦ WHILE R^.elem <> 0 do

¦ begin

¦ ¦ new(R^.next); R:=R^.next;

¦ ¦ read(r^.elem); R^.pred:= Z; Z:= R;

¦ end;

¦ R^.next:= nil; readln;

end.

ПРИМЕЧАНИЕ. В рассмотренном примере для образования дека используются три ссылочные переменные: L - начало дека, R – конец дека, Z - промежуточное звено. Однако эта программа может быть упрощена за счет использования более сложных ссылок типа R^.NEXT^.ELEM и R^.NEXT^.PRED.

Рассмотрим подробно эти объекты. Пусть ссылочная переменная Z указывает на текущее звено дека:

При таких обозначениях динамическая переменная Z^.NEXT^.ELEM означает числовое поле звена 2 (т.е элемент ELi+1), а переменная Z^.NEXT^.PRED - поле PRED звена 2. Учитывая эти соображения, представим программу формирования дека следующим образом:

procedure FORMIR_DEK_2(var L, R: SS);

begin

¦ randomize; new(L);

¦ L^.elem:= random (10);

¦ L^.pred:= nil; R:= L;

¦ while R^.elem <> 0 do

¦ begin new(R^.next);

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

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

¦ end;

R^.next:= nil

end.

Для дека справедливы те же операции, что для очереди и стека - вставка и удаление звеньев.

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

Рассмотрим предварительно схему связи между звеньями дека в процессе вставки нового элемента:

Процедура вставки нового звена Y в дек после звена X принимает вид:

procedure VSTAVKA_V_DEK_POSLE(X, Y: SS);

begin

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

¦ Y^.pred:= X;

¦ X^.next:= Y;

¦ Y^.next^.pred:= Y;

end.

ЗАМЕЧАНИЕ 1. Мы рассмотрели теперь процедуры вставки нового звена во все виды линейных списков с односторонней связью (цепочки, очереди, стеки) и в дек. Однако во всех этих процедурах новое звено вставлялось ПОСЛЕ указанного звена (в стеке - в вершину, в очереди - в хвост). Конечно, можно в односвязном линейном списке поставить новый элемент и ПЕРЕД указанным, но это требует некоторых дополнительных операций. Например, можно новый элемент поместить в следующее звено, а затем произвести обмен информационными полями. В деке же возможна прямая вставка звена ПЕРЕД указанным с использованием ссылки PRED. В результате получаем:

procedure VSTAVKA_V_DEK_PERED(X, Y: SS);

begin

¦ Y^.next:= X^.pred^.next; X^.pred^.next:= Y;

¦ Y^.pred:= X^.pred; X^.pred:= Y;

end.

ЗАМЕЧАНИЕ 2. При вставке нового звена Y в дек относительно X следует учитывать, что на момент применения рассмотренных процедур звенья X и Y уже сформированы и значения этих ссылочных переменных определены. Так, например, звено Y можно сформировать следующим образом:

NEW(Y); Y^.NEXT:= NIL; Y^.PRED:= NIL; READ(Y^.ELEM).

Что касается звена X, то здесь возможны два случая:

1) известен адрес (ссылка) на элемент X; тогда при обращении к процедуре уже задано значение фактического параметра;

2) известен только сам элемент (информационное поле звена X);

для определения ссылки на звено X в указанном деке следует "прокрутить" дек до этого звена (подобно поиску N-го звена в стеке).

Заметим также, что обе процедуры неприменимы для дека, состоящего из одного звена.

При удалении звена из дека, как и в любом линейном списке, происходит перебрасывание ссылок через удаляемое звено: ссылка NEXT предыдущего звена получает своим значением адрес третьего звена, а ссылка PRED третьего звена указывает на первое звено. В результате второе (удалямое) звено X оказывается изолированным от остальных звеньев, что и означает его удаление из дека.

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

procedure UDAL_DEK_1(X: SS; VAR Y, Z: SS);

begin

¦ if Y^.next = nil then writeln('Дек пуст !') else

¦ if X = Y then Y:= Y^.next else

¦ begin x^.pred^.next:=x^.next;

¦ ¦ {Переброска ссылки next вверху}

¦ ¦ x^.next^.pred:=x^.pred;

¦ ¦ {Переброска ссылки pred внизу}

¦ end;

end.

В этой процедуре введены параметры-переменные: Y - начало дека и Z - ссылка на конец дека. Они необходимы, т.к. здесь могут быть изменены начало и конец дека.

Если Y^.NEXT = NIL, то это означает, что дек пуст и никаких действий не производится. Равенство X = Y показывает, что дек состоит из одного звена, которое удаляется путем присваивания ссылке Y (началу дека) значения указателя на последнее нулевое звено дека. Для остальных случаев все действия производятся, как и в предыдущем примере.

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 (конец очереди).

15. ДЕРЕВЬЯ

15.1 Характеристика древовидной структуры данных

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

Существует несколько способов изображения деревьев: вложения множеств, скобок, графы.

При ВЛОЖЕНИИ МНОЖЕСТВ используются хорошо известные в математике диаграммы Венна. Способ изображения дерева в виде ВЛОЖЕНИЯ СКОБОК менее нагляден, например, A(В(D,E)), C(F,G,H)).

Рассмотрим терминологию, присущую представлению дерева в виде графа:

1) элемент дерева - ВЕРШИНА, из которого связи только выходят, называют КОРНЕМ дерева (в нашем случае А);

2) связи между элементами дерева называются РЕБРАМИ;

3) если вершина В находится на графе ниже А, то В называется ПОТОМКОМ, а А - ПРЕДКОМ В;

4) каждая вершина находится на своем УРОВНЕ, причем корню соответствует 0-й уровень;

5) число уровней (или максимальный уровень) называют ВЫСОТОЙ или ГЛУБИНОЙ дерева;

6) если вершина не имеет потомков, то она называется ЛИСТОМ (в нашем примере F,G,H,D,E - листы);

7) вершины, лежащие между корнем и листьями, называют ВНУТРЕННИМИ.

Выделяют из всех деревьев так называемые УПОРЯДОЧЕННЫЕ деревья - такие, у которых ребра (т.е. соответствующие им элементы), выходящие из каждой вершины, упорядочены по какому-либо признаку. Для деревьев, элементами (вершинами) которых являются целые числа, упорядоченность устанавливается по возрастанию (убыванию) элементов.

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

НАПРИМЕР:

5

/ \

3 10

/ \ / \

2 4 9 12

2 < 3 < 5 < 10 < 12; 2 < 3 < 4;

3 < 10;

2 < 4 < 9 < 12; 9 < 10 < 12.

Особый интерес представляют деревья, у которых из каждой вершины может исходить не более 2-х (т.е. ни одного, одно или два) ребер. Такие деревья называют ДВОИЧНЫМИ или БИНАРНЫМИ, либо деревьями 2-й степени.

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

R

/ \

O W

/ | \ \

E Q X H

Бинарное дерево принято также называть ГЕНЕАЛОГИЧЕСКИМ:

X -внук

/ \

сын - Y Z -дочь

/ \ / \

A B C D

мать отец мать отец

ОПРЕДЕЛЕНИЕ: дерево называется ПРЕДЕЛЬНО (ИДЕАЛЬНО) СБАЛАНСИРОВАННЫМ, если разница между числом вершин в его левых и правых поддеревьях (на всех уровнях) не более 1.

15.2 Построение идеально сбалансированного дерева

Для построения такого дерева используется рекурсивное правило:

1. Пусть требуется построить дерево из N элементов (вершин).

Выберем один из них в качестве корня.

2. Строим левое поддерево с количеством вершин NL = N div 2.

3. Так же строим правое поддерево с числом вершин NR = N-NL-1.

Например, при построении дерева из 5 элементов:

1) один элемент идет на корень;

2) оставшиеся 4 элемента разбиваются на два поддерева:

NL = 2 и NR = 2;

3) в каждом из поддеревьев один элемент идет на корень, а другой - на лист: NL1= 1, NR1= 0.

Очевидно, что для отображения структуры дерева в память ЭВМ требуется построение динамических объектов.

Здесь K-ELEMENT есть вершина дерева, а LEFT и RIGHT - поля ссылок на левую и правую вершины поддеревьев.

Отсюда следует процедура-функция формирования дерева, где используется указанный выше принцип построения рекурсивной функции.

У данной процедуры в качестве параметра-аргумента выступает число элементов (вершин) дерева, а значением функции является ссылка - указатель на следующую вершину (левую и правую). Сами элементы запрашиваются с клавиатуры:

function FORMIRTREE (N: integer): SS;

var Z: SS; NL, NR: integer;

begin

¦ if N = 0 then Z:= nil {Пустое дерево}

¦ else

¦ begin

¦ ¦ NL:= N div 2; NR:= N-Nl-1; new(Z);

¦ ¦ write('Ввести вершину'); readln(Z^.k);

¦ ¦ Z^.right:= FORMIRTREE (NR);

¦ end;

¦ FORMIRTREE:= Z; {Запоминание ссылки на корень дерева}

end.

ПОЯСНЕНИЕ. Сначала все N-1 элементов разбиваем на две части - левую и правую. Затем каждую часть соответственно делим на две. Рекурсия прекращается, когда N становится равным нулю - деление закончено, последняя образованная ссылка указывает на корневой элемент:

			1
	left					right
		2			4
l eft			left
	3		right	5		right

Дерево имеет 2 уровня, на нижнем (втором) уровне располагаются только левые листы (правые отсутствуют из-за нехватки элементов).

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

procedure PRINTTREE (Z: ss; X: integer; var Y: integer);

var I: integer;

begin

¦ Y:= (X-5)/5 - 1;{ Подсчет числа уровней }

¦ if Z <> nil then

¦ begin

¦ ¦ PRINTTREE(Z^.right, X+5, Y);

¦ ¦ for I:=1 to X do write(' ');

¦ ¦ writeln(Z^.k);

¦ writeln;

¦ ¦ PRINTTREE(Z^.left, X+5, Y);

¦ end;

end.

ЗАМЕЧАНИЕ. Эта рекурсивная процедура выводит на экран элементы слева направо, причем крайним левым элементом оказывается корень дерева. Между соседними уровнями процедура печатает 5 пробелов, а между элементами одного уровня - одну строчку. В процедуре параметр Y, как выходной, служит для указания числа уровней построенного дерева. Формула (X-5)/5-1 дает число уровней, т.к. по построению между элементами соседних уровней находится 5 пробелов, а в завершение работы этой процедуры последним печатается самый левый (самый нижний и, значит, самый удаленный от левого края экрана) лист дерева:

Теперь, имея рекурсивную функцию FORMIRTREE формирования дерева и рекурсивную процедуру PRINTTREE печати его элементов, можно записать основную программу построения и печати дерева с указанным числом вершин.

program TREE;

type SS = ^ZVENO;

ZVENO = record

K: integer;

left, right: SS;

end;

var KOL: integer; Y: REAL; DER: SS;

{KOL - число элементов дерева; DER - ссылка на корень дерева}

;

;

begin

¦ write('Введите число элементов дерева');

¦ y:= 0; {Число уровней дерева}

¦ readln (KOL); DER:= FORMIRTREE (KOL);

¦ writeln; writeln(' Д Е Р Е В О:');

¦ PRINTTREE (DER, 5, y); writeln;

¦ writeln(' Всего', y:3:0,' уровня(ей) дерева.');

end.

ПОЯСНЕНИЕ. Дерево, состоящее из пяти элементов (1,2,3,4,5), будет выведено на экран в виде следующего графа:

ДЕРЕВО

15.3 Основные операции над деревьями

Над деревьями, как и над другими связными списками, выполняются те же операции: поиск элемента, вставка элемента в дерево и удаление из него.

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

Итак, процедуру поиска элемента в двоичном дереве организуют в виде рекурсивной процедуры, где есть:

1) входные параметры (параметры-значения) - ссылка на дерево (т.е. на корень дерева, где ищется элемент) и значение элемента поиска;

2) выходной параметр (параметр-переменная) - ссылка на найденный элемент.

Таким образом, имеем следующую процедуру:

procedure POISK(S: SS; ZNACH: integer; var ELEM: SS);

begin

¦ if S <> nil then

if S^.k = ZNACH then ELEM:= S

¦ else

begin

¦ ¦ POISK(S^.left, ZNACH, ELEM);

¦ ¦ POISK(S^.right, ZNACH, ELEM);

¦ end;

end.

ЗАМЕЧАНИЕ. Из самой процедуры видно, что рекурсия заканчивается по достижению последнего элемента дерева, поэтому переменная ELEM получит значение ссылки на последний элемент, равный ZNACH. Если такого элемента в дереве нет, то переменная ELEM не будет определена, т.к. на оператор ELEM:= S программа выходит только при условии S^.K = ZNACH. В этом случае значение переменной ELEM^.K - "мусор".

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

procedure POISK1(S: SS; ZNACH: integer; var ELEM: SS);

begin

¦ if (S^.k >= N1) and (S^.k <= N2) then

¦ begin write(S^.k:3); i:= i+1; end;

¦ if S^.k = ZNACH then begin j:=1;ELEM:= S end

¦ else if S <> nil then

¦ begin

¦ ¦ POISK1(S^.left, ZNACH, ELEM);

¦ ¦ if j = 0 then

¦ ¦ POISK1(S^.right, ZNACH, ELEM);

¦ end;

end.

ПОЯСНЕНИЕ. Данная процедура заканчивает работу либо при нахождении искомого элемента, либо при достижении конца дерева. В ней имеются две глобальные переменные I и J, которые должны быть обнулены в основной программе. Переменная I служит для подсчета просмотренных во время поиска элементов, которые попутно выводятся на печать. При нахождении элемента ZNACH в левом поддереве вырабатывается признак J = 1, препятствующий вхождению поиска в правое поддерево.

Условие (S^.k >= N1) and (S^.k <= N2) необходимо для того, чтобы не выводились на печать K - элементы "сухих" ветвей (выходящих из терминальных вершин) при обходе дерева. Здесь N1 - наименьший и N2 - наибольший из введенных в дерево элементов. Обе эти переменные должны быть определены в основной программе.

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

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

						предыдущее звено;
						новое звено;
					фиксированное звено;

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

Чтобы избежать этой неопределенности, условились делать процедуру вставки по следующему алгоритму:

1) вставлять новый элемент S2 между S и S1;

2) если S ссылается на S1 левым полем, то вставляемый элемент S2 будет также ссылаться на S1 левым полем;

3) если S ссылается на S1 правым полем, то и вставляемый элемент должен ссылаться на S1 правым полем.

а). Левое

б). Правое

S

S

…

…

S2

S2

nil

nil

S 1

S1

…

…

Отсюда следует процедура вставки (нерекурсивная):

procedure VSTAVKA (S, S1, S2: SS);

begin

¦ if S^.left = S1 then

¦ begin

¦ ¦ S^.left:= S2;

¦ ¦ S2^.left:= S1;

¦ ¦ S2^.right:= nil;

¦ end

¦ else

¦ begin

¦ ¦ S^.right:= S2;

¦ ¦ S2^.right:= S1;

¦ ¦ S2^.left:= nil;

¦ end;

end.

ЗАМЕЧАНИЕ. В отличие от процедуры POISK здесь нет на входе явного указания на корень дерева. Однако при указании двух соседних вершин в ссылках на них фигурирует ссылка на корень дерева. Например, для вставки в дерево DER некоего элемента EL между вторым и третьим элементами левого поддерева необходимо выполнить следующие операторы:

new(Z); write ('Введите вставляемый элемент: ');

readln(EL); Z^.k:= EL: Z^.left:= nil; Z^.right:= nil;

VSTAVKA (DER^.left, DER^.left^.left, Z).

На практике ссылка S чаще всего есть результат работы процедуры поиска, т.е. получена путем применения POISK(DER,ZNACH,S). Тогда для вставки элемента Z в левое поддерево вершины S в качестве S1 надо взять S^.left, в противном случае – положить S1=S^.right.

Удаление звена из дерева осуществляется по разным правилам и зависит от характеристики дерева и предметной области его вершин. Здесь возможны различные варианты.

Если вершина Si является терминальной (листом) или из нее выходит только одна ветвь, то удаление реализуется довольно просто - для этого надо скорректировать соответствующую ссылку у вершины предшественника:

а).

…

б).

…

Si-1

Si-1

Si

Si

Si-1

NIL

Si-1

Si+1

Si-1

NIL

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

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

Для первого случая надо перейти в следующее звено по левой ветви, а потом все время идти по правой, пока не найдется NIL.

Для второго - надо перейти в следующее звено по правой ветви, а потом идти все время по левой до NIL.

ПРИМЕР. Пусть требуется удалить в дереве вершину 50.

Для решения этой задачи переходим в правое поддерево на вершину 55 и затем идем все время по левым ветвям к вершине 33, которую ставим на место 50.

Заметим, что такой способ удаления звена с замещением его на другое не нарушает упорядоченности (в смысле отношения порядка в множестве целых чисел). Особенно это важно для дерева поиска, в котором и будет рассмотрена процедура удаления звена.

100 | 100

/ \ | / \

20 120 | 20 120

/ \ \ | / \ \

15 50 130 | 15 33 130

/ \ | / \

30 55 | 30 55

/ / \ | / / \

28 35 60 | 28 35 60

/ \ |

33 50 |

Вид дерева |

ДО удаления | Вид дерева ПОСЛЕ удаления 50

15.4 Дерево поиска

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

a) A б) A

/ \ / \

B C C B

/ / \

D D E

Сбалансированное Несбалансированное

Организация ИДЕАЛЬНО СБАЛАНСИРОВАННЫХ деревьев не всегда оправдана, т.к. деревья часто строят для поиска того или иного элемента в структуре данных. В дереве общего вида для поиска одного элемента иногда приходится перебрать и все другие, если этот элемент является листом. Такой путь нерационален, т.к. теряется сама идея построения дерева. Лучше создать линейный список в виде стека, дека или очереди. Вот почему для упрощения поиска при организации дерева его строят в виде ДЕРЕВА ПОИСКА, т.к. число переборов для нахождения нужного элемента здесь значительно меньше.

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

Например, пусть заданы элементы: 10,5,7,12,15,3,7,9. Расположить их в виде дерева поиска с корнем 10.

10

/ \

5 12

/ \ \

3 7 15

\

9

Можно заметить, что в дереве поиска, как и в упорядоченном дереве общего вида, самая левая ветвь состоит из убывающих вершин, а самая правая - из возрастающих.

Рассмотрим теперь процедуру формирования дерева поиска с учетом принципа его построения:

procedure TREEPOISK(var S: SS; ZNACH: integer);

begin

¦ if S = nil then begin

¦ ¦ new(S); S^.k:= ZNACH;

¦ ¦ S^.left:= nil;

¦ ¦ S^.right:= nil; S^.n:= 1;

¦ end

¦ else

¦ if ZNACH < S^.k then TREEPOISK(S^.left,ZNACH)

¦ else

¦ if ZNACH > S^.k then TREEPOISK(S^.right,ZNACH)

¦ else S^.n:= S^.n + 1;

end.

ЗАМЕЧАНИЕ. Из этой процедуры видно, что звено дерева поиска уже состоит из четырех полей: К, LEFT, RIGHT и N. Целочисленное поле N добавлено для того, чтобы увеличивать его значение при появлении в дереве нескольких одинаковых элементов. Поле S^.n позволяет узнать для каждой вершины число породивших ее элементов (кратность вершины). Дело в том, что в отличие от сбалансированного дерева, в дерево поиска элемент входит только один раз. Например, если подавать на вход процедуры TREEPOISK элементы 7,5,3,2,8,4,3,1,7,9, то сформируется дерево из вершин 7,5,3,2,8,4,1,9, а в 4-м поле звена 7 (в нашем случае корень дерева) будет находиться 2.

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

var DER: SS; EL: integer;

begin write('Введите элемент: '); readln(EL);

¦ DER:=nil;

¦ while EL <> 0 do begin TREEPOISK(DER, EL);

¦ readln(EL); end;

end.

15.5 Операции над деревом поиска

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

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

Например, пусть в дерево надо вставить элемент 4:

10

/ \

5 12

/ \ / \

3 7 11 15

1) т.к. 4 < 10, то нужно идти в левое поддерево(т.е. на 5);

2) т.к. 4 < 5, следует спуститься ниже 5;

3) т.к. 4 > 3, необходимо вставить этот элемент в правое поддерево.

ÑÕÅÌÀ ÂÑÒÀÂÊÈ

10

/ \

5 12

/ \ / \

3 7 11 15

\

4

Итак, для вставки в дерево DER элемента 4 надо записать оператор TREEPOISK(DER,4).

Заметим еще раз, что рассмотренная выше процедура TREEPOISK, используемая для формирования дерева, может быть применена и для поиска в нем данного элемента. Действительно, если на вход этой процедуры подать элемент, не содержащийся в дереве, то он будет добавлен к этому дереву. Если же элемент S входит в дерево, то его нового добавления не произойдет, а по значению поля S^.n можно узнать о вхождении данного элемента в дерево (S^.n > 1).

Например, для поиска некоторого элемента EL в дереве DER необходимо выполнить TREEPOISK(DER, EL), добавив в процедуре TREEPOISK оператор WRITELN(DER^.N), который следует поставить в начало ее тела (после слова BEGIN). Наличие в этом списке числа 2 говорит о вхождении элемента EL в дерево, причем можно даже узнать его порядковый номер.

Характеристики

Список файлов ВКР