Динамические структуры данных (реализация в виде объектов) | |
Односвязный список | Очередь (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.Скачать реализацию дека с примером использования можно здесь: