Теоретическое описание используемых структур данных с алгоритмами реализации основных операций

Стек

Стеком назовем последовательность элементов одного и того же типа, к которой можно добавлять и убирать элементы, причем как добавление новых элементов, так и удаление старых производится с одного и того же конца этой последовательности, называемого вершиной стека. Применяются и другие названия стека — магазин, функционирующий по принципу LIFO (Last — In — First — Out — «последним пришел — первым исключается»). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.

При удалении элемента удаляется всегда тот элемент, который был последним добавлен в стек, таким образом, элементы удаляются в порядке, обратном порядку добавления элементов.

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

Основные операции над стеком — включение нового элемента (английское название push — заталкивать) и исключение элемента из стека (англ. pop — выскакивать).

Полезными могут быть также вспомогательные операции:

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

pop (); push ().

Некоторые авторы рассматривают также операции включения / исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению.

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

• · а) пустого;
• · б — г) после последовательного включения в него элементов с именами 'A', 'B', 'C';
• · д, е) после последовательного удаления из стека элементов 'C' и 'B';
• · ж) после включения в стек элемента 'D'.

Как видно из рис. 1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A, B, C, D. Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т. е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом, т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.

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

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

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

Операция очистки стека сводится к записи в указатель стека начального значения — адреса начала выделенной области памяти.

Определение размера стека сводится к вычислению разности указателей: указателя стека и адреса начала области.

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

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

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

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

Обычно под связным списком подразумевается реализация последовательного расположения набора элементов. Начиная с некоторого узла, мы считаем его первым элементом последовательности. Затем прослеживается его ссылка на другой узел, который дает нам второй элемент последовательности и т. д. Поскольку список может быть циклическим, последовательность иногда представляется бесконечной. Чаще всего приходится иметь дело со списками, соответствующими простому последовательному расположению элементов, принимая одно из следующих соглашений для ссылки последнего узла:

• — Это пустая (null) ссылка, не указывающая на какой-либо узел.
• — Ссылка указывает на фиктивный узел (dummy node), который не содержит элементов.
• — Ссылка указывает на первый узел, что делает список циклическим.

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

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

Линейные списки

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

Пусть тип NodeDesc (desc от descriptor) определены, как показано ниже. Каждая переменная типа NodeDesc содержит три компоненты, а именно идентифицирующий ключ key, указатель на следующий элемент next и, возможно, другую информацию. Для дальнейшего нам понадобятся только key и next.

struct NodeDesc {.

int Info;

int key;

NodeDesc * next;

};

NodeDesc * p;

NodeDesc * q;

p, q — указательные переменные На рис. 1 показан список узлов, причём указатель на первый элемент хранится в переменной р. Вероятно, простейшая операция со списком, показанным на рисунке — это вставка элемента в голову списка. Сначала размещается элемент типа NodeDesc, при этом ссылка (указатель) на него записывается во вспомогательную переменную, скажем q. Затем простые присваивания указателей завершают операцию. Отметим, что порядок этих трех операторов менять нельзя.

q=new NodeDesc;

qnext = р; р = q;

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

р = null; (*начинаем с пустого списка*).

while (n > 0).

{.

q=new NodeDesc;

qnext = р; р = q;

qkey = n;

n -;

}.

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

Среди элементарных операций со списками-вставка и удаление элементов (частичное изменение списка), а также, разумеется, проход по списку. Мы сначала рассмотрим вставку (insertion) в список.

Предположим, что элемент, на который ссылается указатель q, нужно вставить в список после элемента, на который ссылается указатель р (рис. 2).

qnext = pnext; pnext = q;

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

Необходимо вставить новую компоненту после pp, а потом произвести обмен значениями между новым элементом и pp.

q=new NodeDesc;

qq=pp;

pkey=k;

pnext=q;

Теперь рассмотрим удаление из списка (list deletion). Нетрудно удалить элемент, стоящий сразу за pp. Эта операция показана здесь вместе с повторной вставкой удалённого элемента в начало другого списка (обозначенного переменной q). Здесь имеет место циклический обмен значений трёх указателей.

r = pnext; pnext = rnext; rnext = q; q = r;

Удаление самого элемента, на который указывает ссылка (а не следующего), труднее, так как здесь возникает та же проблема, что и со вставкой: невозможно просто так перейти назад от элемента к предшествующему.

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

Обратимся теперь к фундаментальной операции прохода по списку. Предположим, что для каждого элемента списка, у которого первый элемент pp, нужно выполнить некоторую операцию Р (х). Эту задачу можно выполнить так:

WHILE (список, на который ссылается р, не пуст)

{

выполнить операцию Р;

перейти к следующему элементу;

}

Из определения оператора while и структуры связей следует, что Р применяется ко всем элементам списка и ни к каким другим.

Очень часто используемая со списками — поиск в списке элемента с заданным ключом.

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

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

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

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

Организацию данных в связный список можно рекомендовать, когда число элементов относительно мало (< 50), меняется и, более того, когда нет информации о частоте обращения к ним. Типичный пример — таблица имен в компиляторах языков программирования. Каждое объявление добавляет новое имя, которое удаляется из списка после выхода из его области видимости. Использование простых связных списков уместно в приложениях с относительно короткими программами. Но даже в этом случае можно добиться значительного ускорения доступа к данным с помощью очень простого приёма, который упоминается здесь прежде всего потому, что он представляет собой удачную иллюстрацию гибкости связных списков.