[стр.-6]
2.1.3. Связанное размещение
Неудобство включения и исключения элементов при смежном представлении происходиттого, что порядок следования
элементов задается неявно требованием, чтобы смежные элементы последовательности находились в смежных ячейках памяти. В результате многие элементы последовательности во время включения или исключения должны передвигаться.
Если требование последовательного размещения элементов опущено, то операции включения и исключения можно выполнить без того, чтобы передвигать элементы. При любом размещении элементов необходимо сохранять информацию о способе их упорядочения. При связанном размещении последовательности „V,, Sl,..., s„ каждому ставится в соответствие указатель /,, который указывает на следующую подобную пару элементов /(+) по списку. Вводится начальный указатель /0, который указывает на первый элемент последовательности. Последний указатель в списке является пустым или нулевым, это признак конца списка. Графическое представление связанного списка можно изобразить следующим образом:
Здесь каждый элемент связанного списка состоит из двух полей. В поле DATA размещен сам элемент последовательности, а в поле NEXT — указатель на следующий за ним элемент. Связанное представление последовательностей облегчает операции
включения и удаления элементов из списка. Например, для исключения второго элемента достаточно переустановить указатели NEXT(/,) = NEXT(/2). Графически это изображается следующим образом:
до исключения — | ||||||
после исключения — , „ о | ь\ it- | — |
Чтобы в последовательность включить новый элемент после необходимо установить указатели:=и
= начальное значение указателя установлено на новый включаемый элемент. Графически включение нового элемента изображается так:
до
включения
«осле включения
4 | ||||||
С помощью связанных распределений мы добились большей гибкости, но потеряли возможность работать с элементами последовательности как с массивами, когда по номеру можно непосредственно обратиться к элементу 5,. В связанном размещении такой возможности не существует, и доступ к элементам последовательности не является прямым и эффективным. Например, при поиске среднего элемента последовательности, даже
при известной ее длине, требуется просмотреть по связанному
списку половину последовательности. В алгоритмах 2.2 и 2.3 приводятся программы, реализованные на языках Pascal и С, связанного формирования списка элементов последовательности. В программы включены операции работы со списком: печать элементов списка, включение новых элементов в список и удаление элементов из списка.
Существуют различные модификации представления последовательностей в виде связанных списков. Следующие два примера позволят, при желании, читателю самостоятельно продолжить получение и других модификаций связанных распределений, отличных от приводимых ниже.
Циклическая форма представления позволяет эффективно возвращаться с последнего элемента списка к первому.
*1 | -Щ | s2 |
%4 | L |
Рис. 2.1. Циклический список
Еще большая гибкость достигается, если использовать дважды связанный список, когда каждый элемент последовательности вместо одного имеет два связанных с ним указателя. В таком списке для любого элемента имеется мгновенный прямой доступ к
предыдущему и последующему элементам. Следует помнить, что
выбор того или иного представления последовательности в значительной степени зависит от типа операций, выполняемых с элементами последовательности.
Рис. 2.2 Дважды связанный f список
—> <— | N | -—* —*\ | lv,l | 0 |
Алгоритм 2.2. Программа на Pascal е включения и исключения элементов из списка
Program(Связанный список данных)
uses CRT;
type
NodePointer=ANode;
Node= RECORD (Элемеш связанного списка} s :Integer; {Элемент последовательности} next .-NodePointer;
{Указатель на следующий элемент}
END;
const first :NodePointer=NIL;
{Указатель начала списка}
{Генерация нового элемента списка} function InitNode: NodePointer;
var newNode :NodePointer;
begin
Now(newKode); {Выделить память новому элементу} newNodeA.s:=Random(99)+1;
нового
newNodeA.next:=NIL; InitNode:=newNode; end;
(Включить новый элемент в начало списка} procedure IncludeNode( newNode: NodePointer );
begin
newNodeA.next:=first; first:=newNode; end;
{Удалить из списка k-й элемент}
