Алгоритмы и структуры данных

PElement = ATypeElement;  {указатель на тип элемента}

TypeElement = record        {тип элемента списка}

Left: PElement; {указатель на предыд. элемент в строке}

Up: PElement; {указатель на предыд. элемент в столбце}

Value: TypeData; {значение элемента матрицы}

Row: integer; {индекс строки матрицы}

Colum: integer; {индекс столбца матрицы}

end;

Связанная структура для разреженной матрицы A показана на рис. 7.

Циклический список представляет отдельную строку или столбец. Список столбца может содержать общие элементы с одним или более списком строки. Для того чтобы обеспечить использование более эффективных алгоритмов включения и исключения элементов, все списки строк и столбцов имеют головные элементы. Головной элемент каждого списка строки содержит ноль в поле Colum. Аналогично, каждый головной элемент в списке столбца имеет ноль в поле Row. Строка или столбец, содержащие только нулевые элементы, представлены головными вершинами, у которых поле Left или Up указывает само на себя.

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

1.2.9. Стек

Стек - это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала. Здесь используется принцип «последним пришел - первым вышел» (LIFO: Last Input - First Output).

Стек можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру - в виде линейного списка (рис. 8).

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

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

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

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

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

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

Основные операции, производимые со стеком:

• записать (положить в стек);
• прочитать (снять со стека);
• очистить стек;
• проверка пустоты стека.

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

procedure PushStack(NewElem:  TypeData;

var ptrStack: PElement); {Запись элемента в стек (положить в стек)} begin

InsFirst LineSingleList(NewElem, ptrStack); end;

procedure PopStack(var NewElem: TypeData, ptrStack: PElement); {Чтение элемента из стека (снять со стека)} begin

if ptrStack <> nil then begin NewElem := ptrStackA.Data;

Del LineSingleList(ptrStack, ptrStack);    {удаляем вершину}

end; end;

procedure ClearStack(var ptrStack: PElement);

{Очистка стека} begin

while ptrStack <> nil do

Del LineSingleList(ptrStack, ptrStack);    {удаляем вершину}

end;

function EmptyStack(var ptrStack: PElement): boolean;

{Проверка пустоты стека} begin

if ptrStack = nil then EmptyStack := true

else EmptyStack := false;

end;

 

1.2.10. Очередь

Очередь - это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Каждый новый элемент размещается в конце очереди; элемент, стоящий в начале очереди, выбирается из нее первым. Здесь используется принцип «первым пришел - первым вышел» (FIFO: First Input - First Output).

Очередь можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру - в виде линейного списка (рис. 9).

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

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

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

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

С точки зрения экономии вычислительных ресурсов более предпочтителен второй способ. Однако здесь усложняется проверка на пустоту очереди и контроль переполнения очереди - индекс конца очереди не должен «набегать» на индекс начала.

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

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

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

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

var

ptrBeginQueue, ptrEndQueue:  PElement;

Основные операции, производимые с очередью:

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

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

procedure InQueue(NewElem:  TypeData;

var ptrBeginQueue, ptrEndQueue: PElement); {Добавление элемента в очередь} begin

Ins LineDoubleList(NewElem, ptrBeginQueue, ptrEndQueue); end;

procedure FromQueue(var NewElem: TypeData;

var ptrBeginQueue: PElement); {Извлечение элемента из очереди} begin

if ptrBeginQueue <> nil then begin

NewElem := ptrEndQueueA.Data;

Del LineDoubleList(ptrBeginQueue, ptrBeginQueue); end; end;

procedure ClearQueue(var ptrBeginQueue,

ptrEndQueue: PElement);

{Очистка очереди} begin

while ptrBeginQueue <> nil do

Del LineDoubleList(ptrBeginQueue, ptrBeginQueue); ptrEndQueue := nil; end;

function EmptyQueue(var ptrBeginQueue: PElement): boolean;

{Проверка пустоты очереди} begin

if ptrBeginQueue = nil then EmptyQueue := true

else EmptyQueue := false;

end;

1.2.11. Дек

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

Выделяют ограниченные деки:

• дек с ограниченным входом - из конца дека можно только извлекать элементы;
• дек с ограниченным выходом - в конец дека можно только добавлять элементы.

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

Дек также можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру - в виде линейного списка (рис. 10).

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

 

Описание элементов дека аналогично описанию элементов линейного двунаправленного списка, где DataType является типом элементов дека. Поэтому здесь приводить его не будем. Но, как и для очереди, введем дополнительно два указателя на начало и конец дека:

var

ptrBeginDeck, ptrEndDeck:  PElement;

Основные операции, производимые с деком:

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

Реализацию этих операций приведем в виде соответствующих процедур, которые, в свою очередь, используют процедуры операций с линейным двунаправленным списком: procedure InBeginDeck(NewElem:  TypeData;

var ptrBeginDeck: PElement); {Добавление элемента в начало дека} begin

InsFirst LineDoubleList(NewElem, ptrBeginDeck); end;

procedure InEndDeck(NewElem: TypeData;

var ptrBeginDeck, ptrEndDeck: PElement); {Добавление элемента в конец дека} begin

Ins LineDoubleList(NewElem, ptrBeginDeck, ptrEndDeck); end;

procedure FromBeginDeck(NewElem: TypeData;

var ptrBeginDeck: PElement); {Извлечение элемента из начала дека} begin

if ptrBeginDeck <> nil then begin NewElem := ptrBeginDeckA.Data;

Del LineDoubleList(ptrBeginDeck, ptrBeginDeck); {удаляем первый} end; end;

procedure FromEndDeck(NewElem: TypeData,

var ptrBeginDeck, ptrEndDeck: PElement); {Извлечение элемента из конца дека} begin

if ptrBeginDeck <> nil then begin NewElem := ptrEndDeckA.Data;

Del LineDoubleList(ptrBeginDeck, ptrEndDeck);  {удаляем конец} end; end;

procedure ClearDeck(var ptrBeginDeck: PElement);

{Очистка дека} begin

while ptrBeginDeck <> nil do

Del LineDoubleList(ptrBeginDeck, ptrBeginDeck); ptrEndDeck := nil; end;

function EmptyDeck(var ptrBeginDeck: PElement): boolean;

{Проверка пустоты дека} begin

if ptrBeginDeck = nil then EmptyDeck := true

else EmptyDeck := false;

end;

1.3. Нелинейные структуры данных

 

1.3.1. Мультисписки

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

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

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

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

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

1.3.2. Слоеные списки

Слоеные (skip), или разделенные, списки - это связные списки, которые позволяют перескакивать через некоторое количество элементов (рис. 12). Это позволяет преодолеть ограничения последовательного поиска, являющейся основной причиной низкой эффективности поиска в линейных списках. В то же время вставка и удаление остаются сравнительно эффективными.