Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ФГБОУ ВПО
«Дальневосточный государственный университет
путей сообщения»
Кафедра: «Информационные технологии и
системы»
Реферат
по дисциплине «Структуры и алгоритмы обработки данных»
Тема: «Динамические структуры данных»
Выполнил: Кондрашин А.С
гр.22К
Проверил: Любомский С.А.
Приходько С.А.
Хабаровск, 2013.
СОДЕРЖАНИЕ
1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
1.1 Ссылочные реализации структур данных 3
1.1.1 Массовые операции 4
1.1.2 Список 5
1.1.3 Ссылочная реализация списка 7
1.1.4 Деревья и графы 8
1.2 Множество 12
1.3 Интерфейс динамических информационных структур 13
1.4 Реализация списков 14
1.4.1 Односвязный список 14
1.4.2 Двусвязный список 14
1.4.3 Прототипы интерфейсных функций 15
1.5 Реализация деревьев 15
1.5.1 Бинарное дерево 15
1.5.2 n-арное дерево 15
1.5.3 Дерево произвольной арности 16
1.6 Реализация бинарных деревьев 16
1.7 Алгоритм пирамиды (метод Уильямса-Флойда) 18
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 21
1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Большинство структур данных реализуется на базе массива. Все реализации можно разделить на два класса: непрерывные и ссылочные. В непрерывных реализациях элементы структуры данных располагаются последовательно друг за другом в непрерывном отрезке массива, причем порядок их расположения в массиве соответствует их порядку в реализуемой структуре. Рассмотренные выше реализации очереди и стека относятся к непрерывным.
В ссылочных реализациях элементы структуры данных хранятся в произвольном порядке. При этом вместе с каждым элементом хранятся ссылки на один или несколько соседних элементов. В качестве ссылок могут выступать либо индексы ячеек массива, либо адреса памяти. Можно представить себе шпионскую сеть, в которой каждый участник знает лишь координаты одного или двух своих коллег. Контрразведчикам, чтобы обезвредить сеть, нужно пройти последовательно по всей цепочке, начиная с выявленного шпиона.
Ссылочные реализации обладают двумя ярко выраженными недостатками: 1) для хранения ссылок требуется дополнительная память; 2) для доступа к некоторому элементу структуры необходимо сначала добраться до него, проходя последовательно по цепочке других элементов. Казалось бы, зачем нужны такие реализации?
Все недостатки ссылочных реализаций компенсируются одним чрезвычайно важным достоинством: в них можно добавлять и удалять элементы в середине структуры данных, не перемещая остальные элементы.
Массовые операции —это операции, затрагивающие значительную часть всех элементов структуры данных. Пусть нужно добавить или удалить один элемент. Если при этом приходится, например, переписывать значительную часть остальных элементов с одного места на другое, то говорят, что добавление или удаление приводит к массовым операциям. Массовые операции —это бедствие для программиста, то, чего он всегда стремится избежать. Хорошая реализация структуры данных —та, в которой массовых операций либо нет совсем, либо они происходят очень редко. Например, добавление элемента должно выполняться за ограниченное число шагов, независимо от того, содержит ли структура десять или десять тысяч элементов.
В непрерывных реализациях добавление или удаление элементов в середине структуры неизбежно приводит к массовым операциям. Поэтому структуры, в которых можно удалять или добавлять элементы в середине, обязательно должны быть реализованы ссылочным образом.
Пример неудачного использования непрерывных реализаций —файловые системы в некоторых старых операционных системах, например, в уже упомянутой ОС ЕС или в системе РАФОС, применявшейся на СМ ЭВМ, на старых советских персональных компьютерах Электроника и т.п. В современных файловых системах файлы фрагментированы, т.е. кусочки большого файла, непрерывного с точки зрения пользователя,на самом деле могут быть разбросаны по всему диску. Раньше это было не так, файлы должны были обязательно занимать непрерывный участок на диске. При постоянной работе файлы уничтожались и создавались заново на новом месте —и всякое редактирование текстового файла приводило к его обновлению. В результате свободное пространство на диске становилось фрагментированным, т.е. состоящим из множества небольших кусков. Возникала ситуация, когда большой файл невозможно записать на диск: хотя свободного места в сумме много, нет достаточно большого свободного фрагмента. Приходилось постоянно выполять длительную и опасную процедуру сжатия диска, которая часто приводила к потере всех данных на нем.
Классический пример структуры данных последовательного доступа, в которой можно удалять и добавлять элементы в середине структуры, —это линейный список. Различают однонаправленный и двунаправленный списки (иногда говорят односвязный и двусвязный).
Элемены списка как бы выстроены в цепочку друг за другом. У списка есть начало и конец. Имеется также указатель списка, который располагается между элементами. Если мысленно вообразить, что соседние элементы списка связаны между собой веревкой, то указатель —это ленточка, которая вешается на веревку. В любой момент времени в списке доступны лишь два элемента —элементы до указателя и за указателем.
Рис. 1.
В однонаправленном списке указатель можно передвигать лишь в одном направлении —вперед, в направлении от начала к концу. Кроме того, можно установить указатель в начало списка, перед его первым элементом. В отличие от однонаправленного списка, двунаправленный абсолютно симметричен, указатель в нем можно передвигать вперед и назад, а также устанавливать как перед первым, так и за последним элементами списка.
В двунаправленном списке можно добавлять и удалять элементы до и за указателем. В однонаправленном списке добавлять элементы можно также с обеих сторон от указателя, но удалять элементы можно только за указателем.
Удобно считать, что перед первым элементом списка располагается специальный пустой элемент, который называется головой списка. Голова списка присутствует всегда, даже в пустом списке. Благодаря этому можно предполагать, что перед указателем всегда есть какой-то элемент, что упрощает процедуры добавления и удаления элементов.
В двунаправленном списке считают, что вслед за последним элементом списка вновь следует голова списка, т.е. список зациклен в кольцо.
Рис. 2.
Можно было бы точно так же зациклить и однонаправленной список. Но гораздо чаще считают, что за последним элементом однонаправленного списка ничего не следует. Однонаправленный список, таким образом, представляет собой цепочку, начинающуюся с головы списка, за которой следует первый элемент, затем второй и так далее вплоть до последнего элемента, а заканчивается цепочка ссылкой в никуда.
Рис. 3.
Мы рассмотрели абстрактное понятие списка. Но в программировании зачастую отождествляют понятие списка с его ссылочной реализацией на базе массива или непосредственно на базе оперативной памяти.
Основная идея реализации двунаправленного списка заключается в том, что вместе с каждым элементом хранятся ссылки на следующий и предыдущий элементы. В случае реализации на базе массива ссылки представляют собой индексы ячеек массива. Чаще, однако, элементы списка не располагают в каком-либо массиве, а просто размещают каждый по отдельности в оперативной памяти, выделенной данной задаче. (Обычно элементы списка размещаются в так называемой динамической памяти, или куче —это область оперативной памяти, в которой можно при необходимости захватывать куски нужного размера, а после использования освобождать, т.е. возвращать обратно в кучу.) В качестве ссылок в этом случае используют адреса элементов в оперативной памяти.
Голова списка хранит ссылки на первый и последний элементы списка. Поскольку список зациклен в кольцо, то следующим за головой списка будет его первый элемент, а предыдущим —последний элемент. Голова списка хранит только ссылки и не хранит никакого элемента. Это как бы пустой ящик, в который нельзя ничего положить и который используется только для того, чтобы написать на нем адреса следующего и предыдущего ящиков, т.е. первого и последнего элементов списка. Когда список пуст, голова списка зациклена сама на себя.
Указатель списка реализуется в виде ссылки на следующий и предыдущий элементы, он просто отмечает некоторое место в цепочке элементов.
В случае однонаправленного списка хранится только ссылка на следующий элемент, таким способом экономится память. Голова однонаправленного списка хранит ссылку на первый элемент списка. Последний элемент списка хранит нулевую ссылку, т.е. ссылку в никуда, т.к. в программах нулевой адрес никогда не используется.
Ценность ссылочной реализации списка состоит в том, что процедуры добавления и удаления элементов не приводят к массовым операциям. Рассмотрим, например, операцию удаления элемента за указателем. Читая ссылку на следующий элемент в удаляемом элементе, мы находим, какой элемент должен будет следовать за указателем после удаления текущего элемента. После этого достаточно связать элемент до указателя с новым элементом за указателем. А именно, обозначим через X адрес элемента до указателя, через Y —адрес нового элемента за указателем. В поле следующий для элемента с адресом X надо записать значение Y, в поле предыдущий для элемента с адресом Y —значение X. Таким образом, при удалении элемента за указателем он исключается из цепочки списка, для этого достаточно лишь поменять ссылки в двух соседних элементах. Аналогично, для добавления элемента достаточно включить его в цепочку, а для этого также нужно всего лишь модифицировать ссылки в двух соседних элементах. Добавляемый элемент может располагаться где угодно, следовательно, нет никаких проблем с захватом и освобождением памяти под элементы.
Граф —это фигура, которая состоит из вершин и ребер, соединяющих вершины. Например, схема линий метро —это граф. Ребра могут иметь направления, т.е. изображаться стрелочками; такие графы называются ориентированными. Допустим, надо построить схему автомобильного движения по улицам города. Почти во всех городах есть много улиц с односторонним движением. Поэтому такая транспортная схема должна представляться ориентированным графом. Улице с односторонним движением соответствует стрелка, с двусторонним —пара стрелок в противоположных направлениях. Вершины такого графа соответствуют перекресткам и тупикам.
Дерево —это связный граф без циклов. Кроме того, в дереве выделена одна вершина, которая называется корнем дерева. Остальные вершины упорядочиваются по длине пути от корня дерева.
Рис. 4.
Зафиксируем некоторую вершину X. Вершины, соединенные с X ребрами и расположенные дальше нее от корня дерева, называются детьми или сыновьями вершины X. Сыновья упорядочены слева направо. Вершины, у которых нет сыновей, называются терминальными. Дерево обычно изображают перевернутым, корнем вверх. .
Деревья в программировании используются значительно чаще, чем графы. Так, на построении деревьев основаны многие алгоритмы сортировки и поиска. Компиляторы в процессе перевода программы с языка высокого уровня на машинный язык представляют фрагменты программы в виде деревьев, которые называются синтаксическими. Деревья естественно применять всюду, где имеются какие-либо иерархические структуры, т.е. структуры, которые могут вкладываться друг в друга. Примером может служить оглавление книги
Рис. 5.
Пусть книга состоит из частей, части —из глав, главы —из параграфов. Сама книга представляется корнем дерева, из которого выходят ребра к вершинам, соответствующим частям книги. В свою очередь, из каждой вершины-части книги выходят ребра к вершинам-главам, входящим в эту часть, и так далее. Файловую систему компьютера также можно представить в виде дерева. Вершинам соответствуют каталоги (их также называют директориями или папками) и файлы. Из вершины-каталога выходят ребра к вершинам, соответствующим всем каталогам и файлам, которые содержатся в данном каталоге. Файлы представляются терминальными вершинами дерева. Корню дерева соответствует корневой каталог диска. Программы, осуществляющие работу с файлами, такие, как Norton Commander в системе MS DOS или Проводник Windows, могут изображать файловую систему графически в виде дерева.
Вершина дерева представляется в виде объекта, содержащего ссылки на родительскую вершину и на всех сыновей, а также некоторую дополнительную информацию, зависящую от конкретной задачи. Объект, представляющий вершину дерева, занимает область фиксированного размера, которая обычно размещается в динамической памяти. Число сыновей обычно ограничено, исходя из смысла решаемой задачи. Так, очень часто рассматриваются бинарные деревья, в которых число сыновей у произвольной вершины не превышает двух. Если один или несколько сыновей у вершины отсутствуют, то соответствующие ссылки содержат нулевые значения. Таким образом, у терминальных вершин все ссылки на сыновей нулевые.
При работе с деревьями очень часто используются рекурсивные алгоритмы, т.е. алгоритмы, которые могут вызывать сами себя. При вызове алгоритма ему передается в качестве параметра ссылка на вершину дерева, которая рассматривается как корень поддерева, растущего из этой вершины. Если вершина терминальная, т.е. у нее нет сыновей, то алгоритм просто применяется к данной вершине. Если же у вершины есть сыновья, то он рекурсивно вызывается также для каждого из сыновей. Порядок обхода поддеревьев зависит от сути алгоритма.
Приведем рекурсивный алгоритм, определяющий высоту дерева. Высотой дерева называется максимальная из длин всевозможных путей от корня дерева к терминальным вершинам. Под длиной пути понимается число вершин, входящих в него, включая первую и последнюю вершины. Так, дерево, состоящее из одной корневой вершины, имеет высоту 1, дерево, приведенное на рисунке в начале этого раздела —высоту 4.
цел алгоритм высота_дерева(вход: вершина V)
| Дано: V - ссылка на корень поддерева
| Надо: Подсчитать высоту поддерева
начало
| цел h, m, s;
| h := 1;
| если у вершины V есть сыновья
| | то // Ищем поддерево максимальной высоты
| | m := 0;
| | цикл для каждого сына X вершины V выполнить
| | | s := высота_дерева(X); // Рекурсия!
| | | если s > m
| | | | то m := s;
| | | конец если
| | конец цикла
| | h := h + m;
| конец если
| ответ := h;
конец алгоритма
Множество —это структура данных, содержащая конечный набор элементов некоторого типа. Каждый элемент содержится только в одном экземпляре, т.е. разные элементы множества не равны между собой. Элементы множества никак не упорядочены. В множество M можно добавить элемент x, из множества M можно удалить элемент x. Если при добавлении элемента x он уже содержится в множестве M, то ничего не происходит. Аналогично, никакие действия не совершаются при удалении элемента x, когда он не содержится в множестве M. Наконец, для заданного элемента x можно определить, содержится ли он в множестве M. Множество —это потенциально неограниченная структура, оно может содержать любое конечное число элементов.
В программировании довольно часто рассматривают структуру чуть более сложную, чем просто множество: нагруженное множество. Пусть каждый элемент множества содержится в нем вместе с дополнительной информацией, которую называют нагрузкой элемента. При добавлении элемента в множество нужно также указывать нагрузку, которую он несет. В разных языках программирования и в различных стандартных библиотеках такие структуры называют Отображением (Map) или Словарем (Dictionary). Действительно, элементы множества как бы отображаются на нагрузку, которую они несут (заметим, что в математике понятие функции или отображения определяется строго как множество пар; первым элементом каждой пары является конкретное значение аргумента функции, вторым —значение, на которое функция отображает аргумент). В интерпретации Словаря элемент множества —это иностранное слово, нагрузка элемента —это перевод слова на русский язык (разумеется, перевод может включать несколько вариантов, но здесь перевод рассматривается как единый текст).
Все элементы содержатся в нагруженном множестве в одном экземпляре, т.е. разные элементы множества не могут быть равны друг другу. В отличие от самих элементов, их нагрузки могут совпадать (так, различные иностранные слова могут иметь одинаковый перевод). Поэтому иногда элементы нагруженного множества называют ключами, их нагрузки —значениями ключей. Каждый ключ уникален. Принято говорить, что ключи отображаются на их значения.
Наиболее часто применяемая операция в нагруженном множестве —это определение нагрузки для заданного элемента x (значения ключа x). Реализация этой операции включает поиск элемента x в множестве, поэтому эффективность любой реализации множества определяется прежде всего быстротой поиска.
Интерфейсом здесь называется минимальный набор функций, реализующих стандартные задачи обработки данных. Среди них:
Insert –вставить новый элемент,
TakeOut –удаление элемента из списка,
Is_present –определение содержания в списке заданного элемента,
Display –вывод всех элементов списка,
Destroy –освобождение памяти, занятой под список,
Структура элемента
struct node
{
char w[10]; // любая информационная часть элемента
struct node *next;
};
Структура заголовка
struct head
{
char info[100]; // любая информационная часть всего списка
struct node *begin;
};
Структура элемента
struct node
{
char w[10]; // любая информационная часть элемента
struct node *next;
struct node *prev;
};
Структура заголовка
struct head
{
char info[100]; // любая информационная часть всего списка
struct node *begin;
};
Предложим примерные прототипы стандартных интерфейсных функций.
void Insert(struct head h, char * text);
int TakeOut(struct head h, struct *ptrnode);
int Is_present(struct head h, char *text);
void Display(struct head h);
void Destroy(struct head h);
Структура элемента
struct node
{
char w[10]; // любая информационная часть элемента
struct node *left;
struct node *right;
};
Деревья, как правило, не имеют заголовка.
Структура элемента
#define N 3
struct node
{
char w[10]; // любая информационная часть элемента
struct node childs[N];
};
Структура элемента
struct node
{
char w[10]; // любая информационная часть элемента
struct node *childs; // указатель на дочерние узлы
int N; // количество дочерних узлов
};
Рассмотрим задачу определения числа появления всех слов в некотором файле. Список слов заранее неизвестен. Слова будем запоминать в бинарном дереве. Используем рекурсивный алгоритм для работы с деревом.
struct node{
char word[20];
int count;
node *left, *right;
};
#define node* T;
T tree(T, char*);
void main()
{
node *root;
char word[20];
root = NULL;
while(getword(word) != EOF)
root = tree(root, word);
treeprint(root);
}
T tree(T p, char *w)
{
int cond;
if(p==NULL)//новое слово
{
p=(T)malloc(sizeof(node));
//проверка
strcpy(p->word, w);
p->count = 1;
p->left = p->right = NULL;
}
else if((cond=strcmp(w, p->word))==0)
++p->count; //повторное слово
else if(cond <0) //левое слово
p->left = tree(p->left, w);
else //правое дерево
p->right –tree(p->right, w);
return p;
}
//--------------------
void treeprint(T p)
{
if(p != NULL)
{
treeprint(p->left);
print(%4d %s \n”, p->count, p->word);
treeprint(p->right);
}
}
Метод сортировки массива, предложенный и развитый Вильямсом и Флойдом, носит название алгоритма "пирамиды". Он основан на специальном представлении массива в форме бинарного дерева, обладающего особыми свойствами и называемого "пирамидой". Алгоритм имеет гарантированную трудоемкость вида 0(n log n) и не требует дополнительной памяти.
Высокая эффективность алгоритма и гарантированная надежность для самого "худшего" случая часто оказываются решающими факторами, заставляющими отдавать предпочтение этому способу сортировки.
Процесс сортировки состоит из двух этапов. На первом этапе массив преобразуется к виду "пирамиды".
На втором этапе осуществляется сортировка "пирамиды".
Под структурой бинарного дерева понимается множество элементов, обладающих иерархией следующего вида:
А[1]
А[2] А[3]
А[4] А[5] А[6] А[7]
А[8] А[9]...
Структура дерева имеет логический характер - в памяти компьютера все элементы массива все равно расположены последовательно. Каждый элемент в структуре бинарного дерева имеет два элемента-потомка A[2i] и A[2i+1], где i - индекс данного элемента ("предка"). Элементы массива, являющегося "пирамидой", обладают следующими дополнительными свойствами:
. Любой элемент пирамиды A[i] не меньше, чем его элементы-потомки A[2i] и A[2i+1] (соответственно первый элемент обладает максимальным значением):
A[i]>=A[2i],
A[i] >= A[2i+1]
. Любая подпоследовательность элементов вида А[n\2+1], А[n\2+2], ... А[n] также является пирамидой, обладающей свойствами 1 и 2.
После преобразования массива к форме пирамиды сортировка осуществляется следующим образом.
В массиве-пирамиде первый элемент не меньше остальных. Обменяем его с последним элементом и "укоротим" массив на 1 элемент с "хвоста". Наибольший элемент массива окажется последним.
"Укороченная" последовательность элементов может уже не быть пирамидой. Поэтому рассмотрим элемент А[1] и его потомки - А[2| и А[3]. Если элемент не меньше потомков, то последовательность является пирамидой. В противном случае меняем местами элемент А[1] и наибольший из потомков: mах( А[2], А[3]). Для элемента-потомка, который обменялся значением, повторяется процесс сравнения и обмена с потомками до тех пор пока последовательность не станет пирамидой. После циклического повторения описанного этапа сортировки пирамида станет отсортированным массивом.
{ Метод "пирамиды" (алгоритм Вильямса-Флойда) }
procedure PIR;
var t, k, i: integer;
begin
for i : = 2 to n do { создание структуры бинарного дерева-"пирамиды" }
begin
t:=i;
while t <>1 do
begin
k := t div 2;
if a[k] >= a[t] then
t := 1
else
begin
OBMEN(a[k],a[t]);t :=k
end
end
end;
for i :=n-l downto 1 do { сортировка массива-"пирамиды"}
begin
OBMEN(a[i+l],a[l]);t:=l;
while t <> 0 do
begin
k := t+1;
if k>I then
t:=0
else
begin
if k < i then if a[k+l] > a[k] then
k : = k+1;
if a[t]>=a[k] then
t:=0
else
begin
OBMEN(a[t],a[k]);t:=k
end
end
end
end
end;