Если последнее звено списка имеет ссылку на первое звено как на следующее, а первое звено ссылается на последнее как на предыдущее, то такой список оказывается замкнутым по кольцу и называется кольцевым.
Часто списки строят по иерархическому принципу. В этом случае его записи могут иметь внутреннюю структуру, организованную также по принципу списка (основной список оказывается состоящим из записей-подсписков). В этом случае приходят к многомерным массивам переменного размера.
Ниже следуют фрагменты программ на Паскале записи и чтения элементов в очереди и стеке.
13. СТРУКТУРЫ ПРЯМОГО ДОСТУПА. СПОСОБЫ СОРТИРОВКИ МАССИВА
Рассмотрим несколько способов упорядочивания одномерных массивов по возрастанию величин их элементов. Такая задача называется сортировкой массива.
При решении ее возможны два подхода: использование промежуточного (вспомогательного) массива и сортировка внутри самого массива.
Первый способ, хотя в какой-то степени и проще, неэффективен, т.к. требует увеличения памяти и лишних операций пересылки элементов из одного массива в другой. Поэтому рассмотрим способы сортировки внутри самого массива.
Выделяют 3 основных способа сортировки:
1. Прямое включение.
2. Прямой выбор.
3. Прямой обмен.
Каждый из перечисленных способов имеет свои достоинства и недостатки. Поэтому стараются эти способы улучшить (модернизировать), хотя в принципе все они находятся в рамках одного из указанных направлений.
Суть этого способа такова: в массиве берется i-й элемент и включается (вставляется) на свое место между 1-м и i-м элементами. Эта идея может быть выражена в виде следующего цикла:
FOR I:=2 TO N DO
BEGIN X:=A[I];
<включить X на свое место между A[1] и A[I]> END.
Из указанного видно, что на каждом шаге i все элементы с 1-го до (I-1)-го уже упорядочены, следовательно, при I = N произойдет последняя сортировка и N-й элемент встанет на свое место. Алгоритм должен быть таким, что если I-й элемент стоит в ряду, т.е. не нарушает порядка, то никаких действий совершать не надо, а следует перейти к I+1-му элементу.
Например, рассмотрим сортировку следующего массива:
| -3 | 2 | 4 | 1 | 6 | 3 |
| 1 | 2 | 3 | 4 | 5 | 6 |
Здесь все элементы до четвертого уже упорядочены и сортировка должна произойти при I = 4. Суть метода состоит в том, что среди элементов с 1-го по 4-й ищется такой, который меньше четвертого, равного 1. В нашем случае этим элементом является первый, равный -3. В ходе поиска четвертый элемент 1 запоминается в специальной переменной X, а все элементы циклически сдвигаются на одну позицию вправо:
1-й шаг: 1<4? - да => сдвиг
| -3 | 2 | 4 | 4 | 6 | 3 |
2-й шаг: 1<2? - да => сдвиг
| -3 | 2 | 2 | 4 | 6 | 3 |
3-й шаг: 1<-3? - нет
| -3 | 1 | 2 | 4 | 6 | 3 |
На третьем шаге сдвига не происходит и после него запомненный элемент ставится на свое место, т.е. на место второго элемента ставится четвертый из исходного массива. Поиск и сдвиг идут по циклу WHILE, в котором в качестве условия берется сравнение X < А[I-1].
Продолжая наш пример, заметим, что на пятом шаге никаких действий происходить не будет, а на шестом элемент А[6]=3 должен пойти на четвертое место, сдвигая пятый элемент на шестое место, а четвертый элемент - на пятое место:
3<6? - да => сдвиг
| -3 | 1 | 2 | 4 | 6 | 6 |
3<4? - да => сдвиг
| -3 | 1 | 2 | 4 | 4 | 6 |
3<2? - нет=>
| -3 | 1 | 2 | 3 | 4 | 6 |
Прежде чем переходить к самой программе, заметим, что если I-й элемент должен передвинуться на 1-е место, то в нашем алгоритме для окончания процесса сдвига нужно иметь элемент слева от А[1] для сравнения (барьер). Таким элементом является А[0]. Отсюда заключаем, что в цикле FOR от 2 до N нужно для каждого шага I предусмотреть засылку в А[0] сортируемого элемента.
procedure PRVKLUCH (var MM:MAS);
var I,J,X: integer;
begin
¦ for I:= 2 to N do
¦ begin
¦ ¦ X:=MM[I]; MM[0]:=X; J:=I;
¦ ¦ while X < MM[J-1] do
¦ ¦ begin
¦ ¦ ¦ MM[J]:=MM[J-1]; J:=J-1;
¦ ¦ end;
¦ ¦ MM[J]:=X;
¦ end;
end.
Из этой процедуры видно, что выход из нее происходит тогда, когда (J-1)-й элемент становится меньше I-го элемента. Слева от I-го уже не может быть меньшего элемента, т.к. на каждом шаге все элементы до него уже отсортированы ранее в цикле FOR.
Суть метода состоит в том, что среди всех элементов массива выбирается наименьший и ставится на первое место, а элемент, занимавший первое место, перемещается на место наименьшего. Затем среди оставшихся элементов от второго до N-го проводится та же операция, а именно: среди элементов массива от второго до N-го выбирается наименьший и перемещается на второе место, а элемент, стоящий на втором месте, занимает место наименьшего.
Эта идея реализуется в виде вложенных циклов: внешний - по I от 1 до N-1; внутренний - по J от I+1 до N.
ОБЩАЯСХЕМАПРОГРАММЫ:
for I:=1 to N-1 do
begin
¦ {Запоминание индекса и самого I-го элемента}
¦ for J:=I+1 to N do
¦ begin
¦ {Поиск минимального элемента от I+1 до N}
¦ end;
¦ {Перестановка I-го и минимального элементов}
end.
ОБЩИЙВИДПРОГРАММЫ:
procedure SELECTION (var MM:MAS);
var I,J,K,X: integer;
begin
¦ for I:= 1 to N-1 do
¦ begin
¦ ¦ { Это тело внешнего цикла }
¦ ¦ K:= I; X:= MM[I];
¦ ¦ { Внутренний цикл - поиск MIN элемента }
¦ ¦ for J:= I+1 to N do
¦ ¦ if X > MM[J] then
¦ ¦ begin
¦ ¦ ¦ { Запоминание номера и значения
¦ ¦ ¦ минимального элемента }
¦ ¦ ¦ X:= MM[J];
¦ ¦ ¦ K:= J;
¦ ¦ end;
¦ ¦ { Минимальный и I-й элементы меняются местами}
¦ ¦ MM[K]:= MM[I]; MM[I]:= X;
¦ end;
end.
Проследим работу этой программы на следующем примере:
I=0
| -3 | 2 | 4 | 1 | 6 | 3 |
® исходный массив
I=1
| -3 | 2 | 4 | 1 | 6 | 3 |
® 1-й шаг: ничего не происходит, т.к. минимальный элемент на своем месте
I=2
| -3 | 1 | 4 | 2 | 6 | 3 |
® 2-й шаг: 2-й и 4-й поменялись местами
I=3
| -3 | 1 | 2 | 4 | 6 | 3 |
® 3-й шаг: 3-й и 4-й поменялись местами
I=4
| -3 | 1 | 2 | 3 | 6 | 4 |
® 4-й шаг: 4-й и 6-й поменялись местами
I=5
| -3 | 1 | 2 | 3 | 4 | 6 |
® 5-й шаг: 5-й и 6-й поменялись местами
Всего N-1=5 шагов. Часть из них результативна (2,3,4,5), а первый шаг никаких перестановок не производит. Отметим, однако, что даже при нерезультативных ходах все циклы работают до конца и за время сортировки внутренний цикл выполнится N(N-1)/2 раз.
Суть его заключается в том, что в отличие от первых двух методов, где просмотр массива шел по увеличению индекса I, т.е. от начала массива к концу, здесь производится проход от конца массива к началу до I-го элемента, и каждый раз, если А[J-1] > А[J], они меняются местами.
В этом методе также есть два вложенных цикла: внешний цикл поидет от 2 до N, а внутренний по J - от N до I:
for I:= 2 to N do
for J:= N downto I do
{ Обмен местами (всплытие) более легкого элемента }
end;
end.
ОБЩИЙ ВИД ПРОГРАММЫ:
procedure BUBLESORT (var MM: MAS);
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=2 | I=3 | ||||||||||||
| J=6 | -3 | 2 | 4 | 1 | 3 | 6 | J=6 | -3 | 1 | 2 | 4 | 3 | 6 |
| J=5 | -3 | 2 | 4 | 1 | 3 | 6 | J=5 | -3 | 1 | 2 | 3 | 4 | 6 |
| J=4 | -3 | 2 | 1 | 4 | 3 | 6 | J=4 | -3 | 1 | 2 | 3 | 4 | 6 |
| J=3 | -3 | 1 | 2 | 4 | 3 | 6 | J=3 | -3 | 1 | 2 | 3 | 4 | 6 |
| J=2 | -3 | 1 | 2 | 4 | 3 | 6 |
Все остальные обработки при I = 4, 5, 6 идут впустую, т.к. массив уже упорядочен. В других ситуациях может случиться так, что сортировка закончится только на последнем цикле.
Все три метода простой сортировки далеки от идеала, однако в некоторых ситуациях их эффективность может оказаться различной. В связи с этим можно выделить следующие случаи: