30. Динамические типы данных. Очередь. Основные операции над элементами очереди. Примеры.

Очередь — это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка — из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first in — first out, первым пришел — первым ушел). Очередь проще всего представить себе, постояв в ней час-другой. В программировании очереди применяются, например при моделировании, диспетчеризации задач операционной системой, буферизованном вводе/выводе.

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

Выделим типовые операции над очередями:

• добавление элемента в очередь (помещение в хвост);

• удаление элемента из очереди (удаление из головы);

• проверка, пуста ли очередь;

• очистка очереди.

31. Динамические типы данных. Стек. Основные операции над элементами стека. Примеры.

Стек — это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел — первым ушел).

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

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

Выделим типовые операции над стеком и его элементами:

• добавление элемента в стек;

• удаление элемента из стека;

• проверка, пуст ли стек;

• просмотр элемента в вершине стека без удаления;

• очистка стека.

32. Динамические типы данных. Бинарное сбалансированное дерево. Правила обхода. Основные операции над элементами. Примеры.

struct Node{

int d;

Node *left;

Node *right;

};

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

Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие — потомками. Высота дерева определяется количеством уровней, на которых располагаются его узлы.

Бинарное дерево называется сбалансированным в целом, если высота левого поддерева отличается от высоты правого поддерева не более чем на единицу, оно называется полностью сбалансированным, если показатель каждого узла = 0.

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

function way_arouncl ( дерево ){

way_around ( левое поддерево )

посещение корня

way_around ( правое поддерево )

}

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

Для бинарных деревьев определены операции:

• включения узла в дерево;

• поиска по дереву;

• обхода дерева;

• удаления узла.

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

Прямой обход . Сначала посещается корень n , затем в прямом порядке узлы поддерева T 1 , далее все узлы поддерева T 2 и т.д. Последними посещаются в прямом порядке узлы поддерева T m .

Обратный обход . Сначала посещаются в обратном порядке все узлы поддерева T 1 , затем в обратном порядке узлы поддеревьев T 2 … T m , последним посещается корень n .

Симметричный обход . Сначала в симметричном порядке посещаются все узлы поддерева T 1 , затем корень n , после чего в симметричном порядке все узлы поддеревьев T 2 … T m .