Тема 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;

}