Разновидности списков

Если порядок элементов в списке не важен, то можно список «зациклить». Для этого в поле Pr последнего элемента заносится адрес первого элемента (см. рис. 10). В этом случае

Рис. 10

для контроля можно хранить адрес одного из элементов списка (не обязательно первого), поскольку список “замкнут” и адрес любого элемента списка содержится в каком-нибудь. Вставку элемента можно осуществить в любое место списка (так как порядок элементов не важен). Поиск какого-либо элемента можно выполнить по значению поля Inf.

В некоторых случаях удобно использовать двунаправленные списки. Отличие этих списков состоит в том, что каждый элемент списка содержит не только адрес следующего элемента, но и предыдущего. Двунаправленный список может быть описан, к примеру, следующим образом:

Type

PEl=^TEl;

TEl=Record

Inf: String[40];

Next, Prior: PEl;

End;

Поля Next и Prior типа PEl, будут хранить адреса следующего и предыдущего элемента соответственно. При описании переменных

Var A, B, C: PEl;

S: String[40];

создание подобного списка (в котором есть хотя бы один элемент) может быть запрограммированы, к примеру, следующим образом:

{1} New(A);

{2} Readln(A^.Inf);

{3} A^.Prior: =nil;

{4} B: =A;

{5} Readln(S);

{6} While Length(S)> 0 do

{7} Begin

{8} New(B^.Next);

{9} C: =B;

{10} B: =B^.Next;

{11} B^.Inf: =S;

{12} B^.Prior: =C;

{13} Readln(S);

{14} end;

{15} B^.Next: =nil;

В этом фрагменте элементы списка создаются до тех пор, пока не будет введена пустая строка. В первых четырёх строках создаётся новый элемент, заполняется поле Inf и его адрес заносится переменные A и B. В поле Prior заносится nil, так как предыдущего элемента нет (рис.11а). Далее запускается цикл создания остальных элементов списка (строки 6-14). На рис. 11(б-г) приводится последовательность создания второго элемента двунаправленного списка. При каждой итерации в цикле: а) создаётся новый элемент (строка 8, рис. 11б);

б) запоминается адрес предыдущего элемента (строка 9);

Рис. 11

в) в переменную B заносится адрес нового элемента (строка 10, рис. 11в);

г) заполняется поле Inf нового элемента (строка 11);

д) в поле Prior заносится адрес предыдущего элемента (строка 12, рис. 11г).

По окончании цикла в поле Next последнего элемента заносится значение nil. На рис. 11д приведён пример уже созданного списка.

Удобство работы с таким списком состоит в том, что по нему можно перемещаться в обоих направлениях. Это может существенно увеличить скорость работы программы при обработке больших списков.

Двунаправленный список также можно зациклить. Для этого в поле Prior первого элемента занести адрес последнего элемента, а в поле Next последнего элемента, наоборот, занести адрес первого элемента. Это можно сделать, добавив к фрагменту создания списка два оператора:

B^.Next: =A;

A^.Prior: =B;

На рис. 12 приведён пример двунаправленного зацикленного списка:

Рис. 12

Пример. Даны два ряда чисел произвольной длины (в каждом не менее двух чисел). Написать программу, сортирующую первый список, а затем добавляющую второй список к первому поэлементно, таким образом, чтобы не нарушить порядок в первом списке.

Program Example;

Uses Crt;

Type

PEl=^TEl;

TEl=Record

Inf: Integer;

Next: PEl;

end;

Var Spisok1, Spisok2: PEl;

Procedure CreateSpisok(var A: PEl);

Var B: PEl;

I: Integer;

begin

New(A);

Readln(A^.Inf);

B: =A;

Readln(I);

While not(I=0) do

begin

New(B^.Next);

B: =B^.Next;

B^.Inf: =I;

Readln(I);

end;

B^.Next: =Nil

end;

Procedure DelSpisok(var A: PEl);

var B: PEl;

begin

While not(A=nil) do

Begin

B: =A;

A: =A^.Next;

Dispose(B);

end;

end;

Procedure PrintSpisok(A: PEl);

var B: PEl;

begin

B: =A;

while not(B=nil) do

begin

Write(B^.Inf: 1, ' ');

B: =B^.Next;

end;

Writeln

end;

Function MinEl(Ab: PEl): Integer;

var B: PEl;

Min: Integer;

begin

Min: =Ab^.Inf;

B: =Ab^.Next;

While not(B=nil) do

begin

If B^.Inf< Min then Min: =B^.Inf;

B: =B^.Next;

end;

MinEl: =Min;

end;

Procedure SortSpisok(var A: PEl);

Var B, C, D: PEl;

I: Integer;

begin

{Переносится первый элемент списка}

I: =MinEl(A);

If I=A^.Inf Then

begin

D: =A;

A: =A^.Next;

end

else

begin

B: =A;

While not(B^.Next^.Inf=I) do

B: =B^.Next;

D: =B^.Next;

B^.Next: =D^.Next;

end;

{Переносятся все остальные элементы списка}

C: =D;

While not(A=nil) do

begin

I: =MinEl(A);

if I=A^.Inf then

begin

C^.Next: =A;

A: =A^.Next

end

else

begin

B: =A;

While not(B^.Next^.Inf=I) do

B: =B^.Next;

C^.Next: =B^.Next;

B^.Next: =C^.Next^.Next;

end;

C: =C^.Next;

end;

C^.Next: =Nil;

A: =D;

end;

Procedure AddSpisok(var A, D: PEl);

Var B, C: PEl;

Begin

While not(D=nil) do

begin

C: =D;

D: =D^.Next;

If C^.Inf< A^.Inf then

begin

C^.Next: =A;

A: =C;

end

else

begin

B: =A;

While not(B^.Next^.Inf> C^.Inf) and not(B^.Next=Nil) do

B: =B^.Next;

C^.Next: =B^.Next;

B^.Next: =C;

end;

end;

end;

Begin

ClrScr;

Writeln('Введите первый список: ');

CreateSpisok(Spisok1);

ClrScr;

Writeln('Введите второй список: ');

CreateSpisok(Spisok2);

ClrScr;

Writeln('Первый список: ');

PrintSpisok(Spisok1);

Writeln('Второй список: ');

PrintSpisok(Spisok2);

Writeln;

SortSpisok(Spisok1);

Writeln('Остсортированный первый список: ');

PrintSpisok(Spisok1);

AddSpisok(Spisok1, Spisok2);

Writeln('Результат объединения списков: ');

PrintSpisok(Spisok1);

DelSpisok(Spisok1);

Readkey;

end.

Контрольные вопросы

1. Какие переменные называются динамическими?

2. Какие переменные являются ссылочными, их применение?

3. Какого типа могут быть динамические переменные?

4. Как создать и удалить динамическую переменную?

5. Опиши структуру списков.

6. Как создать список?

7. Как осуществить вставку в список?

8. Как удалить элемент списка?

9. Как удалить список?

10. Какие разновидности списков Вы знаете?