39 Динамич типы данных (1006387)

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

Текст из файла

Вопрос 39. Динамические структуры данных (списки, деревья, стеки, очереди), способы их представления и основные операции над ними.

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

Линейный список - это множество, состоящее из n0 узлов X[1],...,X[n], структурные свойства которого ограничиваются линейным относительным положением узла, т.е. теми условиями, что если n>0, то X[1] является первым узлом; если 1<K<n, то k-му узлу X[k] предшествует X[k-1], а за ним следует X[k+1]; X[n] является последним узлом.

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

В этом случае:

LOC(X[j+1])=LOC(X[j])+C,

где С - количество слов в узле. В простейшем случае С=1. В общем случае

где - константа, называемая базовым адресом и является адресом гипотетического узла X[0].

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

Каждый элемент связного списка может иметь следующую структуру:

А(ключ, ссылка на следующий элемент, значение переменной). Для последнего элемента ссылка на следующий элемент принимает значение NULL.

Рассмотрим линейный связный список.

Рис 1 Пример списка

Типичные операции, которые выполняются с линейными списками:

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

Allocate(q, Size(A)); q^.next=p; p=q;

1. Включение в любое место списка – пусть после элемента списка, на который указывает ссылка p, нужно включить элемент заданный ссылкой q, тогда:

   1. Включение после р

q^.next=p^.next; p^.next=q;

Рис 2 Включение в список после элемента p

1. Включение перед р – новая компонента включается после р, а затем они меняются местами.

Allocate(q, Size(A)); q^=p^;

p^.key=k; p^.next=q;

Рис 3 Включение в список перед элементом р

1. Получить доступ к k-му узлу для анализа или изменения его полей или осуществить проход по списку – операция осуществляется последовательно в цикле.

2. Исключение:

   1. Исключение элемента, следующего за p^ -

r=p^.next; p^.next=r^.next;

Рис 4 Исключение элемента, следующего за p

1. Исключение самого указанного элемента – это труднее, но можно исключить последующий элемент, а перед этим его значение «передвигается» вперед. Так можно поступать, когда у p есть предшествующий, т. Е. если р – не последний.

1. Объединить несколько списков – осуществляется с помощью операции добавления элемента в начало списка.

2. Разбить список на несколько подсписков;

3. Определить количество узлов списка;

4. Выполнить сортировку узлов списка в возрастающем порядке по некоторым полям;

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

Специальные типы линейных списков

Часто встречаются линейные списки, в которых включение, исключение или доступ к значениям почти всегда производятся в первом или последнем узле. Они получают специальные названия:

Стек - линейный список, в котором все включения и исключения (всякий доступ) делается в одном конце списка.

Последовательно распределение используется при работе со стеком. Для этого достаточно иметь переменную Т, которую называют указателем стека. Когда стек пуст Т=0. Если необходимо разместить новый элемент Y в стек, то выполняются:

1) TT+1; X[T] Y.

При выборке выполняется:

2) YX[T]; TT-1.

Стек часто называют push-down списком, магазином или списком типа LIFO (Last-In-First-Out).

Очередь - линейный список, в котором все включения делаются на одном конце, а исключения на другом;

Дек (очередь с двумя концами - double-ended gueue - degue) - где включения и исключения (всякий доступ) делаются на обоих концах списка.

Представление очереди или дека требует использование двух указателей F и R (начало и конец). При пустой очереди F=R=0.

Включение в очередь сводится к:

3) RR+1; X[R] Y.

Исключение:

4) FF+1; YX[F]; если F=R, то FR0.

Обычно для размещения стека или очереди выбирается некоторое фиксированное пространство. Пусть это некоторое M, т.е. имеем X[1]...X[M] и их замыкаем в кольцо так, что за X[M] следует X[1]. Этот случай циклической очереди.

Циклический связный список

Этот список обладает той особенностью, что связь его последнего узла не равна NULL, а указывает на первый узел списка. Пусть каждый узел имеет два поля: INFO и LINK. Используем специальную переменную связи PTR, которая указывает на самый правый узел списка, а LINK(PTR) является адресом самого левого узла.

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

