ГЛАВА 15. Динамические структуры данных

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

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

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

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

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

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

а шаблон структуры будет иметь вид

struct Spis {

int info;

Spis *p;

} ;

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

Например, если создается линейный список из записей, содержащих фамилию, год рождения, стаж работы и пол, любая часть записи мо­жет выступать в качестве ключа. При упорядочивании такого списка по алфавиту ключом будет являться фамилия, а при поиске, например, ветеранов труда – ключом будет стаж работы. Как правило, ключи должны быть уникальными, но могут и совпадать. В случае совпадения ключей лучше всего использовать схемы организации структур данных по принципам «хеширования».

Над списками можно выполнять следующие операции:

– начальное формирование списка (создание первого элемента);

– добавление элемента в список;

– обработка (чтение, удаление и т.п.) элемента с заданным ключом;

– вставка элемента в заданное место списка (до или после элемента с заданным ключом);

– упорядочивание списка по ключу.

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

– все параметры, не изменяемые внутри функций, должны передаваться с модификатором const;

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

Структура данных СТЕК

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

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

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

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

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

push – добавление элемента в стек (вталкивание);

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

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

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