Введение

Автомат Калашникова - это самый известный преобразователь стека в очередь.

 

Автор неизвестен

 

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

1.       Линейные динамические структуры данных

1.1.       Динамическое выделение памяти

Процесс выделения памяти во время исполнения программы называется динамическим выделением памяти. Область памяти, в которой размещаются объекты при динамическом распределении называется кучей (англ. heap). Для создания объекта необходимо задать его размер, после чего выделенная область памяти будет помечена занятой, став недоступной при последующих вызовах операции выделения памяти. Противоположная по смыслу операция — освобождение занятой ранее под какой-либо объект памяти. При этом, занятая память будет помечена свободной и ее можно будет использовать в дальнейшем.

По мере создания в программе новых объектов, количество доступной памяти уменьшается. Отсюда вытекает необходимость постоянно освобождать ранее выделенную память. В идеальной ситуации программа должна полностью освободить всю память, которая потребовалась для работы. По аналогии с этим, каждая процедура (функция или подпрограмма) должна обеспечить освобождение всей памяти, выделенной в ходе выполнения процедуры. Некорректное распределение памяти приводит к утечкам ресурсов, когда выделенная память не освобождается. Многократные утечки памяти могут привести к исчерпанию всей оперативной памяти и нарушить работу операционной системы.

Другая проблема — это проблема фрагментации памяти. Выделение памяти происходит блоками — непрерывными фрагментами оперативной памяти (таким образом, каждый блок — это несколько идущих подряд байтов). В какой-то момент, в куче попросту может не оказаться блока подходящего размера и, даже, если свободная память достаточна для размещения объекта, операция выделения памяти окончится неудачей. Данную продлему решает алгоритм дефрагментации, который сдвигает выделенные блоки памяти друг другу, тем самым увеличивая размер свободного пространства.

1.2.       Понятие линейной структуры данных

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

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

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

2.       Связанные списки. Линейные и кольцевые списки. Односвязные и двусвязные списки

2.1.       Понятие связного списка

Связный список – структура данных, используемая для хранения последовательности объектов, поддерживающая следующие операции:

• добавление элемента;
• удаление;
• получения элемента из любой позиции списка.

Связный список реализуется как совокупность записей, каждая из которых хранит полезную информацию и ссылку на следующий и/или предыдущий узел списка.

1

2

3

                                                                                                                                                       Рис. 1.      Связный список.

Следующий кусок кода содержит реализацию узла связного списка, в котором в качестве информации предстает переменная целочисленного типа:

type pnode = ^node; { Тип: указатель на узел списка.      }

node = record       { Объявление узла списка.             }

   data: integer;   { Полезная информация.                }

   next: pnode;     { Ссылка на следующий элемент.        }

end;

Записи часто называются элементами или узлами; часть узла, несущая полезную информацию называется значением, нагрузкой или данными; ссылка иногда называется указателем на следующий или предыдущий элемент. Первый элемент связного списка называется головой, последний – хвостом или концом.

2.2.       Линейные и кольцевые списки

1

2

3

nil

Часто, конец связного списка содержит ссылку на следующий элемент, указывающую «в никуда» (в языке программирования Pascal пустая ссылка обозначается ключевым словом nil). В таком случае связный список называется линейным.

 

                                                                                                                                                     Рис. 2.      Линейный список.

Если конец связного списка содержит указатель на голову, то такой список называется кольцевым.

1

2

3

 

 

                                                                                                                                                    Рис. 3.      Кольцевой список.

2.3.       Односвязные и двусвязные списки

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

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

1

nil

nil

2

 

 

                                                                                                                                                   Рис. 4.      Двусвязный список.

Реализация узла двусвязного списка выглядит следующим образом:

type pnode = ^node; { Тип: указатель на узел списка.      }

node = record       { Объявление узла списка.             }

   data: integer;   { Полезная информация.                }

   prev: pnode;     { Ссылка на предыдущий элемент.       }

   next: pnode;     { Ссылка на следующий элемент.        }

end;

2.4.       Реализация односвязного списка

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

type list = record

   first: pnode;   { Указатель на первый элемент.         }

   count: integer; { Количество элементов.                }

end;

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

{ Операция инициализации списка.                          }

{ Входные параметры:                                      }

{   l - список;                                           }

procedure init(var l: list);

begin

   l.first := nil;

   l.count := 0;

end;

Добавление элемента в связный список является одной из ключевых операций. Обычно, рассматриваются две вариации данного метода:

• добавление элемента в конец списка;
• добавление элемента со вставкой на определенную позицию.

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

{ Операция добавления элемента в связный список.          }

{ Входные параметры:                                      }

{   l - связный список;                                   }

{   item - добавляемый элемент.                           }

procedure add(var l: list; item: integer);

var

   i: pnode;

