ГЛАВА 15. Динамические структуры данных
Линейные списки
Некоторые задачи исключают использование структур данных фиксированного размера и требуют введения структур, способных увеличивать или уменьшать свой размер уже в процессе работы программы. Основу таких структур составляют динамические переменные.
Динамическая переменная хранится в некоторой области ОП, обращение к которой производится через переменную-указатель.
Как правило, динамические переменные организуются в списковые структуры данных, элементы которых имеют тип struct. Для адресации элементов в структуру включается указатель (адресное поле) на область размещения следующего элемента.
Такой список называют однонаправленным (односвязным). Если добавить в каждый элемент ссылку на предыдущий, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список.
Например, пусть необходимо создать линейный список, содержащий целые числа, тогда каждый элемент списка должен иметь информационную (infо) часть, в которой будут находиться данные, и адресную часть (р), в которой будут размещаться указатели связей, т.е. элемент такого списка имеет вид
а шаблон структуры будет иметь вид
struct Spis {
int info;
Spis *p;
} ;
Каждый элемент списка содержит ключ, идентифицирующий этот элемент. Ключ обычно бывает либо целым числом, либо строкой и является частью поля данных. В качестве ключа в процессе работы со списком могут выступать разные части поля данных.
Например, если создается линейный список из записей, содержащих фамилию, год рождения, стаж работы и пол, любая часть записи может выступать в качестве ключа. При упорядочивании такого списка по алфавиту ключом будет являться фамилия, а при поиске, например, ветеранов труда – ключом будет стаж работы. Как правило, ключи должны быть уникальными, но могут и совпадать. В случае совпадения ключей лучше всего использовать схемы организации структур данных по принципам «хеширования».
Над списками можно выполнять следующие операции:
– начальное формирование списка (создание первого элемента);
– добавление элемента в список;
– обработка (чтение, удаление и т.п.) элемента с заданным ключом;
– вставка элемента в заданное место списка (до или после элемента с заданным ключом);
– упорядочивание списка по ключу.
Если программа состоит из функций, решающих вышеперечисленные задачи, то необходимо соблюдать следующие требования:
– все параметры, не изменяемые внутри функций, должны передаваться с модификатором const;
– указатели, которые могут изменяться, передаются по адресу. Например, при удалении из списка последнего элемента, измененный указатель на конец списка требует корректировки, т.е. передачи в точку вызова.
Структура данных СТЕК
Стек – упорядоченный набор данных, в котором размещение новых элементов и удаление существующих производится только с одного его конца, который называют вершиной стека, т.е. стек – это список с одной точкой доступа к его элементам. Графически это можно изобразить так:
Стек – структура типа LIFO (Last In, First Out) – последним вошел, первым выйдет. Стек получил свое название из-за схожести с оружейным магазином с патронами (обойма): когда в стек добавляется новый элемент, то прежний проталкивается вниз и временно становится недоступным. Когда же верхний элемент удаляется из стека, следующий за ним поднимается вверх и становится опять доступным.
Максимальное число элементов стека ограничивается, т.е. по мере вталкивания в стек новых элементов память под него должна динамически запрашиваться и освобождаться также динамически при удалении элемента из стека. Таким образом, стек – динамическая структура данных, состоящая из переменного числа элементов одинакового типа.
Состояние стека рассматривается только по отношению к его вершине, а не по отношению к количеству его элементов, т.е. только вершина стека характеризует его состояние.
Операции, выполняемые над стеком, имеют специальные названия:
push – добавление элемента в стек (вталкивание);
pop – выталкивание (извлечение) элемента из стека, верхний элемент стека удаляется (не может применяться к пустому стеку).
Кроме этих обязательных операций часто нужно прочитать значение элемента в вершине стека, не извлекая его оттуда. Такая операция получила название peek.
Рассмотрим основные алгоритмы работы со стеком, взяв для простоты в качестве информационной части целые числа, хотя информационная часть может состоять из любого количества объектов допустимого типа, за исключением файлов.
Алгоритм формирования стека
Рассмотрим данный алгоритм для первых двух элементов.
1. Описание структуры переменной, содержащей информационное и адресное поля:
| struct Stack ® | info | Next |
Шаблон структуры рекомендуется описывать глобально:
struct Stack {
int info;
Stack *Next;
} ;
2. Объявление указателей на структуру:
Stack *begin (вершина стека), *t (текущий элемент);
3. Так как первоначально стек пуст: begin = NULL;
4. Захват памяти под первый (текущий) элемент:
t = (Stack*) malloc (sizeof(Stack)); или t = new Stack;
формируется конкретный адрес ОП (обозначим его А1) для первого элемента, т.е. t равен А1.
5. Ввод информации (например, i1);
а) формирование информационной части:
t -> info = i1;
б) формирование адресной части: значение адреса вершины стека записываем в адресную часть текущего элемента (там был NULL)
t -> Next = begin;
| t ® | info = i1 | Next | ® | begin = NULL |
6. Вершина стека переносится на созданный первый элемент:
begin = t;
в результате получается следующее:
| begin (A1) ® | info = i1 | NULL |
7. Захват памяти под второй элемент:
t = (Stack*) malloc (sizeof(Stack)); или t = new Stack;
формируется конкретный адрес ОП (A2) для второго элемента.
8. Ввод информации для второго элемента (i2);
а) формирование информационной части:
t -> info = i2;
б) в адресную часть записываем значение адреса вершины, т.е. адрес первого (предыдущего) элемента (А1):
t -> Next = begin;
| t (A2) ® | info = i2 | Next = A1 |
9. Вершина стека снимается с первого и устанавливается на новый элемент (A2):
begin = t;
получается следующая цепочка:
| begin (A2) ® | info = i2 | Next = A1 | ® | info = i1 | Next = NULL |
Обратите внимание, что действия 7, 8, 9 идентичны действиям 4, 5, 6, т.е. добавление новых элементов в стек можно выполнять в цикле, до тех пор, пока это необходимо.
Функция формирования элемента стека для объявленного ранее типа данных может выглядеть следующим образом:
Stack* Create(Stack *begin) {
Stack *t = (Stack*)malloc(sizeof(Stack));
printf(“\n Input Info ”);
scanf(“%d”, &t -> info);
t -> Next = begin;
return t;
}
Участок программы с обращением к функции Create для добавление необходимого количества элементов в стек может иметь следующий вид:
¼
Stack *begin = NULL;
int repeat = 1;
while(repeat) { // repeat=1 – продолжение ввода данных
begin = Create(begin);
printf(“ Stop - 0 ”); // repeat=0 – конец ввода данных
scanf(“%d”, &repeat);
}
¼
Если в функцию Сreate указатель на вершину передавать по адресу и использовать для захвата памяти операцию new, то она может иметь следующий вид:
void Create(Stack **pt) {
Stack *t = new Stack;
printf(“\n Input Info ”);
scanf(“%d”, &t -> info);
t -> Next = *pt;
}
Обращение к ней в данном случае будет: Create(&begin);