Слияние двух упорядоченных списков

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

Рис. 9.4. Упорядоченные списки

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

На рис. 9.5 показан результат слияния списков.

Рис. 9.5. Список, полученный в результате слияния.

Алгоритм слияния списков реализован в виде функции, значение которой — указатель на список-результат. Этот алгоритм, учитывающий и два вырожденных случая: оба списка пустые и один из двух списков пустой, приведен в листинге 9.5

Примечание

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

Листинг 9.5. Слияние двух списков

function Merge(List1,List2: PNode): PNode;

var p,q,r,s : PNode;

found : Boolean;

Fin : Boolean;

begin

p:=List1; q:=List2;

if (p<>Nil) and (q<>Nil) then begin // оба списка не пустые

if p^.Info<=q^.Info then begin // указатель Result

Result:=p; r:=p; // ставим на начало

end // того списка, чей

else begin // первый

Result:=q; // элемент

r:=q; q:=p; // меньше

end;

found:=false; // еще не найдено место перецепления списков

s:=r; // s — указатель на предыдущий элемент

Fin:=false;

repeat

while (r<>Nil)and not found do begin

// поиск места перецепления

if r^.Info > q^.Info then found:=true

else begin

s:=r; r:=r^.Next;

end

end;

if found then begin // перецепляем списки

s^.Next:=q; s:=r;

r:=q; q:=s; s:=r; found:=false;

end

else begin // дописываем список

s^.Next:=q;

Fin:=true;

end;

until Fin;

end else // один или оба пустых списка

if p=Nil then Result:=q else Result:=p

end; // Merge

Создадим проект, иллюстрирующий слияние списков. На форме, приведенной на рис. 9.6, выставим компоненты:

q для каждого из исходных списков:

компонент Edit ввода очередного значения;

кнопка вставки элемента в список;

компонент Panel вывода списка;

q кнопка Выполнить, при нажатии на которую осуществляется слияние (перецепление) списков;

q компонент Panel вывода списка-результата;

q кнопка Очистить, удаляющая старый список-результат и проводящая очистку полей и инициализацию.

Рис. 9.6 Форма для иллюстрации слияния двух упорядоченных списков.

Формирование исходных списков осуществляется обычным образом, причем добавлять значения можно то в один, то в другой список. Однако после слияния списков — после нажатия на кнопку Выполнить — исходные списки перестают существовать, так как образуется один список‑результат. Поэтому обработчик события Click кнопки учитывает контекст события: после слияния вставка нового значения в несуществующий уже список теряет смысл. Для определения, было ли слияние, используется булевская переменная MergeYes. В листинге 9.6 приведен обработчик события Click кнопки для первого списка (для второго списка обработчик аналогичен).

Листинг 9.6. Вставка в один из списков. Форма Слияние двух упорядоченных списков (обработчик события Click кнопки )

procedure TFormMergeList.SpeedButtonInsert1Click(Sender: TObject);

var s: string;

x: integer;

r: PNode;

begin

if not MergeYes then begin // если слияния не было,

s:=EditInsert1.Text; // считываем

x:=StrToInt(s); // элемент

Insert(List1,x); // и вставляем в список1

s:='';

r:=List1;

while r<>nil do begin // собираем список для вывода

s:=s+' '+IntToStr(r^.Info);

r:=r^.Next;

end;

Panel1.Caption:=s; // вывод результата

EditInsert1.Text:='';

EditInsert1.SetFocus;

end else begin // слияние было, очистка всех полей

Panel1.Caption:='';

Panel2.Caption:='';

DelList(res);

List1:=Nil; List2:=Nil; // инициализация списков

Panel3.Caption:='';

MergeYes:=False;

EditInsert1.Text:='';

EditInsert2.Text:='';

EditInsert1.SetFocus;

ShowMessage('Все сначала: создание списков и слияние');

end;

end;

Представляется интересным сравнить листинг 9.2 и листинг 9.6.

Обработчик события Click кнопки Выполнить:

Листинг 9.7.

procedure TFormMergeList.ButtonExecuteClick(Sender: TObject);

var s : string;

x : integer;

begin

if not MergeYes then begin // если слияния не было

res:=Merge(List1,List2); // слияние

s:='';

while res<>nil do begin // собираем список для вывода

s:=s+' '+IntToStr(res^.Info);

res:=res^.Next;

end;

Panel3.Caption:=s;

MergeYes:=True; // признак слияния

end;

end;