При разработке программ во многих случаях достаточно использовать простые переменные и массивы. Память под такие объекты выделяется либо на этапе компиляции, либо на этапе выполнения программы. Приведём фрагменты программ, показывающие оба эти способа на примере выделения памяти под одномерный массив:
а) Память выделена на этапе компиляции:
const int N = 5;
int x1[N];
б) Память выделена на этапе исполнения программы с помощью операции new:
int *x2;
int n;
do{
cout << "n=";
cin >> n;
}while(n <= 0);
x2 = new int[n];
Теперь массивы x1 и x2 можно использовать, например, задать значения элементам этих массивов.
Но в обоих случаях после того, как память под массивы выделена, мы не можем изменять размеры этих массивов по своему усмотрению. Если быть более точным, то это справедливо только для случая а). Для варианта б) проблему решить можно. Но какой ценой?! Приведём возможную программную реализацию изменения размера динамического массива:
//пусть k — новый размер массива
int k = n + 1;
// выделяем новый участок памяти необходимого размера
int *t = new int[k];
// переписываем в него содержимое исходного массива x2
for(int i = 0; i < k && i < n; i++)
t[i] = x2[i];
// освобождаем память, на которую указывал x2
delete []x2;
// настраиваем x2 на новый участок памяти
x2 = t;
Как не сложно понять, такой подход к решению проблемы будет занимать слишком много машинного времени. В общем-то, неразумно выделять заново память под целый массив, когда нам требовался дополнительный участок всего для одного элемента.
Для того, чтобы в процессе выполнения программы произвольно добавлять и удалять данные, необходимо организовать наши данные не в массив, а в нечто другое. Если к элементу данных добавить ещё и указатель, в котором будет храниться адрес какого-то другого элемента, то это и будет кардинальным решением проблемы. Такая организация представления и хранения данных называется динамической структурой данных.
Каждый элемент динамических структур данных состоит из собственно данных и одного или нескольких указателей, ссылающихся на аналогичные элементы. Это позволяет добавлять в динамическую структуру новые данные или удалять какие-то из имеющихся, не затрагивая при этом другие элементы структуры.
Кроме того, динамические структуры позволяют нам организовать данные так, чтобы их представление в программе было максимально приближено к тому, как эти данные выглядят в реальности. Так, для моделирования обслуживания очереди к кассе в магазине лучше всего подойдет динамическая структура данных под названием «очередь», а не пресловутый массив, а для представления сети автомобильных дорог массив вообще неприемлем. Здесь нужна именно «сеть».
Динамические структуры данных бывают линейные и нелинейные. В линейной динамической структуре данные связываются в цепочку. К линейным структурам относятся списки (односвязные, двухсвязные, кольцевые), стеки, очереди (односторонние, двухсторонние, очереди с приоритетами). Организация нелинейных структур более сложная. Нелинейные структуры представляются, как правило, в виде дерева (каждый элемент имеет некоторое количество связей, например, в бинарном дереве каждый элемент (узел) имеет ссылку на левый и правый элемент).
Рассмотрим более подробно хотя бы некоторые виды динамических структур. Начнём с линейных списков.