Динамические структуры данных (реализация в виде объектов)
   
Односвязный список Очередь (FIFO: First In First Out) / Приоритетная очередь
Двухсвязный список Стек (LIFO: Last In First Out)
  Дек (Double Ended QUEue)

Примеры реализации динамических структур данных с использованием ООП.

Внимание:

В качестве базового типа для всех структур приведенных ниже используется тип Integer (который при желании можно заменить на любой встроенный тип Паскаля: числовой, логический, символьный или строковый). Для подстановки в TType (см. присоединенный модуль item.pas) типа, определенного пользователем может потребоваться корректировка кода (функций сравнения и вывода на печать, которые не определены для пользовательских типов).


Односвязный список

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

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

Линейные связные списки являются простейшими динамическими структурами данных.

(интерфейсная часть модуля):
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.
Скачать реализацию односвязного списка с примером использования можно здесь:
list.rar


Двухсвязный список

Двухсвязный список отличается от односвязного наличием пары указателей в каждом элементе: на предыдущий элемент и на следующий...

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

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


Очередь (FIFO: First In First Out)

Очередью 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.
Скачать реализацию очереди с примером использования можно здесь:
queue.rar


Приоритетная очередь

Иногда в некоторых приложениях требуется не просто очередь, которая имеет один "вход", один "выход", и все элементы, поступившие в которую будут извлечены в том же порядке, а очередь с приоритетами, то есть такая структура данных, которая получает элементы, разделенные на несколько групп по приоритетности обработки, и в каком бы порядке данные не были записаны в очередь, обрабатываться первыми всегда будут элементы с наивысшим приоритетом, а последними - с самым низким приоритетом из тех, которые на данный момент находятся в приоритетной очереди...

Существует несколько возможных путей реализации приоритетной очереди:
  1. С использованием связанных списков.

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

  2. С использованием частично упорядоченных деревьев.

    Какие бы списки (упорядоченные или нет) не были выбраны для представления очередей с приоритетами, для выполнения операций вставки/удаления придется затратить время, пропорциональное n (размеру очереди).

    Существует другая реализация очередей с приоритетами, в которой на выполнение этих операций требуется порядка O(logn) шагов, что значительно меньше n для больших значений n, (скажем, для n > 100). Основная идея такой реализации заключается в том, чтобы организовать элементы очереди в виде сбалансированного (по возможности) двоичного дерева. На нижнем уровне, где некоторые листья могут отсутствовать, в таком случае требуется, чтобы все отсутствующие листья в принципе могли располагаться только справа от присутствующих листьев нижнего уровня.

  3. Я хотел бы привести здесь реализацию приоритетной очереди еще одним, третьим способом, который обеспечивает вставку/удаление за константное время... Для реализации воспользуемся приведенным чуть выше типом TQueue (обычная очередь):
    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)

Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last In First Out - "Последним пришел - первым исключается").

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

Основные операции над стеком:
  1. включение нового элемента (push - заталкивать);
  2. исключение элемента из стека (pop - выскакивать);
  3. неразрушающее чтение элемента из вершины стека;
Стек может быть реализован статически - на основе массива - (этот способ рассматривается здесь:
АлгоЛист: Статическая реализация стека на основе массива) или динамически:

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


Дек (Double Ended QUEue)

Дек - особый вид очереди. Это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди.

Операции над деком:
  1. включение элемента спереди;
  2. включение элемента сзади;
  3. исключение элемента спереди;
  4. исключение элемента сзади;
Динамическая реализация дека приведена ниже...

Обратите внимание на использование наследования (вводится тип TDequeItem - наследник TItem). Дело в том, что для реализации Дека используется двухсвязный элемент, а TItem является элементом односвязным. В наследнике (TDequeItem) добавляется указатель на предыдущий элемент...


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



Free Web Hosting