Сортированные списки

Широкое применение связные списки получили при решении задач сортировки последовательностей данных.

Пусть имеется связный список из трех чисел, расположенных по возрастанию от головы к хвосту списка: 3, 5, 12.

Добавим в описание переменных новую ссылку v, которую будем использовать для формирования нового элемента:

Var head, q, r, V: tPoint;

Остальные ссылки выполняют следующие функции:

head– ссылка на первый элемент списка,

r- поисковая ссылка,

v- всегда отстает от нее на шаг, используется для переадресации элементов списка.

Список сформирован, и значениями переменных headиrявляется ссылка на первый элемент списка, а переменная qотстает на шаг отr и ссылается наhead:

Необходимо вставитьэлемент 7на свое место в списке, то естьперед12.

Для включениянового элемента в готовый список выполняются следующие действия:

1.создается новый элемент и заполняется его информационное поле:

New(v);

v^.Inf := 7;

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

While (r <> Nil) Do пока не дошли до конца списка

If (r^.Inf <= v^.Inf) Then если текущий еще меньше вставляемого,

Begin

q := r; то подтягиваем q к r

r := r^.Next; и делаем шаг по списку указателем r

End;

сейчас ссылка rуказывает на элемент12 , то естьr^.Inf = 12,q^.Inf = 5, и q указывает на элемент,послекоторого нужно вставить новый:

3.в ссылочное поле нового элемента помещается адрес, стоящий в ссылочном поле найденного элементаq(т.е. адрес следующего за ним элемента, в данном случае элемента12):

v^.Next := q^.Next;

сейчас оба элемента (7и5) будут соединены с элементом12,

4.в ссылочное поле найденного элемента 5 помещается адрес нового элемента7:

q^.Next := v;

Пример: сформировать сортированный список из элементов5, 3, 12, 7и вывести его на экран (конец ввода – число0).

Интерфейс:

Создание сортированного списка

Первое число: 5

Следующее число: 3

Следующее число: 12

Следующее число: 7

Следующее число: 0

Введено чисел: 4

Список:

3 5 7 12

Программа:

Program Sort_spisok;

Uses CRT;

Type TPoint = ^TElement;

TElement = Record

Inf: Integer;

Next: TPoint;

End;

Var head, q, r, V : tPoint;

Procedure Formir_sort_spisok;

Begin

New(head); head - указатель на голову списка

head^.Inf := 0; количество элементов в списке

head^.Next := Nil; списка еще нет

New(v); формируем первый элемент

Write(‘Первое число: ’);

ReadLn(v^.Inf); вводим его информационную часть

If (v^.Inf=0) если ввели 0,

Then Exit; то выходим из процедуры

head^.Inf := 1; в списке один элемент

v^.Next := head^.Next; вставляем его в голову списка

head^.Next := v; в head^.Next адрес первого элемента списка

New(r); r - поисковая ссылка

Repeat

New(v); формируем очередной элемент

Write(‘Очередное число: ’);

ReadLn(v^.Inf); вводим его информационную часть

If (v^.Inf=0) если ввели 0,

Then Break; то выходим из цикла ввода

head^.Inf := head^.Inf + 1; увеличиваем счетчик элементов на 1

r := head^.Next; поисковик r - на первый элемент списка

q := head; q – отстает на шаг

While (r <> Nil) Do пока не дошли до конца списка

If (r^.Inf <= v^.Inf) Then если текущий еще меньше

Begin вставляемого,

q := r; то подтягиваем q к r

r := r^.Next; и делаем шаг по списку

End

Else Break; иначе выходим из цикла поиска - место найдено

v^.Next := q^.Next; ставим новый элемент на место

q^.Next := v;

Until (v^.Inf = 0);

End;

Procedure Vyvod_spisok; процедура вывода списка

Begin

q := head^.Next; текущую ссылку – на первый элемент

While (q <> Nil) Do пока не конец списка

Begin

Write(q^.Inf:5); выводим очередной элемент

q := q^.Next; ссылку – на следующий элемент

End;

WriteLn;

End;

Begin головная программа

ClrScr;

WriteLn(‘Создание сортированного списка’);

WriteLn;

Formir_sort_spisok; обращение к процедуре создания списка

WriteLn(‘Введено чисел: ’, head^.Inf);

WriteLn(‘Список:’);

Vyvod_spisok; обращение к процедуре вывода списка

ReadLn;

End.