begin

   { Если ссылка на первый элемент пуста, значит          }

   { в списке нет ни одного элемента. Добавляемый         }

   { элемент будет первым.                                }

   if (l.first = nil) then

   begin

      new(l.first);

      l.first^.data := item;

      l.first^.next := nil;

   end

   { В противном случае доходим до последнего элемента    }

   { списка. Добавляем новый элемент в конец.             }

   else

   begin

      i := l.first;

      while (i^.next <> nil) do

         i := i^.next;

      new(i^.next);

      i^.next^.next := nil;

      i^.next^.data := item;

   end;

   { После добавления увеличиваем количество элементов    }

   { в списке на единицу.                                 }

   inc(l.count);

end;

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

{ Операция добавления элемента в связный список.          }

{ Входные параметры:                                      }

{   l - связный список;                                   }

{   item - добавляемый элемент.                           }

{   index - позиция нового элемента.                      }

procedure insert(var l: list; item: integer;

                 index: integer);

var

   i: pnode;

   j: pnode;

   pos: integer;

begin

   { Если список пуст и мы добавляем новый элемент на     }

   { первую позицию, то он будет в начале списка.         }

   if (l.count = 0) then

   begin

      if (index = 1) then

      begin

         new(l.first);

         l.first^.data := item;

         l.first^.next := nil;

         { Увеличиваем количество элементов.              }

         inc(l.count);

      end;

   end

   { В противном случае список не пуст. Проверяем         }

   { позицию, на которую добавляем новый элемент.         }

   else

   begin

      if ((index > 0) and (index <= l.count)) then

      begin

         { Отдельно обрабатываем добавление на            }

         { первую позицию.                                }

         if (index = 1) then

         begin

            i := l.first;

            new(l.first);

            l.first^.data := item;

            l.first^.next := i;

         end

         { В другом случае сдвигаемся до                  }

         { необходимого элемента списка и на его          }

         { место ставим новый элемент, а старый           }

         { сдвигаем вправо.                               }

         else

         begin

            j := l.first;

            i := l.first;

            pos := 1;

            while (pos < index) do

            begin

               j := i;

               i := i^.next;

               inc(pos);

            end;

            new(j^.next);

            j^.next^.data := item;

            j^.next^.next := i;

         end;

         { Увеличиваем количество элементов в списке. }

         inc(l.count);

      end

   end;

end;

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

{ Операция удаления элемента из связного списка.          }

{ Входные параметры:                                      }

{   l - связный список;                                   }

{   index - позиция.                                      }

procedure remove(var l: list; index: integer);

var

   i, j: pnode;

   pos: integer;

begin

   { Проверяем наличие элементов в списке.                }

   if (l.count <> 0) then

   begin

      { Операцию удаления первого элемента необходимо     }

      { обрабатывать отдельно.                            }  

      if (index = 1) then

      begin

         { Удаляем элемент. Исправляем ссылку на первый.  }

         i := l.first^.next;

         dispose(l.first);

         l.first := i;

         { Уменьшаем число элементов на 1.                }

         dec(l.count);

      end

      { Если удаляем не первый элемент, проверяем         }

      { позицию удаляемого элемента и общее число         }

      { в связанном списке.                               }

      else if ((index > 0) and (index <= l.count)) then

      begin

         pos := 1;

         i := l.first;

         { Циклом доходим до необходимой позиции.         }

         while (pos < index - 1) do

         begin

            i := i^.next;

            inc(pos);

         end;

        { Удаляем элемент. Исправляем ссылки.            }

        j := i^.next^.next;

        dispose(i^.next);

        i^.next := j;

        { Уменьшаем число элементов на 1.                }

        dec(l.count);

      end;

   end;

end;

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

{ Операция получения элемента на определенной позиции.    }

{ Входные параметры:                                      }

{   l - связный список;                                   }

{   index - позиция элемента.                             }

function get(l: list; index: integer): integer;

var

   i: pnode;

   pos: integer;

begin

   { Если позиция не больше нуля, то возвращаем 0.        }

   if (index <= 0) then

      get := 0

   { Если позиция больше количества элементов,            }

   { также возвращаем 0.                                  }

   else if (index > l.count) then

      get := 0

   else

   { В противном случае сдвигаемся к необходимому         }

   { элементу и возвращаем его.                           }

   begin

      i := l.first;

      pos := 1;

      while (pos < index) do

      begin

         i := i^.next;

         inc(pos);

      end;

      get := i^.data;

   end;

end;

3.       Очереди. Реализации на базе массива и списка

3.1.       Понятие очереди

Очередь (англ. queue) – линейная упорядоченная группа объектов, в которой элементы добавляются в конец, а удаляются из начала. В  качестве примера можно представить группу покупателей, находящихся в очереди. Каждый новый покупатель встает в конец очереди. После того, как продавец обслужит текущего покупателя, удаление клиента произойдет из начала очереди.

конец

начало

1

2

3

 

 

                                                                                                                                                                  Рис. 5.      Очередь.

Чтобы добавить элемент в очередь нужно получить доступ к концу очереди, чтобы удалить – к началу. Логически доступ к другим элементам очереди отсутствует, даже если хранить их в структуре данных с произвольным доступом (например, массив). Такой принцип доступа имеет название FIFO (First In, First Out), что по-русски означает «Первым пришел – первым ушел».

Очередь поддерживает следующие операции:

• добавление нового элемента;
• удаление элемента;
• получение первого элемента очереди;
• получение последнего элемента очереди.

3.2.       Реализация очереди на базе массива

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

Сперва необходимо задать максимальное количество элементов. Пусть оно равно одной тысяче:

const max_elem_count = 1000;

Сама очередь представляет собой структуру, содержащую массив элементов и переменную, хранящую их текущее количество:

type queue = record

   buf: array [1..max_elem_count]

      of integer;                { Массив элементов.      }

   count: integer;               { Количество элементов.  }

end;

Инициализация очереди осуществляется путем обнуления переменной, хранящей количество элементов. Обнулять массив нет необходимости, поскольку он будет затираться входящими элементами:

{ Операция инициализации очереди.                         }

{ Входные параметры:                                      }

{   q - очередь;                                          }

procedure init(var q: queue);

begin

   q.count := 0;

end;

Операция добавления элемента записывает новое значение в конец массива. При этом следует учесть, если текущее количество элементов достигло максимума, ничего добавлять не нужно. Сложность операции O(1).

{ Операция добавления нового элемента.                    }

{ Входные параметры:                                      }

{   q - очередь;                                          }

{   item - новый элемент.                                 }

procedure add(var q: queue; item: integer);

begin

   { Если текущее количество элементов меньше             }

   { максимального, то записываем новый элемент в конец.  }

   if (q.count < max_elem_count) then

   begin

      q.buf[q.count + 1] := item;

      { Увеличиваем количество элементов на 1.            }

      inc(q.count);

   end

end;

Удаление элемента происходит их начала массива. После удаления все остальные элементы очереди необходимо сдвинуть влево на одну позицию, чтобы закрыть пустую ячейку в массиве. При этом, если в очереди нет ни одного элемента, ничего делать не нужно. Сложность операции O(n), поскольку после удаления необходимо делать сдвиг.

{ Операция удаления элемента.                             }

{ Входные параметры:                                      }

{   q - очередь.                                          }

procedure remove(var q: queue);

var

   i: integer;

begin

   { Если количество елементов не 0, то удаляем.          }

   if (q.count > 0) then

   begin

      { Выполняем сдвиг всех остальных элементов.         }

      i := 1;

      while (i < q.count) do

      begin

         q.buf[i] := q.buf[i + 1];

         inc(i);

      end;

      { Уменьшаем количество элементов на 1.              }

      dec(q.count);

   end;

end;

Операция получения элемента, стоящего в начале очереди, выполняет возврат первого элемента массива. Если в очереди нет ни одного элемента, метод возвратит 0. Сложность операции O(1).

{ Операция получения первого элемента очереди.            }

{ Входные параметры:                                      }

{   q - очередь.                                          }

function get_first(q: queue): integer;

begin

   { Если очередь содержит хотя бы один элемент,          }

   { возвращаем первый.                                   }

   if (q.count > 0) then

      get_first := q.buf[1]

   { В противном случае возвращаем 0.                     }

   else

      get_first := 0;

end;

Операция получения элемента, стоящего в конце очереди, выполняет возврат элемента массива с индексом, равным количеству элементов в очереди. Если в очереди нет ни одного элемента, метод возвратит 0. Сложность операции O(1).

{ Операция получения последнего элемента очереди.         }

{ Входные параметры:                                      }

{   q - очередь.                                          }

function get_last(q: queue): integer;

begin

   { Если очередь содержит хотя бы один элемент,          }

   { возвращаем последний.                                }

   if (q.count > 0) then

      get_last := q.buf[q.count]

   { В противном случае возвращаем 0.                     }

   else

      get_last := 0;

end;

3.3.       Реализация очереди на базе связного списка

Преимуществом данного подхода по сравнению с реализацией на основе массива является отсутствие ограничения на максимальное количество элементов. Элемент очереди представляет собой структуру, хранящую полезные данные (в нашем случае – целочисленную переменную) и ссылку на следующий элемент.

type pnode = ^node; { Тип: указатель на элемент очереди.  }

node = record       { Объявление узла очереди.            }

   data: integer;   { Полезная информация.                }<… Продолжение »