Тема 13. Динамические структуры данных
Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, память выделяется по мере необходимости отдельными блоками, связанными друг с другом с помощью указателей. Такой способ организации данных называется динамическими структурами данных, поскольку их размер изменяется во время выполнения программы.
Из динамических структур в программах чаще всего используются линейные списки, стеки, очереди и бинарные деревья.
Компонент (узел) любой динамической структуры данных представляет собой структуру (struct), содержащую по крайней мере два поля: для хранения данных и для указателя следующего узла. Полей данных и указателей может быть несколько. Поля данных могут быть любого типа: базового, составного или типа указатель. Описание простейшего узла выглядит следующим образом:
struct node
{
int data; //поле данных для хранения целого числа
node *next; //поле указателя на следующий узел
};
Очереди
Очередь - это частный случай однонаправленного списка, добавление узлов в который выполняется в один конец, а выборка - из другого конца. Другие операции с очередью не определены. При выборке узел исключается из очереди.
Для работы с очередью будем использовать два указателя: на начало очереди (begin) и на ее конец (end):
node *begin, *end;
Теперь определим функции, реализующие указанные выше операции над очередью.
1. Начальное формирование очереди (создание самого первого узла)
void first(int d)
{
node *pv = new node; //выделяем динамическую память под первый узел
pv->data = d; //заполняем поле данных
pv->next = NULL; //заполняем поле указателя на следующий узел
begin = pv; //инициализируем указатель на начало списка
end = pv; //инициализируем указатель на конец списка
}
2. Добавление нового узла в конец очереди
void add(int d)
{
node *pv = new node; //выделяем динамическую память под новый узел
pv->data = d; //заполняем поле данных
pv->next = NULL; //заполняем поле указателя на следующий узел
end->next = pv; //указываем ссылку на новый узел
end = pv; //корректируем указатель на конец списка
}
3. Выборка узла из очереди
int del()
{
int temp = begin->data;
node *pt = begin; //определяем и инициализируем указатель на node
begin = begin->next;
delete pt;
return temp;
}
Пример работы с очередью.
int main()
{
//формирование первого узла очереди со значением 10
first(10);
//добавление в конец очереди пяти узлов со значениями 20,30,40,50 и 60
for (int i=20; i<70; i+=10)
add(i);
//вывод очереди на экран
puts("Ochered 1:");
node *pt = begin; //определяем переменную-указатель и инициализируем ее
while (pt != NULL)
{
printf("Value = %d\n", pt->data);
pt = pt->next;
}
//выборка четырех узлов из очереди
puts("\nSelection 4 nodes:");
for (i=0; i<4; ++i)
printf("%d\t", del());
//добавление в конец очереди трех узлов со значениями 100,200 и 300
puts("\n\nAddition 3 nodes:");
for (i=100; i<400; i+=100)
{
add(i);
printf("%d\t", i);
}
//вывод очереди на экран
puts("\n\nOchered 2:");
pt = begin;
while (pt != NULL)
{
printf("Value = %d\n", pt->data);
pt = pt->next;
}
return 0;
}
Стеки
Стек - это частный случай однонаправленного списка, добавление узлов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке узел исключается из стека.
Для работы со стеком будем использовать указатель (top), который всегда ссылается на вершину стека:
node *top;
Теперь определим функции, реализующие указанные выше операции над стеком.
1. Начальное формирование стека
void first(int d)
{
node *pv = new node; //выделяем динамическую память под первый узел
pv->data = d; //заполняем поле данных
pv->next = NULL; //заполняем поле указателя на следующий узел
top = pv; //инициализируем указатель на вершину стека
}
2. Добавление нового узла в стек
void push(int d)
{
node *pv = new node; //выделяем динамическую память под новый узел
pv->data = d; //заполняем поле данных
pv->next = top; //заполняем поле указателя на следующий узел
top = pv; //корректируем ссылку на вершину стека
}
3. Выборка из стека
int pop()
{
int temp = top->data; //в переменную temp заносим данные из вершины стека
node *pt = top; //определяем и инициализируем указатель на node
top = top->next; //корректируем ссылку на вершину стека
delete pt; //освобождаем память из-под удаленного узла
return temp;
}
Пример работы со стеком.
int main()
{
//формирование первого узла стека со значением 10
first(10);
//добавление в стек пяти узлов со значениями 20,30,40,50 и 60
for (int i=20; i<70; i+=10)
push(i);
//вывод содержимого стека на экран
puts("Stack 1:");
node *pt = top;
while (pt != NULL)
{
printf("Value = %d\n", pt->data);
pt = pt->next;
}
//выборка четырех узлов из стека
puts("\nSelection 4 nodes:");
for (i=0; i<4; ++i)
printf("%d\t", pop());
//добавление в стек трех узлов со значениями 100,200 и 300
puts("\n\nAddition 3 nodes:");
for (i=100; i<400; i+=100)
{
push(i);
printf("%d\t", i);
}
//вывод содержимого стека на экран
puts("\n\nStack 2:");
pt = top;
while (pt != NULL)
{
printf("Value = %d\n", pt->data);
pt = pt->next;
}
return 0;
}
Линейные списки
Самый простой способ связать множество узлов - сделать так, чтобы каждый узел содержал ссылку на следующий. Такой список называется однонаправленным (односвязным). Если добавить в каждый узел вторую ссылку - на предыдущий узел, получится двунаправленный список (двусвязный), если последний узел связать указателем с первым, получится кольцевой список.
Каждый узел списка содержит ключ, идентифицирующий этот узел. В качестве ключа в процессе работы со списком могут выступать те или иные поля данных или части поля данных если оно составного типа. Например, если создается линейный список из записей, содержащих данные о сотрудниках, то в качестве ключа может использоваться фамилия или год рождения или стаж работы и т.п.
Над списками можно выполнять следующие операции:
1) формирование первого узла списка;
2) добавление нового узла в конец списка;
3) поиск узла по ключу;
4) вставка нового узла в определенное место списка (после узла с заданным ключем);
5) удаление узла с заданным ключем;
6) вставка нового узла с упорядочением по ключу.
Рассмотрим простейший односвязный список, предназначеный для хранения целых чисел. Описание узла списка:
struct node
{
int data; //поле данных
node *next; //поле указателя на следующий узел
};
Для работы со списком будем использовать два указателя: на начало списка (begin) и на его конец (end):
node *begin, *end;
Теперь определим функции, реализующие указанные выше операции над списком.
1. Формирование первого узла списка
void first(int d)
{
node *pv = new node; //выделяем динамическую память под первый узел
pv->data = d; //заполняем поле данных
pv->next = NULL; //заполняем поле указателя на следующий узел
begin = pv; //инициализируем указатель на начало списка
end = pv; //инициализируем указатель на конец списка
}
2. Добавление нового узла в конец списка
void add(int d)
{
node *pv = new node; //выделяем динамическую память под новый узел
pv->data = d; //заполняем поле данных
pv->next = NULL; //заполняем поле указателя на следующий узел
end->next = pv; //указываем ссылку на новый узел
end = pv; //корректируем указатель на конец списка
}
3. Поиск узла по ключу
node *find(int key) //функция возвращает указатель на искомый узел
{
node *pt = begin; //определяем и инициализируем указатель на node
while (pt != NULL)
{
if (pt->data == key)
break; //нашли узел с нужным ключем и выходим из цикла
pt = pt->next; //переходим к следующему узлу списка
}
return pt;
}
4. Вставка нового узла в определенное место списка
void insert(int key, int d)
{
node *pkey; //определяем указатель на node
pkey = find(key); //ищем узел по заданному ключу
if (pkey != NULL)
{
//узел с заданным ключем найден
node *pv = new node; //выделяем динамическую память под новый узел
pv->data = d; //заполняем поле данных
pv->next = pkey->next; //устанавливаем связь нового узла с последующим
pkey->next = pv; //устанавливаем связь предыдущего узла с новым
if (pkey == end)
end = pv; //корректируем указатель на конец списка
}
}
5. Удаление узла с заданным ключем
int remove(int key)
{
node *pkey; //определяем указатель на node
pkey = find(key); //ищем узел по заданному ключу
if (pkey != NULL)
{
//узел с заданным ключем найден
if (pkey == begin)
{
begin = begin->next; //корректируем указатель на начало списка
if (pkey == end)
end = NULL; //корректируем указатель на конец списка
}
else
{
//поиск узла, предшествующего удаляемому
node *prev = begin; //определяем и инициализируем указатель на node
while (prev != NULL)
{
if (prev->next == pkey)
break; //нашли предшествующий узел и выходим из цикла
prev = prev->next; //переходим к следующему узлу списка
}
if (pkey == end)
{
prev->next = NULL;
end = prev; //корректируем указатель на конец списка
}
else
prev->next = pkey->next;
}
delete pkey; //освобождаем память из-под удаленного узла
return 1; //удаление выполнено успешно
}
return 0; //удаление не выполнено (нет узла с указанным ключом)
}
6. Вставка нового узла с упорядочением по ключу (предполагается, что первый узел существует)
void add_sort(int d)
{
node *pv = new node; //выделяем динамическую память под новый узел
pv->data = d; //заполняем поле данных
node *pt = begin, *prev = begin; //определяем и инициализируем указатели на node
while (pt != NULL)
{
if (pt->data > d)
{
//поместить новый узел перед текущим узлом (pt)
pv->next = pt;
if (pt == begin)
begin = pv; //корректируем указатель на начало списка
else
prev->next = pv; //помещаем в середину списка
return; //здесь может быть выход из функции
}
prev = pt;
pt = pt->next;
}
//поместить новый узел в конец списка
pv->next = NULL;
end->next = pv;
end = pv; //корректируем указатель на конец списка
}
Пример работы со списком.
int main()
{
//С о з д а н и е н е у п о р я д о ч е н н о г о с п и с к а
//формирование первого узла списка с ключом 10
first(10);
//добавление в конец списка четырех узлов с ключами 20,30,40 и 50
for (int i=20; i<60; i+=10)
add(i);
//вставка узла с ключом 200 после узла с ключом 20
insert(20, 200);
//вставка узла с ключом 400 после узла с ключом 40
insert(40, 400);
//удаление узла с ключом 40
if (!remove(40)) //эквивалентно if (remote(40) == 0)
puts("Remove --> not found");
//добавление в конец списка узла с ключом 500
add(500);
//вывод списка на экран
puts("Unordered spisok:");
node *pt = begin;
while (pt != NULL)
{
printf("Key = %d\n", pt->data);
pt = pt->next;
}
//С о з д а н и е у п о р я д о ч е н н о г о с п и с к а
//очистка списка (удаление из списка всех узлов)
while (begin != NULL)
remove(begin->data);
//формирование первого узла списка с ключом 20000
first(20000);
//добавление в список девяти узлов со случайными ключами
for (i=0; i<9; ++i)
add_sort(rand()); //функция rand генерирует случайное число
//вывод списка на экран
puts("\nOrdered spisok:");
pt = begin;
while (pt != NULL)
{
printf("Key = %d\n", pt->data);
pt = pt->next;
}
return 0;
}
Бинарные деревья
Бинарное дерево - это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, ноль, одну или две ссылки на различные бинарные поддеревья. На каждый узел имеется ровно одна ссылка. Начальный узел называется корнем дерева. Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие - потомками. Высота дерева определяется количеством уровней, на которых располагаются его узлы.
Если дерево организовано таким образом, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева - больше, оно называется деревом поиска (одинаковые ключи не допускаются). В дереве поиска можно найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значения ключа в каждом узле.
Дерево является рекурсивной структурой данных, поскольку каждое поддерево также является деревом.
Для бинарных деревьев определены следующие операции:
- формирования первого узла дерева;
- включения узла в дерево;
- поиска по дереву;
- обхода дерева;
- удаления узла.
Простейшее бинарное дерево, предназначенное для хранения и выборки целых чисел. Описание узла дерева выглядит следующим образом:
struct node
{
int data; //поле данных
node *left; //поле указателя на левого потомка
node *right; //поле указателя на правого потомка
};
Эффективная программная реализация бинарных деревьев основана на использовании рекурсивных алгоритмов и здесь не рассматривается.
ПРАКТИЧЕСКИЙ РАЗДЕЛ
Общие указания
Указания по выбору варианта
Каждая из ИПР и КР содержит по 20 вариантов заданий. Выбор варианта, в соответствии с которым необходимо написать и отладить соответствующую программу на языке программирования С, выполняется следующим образом.
Если две последние цифры номера вашей зачетки образуют число N, не превышающее 20, то это число и будет номером вашего варианта. Если же число N будет больше двадцати, то необходимо из N последовательно вычитать число 20 до тех пор, пока полученный остаток не окажется меньшим или равным числу 20. Этот остаток и будет представлять собой ваш номер варианта, по которому нужно выполнить две ИПР и две КР.
Например, две последние цифры номера вашей зачетки представляют собой число N = 47. В этом случае N > 20 и, поэтому, придется дважды вычитать из числа N число 20 для получения остатка, не превосходящего число 20. Этим остатком будет число 7, которое и будет вашим номером варианта.