Циклические списки.

Операция включения элемента в циклический список аналогична операции включения элемента в линейный список.

p <> LST – условие прохождения по списку.

При удалении элементов из списка проверить, не является ли список пустым. Если список пуст, вывести сообщение «Пусто».

Соединение двух циклических списков в один.

procedure concatLst(var L1, L2: List);

var p: List;

begin

if L1 = nil then exit;

if L2 = nil then begin

L2 := L1;

exit;

end;

p := L1.^next;

L1^.next := L2^.next;

L2^.next := p;

end;

Задание: выбирается число n и одно из имён. При заданном порядке расположения солдат в круге, известном числе n и известном солдате, с которого начинается счёт, окружить солдата, который поедет за подмогой.

1) Формируется циклический список. Окончание ввода имён – ввод пустой строки.

2) Ввод числа n и имени солдата, с которого начинать счёт.

Далее идёт проход по циклическому списку с целью нахождения узла, где содержится введённое имя. Если солдата с таким именем в списке нет, вывести сообщение и запросить новое имя. Если имя есть, реализовать задачу удаления солдата из списка. После этого счёт продолжается до следующего узла, и так до тех пор, пока не останется 1 узел.

Также вывести имена удалённых солдат.

Пример использования списков.

Циклический список можно использовать для сложения длинных целых положительных чисел.

45,9763,4972,1069,8463

Функция просматривает оба списка с одновременным формированием четырёхзначных сумм.

CARRY = SUM div 10000

SUM – сумма четырёхзначных чисел.

Двунаправленные связанные списки.

Каждый узел такого списка имеет два указателя. Один указатель ссылается на следующий элемент, второй – на предыдущий.

type LISTELEM = … ;

List2 = ^LINK;

LINK = record

elem: LISTELEM;

predc, next: List2;

end;

Удаление из списка.

q := p^.predc;

pq := p^.next;

q^.next := pq;

pq^.predc := q;

dispose(q);

Включение в список.

new(q);

q^.next := p^.next;

p^.next := q;

pq := q^.next;

pq^.predc := q;

q^.predc := p;

Реализация очередей.

Очередью называется упорядоченный набор элементов

Извлечение которых возможно с одного конца, называемого началом очереди, а добавлением в другой конец.

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

FIFO (first in first out)

Для работы с очередью необходимы следующие операции

1) создать пустую очередь или очистить очередь

2) является ли очередь пустой

3) поместить элемент в конец очереди

4) удалить из очереди первый элемент

Очередь можно реализовать тремя способами.

Первый способ - реализация очереди с помощью массива.

>>для очереди отводится массив из n компонентов

В котором элементы очереди занимают группу соседних компонентов

Когда очередь при такой реализации достигает правого края массива,все её элементы сдвигаются к левому краю

Const

N= ;

Type

TE= ;

Turn=record

Begt,endt:0..N; {начало и конец}

Mas:array[1..N] of TE

End;

Операция создании пустой очереди

Procedure delque(var Q:turn);

Begin

Q.begt:=1;

Q.endt:=0;

End;

Function empty(var Q:turn):Boolean;

Begin

Q.endt:=Q.endt=0

End;

Операция постановки в очередь.

Элемент в очередь можно поместить тлько в её конец

Но надо сначала проверить,незаполнена ли она (иначе сместить её по левому краю)

Procedure insert_in_Q(var Q:turn;X:TE);

Var i:integer;

Begin

With Q do begin

If endt=n then

If begt=1 then begin writeln(‘очередь переполнена’); exit

Else {сдвиг очереди к левому краю}

Begin

For i:=begt to endt do

Mas[i-begt+1]:=mas[i];

Begt:=1;

Endt:=endt-begt+1;

End;

Endt:=endt+1;

Mas[endt]:=x

End;

End;

Удаление первого элемента очереди.

Procedure remove(var Q:turn; var X:TE);

If empty(Q) then begin writelen(‘очередь пуста’); exit end;

With Q do begith

X:=mas[begth];

If begt=endt then delque(Q) else begt:=begt+1

End;

End;