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