Динамические структуры данных

Любая программа предназначена для обработки данных, от способа организации которых зависят алгоритмы работы, поэтому выбор структур данных должен предшествовать созданию алгоритмов. Выше были рассмотрены стандартные способы организации данных, предоставляемые языком C++, — основные и составные типы. Наиболее часто в программах используются массивы, структуры и их сочетания, например, массивы структур, полями которых являются массивы и структуры.

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

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

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

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

struct Node{

Data d; // тип данных Data должен быть определен ранее

Node *р;

};

Рассмотрим реализацию основных операций с динамическими структурами данных (в дальнейшем будет приведен пример реализации списка в виде шаблона класса).

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

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

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

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

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

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

§ чтение элемента с заданным ключом;

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

§ удаление элемента с заданным ключом;

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

Рассмотрим двунаправленный линейный список. Для формирования списка и работы с ним требуется иметь по крайней мере один указатель — на начало списка. Удобно завести еще один указатель — на конец списка. Для простоты допустим, что список состоит из целых чисел, то есть описание элемента списка выглядит следующим образом:

struct Node{

int d;

Node *next;

Node *prev;

};

Ниже приведена программа, которая формирует список из 5 чисел, добавляет число в список, удаляет число из списка и выводит список на экран. Указатель на начало списка обозначен pbeg, на конец списка — pend, вспомогательные указатели — pv и pkey.

#include < iostream.h>

struct Node{

int d;

Node *next;

Node *prev;

};

//-----------------------------------------------

Node * first (int d);

void add(Node **pend, int d);

Node * find(Node * const pbeg, int i);

bool remove(Node **pbeg, Node **pend, int key);

Node * insert(Node * const pbeg, Node **pend, int key, int d);

//-----------------------------------------------

int main(){

Node *pbeg = first(l); // Формирование первого элемента списка

Node *pend = pbeg; // Список заканчивается, едва начавшись

// Добавление в конец списка четырех элементов 2, 3, 4, и 5:

for (int i = 2; i< 6; i++)add(& pend, i);

// Вставка элемента 200 после элемента 2:

insert(pbeg. & pend, 2, 200);

// Удаление элемента 5:

if(! remove (& pbeg. & pend, 5))cout < < " не найден";

Node *pv = pbeg;

while (pv){ // вывод списка на экран

cout < < pv-> d < < ' ';

pv = pv-> next;

}

return 0;

}

//-------------------------------------------------

// Формирование первого элемента

Node * first(int d){

Node *pv = new Node;

pv-> d = d; pv-> next = 0; pv-> prev = 0;

return pv;

}

//---------------------------------------------------------

// Добавление в конец списка

void add(Node **pend, int d){

Node *pv = new Node;

pv-> d = d; pv-> next = 0; pv-> prev = *pend;

(*pend)-> next = pv;

*pend = pv;

}

//--------------------------------------------------------

// Поиск элемента по ключу

Node * find(Node * const pbeg, int d){

Node *pv = pbeg;

while (pv){

if(pv-> d == d)break;

pv = pv-> next;

}

return pv;

}

//--------------------------------------------------------

// Удаление элемента

bool remove(Node **pbeg, Node **pend, int key){

if(Node *pkey = find(*pbeg. key)){ // 1

if (pkey — *pbeg){ // 2

*pbeg = (*pbeg)-> next;

(*pbeg)-> prev =0; }

else if (pkey = *pend){ // 3

*pend = (*pend)-> prev;

(*pend)-> next = 0; }

else{ // 4

(pkey-> prev)-> next = pkey-> next;

(pkey-> next)-> prev = pkey-> prev; }

delete pkey;

return true; // 5

}

return false; // 6

}

//-------------------------------------------------------------

// Вставка элемента

Node * insert(Node * const pbeg. Node **pend. int key, int d){

if(Node *pkey = find(pbeg, key)){

Node *pv = new Node;

pv-> d = d;

// 1 - установление связи нового узла с последующим;

pv-> next = pkey-> next;

// 2 - установление связи нового узла с предыдущим:

pv-> prev = pkey;

// 3 - установление связи предыдущего узла с новым:

pkey-> next = pv;

// 4 - установление связи последующего узла с новым:

if(pkey! = *pend) (pv-> next)-> prev = pv;

// Обновление указателя на конец списка,

// если узел вставляется в конец:

else *pend = pv;

return pv;

}

return 0;

}

Результат работы программы:

1 2 200 3 4

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

Рассмотрим подробнее функцию удаления элемента из списка remove. Ее параметрами являются указатели на начало и конец списка и ключ элемента, подлежащего удалению. В строке 1 выделяется память под локальный указатель pkey, которому присваивается результат выполнения функции нахождения элемента по ключу find. Эта функция возвращает указатель на элемент в случае успешного поиска и 0, если элемента с таким ключом в списке нет. Если pkey получает ненулевое значение, условие в операторе if становится истинным (элемент существует), и управление передается оператору 2, если нет — выполняется возврат из функции со значением false (оператор 6).

