На этом шаге мы рассмотрим однонаправленные списки с заглавным звеном..
Желательно, чтобы операции включения элемента в список и исключения элемента из списка проводились единым способом. Для этого необходимо наличие у всех элементов, в том числе и у первого,
предшественника, поэтому в начало каждого списка добавляется заглавное звено.
Заглавное звено располагают в списке первым и никогда не исключают из списка. Информационная часть заглавного звена
или не используется совсем, или используется для специальных целей, например, для хранения количества элементов списка.
Изобразим однонаправленный список с заглавным звеном следующим образом:
Рис.1. Схематичное изображение однонаправленного списка с заглавным звеном
Существует два способа построения однонаправленного списка:
1). Каждый новый элемент добавляется в начало или в конец списка.
2). Каждый элемент добавляется в свое место в списке, например, так, чтобы обеспечить упорядоченность по возрастанию или убыванию.
Изобразим схематично с помощью диаграмм "до и после" Д. Кнута процесс формирования однонаправленного списка с заглавным звеном с сохранением порядка поступления элементов:
1 шаг. Отведем место для указателей pBegin и pAux, переменной Elem в статической области памяти:
Var pBegin, pAux : PtrRec;
Elem : Integer;
Рис.2. Определение места для pBegin и pAux в статической области памяти
2 шаг. В динамической области памяти резервируем место для динамического объекта pBegin:
New (pBegin);
Рис.3. Определение места для объекта pBegin в куче
3 шаг. Пусть вспомогательная переменная pAux ссылается на заглавное звено:
pAux := pBegin;
Рис.4. pAux ссылается на заглавное звено
4 шаг. Определим ссылку заглавного звена (следующего элемента возможно и не будет):
pAux^.pNext := NIL;
Рис.5. pAux ссылается на заглавное звено
5 шаг. Заполняем список, пока не выполнится условие …:
Write ('Задайте первый элемент '); ReadLn (Elem); While Elem <> ... Do Begin New (pAux^.pNext); {резервируем место для нового объекта}
Рис.6. Резервирование места под новое звено
pAux := pAux^.pNext; {передвигаем указатель}
Рис.7. pAux ссылается на новое звено
pAux^.Element :=Elem;
pAux^.pNext := Nil;
Рис.8. Заполнение нового звена списка данными
Write ('Задайте следующий элемент '); ReadLn (Elem); End;
В результате будет построен однонаправленный список с заглавным звеном с сохранением порядка поступления элементов.
Приведенный алгоритм оформим в виде процедуры:
Procedure Create_List (var pBegin : PtrRec); var pAux : PtrRec; Elem : Integer; Begin New (pBegin); pAux := pBegin; pAux^.pNext := Nil;{Построили пустой список с заглавным звеном} Write ('Задайте первое целое число '); ReadLn (Elem); While Elem <> 0 do Begin New (pAux^.pNext); pAux := pAux^.pNext; pAux^.Element := Elem; pAux^.pNext:= Nil; Write ('Следующий элемент '); ReadLn (Elem); End; WriteLn; End;
На следующем шаге мы рассмотрим определение наличия элементов в списке с заглавным звеном.