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

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

Односвязным списком является элемент, называемый головой, и стоящий после него односвязный список, называемый хвостом: [x|L], где x — элемент, а L — какой-то список (прямая черта служит для разделения элементов).

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

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

Пустым списком будем считать указатель NULL. А непустым — указатель на такую структуру:

typedef struct ONE_WAY_LIST

{ int data;

struct ONE_WAY_LIST* tail;

} one_way_list;

Поле data — это данные, хранящиеся в списке. Разумеется, они могут быть заменены на любые другие. А tail — хвост списка.

20 Списки общего вида. Графы.

Граф – это совокупность непустого множества вершин и множества пар вершин (дуг (для неор.) или ребер). 2 вершины называются смежными, если в графе есть дуга (ребро), соединяющая эти вершины.

Граф представляется в виде матрицы смежности. Матрица смежности для графа А — матрица M(A) = [aij] порадка n { aij = 1, if есть ребро (vi, vj); elseaij = 0 } (аналогично для неор. Графа)

Другие представления графа в ЭВМ: а) целочисленный массив из n столбцов и m сторок (m – макс. Число вершин, смежных с произвольной вершиной графа) – удобен, когда у многих вершин графа количество смежных близко к m б) граф описывается в виде основного списка вершин и списков дуг; в основном списке перечислены узлы (вершины графа), каждый из которых указывает на свой список дуг; каждый узел списка дуг указывает на узел основного списка, входящего в соответствующую дугу

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

Поиск в ширину: Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам – метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т.д. {реализуется через очередь}.

Уровни описания структур данных.

При описании объекта необходимо четко понимать его абстрактные свойства (и их реализацию в языках)

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

Функциональная спецификация типа данных – внешнее формальное определение, не зависящее от языка программирования и ЭВМ. Дать формальное определение типа данных – это задать: 1)множество значений этого типа 2)множество изображений этих значений с правилом интерпритаций 3)базовое множество атрибутов этого типа: изображения (некоторых) выделенных значений, операции/отношения и их свойства и функции создания, доступа и модификации объектов этого типа.

Пример: целый тип – последовательность цифр со знаком или без (множество изображений значений); с операциями [=, -, *, /, div, mod ], их свойствами [ассоциативность, дистрибутивность, …] и отношениями [=,!=, <, <=, >=, >] (а также ряд функций аргументами/результатами которых являются значения этого типа); которую можно представить в полиномиальной форме в позиционной системе счисления с основанием 10

Логическое описание – отображение функциональной спецификации на средства выбранного языка программирования. Возможны 2 ситуации в выбранном языке: 1) есть подходящий тип данных 2) нет. в таком случае – разбить объект на части, которые можно описать на выбранном языке).

Физическое представление – как тип представляется в памяти ЭВМ {описание всегда связанно с линеаризацией (2мерный массив в Фортране линеаризован “по столбцам”, а в С/Паскале - “по строкам”)}

2 вида физического представления объектов в памяти: сплошное и цепное

Сплошное - объект размещён в непрерывном куске памяти (для простых объектов)

Цепное – объект разбит на куски, расположенные в памяти “как попало” и в каждом есть указатель на следующий (для динамических объектов).

 

21 Понятие рекурсии Рекурсия и итерация. Примеры.

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

Рекурсия в программирование – вызов функциеё самой себя.

Т.к. Мы используем рекурсию для сведения программы к более простой (как и цикл) рекурсия должна заканчиваться! (необходимо условие вывода из рекурсии)

вызов подпрограммой самой себя по имени. Такая рекурсия называется прямой. Если программа Р вызывает себя посредством другой Q, то рекурсия косвенная.

Существует более сложная классификация рекурсий: линейная, повторная (концевая, хвостовая), каскадная, удаленная, взаимная

определение факториала от n: n! = n * (n-1)! через рекурсию:

int f (int i){

return (i > 0)? i * f(i – 1): 1;

}

Итерация – многократно повторяющиеся действия, не приводящие к вызовам самих себя (шаг цикла).{итерация намноо дешевле рекурсии}

определение факториала от n: n! = n * (n-1)! через итерации

int i = 0;

int f = 1;

while(i < n)

f *= i++;

Деревья. Двоичные деревья.

Пусть Т – некоторый тип данных. Деревом типа Т называется структура, образованная элементом типа Т (корнем) и конечным (возможно пустым) множеством с переменным числом элементов – деревьев типа Т (поддеревьев) {не пустое}

{дерево с нулевым разветвлением – линейная структура}

{для описания взаимного расположения элементов взята терминология из генеалогичекого дерева (отец и сын; потомок и предок; НО дочерняя вершина); сыновья одного дерева – братья}

Приведём определения, относящиеся к дереву: а) элементы типа Т, входящие в дерево называют узлами (вершинами) б) число поддеревьев данного узла называют его степенью в) узел, не имеющий поддеревьев, называют листом (концевым узлом) г) уровень в дереве определяется рекурсивно: уровень корня каждого поддерева данного узла на “1” больше уровня донного узла; уровень корня всего дерева = 1. д) уровень дерева – макс. Уровень его вершин.

Если порядок сыновей существенен, то сыновей упорядочивают “по старшенству” (подобно очереди), т.е. чем больше номер, тем дальше от предка. Определённые таким образом деревья называют деревьями общего вида.

Двоичное (бинарное) дерево – конечное множество узлов, которое или пусто, или состоит из корня и 2х непересекающихся поддеревьев (левое и правое) {может быть пустым} (Пример:схема спортивного турнира)

Предком для узла x называется узел дерева, из которого существует путь в узел x. Потомком узла x называется узел дерева, в который существует путь (по стрелкам) из узла x.

Родителем для узла x называется узел дерева, из которого существует непосредственная дуга в узел x.

Сыном узла x называется узел дерева, в который существует непосредственная дуга из узла x. Уровнем узла x называется длина пути (количество дуг) от корня к данному узлу.

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

23 Двоичное дерево. Функциональная спецификация

Пусть BTt -двоичное дерево компонент типа T. Он характеризуется следующими операциями: а) создать (всегда создаётся пустое дерево) б) проверка на пустоту в) построить дерево (из корня и 2х поддеревьев) г) получение корня д) получение левого/правого поддеревьев е) уничтожение дерева

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