Введение

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

Структуры данных фиксированного размера – массивы, структуры. Память под данные выделяется на этапе компиляции. Необходимый объем известен до начала выполнения программы и задан в виде константы.

Динамические структуры – линейные списки, стеки, очереди и бинарные деревья. Память выделяется во время выполнения программы с помощью операций new или функций malloc(), calloc(). Объем должен быть известен до распределения памяти.

Динамические структуры данных различаются способами связи элементов и допустимыми операциями и занимают несмежные участки оперативной памяти.

Линейные структуры данных – списки, стеки, очереди. Нелинейные структуры – бинарные деревья.

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

Стек – структура данных, вставка и удаление данных производится в вершине.

Очередь – структура данных, связанная с ожиданием. Вставка производится в конце очереди (хвост), а удаление – в начале очереди (голова).

Бинарные деревья – структура данных, состоящая из узлов, каждый из которых содержит не более двух ссылок на бинарные деревья.

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

Динамические структуры применяют для эффективной работы с данными: сортировка и поиск данных, устранение дубликатов, представление каталогов файловых систем и компиляция выражений в машинный язык. Например, при упорядочивании массива данных организуется линейный список. Для поиска элемента данные представляются в виде бинарного дерева.

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

Формализация структур данных производится структурным и объектно-ориентированным методами программирования.

1. Линейные структуры данных

1.1. Линейный список

Линейные структуры данных – связанный список, стек и очередь.

Связанный список – набор объектов автореферентного класса, называемых узлами, соединенных указателями-связками.

Автореферентный класс – класс, содержащий элемент-указатель, ссылающийся на объект того же классового типа.

Доступ к связанному списку осуществляется через указатель (ключ) на первый узел списка, обращение к последующему узлу осуществляется через указатель, хранящийся в предыдущем узле. Указатель-связка в последнем узле списка устанавливается в нуль, который отмечает конец списка. Данные сохраняются динамически – узлы создаются по мере необходимости. Узел может содержать данные любого типа, включая объекты других классов. Если узлы содержат указатели базового класса на объекты базового или производного классов, связанных отношением наследования, то можно создавать из таких узлов связанный список и полиморфно обрабатывать объекты посредством вызова виртуальных функций.

Над списками выполняются операции:

- формирование списка (создание первого элемента);

- добавление элемента в конец списка;

- чтение элемента с заданным ключом;

- вставка элемента в заданное место списка (до или после элемента с заданным ключом);

- удаление элемента с заданным ключом;

- упорядочивание списка по ключу.

Способы реализации списков:

- односвязный список – список начинается с указателя на первый узел. Узел содержит указатель на последующий узел. Заканчивается указателем, имеющим значение нуль. Односвязный список можно проходить в одном направлении;

- циклический односвязный список – узел начинается с указателя на первый узел. Каждый узел содержит указатель на следующий узел. Последний узел не содержит нулевого указателя и ссылается на первый узел;

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

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

Связные списки имеют преимущества перед массивами:

1. cвязанные списки являются динамическими;

2. cвязанные списки заполняются до отказа, когда памяти в системе недостаточно для удовлетворения запросов динамического выделения памяти;

3. cвязанный список производит эффективную операцию вставки/удаления в любом месте списка [1; 2; 3].