Тема Структуры данных и алгоритмы

Вид материала

Конспект

Содержание 6.1.2 Машинное представление оpгpафов 6.2.3 Бинарные деревья. 6.2.4 Представление любого дерева, леса бинарными деревьями. 6.2.5 Машинное представление деревьев в памяти ЭВМ. 6.2.6 Основные операции над деревьями. 6.4 Сбалансированные деревья 7.2. Последовательные файлы 7.3. Файлы, организованные разделами

Подобный материал:

• Программа дисциплины «Структуры данных», 88.1kb.
• Программа курса Алгоритмы программирования, 47.59kb.
• Цель любой программы обработка данных, т е. надо грамотно построить структуры данных, 165.23kb.
• Borland Turbo Pascal, знать простые основные алгоритмы работы с простыми типами данных, 316.19kb.
• Об использовании структур представления данных для решения возникающих задач; знать, 116.73kb.
• Курс, 1-й семестр лекции (51 час), экзамен практикум на ЭВМ (68 часов), зачет (с оценкой), 24.4kb.
• Программа дисциплины структуры и алгоритмы компьютерной обработки данных для специальности, 506.16kb.
• Введение Предмет "Программирование", 19.2kb.
• Рабочей программы дисциплины Структуры и алгоритмы обработки данных по направлению, 21.62kb.
• Ю. А. Самарский 10 июня 2008 г. Программа, 97.03kb.

Тема 6. Нелинейные структуры данных


6.1 Графы

6.1.1 Логическая структура, определения

Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.

Многосвязная структура обладает следующими свойствами:

1). на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

2). каждый элемент может иметь связь с любым количеством других элементов;

3) каждая связка (ребро, дуга) может иметь направление и вес.

В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра графа могут иметь направленность, показываемую стрелками, тогда они называются ориентированными, ребра без стрелок - неориентированные.

Граф, все связи которого ориентированные, называется ориентированным графом или орграфом; граф со всеми неориентированными связями - неориентированным графом; граф со связями обоих типов - смешанным графом.

Для ориентированного графа число ребер, входящих в узел, называется полустепенью захода узла, выходящих из узла - полустепенью исхода. Количество входящих и выходящих ребер может быть любым, в том числе и нулевым. Граф без ребер является нуль-графом.

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

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

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

Логически структура-граф может быть представлена матрицей смежности или матрицей инцидентности.


^ 6.1.2 Машинное представление оpгpафов

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

МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ. При использовании матриц смежности их элементы представляются в памяти ЭВМ элементами массива. При этом, для простого графа матрица состоит из нулей и единиц, для мультиграфа - из нулей и целых чисел, указывающих кратность соответствующих ребер, для взвешенного графа - из нулей и вещественных чисел, задающих вес каждого ребра.

СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ. Орграф представляется связным нелинейным списком, если он часто изменяется или если полустепени захода и исхода его узлов велики. Имеются два основных варианта представления орграфов связными нелинейными списковыми структурами.

В первом варианте два типа элементов - атомарный и узел связи (см. раздел 5.5).

Более рационально представлять граф элементами одного формата, двойными: атом-указатель и указатель-указатель или тройными: указатель -data/down - указатель (см.раздел 5.5).


6.2 Деревья

6.2.1 Основные определения

Дерево - это граф, который характеризуется следующими свойствами:

1. Cуществует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется КОРНЕМ (рис. 6.8 - A,G,M - корни).
   
2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры.
   
3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.
   

Ориентированное дерево - это такой ациклический орграф (ориентированный граф), у которого одна вершина, называемая корнем, имеет полустепень захода, равную 0, а остальные - полустепени захода, равные 1. Ориентированное дерево должно иметь по крайней мере одну вершину. Изолированная вершина также представляет собой ориентированное дерево.

Вершина ориентированного дерева, полустепень исхода которой равна нулю, называется КОНЦЕВОЙ (ВИСЯЧЕЙ) вершиной или ЛИСТОМ; все остальные вершины дерева называют вершинами ветвления. Длина пути от корня до некоторой вершины называется УРОВНЕМ (НОМЕРОМ ЯРУСА) этой вершины. Уровень корня ориентированного дерева равен нулю, а уровень любой другой вершины равен расстоянию (т.е. модулю разности номеров уровней вершин) между этой вершиной и корнем. Ориентированное дерево является ациклическим графом, все пути в нем элементарны.

