Деревья

Date: 2015-10-07; view: 454.

Списки

Структуры данных

Дополнительно

Экономичность мультимедийных потоков. Кодеки.

Мы рассмотрели, как различные данные представляются в двоичном виде. Но, как правило, компьютер обрабатывает не одиночные данные, а их большие совокупности. Естественно встает вопрос об организации совокупности данных и удобства их обработки.

Рассмотрим основные структуры данных.

(Кнут т.1 гл.2)

Линейный список — это множество, состоящее из п >= 0 элементов Х [1], Х [2], ..., Х [n], структурные свойства которого по сути ограничиваются лишь линейным (одномерным) относительным поло­жением элементов, т. е. теми условиями, что если п > 0, то Х [1] явля­ется первым элементом; если 1<: k <: п, то за k-м элементом Х [k] следует Х [k + 1]; Х [n] является послед­ним элементом. Т.е., вообще говоря, элементы могут иметь различную структуру, размеры и т.д.

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

1) Получить доступ к k-му элементу списка, чтобы проанализировать и/или изменить содержимое его полей.

2) Включить новый узел непосредственно перед k-м элементом.

3) Исключить k-й. узел.

4) Объединить два (или более) линейных списка в один список.

5) Разбить линейный список на два (или более) списка.

6) Сделать копию линейного списка.

7) Определить количество элементов в списке.

8) Выполнить сортировку элементов списка в возрастающем порядке по некоторым полям в элементах.

9) Найти в списке узел с заданным значением в некотором поле.

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

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

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

Очередь — линейный список, в котором все включения произво­дятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце(FIFO).

Дек (double ended queue - очередь с двумя концами) — линейный список, в котором все включения и исключения (и обычно всякий доступ) де­лаются на обоих концах списка.

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

Двунаправленные списки. Все рассмотренные выше списки имеют строгую упорядоченность в одном направлении: вперед. Для удобства поиска строят двунаправленные списки, для которых существует не только «следующий», но и «предыдущий» элемент. Двунаправленность, естественно, требует дополнительных затрат как по памяти, так и по дополнительным операциям (надо менять две ссылки вместо одной).

Одним из простейших обобщений списков являются массивы. Массивы представляют собой упорядоченную совокупность однородных элементов. Как правило, элементы массива располагаются в памяти последовательно. Т.о. для одномерного массива а₀, а₁, …, а_n положение к-го элемента определяется по формуле а[0]+к_. Для двумерного a[i,j] = a[0,0]+n*i+j.

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

Определим формально дерево как конечное множество Т, со­стоящее из одного или более узлов, таких, что

a) Имеется один специально обозначенный узел, называемый корнем данного дерева.

b) Остальные узлы (исключая корень) содержатся в т > 0 по­парно не пересекающихся множествах Т_i, ..., Т_m, каждое из которых в свою очередь является деревом. Деревья Т_i, ..., Т_m называются поддеревьями данного корня.

Это определение является рекурсивным, т. е. мы определили дерево в терминах самих же деревьев. Разумеется, никакого пороч­ного круга здесь не возникает, поскольку деревья с п > 1 узлами определяются с использованием понятия дерева с количеством уз­лов, меньшим чем п', следовательно, наше определение дает понятия деревьев с двумя узлами, тремя узлами, в конечном итоге с любым числом узлов. Можно попытаться дать и нерекурсивное определение дерева, но рекурсивное опреде­ление кажется более подходящим, так как рекурсивность являет­ся естественной характеристикой структур типа дерева. Рекурсив­ный характер деревьев налицо также и в природе, поскольку почки молодого дерева вырастают в ветви, имеющие собственные почки, которые дают новые ветви и т. д. Основываясь на рекурсивном определении, подобном тому, которое мы привели выше, легко дать строгие доказательства многих важных фактов относительно де­ревьев, используя индукцию по числу узлов в дереве.

Из нашего определения следует, что каждый узел дерева явля­ется корнем некоторого поддерева, которое содержится в этом де­реве. Число поддеревьев данного узла называется степенью этого узла. Узел с нулевой степенью называется концевым узлом; иногда его называют листом. Неконцевые узлы часто называют узлами разветвления. Уровень узла по отношению к дереву Т определяется следующим образом: говорят, что корень имеет уровень 1, а дру­гие узлы имеют уровень на единицу выше их уровня относительно содержащего их поддерева Т, этого корня.

На рис. 15 показано дерево с семью узлами. Проиллюстрируем на нем введенные нами понятия. Корнем дерева является А; дерево имеет два поддерева: {В} и [С, D, Е, F, G]. Корнем дерева {С, D, Е, F, G} является С. Узел С имеет уровень 2 относительно всего дерева; он имеет три поддерева: [D], [Е] и {F, G), и, следовательно, его степень равна 3. Узлы В, D, Е и G являются конце­выми узлами; F—единственный узел степени 1, а G—единствен­ный узел уровня 4.

Обход деревьев

Сначала вглубь и сначала вширь

[1] Фомин С.В. Системы счисления, издание пятое, М., Наука, главная редакция физико-математической литературы, 1987, серия Популярные лекции по математике, вып. 40

[2] двоично-десятичная форма представления чисел Ее появление объясняется следующим. При обработке больших массивов десятичных чисел (например, больших экономических документов) приходится тратить существенное время на перевод этих чисел из десятичной системы счисления в двоичную для последующей обработки и обратно -для вывода результатов. Каждый такой перевод требует выполнения двух - четырех десятков машинных команд. С включением в состав отдельных ЭВМ специальных функциональных блоков или спецпроцессоров десятичной арифметики появляется возможность обрабатывать десятичные числа напрямую, без их преобразования, что сокращает время вычислений. При этом каждая цифра десятичного числа представляется двоичной тетрадой. Например, A₁₀=3759, A_2-10= 0011 0111 0101 1001. Положение десятичной точки (запятой), отделяющей целую часть от дробной, обычно заранее фиксируется. Значение знака числа отмечается кодом, отличным от кодов цифр. Например, ⌠+■ имеет значение тетрады ⌠1100■, а ⌠-■ - ⌠1101■.