Классическое формирование очереди (по Вирту).

begin

new(p);

p^.inf:=x;

n:=p;

repeat

new(p^.next);

q:=p^.next;

q^.inf:=x;

q^.next:=nil;

p:=q;

until...

Работа со списками.

Работа со стеком и очередью не отличается. Формирование определяет порядок следования элементов в связке.

Проход по списку, удаление элемента, добавление элемента в список алгоритмически идентично для очереди и стека.

1) Проход по списку;

отрывок программы, реализующий проход по списку, при условии, что n – начало списка.

p:=n;

while p< >nil do

begin write (p^.inf);

p:=p^.next;

end;

При прохождении по списку обеспечивается передвижение вспомогательного указателя от начала списка, затем перемещение осуществляется путем присвоения указателю содержимого адресной части текущего значения. Цикл заканчивается, как только значение текущего указателя становится равным «nil».

2) Добавление элемента в список;

Добавление может иметь три варианта:

а) в начало списка;

б) за элементом, обозначенным ключом;

в) перед элементом, обозначенным ключом;

а) Чтобы добавить элемент в начало списка, необходимо сформировать добавляемый элемент, в адресную часть добавляемого элемента записать адрес начала списка; переменную-указатель, в которой хранится адрес начала списка, записать адрес сформированного добавляемого элемента.

Примечание: шаги необходимо выполнять в строгой последовательности, как они перечислены.

Фрагмент программы добавления элемента в начало списка:

new(q);

q^.inf:=x;

q^.next:=n;

n:=q;

Добавление элемента за элементом, обозначенным ключом.

1) Адрес начала списка хранится в переменной n. Ключ (значение информационной части) = X. За элементом со значением Х необходимо добавить элемент. При решении этой задачи вводим ограничения: считаем, что Х – единственный в списке и обязательно присутствует.

2) Формируем добавляемый элемент, не определяя адреса списка элемента (next ничего не присваиваем).

3) Используя дополнительный указатель, передвигаем его по списку до элемента с ключом Х, т.е. этот дополнительный указатель послу выполнения третьего пункта будет равен адресу элемента, информационная часть которого равна «Х».

4) Адрес, который располагается в элементе с ключом Х (next), переносим в адресное поле добавляемого элемента. В адресное поле элемента с ключом записываем адрес добавляемого элемента.

new(q);

q^.inf:=x;

p:=n;

while (p^.inf< >x) and (p< >nil) do p:=p^.next;

q^.next:=p^.next;

p^.next:=q;

Добавление элемента перед элементом с ключом Х в итоге все равно сводится к алгоритму добавления элемента, стоящего за элементом с ключом Х. От предыдущего алгоритма данный отличается только тем, что при передвижении дополнительного указателя анализируется информационное поле не текущего элемента, а элемента, следующего за текущим, т.е. p^.next.inf. При таком анализе необходимо первоначально проверять на равенство ключу значения информационной части первого элемента. Но если ключ расположен в первом элементе, то добавление элемента сводится к добавлению элемента в начало списка.

Фрагмент программы:

new(q);

q^.inf:=x;

if n^.inf=x then

begin q^.next:=n; n:=q;

end else begin

p:=n;

while p^.next^.inf< >x) and (p < >nil) do

p:=p^.next;

q^.next:=p^.next;

p^.next:=q;

end;

Примечание. Обычно добавление элемента в конец списка отдельным случаем не рассматривается. Поэтому если во втором случае ключ будет располагаться в конце списка, то элемент добавится в конец списка автоматически.

Но если алгоритм решения задачи конкретизирован на добавление элемента в конец списка, то необходимо обратить внимание на то, что вспомогательный указатель при добавлении элемента в конец списка необходимо передвинуть на последний элемент списка.

new(q);

q^.inf:=x;

p:=n;

while p^.next < > nil do

p:=p^.next;

q^.next:=p^.next;

p^.next:=q;

end;