Во многих приложениях относительный порядок следования вершин на каждом отдельном ярусе имеет определенное значение. При представлении дерева в ЭВМ такой порядок вводится автоматически, даже если он сам по себе произволен. Порядок следования вершин на некотором ярусе можно легко ввести, помечая одну вершину как первую, другую - как вторую и т.д. Вместо упорядочивания вершин можно задавать порядок на ребрах. Если в ориентированном дереве на каждом ярусе задан порядок следования вершин, то такое дерево называется УПОРЯДОЧЕННЫМ ДЕРЕВОМ.

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


^ 6.2.3 Бинарные деревья.

Существуют m-арные деревья, т.е. такие деревья у которых полустепень исхода каждой вершины меньше или равна m (где m может быть равно 0,1,2,3 и т.д.). Если полустепень исхода каждой вершины в точности равна либо m, либо нулю, то такое дерево называется ПОЛНЫМ m-АРНЫМ ДЕРЕВОМ.

При m=2 такие деревья называются соответственно БИНАРНЫМИ, или ПОЛНЫМИ БИНАРНЫМИ.

Представить m-арное дерево в памяти ЭВМ сложно, т.к. каждый элемент дерева должен содержать столько указателей, сколько ребер выходит из узла (при m-3,4.5.6... соответствует 3,4,5,6... указателей). Это приведет к повышенному расходу памяти ЭВМ, разнообразию исходных элементов и усложнит алгоритмы обработки дерева. Поэтому m-арные деревья, лес необходимо привести к бинарным для экономии памяти и упрощению алгоритмов. Все узлы бинарного дерева представляются в памяти ЭВМ однотипными элементами с двумя указателями (см.разд. 6,2,5), кроме того, операции над двоичными деревьями выполняются просто и эффективно.


^ 6.2.4 Представление любого дерева, леса бинарными деревьями.

Дерево и лес любого вида можно преобразовать единственным образом в эквивалентное бинарное дерево.

Правило построения бинарного дерева из любого дерева:

1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение);
   
2. Соединить горизонтальными ребрами всех братьев одного отца;
   
3. Таким образом перестроить дерево по правилу: левый сын - вершина, расположенная под данной; правый сын - вершина, расположенная справа от данной (т.е. на ярусе с ней).
   
4. Развернуть дерево таким образом, чтобы все вертикальные ветви отображали левых сыновей, а горизонтальные - правых.
   

В результате преобразования любого дерева в бинарное получается дерево в виде левого поддерева, подвешенного к корневой вершине.

В процессе преобразования правый указатель каждого узла бинарного дерева будет указывать на соседа по уровню. Если такового нет, то правый указатель NIL. Левый указатель будет указывать на вершину следующего уровня. Если таковой нет, то указатель устанавливается на NIL.


^ 6.2.5 Машинное представление деревьев в памяти ЭВМ.

Деревья можно представлять с помощью связных списков и массивов (или последовательных списков).

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

LPTR

DATA

RPTR

где LPTR - указатель на левое поддерево, RPTR - указатель на правое поддерево, DATA - содержит информацию, связанную с вершиной.


^ 6.2.6 Основные операции над деревьями.

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

1) Поиск узла с заданным ключом (Find).

2) Добавление нового узла (Dob).

3) Удаление узла (поддерева) (Udal).

4) Обход дерева в определенном порядке:

• Нисходящий обход (процедура Preorder , рекурсивная процедура r_Preoder);
  
• Смешанный обход (процедура Inorder, рекурсивная процедура r_Inorder);
  
• Восходящий обход (процедура Postorder, рекурсивная процедура r_Postorder).
  

ПОИСК ЗАПИСИ В ДЕРЕВЕ. Нужная вершина в дереве ищется по ключу. Поиск в бинарном дереве осуществляется следующим образом.

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

1). найдена вершина, содержащая ключ, равный ключу X;

2). в дереве отсутствует вершина, к которой нужно перейти для выполнения очередного шага поиска.

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

ДОБАВЛЕНИЕ НОВОГО УЗЛА. Для включения записи в дерево прежде всего нужно найти в дереве ту вершину, к которой можно "подвести" (присоединить) новую вершину, соответствующую включаемой записи. При этом упорядоченность ключей должна сохраняться.

