Полустатические структуры данных

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

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

Finally

Try

Begin

Begin

Var

Begin

Else

End

Begin

Begin

ToInx - индекс в результирующем списке, куда будут копироваться

Begin

Mid, i, j, ToInx,

Var

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

{ Сортировка слиянием }

procedure MSS(aList: TList; aFirst, aLast: Integer;

aCompare: TCompareFunc; aTempList: PPointerList);

FirstCount: Integer;

{ Вычислить среднюю точку }

Mid:=(aFirst + aLast) div 2;

{ Рекурсивная сортировка слиянием первой и второй половин списка }

if aFirst < Mid then

MSS(aList, aFirst, Mid, aCompare, aTempList);

if (Mid+1) < aLast then

MSS(aList, Mid+1, aLast, aCompare, aTempList);

{ Скопировать первую половину списка во вспомогательный список }

FirstCount:=Mid-aFirst+1;

Move(aList.List[aFirst], aTempList[0], FirstCount*SizeOf(Pointer));

{ Установить значения индексов: i - индекс для вспомогательного списка

(т.е. первой половины); j - индекс для второй половины списка;

отсортированные элементы }

i:=0; j:=Mid+1; ToInx:=aFirst;

{ Выполнить слияние двух списков; повторять

пока один из списков не опустеет }

while (i < FirstCount) and (j <= aLast) do

{ Определить элемент с наименьшим значением из следующих

элементов в обоих списках и скопировать его; увеличить

значение соответствующего индекса }

if aCompare(aTempList[i], aList.List[j]) <= 0 then

aList.List[ToInx]:=aTempList[i];

Inc(i);

aList.List[ToInx]:=aList.List[j];

Inc(j);

end;

{ В объединенных списках есть еще один элемент }

Inc(ToInx);

end;

{ Если в первом подсписке остались элементы, скопировать их }

if i < FirstCount then

Move(aTempList[i], aList.List[ToInx], (FirstCount - i)*SizeOf(Pointer));

{ Если во втором списке остались элементы, то они уже находятся в нужных

позициях, т.е. сортировка завершена; если второй список пуст, сортировка

также завершена }

end;

procedure MergeSortStd(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

TempList: PPointerList;

ItemCount: Integer;

{ Есть хотя бы два элемента для сортировки }

if aFirst < aLast then

{ создать временный список указателей }

ItemCount:=aLast-aFirst+1;

GetMem(TempList, ((ItemCount+1) div 2)*SizeOf(Pointer));

MSS(aList, aFirst, aLast, aCompare, TempList);

FreeMem(TempList, ((ItemCount+1) div 2)*SizeOf(Pointer));

end;

end;

end;

Рис. 4.2. Пример слияния двух массивов.

Контрольные вопросы

1. Перечислите свойства статических структур данных.

2. Приведите примеры объявления и применения вектор и массивов.

3. В чем состоит преимущество их использования открытых массивов?

4. Что такое множества? Описание и применение множеств.

5. Записи упакованные, неупакованные, с вариантами.

6. Опишите алгоритмы линейного и бинарного поиска.

7. Перечислите стратегии сортировки, приведите классификацию алгоритмов сортировки.

8. Опишите алгоритмы сортировки выборкой, пузырьковой, вставками.

9. Опишите разновидности алгоритмов сортировки методом Шелла.

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

Полустатические структуры данных характеризуются следующими признаками:

- переменная длина и простые процедуры ее изменения;

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

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

Дата добавления: 2014-01-07