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

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

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

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

Var head, q, r, v: TPoint;

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

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

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

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

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

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

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

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

New(v);

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;

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

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

Интерфейс: