Задание Г – «ДЕК»
Часть 1
Условие: Смоделироватьдвумя способами новый тип «Дек» («Двухконечная очередь»):
1) на основе ссылочного типа «Линейный двусвязный список»;
2) на основе динамического массива(ов).
Предусмотреть базовые операции:
- проверка на пустоту дека;
- создание пустого дека или из одного элемента;
- добавление элемента в дек;
- взятие элемента из дека (считывание + удаление);
- поменять направление (голова ßà хвост);
- вывод (дописывание) содержимого дека (с текущего конца-головы) в текстовый лог-файл для контроля за состоянием дека после каждой операции с начала и до конца работы программы.
Определение:
Двухсторонняя очередь - двусвязный список/очередь с двумя концами —структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO.
Способ 1
Моделирование новой структуры на основе ссылочного типа «Линейный двусвязный список».
Схема:
Описание нового типа «Дек»:
type
TStruct = record // сведения о заказе
Title: string; // наименование заказа
Hours: integer; // часы поступления
Minutes: integer; // минуты поступления
Seconds: integer; // секунды поступления
end;
PElem =^TElem;
TElem = record
info: Tstruct; //данные
next,prev: PElem //указатель на следующий/предыдуший
end;
Deq = record
listB,ListE: PElem; //указатель на начало/конец
end;
Базовые операции:
function Check(a:deq):boolean; //проверка на пустоту
procedure CreateDeq(var a:deq); //создание дека из одного элемента
procedure Add(var a:deq; r:tstruct); //добавить в конец
function Get(var a:deq):tstruct; //обработать первый элемент и удалить
procedure ChangeDir(var a:deq); //смена направления
procedure addlog(s:string; a:deq);//вывод в лог фаил
A) Проверка дека на пустоту
function Check(a:deq):boolean; // возвращаемое значение - логическое
begin
if (a.listB = nil) or (a.listE = nil) then
result:=True //если указатель на начало
else
result:=false; //или на конец списка равен nil, то список пуст
end;
B) Создание дека из одного нулевого элемента
procedure CreateDeq(var a:Deq);
var elem:pelem; //вспомогательный указатель
begin
new(elem); //выделение памяти
elem^.next:= nil;
a.listB:= elem; //после элемента ничего нет;этот елемент первый
elem^.prev:= nil;
a.listE:= a.listB; //перед эл-том ничего нет; он последний
elem^.info:= nul; //в данные записываем нулевой элемент
end;
const
nul: TStruct = (//нулевой элемент
Title: ' ';
Hours: 0;
Minutes: 0;
Seconds: 0;
);
C) Добавление одного элемента в дек
procedure Add(var a:deq; r:TStruct);
var elem:pelem; //вспомогательный элемент
begin
if check(a) then //если пустой, то создаем и в данные записываем
begin
createDeq(a);
a.listb^.info:= r; // введенное значение
end
else //если не пустой
begin
new(elem); //выделяем память(создаем новый)
elem^.info:= r; //в данные записываем введенное значение
elem^.prev:= a.listE; //предыдущий за новым - хвост
a.listE^.next:= elem; //следующий за хвостом - новый
a.listE:= elem; //текущий элемент делаем последним
a.listE^.next:= nil; //за хвостом дека ничего нет
end;
end;
D) Обработка (получение) первого элемента (с удалением)
function Get(var a:deq):tstruct;
var
r: tstruct;
elem: pelem; //буфер данных и вспомогательный указатель
begin
if check(a) then
result:=nul //если дек пуст - возвращаем нулевой элемент
else
if a.listB=a.listE then //иначе, если начало и конец совпадают
begin
r:= a.listb^.info; //считываем значение
dispose(a.listB); //удаляем
a.listB:= nil;
a.listE:= nil; //и начало значение nil
result:= r; //выводим значение
end
else //если не совпадают
begin
elem:= a.Listb; //ставим вспомогательный указатель на начало списка
r:=elem^.info; //считываем данные из эл-та
a.Listb:=Elem^.next;//первый элемент теперь следующий после 1-ого
dispose (elem); //удаляем бывший первый
a.listB^.prev:=nil; //перед новым первым ничего
result:=r; //выводим значение предыдущего первого
end;
end;
E) Смена направления
procedure ChangeDir(var a:deq);
var i,elem:pelem; //вспомогательные указатели
begin
elem:=a.listB; //устанавливаем вспомогательный элемент на начало
while elem<>nil do //пока список не закончился
begin
i:=elem; //второй вспомогательный указывает на первый вспомогательный
elem:=elem^.next;//первый вспомогательный указывает на след. после него
i^.next:=i^.prev;//меняем связи местами. Следующий теперь предыдущий
i^.prev:=elem;//и наоборот. Предыдущий теперь следующий
end;
a.liste:=a.listb;a.listB:=i; //меняем местами указатель на начало и конец
end;
F) Вывод в лог файл
procedure addlog(s:string; a:deq);
var i:pelem; F:textFile;//вспомогательный указатель и файловая переменная
begin
assignfile (f, 'log.txt');//подключаем лог файл
try if fileexists('log.txt') then //если лог файл существует - дописать
append(f) else Rewrite(F); //иначе создать
try
try
WriteLn(F,DateTimeToStr(Now) + ': ');//дата, время
writeln (f,s); //заголовок лог файл
if check(a) then writeln (f,'Дек пуст.')//если пуст, то выводим соотв.
else begin //если нет: вспомогательный указатель на начало
i:=a.listb;
while i<>nil do //пока список не закончился
begin
with i^.info do //выводим данные
begin
writeln(f, 'Наименование заказа: ', Title);
writeln(f, 'Часы поступления: ', Hours);
writeln(f, 'Минуты поступления: ', Minutes);
writeln(f, 'Секунды поступления: ', Seconds);
end;
writeln(f);i:=i^.next;//переход на новую строку и к следующему эл-ту
end;
end;
except writeln ('Eror writing log file.');end;//вывод в случае ошибки записи
finally writeln(f); CloseFile (f); end;//обязательно закрыть файл
except Writeln ('Eror opening log file.');end;//вывод в случае ошибки чтения
end;
Способ 2
Моделирование новой структуры на основе динамического массива.
Схема:
Описание моделирования дека на основе динамического массива
type
TStruct = record // сведения о заказе
Title: string; // наименование заказа
Hours: integer; // часы поступления
Minutes: integer; // минуты поступления
Seconds: integer; // секунды поступления
end;
mas = array of TStruct; //динамический массив из записей
deq = record
data:mas; //массив с данными
begl,endl:byte;// индекс начала/конца
end;
Базовые операции:
function Check(a:deq):boolean; //проверка на пустоту
procedure CreateDeq(var a:deq); //создание дека из одного элемента
procedure Add(var a:deq; r:tstruct); //добавить
function Get(var a:deq):tstruct; //обработать первый элемент и удалить
procedure ChangeDir(var a:deq);//смена направления
procedure addlog(s:string; a:deq);//вывод в лог фаил