Очередь и дек

Очередь и дек.

Условие задачи (см также 5.2.2)

Создать С1 на основе С2-связногоного списка. Данные взять из файла. Создать еще две(а) С1, в первую(ый) поместить данные удовлетворяющие условию, во вторую(ой) – не удовлетворяющие.

Вывести заданный и созданные С1. Для деков – все данные выводить дважды: в прямом и обратном порядке. Предусмотреть возможность сохранения отчета (что было дано, и что получилось) в текстовый файл.

Условие отбора и структуру информационной части смотрите в задаче 5.2.2

Варианты заданий

№	С1	С2
Нечетные 1,3,5,7,9,…	Дек	Дву-
Четные 2,4,6,8,10,…	Очередь	Одно-

Пример

Процедуры создания двух новых очередей

С созданием дополнительной очереди

var

ListDN, ListDK: PElem;

ball: byte;

chel: Tinfo;

begin

ListDN:=nil; ListDK:=nil;

FreeList(Res1Nachalo, Res1Konec);

FreeList(Res2Nachalo, Res2Konec);

ball:=UpDown2.Position;

while NachaloQueue<>nil do

begin

chel:=NachaloQueue^.info;

if chel. b > ball then

Dobavit(Res1Nachalo, Res1Konec, chel)

else

Dobavit(Res2Nachalo, Res2Konec, chel);

DelFirst(NachaloQueue, KonecQueue);

Dobavit(ListDN, ListDK, chel);

end;

NachaloQueue:=ListDN;

KonecQueue:=ListDK;

End;

Без создания дополнительной очереди – перекладываем
рассмотренный элемент в конец той же очереди

var

ListCN, ListCK: PElem;

ball: byte;

begin

ball:=UpDown2.Position;

ListCN:=NachaloQueue; ListCK:=KonecQueue;

if NachaloQueue<> nil then

repeat

if ListCN^.info. b > ball then

Dobavit(Res1Nachalo, Res1Konec, ListCN^.info)

else

Dobavit(Res2Nachalo, Res2Konec, ListCN^.info);

Perestavit(ListCN, ListCK);

until ListCN=NachaloQueue;

end;

procedure Perestavit(var ListCN, ListCK: PElem);

begin

if ListCN <> ListCK then

begin

ListCK^.next:=ListCN;

ListCN:=ListCN^.next;

ListCK:=ListCK^.next;

ListCK^.next:=nil;

end;

end;

Информационно-логические структуры:

Очередь

(FIFO - First In First Out)

Данные:

Адрес головы очереди,

Адрес хвоста очереди.

Допустимые операции:

Создать очередь из 1 элемента;

Добавить элемент в хвост очереди;

Удалить элемент из головы очереди;

Проверка на отсутствие элементов (пустая очередь);

Узнать/Взять значение информационной части первого элемента.

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

Дек (двухконечная очередь)

DEQ (Double Ended Queue)

Данные:

Адрес головы дека,

Адрес хвоста дека.

Допустимые операции:

Создать дек из 1 элемента;

Добавить элемент в голову/хвост дека;

Удалить элемент из головы/хвоста дека;

Проверка на отсутствие элементов.

Очистить дек (удалить все элементы)

Узнать/Взять значение информационной части первого или последнего элемента.

Для работы с элементами дека используется перемещение элементов из головы в хвост, с запоминанием прежнего конца дека, чтобы не зациклиться; или при просмотр элементов с конца – наоборот, перемещение элементов из хвоста в голову, с запоминанием прежней головы дека, чтобы не зациклиться. А также можно использовать дополнительный дек.