1.Очереди и операции над ними.
Очередь – линейный список, элементы в который добавляются только в конец, а исключаются из начала.
При программировании на Паскале также считается, что для очереди не существует обход элементов. Доступ возможен только к нижнему элементу структуры.
Итак, очередь – это вид связанного списка, в котором извлечение элементов происходит с начала списка, а добавление новых элементов – с конца.
Очередь является динамической структурой – с течением времени изменяется и ее длина, и набор составляющих ее элементов.
Опишем очередь на языке программирования:
Type
EXO = ^O;
O = record
Data : integer;
Next : EXO;
end;
Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.
В очереди, в силу ее определения, доступны две позиции: ее конец, куда заносятся новые элементы, и ее начало, откуда извлекаются элементы. Поэтому для работы с очередью необходимо описать две переменные:
Var
Begin, End : EXO; где Begin – соответствует началу очереди и будет использоваться для вывода элемента из очереди, End – соответствует концу очереди и будет использоваться для добавления новых элементов в очередь.
Занесение элемента в очередь
Занесение элемента в очередь соответствует занесению элемента в конец списка.
Procedure writeO(Var BeginO, EndO : EXO; c : integer);
Var
u : EXO;
Begin
new(u);
u^.Data := c;
u^Next := Nil;
if BeginO =Nil {проверяем пуста ли очередь}
then
BeginO := u {ставим указатель начала очереди на первый созданный элемент}
else
EndO^.Next := u; {ставим созданный элемент в конец очереди}
EndO := u; {переносим указатель конца очереди на последний элемент}
End;
2. Сортировка слиянием
Различают две модификации данного метода: простое двухпутевое слияние и естественное двухпутевое слияние. Идея метода основана на том, что если имеются два упорядоченных массива, то за один цикл их можно слить в один упорядоченный массив.
При простом слиянии исходный массив разбивается на n цепочек, в каждой из которых содержится по одному элементу. Далее выполняется слияние первой цепочки с последней, второй с предпоследней и т.д. Результаты цепочки в два раза длиннее, записываются поочередно в начало или в конец нового массива. Так как на каждом шаге слияния длины цепочек удваиваются, то достаточно выполнить log2n шагов.
Естественное двухпутевое слияние отличается от простого только первым шагом первоначальным разбиением на цепочки, которое выполняется естественным способом.
Как видим, количество цепочек может быть значительно меньше n, что позволит несколько ускорить сортировку. То, что количество элементов в сливаемых цепочках различно, никакой роли при организации слияния не играет. В данном случае незначительно усложняется алгоритм из-за того, что один «средний» элемент может попасть в две цепочки.
Пример работы алгоритма на массиве 3 7 8 2 4 6 1 5..
Билет № 25