Динамические структуры данных. От способа организации данных в программе зависят алгоритмы работы, поэтому выбор структур данных должен предшествовать созданию алгоритмов
От способа организации данных в программе зависят алгоритмы работы, поэтому выбор структур данных должен предшествовать созданию алгоритмов. Стандартные способы организации данных представлены простыми и составными типами языка C++.
Память под данные может выделяться на этапе компиляции (ее объем должен быть известен до начала выполнения программы, т.е. задан в виде константы), либо во время выполнения программы с помощью операции выделения динамической памяти new или функции mallос (ее объем должен быть известен до распределения памяти). В обоих случаях выделяется непрерывный участок памяти.
Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, она выделяется по мере необходимости отдельными блоками, связанными друг с другом с помощью указателей. Такой способ организации данных называется динамическими структурами данных. Динамическая структура может занимать несмежные участки оперативной памяти, ее размер изменяется во время выполнения программы.
Из динамических структур чаще всего используются линейные списки, стеки, очереди и бинарные деревья. Они различаются способами связи отдельных элементов и допустимыми операциями.
Динамические структуры также применяют для более эффективной работы с данными, размер которых известен, например, для решения задач сортировки (упорядочивание динамических структур не требует перестановки элементов, а сводится к изменению указателей на эти элементы). Например, если требуется многократно упорядочивать большой массив данных, его следует представить в виде линейного списка. При решении задач поиска в случаях, когда важна скорость, данные лучше всего представить в виде бинарного дерева.
Элемент любой динамической структуры данных представляет собой структуру (в смысле struct), содержащую, по крайней мере, два поля: для хранения данных и для указателя. Таких полей может быть и несколько. Поля данных могут быть любого типа: основного, составного или типа указатель.
Описание простейшего элемента динамической структуры:
struct Node{
Data d; // тип данных Data должен быть определен ранее
Node *р;
};
Линейные списки
Однонаправленный (односвязный) список – множество элементов, каждый из которых содержит ссылку на следующий. Двунаправленный (двусвязный) список – множество элементов, каждый из которых имеет ссылки на предыдущий и на следующий элемент. Если последний элемент списка имеет указатель на первый, это кольцевой список.
Каждый элемент списка содержит ключ,идентифицирующий этот элемент. Ключ обычно бывает целым числом, строкой и является частью поля данных.
В качестве ключа списка могут выступать разные части поля данных. Например, если создается линейный список из записей, содержащих фамилию, год рождения, стаж работы и пол ключом, то ключом при упорядочивании списка по алфавиту будет фамилия, а при поиске ветеранов труда – стаж. Ключи разных элементов списка могут совпадать.
Над списками можно выполнять следующие операции:
· начальное формирование списка (создание первого элемента);
· добавление элемента в конец списка;
· чтение элемента с заданным ключом;
· вставка элемента в заданное место списка (до или после элемента с заданным ключом);
· удаление элемента с заданным ключом;
· упорядочивание списка по ключу.
Пример: формирование списка из 5 чисел, добавление элемента в список, его удаление из списка, вывод списка на экран. Указатель на начало списка обозначен pbeg, на конец списка – pend, вспомогательные указатели – pv и ркеу.
#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(1); // Формирование первого элемента списка
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( рkеу != *pend)
(pv->next)->prev = pv;
// Обновление указателя на конец списка, если узел вставляется в конец
else *pend = pv;
return pv;
}
return 0;
}
Результат работы программы:
1 2 200 3 4
Все параметры, не изменяемые внутри функций, должны передаваться с модификатором const. Указатели, которые могут измениться передаются по адресу. Например, указатель на конец списка при удалении последнего элемента требуется скорректировать.
Функция удаления элемента remove.
Параметрами функции являются указатели на начало и конец списка и ключ удаляемого элемента. В строке 1 выделяется память под локальный указатель ркеу, которому присваивается результат выполнения функции нахождения элемента по ключу find. Эта функция возвращает указатель на элемент в случае успешного поиска и 0, если элемента с таким ключом в списке нет. Если ркеу получает ненулевое значение (элемент существует), условие в операторе if становится истинным и управление передается оператору 2, если нет — выполняется возврат из функции со значением false (оператор 6).
Удаление из списка происходит по-разному в зависимости от того, находится элемент в начале середине или в конце списка. В операторе 2 проверяется, находится ли удаляемый элемент в начале списка – в этом случае следует скорректировать указатель pbeg на начало списка так, чтобы он указывал на следующий элемент в списке, адрес которого находится в поле next первого элемента. Новый начальный элемент списка должен иметь в своем поле указателя на предыдущий элемент значение 0.
Если удаляемый элемент находится в конце списка (оператор 3), требуется сместить указатель pend конца списка на предыдущий элемент, адрес которого можно получить из поля prev последнего элемента. Кроме того, нужно обнулить для нового последнего элемента указатель на следующий элемент. Если удаление происходит из середины списка, то необходимо обеспечить двустороннюю связь предыдущего и последующего элементов. После корректиpoвки указателей память из-под элемента освобождается, и функция возвращает значение true.
Работа функции вставки элемента в список проиллюстрирована на рис. 1.9. Номера около стрелок соответствуют номерам операторов в комментариях.
Пример: функция формирования упорядоченного списка (предполагается, что первый элемент существует).
Сортировка связанного списка заключается в изменении связей между элементами. Алгоритм состоит в том, что исходный список просматривается, и каждый элемент вставляется в новый список на место, определяемое значением его ключа.
Рисунок 1.9 – Вставка элемента в список
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 (&top) << ‘ ’;
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 **tор){
int temp = (*top)->d;
Node *pv = *tор;
*tор = (*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
Бинарные деревья
Бинарное дерево – это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья. На каждый узел имеется ровно одна ссылка. Начальный узел называется корнем дерева. Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие – потомками. Высота дерева определяется количеством уровней, на которых располагаются его узлы.
На рисунке 1.10 приведен пример бинарного дерева поиска.
Рисунок 1.10 – Бинарное дерево
Дерево поиска – дерево, для каждого узла которого все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева – больше. Одинаковые ключи не допускаются.
В дереве поиска можно найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значения ключа в каждом узле. Такой поиск гораздо эффективнее поиска по списку, поскольку время поиска определяется высотой дерева, которая пропорциональна двоичному логарифму количества узлов. Для сбалансированного дерева, в котором количество узлов справа и слева отличается не более чем на единицу, высота дерева равна двоичному логарифму количества узлов.
Линейный список можно представить как вырожденное бинарное дерево, в котором каждый узел имеет не более одной ссылки. Для списка среднее время поиска равно половине длины списка.
Для бинарных деревьев определены операции:
· включения узла в дерево,
· поиска по дереву,
· обхода дерева,
· удаления узла.
Дерево – это только метод логической организации данных, в оперативной памяти ячейки расположены линейно по возрастанию адресов.
Дерево является рекурсивной структурой данных, т.к. каждое поддерево также является деревом. Поэтому действия с такими структурами удобно реализовывать с помощью рекурсивных алгоритмов. Например, функцию обхода всех узлов дерева в общем виде можно описать так:
function way_around ( дерево ){
way_around ( левое поддерево )
посещение корня
way_around ( правое поддерево )
}
Можно обходить дерево и в другом порядке (например, сначала корень, потом поддеревья), но приведенная функция позволяет получить на выходе отсортированную последовательность ключей, поскольку сначала посещаются вершины с меньшими ключами, расположенные в левом поддереве. Результат обхода дерева, изображенного на рис. 24.1: 1, 6, 8, 10, 20, 21, 25, 30.
Если в функции обхода первое обращение идет к правому поддереву, результат обхода будет другим: 30, 25, 21, 20, 10, 8, 6, 1.
Таким образом, деревья поиска можно применять для сортировки значений. При обходе дерева узлы не удаляются.
Для каждого рекурсивного алгоритма можно создать его нерекурсивный эквивалент.
Пример: формирование дерева из массива целых чисел и вывод его на экран. Текущий указатель для поиска по дереву обозначен pv,указатель на предка pv–prev. Переменная pnew используется для выделения памяти под включаемый в дерево узел.
Реализована нерекурсивная функция поиска по дереву с включением и рекурсивная функция обхода дерева. Поиск элемента осуществляется по ключу. Если элемент найден, функция возвращает указатель на него, а если нет – включает элемент в соответствующее место дерева и возвращает указатель на него. Для включения элемента необходимо помнить пройденный по дереву путь на один шаг назад и знать, выполняется ли включение нового элемента в левое или правое поддерево его предка.
Рекурсии удалось избежать, сохранив всего одну переменную (prev)и повторив при включении операторы, определяющие, к какому поддереву присоединяется новый узел.
#include <iostream.h>
struct Node{
int d;
Node *left;
Node *right;
};
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); // вывод правого поддерева
}
}
Результат работы программы для дерева, изображенного на рисунке 1.10:
Функция обхода дерева
Вторым параметром в нее передается целая переменная, определяющая, на каком уровне находится узел. Корень находится на уровне 0.
Дерево печатается по горизонтали так, что корень находится слева. Перед значением узла для имитации структуры дерева выводится количество пробелов, пропорциональное уровню узла. Если закомментировать цикл печати пробелов, отсортированный по возрастанию массив будет выведен в столбик.
Удаление узла из дерева
Удаляемый узел может быть корневым, содержать две, одну или ни одной ссылки на поддеревья. Для узлов, содержащих меньше двух ссылок, удаление тривиально. Чтобы сохранить упорядоченность дерева при удалении узла с двумя ссылками, его заменяют на узел с самым близким к нему ключом. Это может быть самый левый узел его правого поддерева или самый правый узел левого поддерева (например, чтобы удалить из дерева на рис. 24.1 узел с ключом 25, его нужно заменить на 21 или 30, узел 10 заменяется на 20 или 8, и т. д.).