Семинар 9. Динамические структуры данных. Работа со списками

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

Основными операциями над структурой данных в целом и отдельными ее элементами являются:

· создание и уничтожение структуры данных;

· включение и исключение элементов;

· доступ к элементам и др.

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

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

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

В однонаправленном (односвязном) списке элемент данных содержит только один указатель на следующий элемент. У последнего элемента значение этого указателя равно нулю (NULL). Кроме этого есть переменная, в которой хранится указатель на первый элемент списка. Если значение этой переменной равно нулю, то список пуст. Схематично подобную структуру данных можно представить так:

Частными случаями односвязного списка являются структуры данных стек и очередь.

Стек (англ. stack – стопка) – это список, в котором элемент всегда записывается и извлекается с одного конца списка (с начала списка), поэтому элемент, занесенный последним, извлекается первым.

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

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

Частным случаем двунаправленного списка является дек (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь). то список, в котором можно добавлять и удалять в произвольном порядке элементы с двух сторон. Первый и последний элементы дека соответствуют входу и выходу дека.

Пример 1. Реализация стека

Для хранения элемента стека создадим структуру Cell. Поле d используется для хранения целочисленного значения, поле next – для хранения указателя на следующий элемент.

Реализуем следующие операции: помещение элемента в стек (put_stack), извлечение элемента из стека (get_stack) и освобождение памяти, занимаемой элементами стека (clear_stack). Всем этим функциям в качестве аргумента передается указатель на первый элемент стека, причем передается «по ссылке», так как его значение меняется при выполнении функции. Нужно не забывать вызывать в конце работы функцию clear_stack, так как память под элементы выделяли мы, мы же должны ее освободить.

Пример 2. Реализация односвязного списка.

Для хранения элемента списка используем ту же структуру Cell, которая использовалась в примере 10.1. Реализуем следующие операции:

· помещение элемента в конец списка (put_list);

· удаление элемента с заданным номером (remove_list);

· поиск элемента c заданным номером (find_list);

· вывод на экран элементов списка (print_list);

· освобождение памяти, занимаемой элементами списка (clear_list).

Всем этим функциям в качестве аргумента передается указатель на первый элемент списка и, если нужно, указатель на последний элемент списка. Функция Prim10_2 демонстрирует работу со списком, вызывая вышеприведенные функции.