Сортированные списки
Широкое применение связные списки получили при решении задач сортировки последовательностей данных. Пусть имеется связный список из трех чисел, расположенных по возрастанию от головы к хвосту списка: 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). Интерфейс: ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|