а) Включить Y слева: PAVAIL, INFO(P) Y,

LINK(P) LINK(PTR), LINK(PTR) P.

b) Включить Y справа: Включить Y слева, затем PTRP.

c) Установить Y по левому узлу и исключить узел:

PLINK(PTR), YINFO(P), LINK(PTR) LINK(P), AVAILP.

Деревья

Определим дерево следующим образом: дерево с базовым типом Т – это

1. либо пустое дерево

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

Рис 5 Дерево, представленное в виде графа

Упорядоченное дерево – это дерево, у которого ребра исходящие из каждой вершины, упорядочены.

Рис 6. Различные упорядоченные деревья

Вершина y, находящаяся непосредственно ниже вершины x, называется непосредственным потомком x, а вершину х называют предком y. Считается, что корень дерева находиться на уровне 0. Максимальный уровень какой-либо из вершин дерева называется его глубиной или высотой.

Если элемент не имеет потомков, то его называют терминальной вершиной или листом, а нетерминальную вершину называют внутренней. Число непосредственных потомков внутренней вершины называют ее степенью. Максимальная степень всех вершин есть степень дерева. Число ветвей или ребер, которые нужно пройти от корня к вершине х, называется длиной пути к х. Корень имеет путь 0. Длина пути всего дерева определяется как сумма длин путей для всех его компонент, ее называют длинной внутреннего пути.

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

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

Рис 7 Представление дерева в машине

Дерево называется идеально сбалансированным, если число вершин в его левых и правых поддеревьях отличается не более чем на 1.

Основные операции:

1. Обход дерева

   1. Сверху вниз: рис 6 а) – А, В, С (корень посещается раньше, чем поддеревья)

   2. Слева направо: В, А, С

   3. Снизу вверх: В, С, А (корень посещается после поддеревьев).

2. Поиск по дереву с включением – если элемент найден, то его значение изменяется, если нет, то он включается в дерево.

3. Сортировка.

4. Исключение – изъятие из упорядоченного дерева вершины с ключом х. Самый простой вариант исключения – это исключение терминальной вершины (листа) или вершина с одним потомком. Трудность возникает, если нужно удалить элемент с двумя потомками. В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева, причем они должны иметь самое большее одного потомка.

Рис 8 Различные варианты исключения, выполненные последовательно

Дерево поиска – дерево, организованное так, что для каждой вершины ti справедливо утверждение, что все ключи левого поддерева ti меньше ключа ti, а все ключи правого поддерева больше его. В таком дереве легко обнаружить искомый ключ – достаточно, начав с корня, двигаться к левому или правому поддереву на основании лишь одного сравнения с ключом текущей вершины. Так как из n элементов можно организовать двоичное дерево с высотой не более log n, то если дерево идеально сбалансировано, поиск осуществляется максимально за log n сравнений.

Деревья оптимального поиска – дерево поиска, организованное таким образом, что общее число шагов для большого числа обращений было минимальным. В этом случае учитывается частота обращений для каждого элемента, которая приписывается в виде веса элемента.

Б-деревья порядка m называется дерево, обладающее следующими свойствами :

• каждая вершина имеет не более m потомков

• каждая вершина, кроме корня и висячих вершин , имеет не менее m/2 потомков

• не висячая вершина с k потомками содержит k-1 ячеек информации

• корень, если он не является висячей вершиной, имеет не менее 2 потомков

• все висячие вершины расположены на одном уровне и не содержат информации

На рис 9 представлено Б-дерево с 3 ключами на узел. Ключи во внутреннем узле окружены указателями или смещениями записей, отсылающими к ключам, которые либо все больше, либо все меньше окруженного ключа. Например, все ключи, меньшие 22, адресуются левой ссылкой, все большие - правой. Для простоты здесь не показаны адреса записей, связанные с каждым ключом.

Рис. 9: Б-дерево

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)