ОБХОД ДЕРЕВА. Во многих задачах, связанных с деревьями, требуется осуществить систематический просмотр всех его узлов в определенном порядке. Такой просмотр называется прохождением или обходом дерева. Бинарное дерево можно обходить тремя основными способами: нисходящим, смешанным и восходящим (возможны также обратный нисходящий, обратный смешанный и обратный восходящий обходы). Принятые выше названия методов обхода связаны с временем обработки корневой вершины: До того как обработаны оба ее поддерева (Preorder), после того как обработано левое поддерево, но до того как обработано правое (Inorder), после того как обработаны оба поддерева (Postorder). Используемые в переводе названия методов отражают направление обхода в дереве: от корневой вершины вниз к листьям - нисходящий обход; от листьев вверх к корню - восходящий обход, и смешанный обход - от самого левого листа дерева через корень к самому правому листу.

Схематично алгоритм обхода двоичного дерева в соответствии с нисходящим способом может выглядеть следующим образом:

1). В качестве очередной вершины взять корень дерева. Перейти к пункту 2.

2). Произвести обработку очередной вершины в соответствии с требованиями задачи. Перейти к пункту 3.

3)

a).Если очередная вершина имеет обе ветви, то в качестве новой вершины выбрать ту вершину, на которую ссылается левая ветвь, а вершину, на которую ссылается правая ветвь, занести в стек; перейти к пункту 2;

б) если очередная вершина является конечной, то выбрать в качестве новой очередной вершины вершину из стека, если он не пуст, и перейти к пункту 2; если же стек пуст, то это означает, что обход всего дерева окончен, перейти к пункту 4;

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

4). Конец алгоритма.

ПРОШИВКА БИНАРНЫХ ДЕРЕВЬЕВ. Под прошивкой дерева понимается замена по определенному правилу пустых указателей на сыновей указателями на последующие узлы, соответствующие обходу.

В бинарном дереве имеется много указателей со значением NIL. В дереве с N вершинами имеется (N+1) указателей типа NIL. Это незанятое пространство можно использовать для изменения представления деревьев. Пустые указатели заменяются указателями - "нитями", которые адресуют вершины дерева, расположенные выше. При этом дерево прошивается с учетом определенного способа обхода. Например, если в поле left некоторой вершины P стоит NIL, то его можно заменить на адрес, указывающий на предшественника P, в соответствии с тем порядком обхода, для которого прошивается дерево. Аналогично, если поле right пусто, то указывается преемник P в соответствии с порядком обхода.

Поскольку после прошивания дерева поля left и right могут характеризовать либо структурные связи, либо "нити", возникает необходимость различать их, для этого вводятся в описание структуры дерева характеристики левого и правого указателей (FALSE и TRUE).

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


^ 6.4 Сбалансированные деревья

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

Дерево является СБАЛАНСИРОВАННЫМ тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более, чем на 1.

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

1). Выполнить обход дерева слева направо и выбрать элементы дерева в упорядоченный линейный список.

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

3). Проделать операции пп 2- 4 с левым подсписком и сформировать левое поддерево

4). Проделать операции пп 2- 4 с правым подсписком и сформировать правое поддерево


Тема 7. Файловые структуры данных


7.1. Физическая структура дисковой памяти


Дисковая память имеет иное физическое строение и иные показатели доступа, чем оперативная память. Схематично ее физическое строение можно представить так, как показано на рис.7.1.

1 2 3 а). Вид сбоку 3 2 1 б). Вид сверху 1 – диски 2 – головки чтения/записи 3 – ось вращения Рис.7.1. Физическое строение дисковой памяти

Накопитель на жестких магнитных дисках представляет собой несколько дисков, покрытых с двух сторон ферромагнитным материалом (который, собственно, и является носителем информации). Диски вращаются на одной оси. Механизм чтения-записи представляет собой «гребенку», «зубцы» которой вставляются между дисками. На зубцах находятся головки чтения-записи, каждой поверхности соответствует своя головка. Гребенка может перемещаться взад-вперед в радиальном направлении, занимая конечное число фиксированных позиций. Вся гребенка является жесткой конструкцией, т.е. все головки перемещаются вместе. Окружность, которая «рисуется» на поверхности диска при прохождении его под находящейся в одном из фиксированных положений головкой, называется дорожкой. В общем случае время доступа к требуемой информации на диске складывается из четырех составляющих: Tдост = Tгол + Tдор + Tсект + Tчт где:

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

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

T_сект – время выбора сектора. Выбор сектора состоит в ожидании того, когда сектор с требуемыми данными за счет вращения диска окажется под головкой чтения-записи. Поскольку здесь механическое перемещение связано с равномерным вращением с высокой скоростью, T_сект << T_дор, но не настолько, чтобы им можно біло пренебречь.

T_чт – время чтения – интервал времени, за который участок дорожки с читаемыми данными проходит под головкой чтения-записи. Это время сопоставимо с T_сект, но представляет собой совершенно неизбежные затраты времени.

При чтении записей в произвольном порядке для чтения каждой записи необходимо выполнить затраты времени доступа в полном объеме. При чтении же записей, расположенных на диске последовательно затраты T_гол + T_дор + T_сект необходимо выполнить только для доступа к первой записи. После прочтения первой записи следующая уже окажется под головкой. Когда все записи на дорожке будут прочитаны потребуется переключить головку и читать дорожку на следующей поверхности. Только после прочтения всех дорожек, доступных при данном фиксированном положении гребенки, приходится позиционировать гребенку в следующее фиксированное положение, т.е., затрачивать T_гол + T_дор + T_сект.


^ 7.2. Последовательные файлы

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


7.2.1. Внешняя сортировка

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

1. частичная сортировка
   
2. слияние.
   

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

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


^ 7.3. Файлы, организованные разделами

Такой файл представляет собой совокупность последовательных подфайлов или разделов, расположенных в произвольном порядке в той области памяти, которая выделена для файла. Каждый раздел имеет собственное имя и обрабатывается как последовательный файл независимо от других разделов. Но вся совокупность разделов такого файла (часто именуемого библиотекой) имеет общее имя и представляет собой один файл с точки зрения операционной системы.

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

У библиотечных файлов имеется два существенных недостатка. Во-первых, это накопление «дыр» – неиспользуемых участков дискового пространства внутри области данных. Во-вторых, ограничение на максимальное количество разделов в библиотеке, поскольку оглавление создается при создании файла и уже не может быть увеличено впоследствии. В связи с этими недостатками библиотечная структура в настоящее время применяется только для файлов, не обладающих изменчивостью, например, для LIB- или HLP-файлов.


7.4. Файлы прямого доступа

Эти файлы представляют собой в сущности реализацию на внешней памяти хешированных таблиц прямого доступа (см.3.6.3.3). Файл прямого доступа, как правило состоит из двух частей: индекса и пространства данных. Индекс и является, собственно таблицей прямого доступа, каждая запись которой содержит только ключ, адрес соответствующей записи в области данных и адрес следующей записи в возможной цепочке переполнений (для разрешения коллизий используются раздельные цепочки переполнений). Область данных – неупорядоченный последовательный файл. Обычно индекс или его часть считывается в оперативную память и поиск по ключу ведется, по возможности, в оперативной памяти. Если запись файла прямого доступа содержит несколько полей, которые могут использоваться в качестве ключа, для каждого ключа строится свой индекс при одной общей области данных.

Поскольку в процессе «жизни» файла прямого доступа имеется тенденция к накапливанию в нем коллизий, со временем эффективность доступа к файлу ухудшается. Поэтому файлы прямого доступа нуждаются в периодической реорганизации, в ходе которой расширяется пространство записей и модифицируются параметры функции хеширования, что приводит к «рассасыванию» коллизий.

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


7.5. B⁺ деревья

Файлы со структурой B⁺-деревьев являются основной структурой, используемой в современных СУБД. Эта структура позволяет организовать как быстрый поиск записи по ключу, так и последовательную упорядоченную обработку записей.

Дерево называется B⁺-деревом порядка m, если:

1). В каждом узле, кроме корневого, число ключей M находится в пределах (m/2)<=M<=m-1. В корне дерева минимальное число ключей м.б. равно 1.

2). Каждый не являющийся «листом» узел с M ключами содержит M+1 указателей на узлы-потомки.

3). Все «листья» дерева находятся на одном и том же уровне

4). В каждом узле ключи упорядочены по возрастанию.

Пример B⁺-дерева порядка 5 показан на рис.7.2.