На этом шаге мы рассмотрим формирование однонаправленного списка с изменением порядка поступающих элементов.
Список можно формировать путем постоянной вставки нового элемента после заглавного звена. Такой способ позволит получить список с обратным порядком расположения элементов. При помощи диаграмм "до и после" Д.Кнута рассмотрим формирование однонаправленного списка с изменением порядка поступающих элементов.
1 шаг. Отведем место для переменных рBegin и рAux в статической области:
Var
рBegin, рAux : PtrRec;
Рис.1. Определение места для pBegin и pAux в статической области
2 шаг. В динамической области памяти резервируем место для динамического объекта pBegin и определяем ссылку заглавного звена:
New (pBegin); pBegin^.pNext := Nil ; WriteLn ('Первый элемент '); ReadLn (Elem1);
Рис.2. Определение места для значения, на которое будет ссылаться pBegin
3 шаг. В куче резервируем место для динамического объекта pAux, определяем информационное поле и его ссылку:
New (pAux);
pAux^.Element := Elem1;
pAux^.pNext := Nil;
Рис.3. Определение места для объекта pAux
4 шаг. Определим место нового компонента в списке:
pAux^.pNext := pBegin^.pNext; pBegin^.pNext := pAux;
Рис.4. Определение места нового компонента в списке
WriteLn ('Следующий элемент '); ReadLn (Elem);
5 шаг. В куче резервируем место для динамического объекта pAux, определяем информационное поле и его ссылку:
New (pAux);
pAux^.Element := Elem2;
pAux^.pNext := Nil;
Рис.5. Определение места для объекта pAux
6 шаг. Определим место нового компонента в списке:
pAux^.pNext := pBegin^.pNext; pBegin^.pNext := pAux;
Рис.6. Определение места нового компонента в списке
7 шаг. Процесс (шаги с 3 по 6) продолжается до тех пор, пока ElemN <> 0.
Приведем процедуру формирования списка на языке Pascal:
Procedure Create_List_D (var pBegin: PtrRec); var pAux : PtrRec; Elem : TypeElement; Begin New (pBegin); pBegin^.pNext := Nil; Write ('Введите последовательность... '); ReadLn (Elem); While Elem <> 0 do Begin New (pAux); pAux^.Element := Elem; pAux^.pNext := Nil; pAux^.pNext := pBegin^.pNext; pBegin^.pNext := pAux; ReadLn (Elem); End; Writeln; End;
На следующем шаге мы рассмотрим cтеки, сформированные на базе однонаправленных списков.