Удаление из списка происходит по-разному в зависимости от того, находится элемент в начале списка, в середине или в конце. В операторе 2 проверяется, находится ли удаляемый элемент в начале списка — в этом случае следует скорректировать указатель pbeg на начало списка так, чтобы он указывал на следующий элемент в списке, адрес которого находится в поле next первого элемента. Новый начальный элемент списка должен иметь в своем поле указателя на предыдущий элемент значение 0.

Если удаляемый элемент находится в конце списка (оператор 3), требуется сместить указатель pend конца списка на предыдущий элемент, адрес которого можно получить из поля prev последнего элемента. Кроме того, нужно обнулить для нового последнего элемента указатель на следующий элемент. Если удаление происходит из середины списка, то единственное, что надо сделать, — обеспечить двустороннюю связь предыдущего и последующего элементов. После корректировки указателей память из-под элемента освобождается, и функция возвращает значение true.

Работа функции вставки элемента в список проиллюстрирована на рис. 3.2. Номера около стрелок соответствуют номерам операторов в комментариях.

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

Ниже приведена функция формирования упорядоченного списка (предполагается, что первый элемент существует):

void add_sort(Node **pbeg, Node **pend, int d){

Node *pv = new Node; // добавляемый элемент

pv-> d = d;

Node * pt = *pbeg;

while (pt){ // просмотр списка

if (d < pt-> d){ // занести перед текущим элементом (pt)

pv-> next = pt;

if (pt == *pbeg){ // в начало списка

pv-> prev = 0;

*pbeg = pv; }

else{ // в середину списка

(pt-> prev)-> next = pv;

pv-> prev = pt-> prev; }

pt-> prev = pv;

return;

}

pt = pt-> next;

}

pv-> next = 0; //в конец списка

pv-> prev = *pend;

(*pend)-> next = pv;

*pend = pv;

}

Стеки

Стек — это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел — первым ушел). Стек проще всего представить себе как закрытую с одного конца узкую трубу, в которую бросают мячи. Достать первый брошенный мяч можно только после того, как вынуты все остальные. Кстати, сегмент стека назван так именно потому, что память под локальные переменные выделяется по принципу LIFO. Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.

Ниже приведена программа, которая формирует стек из пяти целых чисел (1, 2, 3, 4, 5) и выводит его на экран. Функция помещения в стек по традиции называется push, а выборки — pop. Указатель для работы со стеком (top) всегда ссылается на его вершину.

#include < iostream.h>

struct Node{

int d;.

Node *p;

};

Node * first (int d);

void push(Node **top, int d);

int pop(Node **top);

//-----------------------------------------------

int main(){

Node *top = first(1);

for (int i = 2; i< 6; i++)push(& top, i);

while (top)

cout < < pop(Stop) < < ' ';

return 0;

}

// Начальное формирование стека

Node * first (int d){

Node *pv = new Node;

pv-> d = d;

pv-> p = 0;

return pv;

}

//-------------------------------------------------

// Занесение в стек

void push(Node **top, int d){

Node *pv = new Node;

pv-> d = d;

pv-> p = *top;

*top = pv;

}

//-------------------------------------------------

// Выборка из стека

int pop(Node **top){

int temp = (*top)-> d;

Node *pv = *top;

*top = (*top)-> p;

delete pv;

return temp;

}

Результат работы программы:

5 4 3 2 1

Очереди

Очередь — это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка — из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first in — first out, первым пришел — первым ушел). Очередь проще всего представить себе, постояв в ней час-другой. В программировании очереди применяются, например при моделировании, диспетчеризации задач операционной системой, буферизованном вводе/выводе.

Ниже приведена программа, которая формирует очередь из пяти целых чисел и выводит ее на экран. Функция помещения в конец очереди называется add, а выборки — del. Указатель на начало очереди называется pbeg, указатель на конец — pend.

#include < iostream.h>

struct Node{

int d;

Node *p;

};

Node * first(int d);

void add(Node **pend, int d);

int del(Node **pbeg);

//----------------------------------------------------

int main(){

Node *pbeg = first(1);

Node *pend = pbeg;

for (int i = 2; i< 6; i++)add(& pend, i);

while (pbeg)

cout < < del(& pbeg) < < ' ';

return 0;

}

//----------------------------------------------------

// Начальное формирование очереди

Node * first(int d){

Node *pv = new Node;

pv-> d = d;

pv-> p = 0;

return pv;

}

//-----------------------------------------------------

// Добавление в конец

void add(Node **pend, int d){

Node *pv = new Node;

pv-> d = d:

pv-> p = 0;

(*pend)-> p = pv;

*pend = pv;

}

//-----------------------------------------------------

// Выборка

int del(Node **pbeg){

int temp = (*pbeg)-> d;

Node *pv = *pbeg;

*pbeg = (*pbeg)-> p;

delete pv;

return temp;

}

