| Динамические структуры данных (реализация в виде объектов) | |
| Односвязный список | Очередь (FIFO: First In First Out) / Приоритетная очередь |
| Двухсвязный список | Стек (LIFO: Last In First Out) |
| Дек (Double Ended QUEue) | |
Примеры реализации динамических структур данных с использованием ООП.
Внимание:
unit list;
interface
uses item; { Описание самого элемента списка }
type
tlist = object
first, last: ptitem;
{ Инициализация }
constructor init;
{ Удаление }
destructor done;
{ Инвертирование списка }
procedure invert;
{ Добавление элемента в конец списка }
procedure append(x: ttype);
{ Добавление элемента в начало списка }
procedure insert(x: ttype);
{ Функция, проверяющая, присутствует ли элемент X в списке }
function present(x: ttype): boolean;
{ Функция, возвращающая адрес первого элемента со значением X }
function find(x: ttype): ptitem;
{ Функция, удаляющая ВСЕ вхождения элементов со значением X }
function remove(x: ttype): integer;
{ Добавление элемента ПЕРЕД тем, адрес которого передается в P }
procedure insert_before(p: ptitem;
x: ttype);
{ Добавление элемента ПОСЛЕ того, адрес которого передается в P }
procedure insert_after(p: ptitem;
x: ttype);
{ Проверка пустоты списка }
function empty: boolean;
{ Распечатка содержимого списка }
procedure print;
private
end;
implementation
...
Пример использования:
uses list;
var
il: tlist;
i: integer;
begin
il.init;
for i := 1 to 10 do
il.append(2 * i);
il.print;
il.insert_before(il.find(14), 25);
il.print;
il.insert_after(il.find(10), 25);
il.print;
writeln('items deleted: ', il.remove(25));
il.print;
il.invert;
il.print;
il.done
end.
Скачать реализацию односвязного списка с примером использования можно здесь:unit list_dx;
interface
uses item_dx; { Описание самого элемента списка }
type
tlist = object
first, last: ptitem;
{ Инициализация }
constructor init;
{ Удаление }
destructor done;
{ Инвертирование списка }
procedure invert;
{ Добавление элемента в конец списка }
procedure append(x: ttype);
{ Добавление элемента в начало списка }
procedure insert(x: ttype);
{ Функция, проверяющая, присутствует ли элемент X в списке }
function present(x: ttype): boolean;
{ Функция, возвращающая адрес первого элемента со значением X }
function find(x: ttype): ptitem;
{ Функция, удаляющая ВСЕ вхождения элементов со значением X }
function remove(x: ttype): integer;
{ Добавление элемента ПЕРЕД тем, адрес которого передается в P }
procedure insert_before(p: ptitem;
x: ttype);
{ Добавление элемента ПОСЛЕ того, адрес которого передается в P }
procedure insert_after(p: ptitem;
x: ttype);
{ Проверка пустоты списка }
function empty: boolean;
{ Распечатка содержимого списка }
procedure print;
private
end;
implementation
...
Пример использования:
uses list_dx;
var
ix: integer;
myList: tlist;
Begin
myList.init;
myList.print;
for ix := 1 to 5 do
myList.append(ix);
mylist.append(1);
myList.print;
writeln(myList.remove(1), ' element(s) removed ...');
myList.print;
myList.done;
end.
Скачать реализацию двухсвязного списка с примером использования можно здесь:
Очередь (FIFO: First In First Out)
unit queue;
interface
uses item; { Описание самого элемента списка }
type
pttype = ^ttype;
tqueue = object
{ Инициализация }
constructor init;
{ Удаление }
destructor done;
{ Занесение элемента в очередь }
procedure put(x: ttype);
{ Извлечение элемента из очереди }
function get(var x: ttype): boolean;
{ Проверка пустоты очереди }
function empty: boolean;
{ Распечатка содержимого очереди }
procedure print;
private
head, tail: ptitem;
end;
implementation
...
Использование очереди:
uses item, queue;
var
ist: tqueue;
i: integer;
x: ttype;
begin
ist.init;
for i := 1 to 15 do
ist.put(12*i);
ist.print;
for i := 1 to 5 do
if ist.get(x) then writeln(x);
ist.print;
ist.done
end.
Скачать реализацию очереди с примером использования можно здесь:uses item, queue;
type
{ Описываем все возможные приоритеты, которые должны обрабатываться очередью }
tpriority = (
p_critical, { Наивысший приоритет }
p_very_important,
p_important,
p_information { Самый низкий приоритет }
);
type
{ Тип заявки, состоящий из элемента данных, с которым работает TQueue, и ее приоритета }
tinfo = record
data: ttype;
priority: tpriority;
end;
{
Тип - приоритетная очередь: содержит в себе столько "обычных" очередей,
сколько уровней приоритетности заявок она должна обрабатывать...
Это немного увеличивает размер данной структуры, но дает значительное ускорение,
за счет того что как удаление так и добавление происходят за линейное время, и не
требуется никаких перестановок (или поиска) элементов, как в двух описанных выше
случаях.
}
tpriorityqueue = object
qs: array[tpriority] of record
q: tqueue;
has: boolean;
end;
constructor init;
destructor done;
procedure put(x: tinfo);
function get(var x: ttype): boolean;
procedure print;
end;
constructor tpriorityqueue.init;
var p: tpriority;
begin
for p := low(tpriority) to high(tpriority) do
with qs[p] do begin
q.init; has := false;
end;
end;
destructor tpriorityqueue.done;
var p: tpriority;
begin
for p := low(tpriority) to high(tpriority) do
with qs[p] do q.done;
end;
procedure tpriorityqueue.put(x: tinfo);
begin
with qs[x.priority] do begin
q.put(x.data); has := true;
end;
end;
function tpriorityqueue.get(var x: ttype): boolean;
var p: tpriority;
begin
get := true;
for p := low(tpriority) to high(tpriority) do
if qs[p].has then begin
qs[p].q.get(x);
qs[p].has := not qs[p].q.empty;
exit;
end;
get := false;
end;
procedure tpriorityqueue.print;
var p: tpriority;
begin
for p := low(tpriority) to high(tpriority) do begin
write('P = ', ord(p), ' '); qs[p].q.print;
end;
end;
var
i: integer;
the_queue: tpriorityqueue;
x_data: ttype;
x_info: tinfo;
begin
the_queue.init;
for i := 1 to 20 do begin
x_info.priority := tpriority(random(ord(high(tpriority)) + 1));
x_info.data := random(100);
writeln('adding: priority = ', ord(x_info.priority):3,
', data = ', x_info.data:4);
the_queue.put(x_info);
end;
the_queue.print;
while the_queue.get(x_data) do begin
write(X_data:4);
end;
writeln;
the_queue.done;
end.
После запуска этой программы на выполнение получаем следующий результат:
adding: priority = 2, data = 59 adding: priority = 2, data = 84 adding: priority = 2, data = 85 adding: priority = 2, data = 84 adding: priority = 1, data = 62 adding: priority = 2, data = 38 adding: priority = 1, data = 29 adding: priority = 3, data = 5 adding: priority = 3, data = 27 adding: priority = 1, data = 47 adding: priority = 3, data = 81 adding: priority = 2, data = 47 adding: priority = 2, data = 39 adding: priority = 3, data = 83 adding: priority = 0, data = 33 adding: priority = 0, data = 64 adding: priority = 0, data = 36 adding: priority = 3, data = 95 adding: priority = 3, data = 14 adding: priority = 3, data = 87 P = 0 (queue) <33 64 36 > P = 1 (queue) <62 29 47 > P = 2 (queue) <59 84 85 84 38 47 39 > P = 3 (queue) <5 27 81 83 95 14 87 > 33 64 36 62 29 47 59 84 85 84 38 47 39 5 27 81 83 95 14 87 reading from empty queue reading from empty queue reading from empty queue reading from empty queue(сообщение "reading from empty queue" - тестовое, его вывод можно убрать из метода TQueue.Print)
Стек (LIFO: Last In First Out)
unit stack;
interface
uses item; { Описание самого элемента стека }
type
pttype = ^ttype;
tstack = object
constructor init;
destructor done;
{ Занесение элемента в стек }
procedure push(x: ttype);
{ Извлечение элемента из стека }
function pop(var x: ttype): boolean;
{ Получение указателя на элемент, находящегося на вершине стека без его извлечения }
function top: pttype;
{ Проверка пустоты стека }
function empty: boolean;
{ Распечатка содержимого стека }
procedure print;
private
head: ptitem;
end;
implementation
...
Использование стека:
uses item, stack;
var
ist: tstack;
i: integer;
x: ttype;
begin
ist.init;
for i := 1 to 15 do
ist.push(12*i);
ist.print;
for i := 1 to 5 do
if ist.pop(x) then writeln(x);
ist.print;
ist.done
end.
Скачать реализацию стека с примером использования можно здесь:unit deque;
interface
uses item;
type
ptdequeitem = ^tdequeitem;
tdequeitem = object(titem)
prev: ptitem;
constructor init(x: ttype;
a_prev, a_next: ptitem);
destructor done;
end;
pttype = ^ttype;
tdeque = object
constructor init;
destructor done;
procedure put_start(x: ttype); { Занесение в начало дека }
function get_start(var x: ttype): boolean; { Извлечение из начала дека }
procedure put_finish(x: ttype); { Занесение в конец дека }
function get_finish(var x: ttype): boolean; { Извлечение из конца дека }
{ Проверка пустоты дека }
function empty: boolean;
{ Распечатка содержимого дека }
procedure print;
private
start, finish: ptdequeitem;
end;
implementation
...
Пример использования дека:
uses item, deque;
var
idq: tdeque;
i: integer;
x: ttype;
begin
idq.init;
for i := 1 to 10 do
idq.put_start(12*i);
idq.print;
for i := 1 to 10 do
idq.put_start(12*i);
idq.print;
for i := 1 to 5 do
if idq.get_start(x) then writeln(x);
idq.print;
for i := 1 to 5 do
if idq.get_finish(x) then writeln(x);
idq.print;
idq.done
end.
Скачать реализацию дека с примером использования можно здесь: