Фундаментальные структуры данных. Списки. Деревья

Фундаментальные структуры данных

Списки

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

• Массивы
• Стеки
• Очереди
• Деки
• Линейные списки

Списки

Список (LIST) – линейная структура данных, представляющая собой последовательность элементов определенного типа. Количество элементов n называется длиной списка. Каждый элемент имеет позицию в списке. Список называется пустым, если он не содержит элементов. Примеры. 1. Список студентов в группе. 2. Список покупок. 3. Список приглашенных.

Списки

АДТ LIST обычно использует следующие операции: INSERT (x, p, L) – вставляет элемент x в позицию p списка L. LOCATE (x, L) – возвращает позицию элемента x в списке L. RETRIEVE (p, L) – возвращает элемент, который стоит в позиции p. DELETE (p, L) – удаляет элемент в позиции p списка L. NEXT (p, L) – возвращает следующую позицию от позиции p в списке L. PREVIOUS (p, L) – возвращает предыдущую позицию от позиции p в списке L.

Списки

MAKENULL (L) – делает список пустым. PRINTLIST (L) – печатает элементы списка L в порядке расположения. Кроме того, могут быть реализованы следующие операции: Копирование списка. Упорядочение списка. Объединение списков. Разделение списков. Сохранение и восстановление списка. Другие.

Списки

Реализация списков на основе статических массивов Элементы списка размещаются в смежных ячейках массива. Легко просматривать содержимое списка и вставлять новые элементы в его конец. Вставка нового элемента в середину списка требует перемещения всех последующих элементов на одну позицию к концу массива, чтобы освободить место для нового элемента. Удаление элемента также требует перемещения элементов, чтобы закрыть освободившуюся ячейку. Позиция элемента определяется его индексом.

Списки

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

Списки

Динамическая реализация списков Односвязные (однонаправленные) списки struct node { информационные поля; struct node * next; }; Указатель указывает на следующий элемент в списке. Позиция элемента в списке определяется указателем. Список можно проходить только в прямом направлении.

Списки

Динамическая реализация списков Двусвязные (двунаправленные) списки struct node { информационные поля; struct node *next; struct node *previous; }; Указатели указывают на следующий и предыдущий элементы в списке. Позиция элемента в списке определяется указателем. Список можно проходить как в прямом, так и в обратном направлении.

Фундаментальные структуры данных

Деревья

Нелинейные структуры данных

• Деревья
• Леса
• Графы

Деревья

Дерево (TREE) – конечное множество Т одного или нескольких узлов со следующими свойствами: а) существует один выделенный узел – корень (root) данного дерева Т; б) остальные узлы (за исключением корня) распределены среди m>=0 непересекающихся множеств Т1,…,Тm, и каждое из этих множеств, в свою очередь, является деревом; эти деревья называются поддеревьями данного корня. Данное определение является рекурсивным.

Деревья

Степенью узла называется количество поддеревьев для этого узла. Степень дерева – max степеней его узлов. Листом или концевым узлом называется узел со степенью нуль. Уровень узла определяется рекурсивно: а) уровень корня равен нулю, б) уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева Т, содержащего данный узел. Каждый узел называется родителем корней его поддеревьев, а сами корни – детьми.

Деревья

m-арное дерево - дерево степени m. Полным m-арным деревом называется дерево, все узлы которого, кроме листьев, имеют степень, равную m. Ключом называется часть информации, по которой ее можно идентифицировать. Бинарное дерево поиска – бинарное дерево, для каждого узла которого все ключи в левом поддереве меньше ключа в данном узле, а все ключи в правом поддереве больше ключа в данном узле.

Деревья

АДТ TREE обычно использует следующие операции: INSERT (x, Т) – вставляет элемент x в дерево Т. SEARCH (x, T) – ищет элемент x в дереве Т. DELETE (x, T) – удаляет элемент x в дереве Т. INORDER (T) – обход дерева Т в прямом порядке (порядковая выборка). PREORDER (Т) – предварительная выборка. POSTORDER (T) – отложенная выборка. MAKENULL (T) – делает дерево Т пустым. Могут быть реализованы и другие операции.

Деревья

Реализация деревьев в помощью массивов Размещение информации в массиве производится по уровням дерева, начиная с корня, а на уровне слева направо. Если какой-нибудь узел отсутствует, то соответствующий элемент в массиве пропускается. Он может быть заполнен при последующей вставке элементов в дерево. Если i есть индекс родителя, у потомков у потомков будут соответственно индексы 2*i+1 и 2*i+2. И обратно, зная индекс потомка, можно вычислить индекс родителя.

Деревья

Реализация деревьев в помощью указателей struct node { информационные поля; // int data; struct node *left; struct node *right; }; где left – указатель на левого потомка, а right – указатель на правого потомка. В узел может быть добавлен указатель на родителя struct node *parent