Результат работы программы:

1 2 3 4 5

Бинарные деревья

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

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

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

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

function way_around (дерево){

way_around (левое поддерево)

посещение корня

way_around (правое поддерево) }

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

1, 6, 8, 10, 20, 21, 25, 30

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

30, 25, 21, 20, 10, 8, 6, 1

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

Для бинарных деревьев определены операции:

§ включения узла в дерево;

§ поиска по дереву;

§ обхода дерева;

§ удаления узла.

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

Программа формирует дерево из массива целых чисел и выводит его на экран.

#include < iostream.h>

struct Node{

int d;

Node *left;

Node *r1ght;

};

Node * first (int d);

Node * search_insert(Node *root, int d);

void print_tree(Node *root, int l);

//---------------------------------------------------------

int main(){

int b[] = {10, 25, 20, 6, 21, 8, 1, 30};

Node *root = first(b[0]);

for (int i = 1; i< 8; i++)search_insert(root, b[i]);

print_tree(root, 0);

return 0;

}

//----------------------------------------------------------

// Формирование первого элемента дерева

Node * first(int d){

Node *pv = new Node;

pv-> d = d;

pv-> left =0;

pv-> right = 0;

return pv;

}

//------------------------------------------------------------

// Поиск с включением

Node * search_insert(Node *root, int d){

Node *pv = root, *prev;

bool found = false;

while (pv & &! found){

prev = pv;

if (d == pv-> d) found = true;

else if (d < pv-> d) pv = pv-> left;

else pv = pv-> right;

}

if (found) return pv;

// Создание нового узла:

Node *pnew = new Node;

pnew-> d = d;

pnew-> left = 0;

pnew-> right = 0;

if (d < prev-> d)

// Присоединение к левому поддереву предка:

prev-> left = pnew;

else

// Присоединение к правому поддереву предка:

prev-> right = pnew;

return pnew;

}

//--------------------------------------------------------

// Обход дерева

void print_tree(Node *p, int level){

if (p){

print_tree(p-> left, level +1); // вывод левого поддерева

for (int i = 0; i< level; i++)cout < < " ";

cout < < p-> d < < endl; // вывод корня поддерева

print_tree(p-> right, level +1); // вывод правого поддерева

}

}

Текущий указатель для поиска по дереву обозначен pv, указатель на предка pv обозначен prev, переменная pnew используется для выделения памяти под включаемый в дерево узел. Рекурсии удалось избежать, сохранив всего одну переменную (prev) и повторив при включении операторы, определяющие, к какому поддереву присоединяется новый узел.

Результат работы программы для дерева, изображенного па рис. 3.3:

Рассмотрим подробнее функцию обхода дерева. Вторым параметром в нее передается целая переменная, определяющая, па каком уровне находится узел. Корень находится на уровне 0. Дерево печатается по горизонтали так, что корень находится слева (посмотрите на результат работы программы, наклонив голову влево, и сравните с рис. 3.3). Перед значением узла для имитации структуры дерева выводится количество пробелов, пропорциональное уровню узла. Если закомментировать цикл печати пробелов, отсортированный по возрастанию массив будет выведен в столбик. Заметьте, что функция обхода дерева длиной всего в несколько строк может напечатать дерево любого размера — ограничением является только размер стека.

Удаление узла из дерева представляет собой не такую простую задачу, поскольку удаляемый узел может быть корневым, содержать две, одну или ни одной ссылки на поддеревья. Для узлов, содержащих меньше двух ссылок, удаление тривиально. Чтобы сохранить упорядоченность дерева при удалении узла с двумя ссылками, его заменяют на узел с самым близким к нему ключом. Это может быть самый левый узел его правого поддерева или самый правый узел левого поддерева (например, чтобы удалить из дерева на рис. 3.3 узел с ключом 25, его нужно заменить на 21 или 30, узел 10 заменяется на 20 или 8, и т. д.). Реализация функции удаления из дерева оставлена читателю для самостоятельной работы.

Реализация динамических структур с помощью массивов

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

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

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

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

10 25 20 6 21 8 1 30 - массив данных

1 2 3 4 5 6 7 -1- вспомогательный массив

0 - индекс первого элемента в списке

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

10 25 20 6 21 8 1 30 - массив данных

2 7 4 5 1 0 3 -1- вспомогательный массив

6 - индекс первого элемента в списке

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

10 25 20 6 21 8 1 30 - массив данных

3 2 -1 6 -1 -1 -1 -1 - левая ссылка

1 7 4 5 -1 -1 -1 -1 - правая ссылка

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

struct Node{

Data d; // тип данных Data должен быть определен ранее

int i;

};

Node spisok1[1000]; // на этапе компиляции

Node *pspisok2 = new Node[m]; // на этапе выполнения

ВНИМАНИЕ

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

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

Работа с динамическими структурами данных подробно рассмотрена в девятом семинаре практикума [11].