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

Семинар 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 демонстрирует работу со списком, вызывая вышеприведенные функции.