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

Федеральное агентство по образованию

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

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

СТРУКТУРЫ И АЛГОРИТМЫ

ОБРАБОТКИ ДАННЫХ

Динамические структуры данных

Методические указания

Рязань 2008

Содержание

Введение 4

1. Терминология. 4

2. Классификация структур данных по различным признакам.. 5

3. Типовые операции над структурами данных. 6

4. Эффективность алгоритмов. O-обозначения. 6

Тема 1. Стеки, очереди, деки.. 8

1. Стек. 8

2. Операции над стеком.. 8

3. Реализация стека. 8

4. Реализация основных операций над стеком.. 10

5. Использование стека для преобразования форм записи выражений. 11

6. Очередь. 12

7. Операции над очередью.. 13

8. Дек. 13

9. Операции над деком.. 14

10. Реализация очереди и дека. 14

11. Реализация основных операций над очередью и деком.. 14

12. Итератор. 17

Лабораторная работа 1. Стеки, очереди, деки. 18

Тема 2. Односвязные и двусвязные линейные списки.. 23

1. Линейный список. 23

2. Операции над линейным списком.. 23

3. Реализация линейного списка
в виде односвязной динамической структуры.. 24

4. Реализация основных операций над односвязным списком.. 24

5. Циклический список. 28

6. Операции над циклическим списком.. 28

7. Односвязная реализация циклического списка. 28

8. Реализация основных операций
над односвязным циклическим списком.. 30

9. Реализация линейного списка
в виде двусвязной динамической структуры.. 32

10. Реализация основных операций над двусвязным списком.. 34

11. Циклический двусвязный список. 36

12. Реализация основных операций
над двусвязным циклическим списком.. 37

Лабораторная работа 2. Односвязные и двусвязные линейные списки. 38

Тема 3. Бинарные деревья.. 43

1. Основные понятия и определения. 43

2. Построение бинарного дерева. 44

3. Операции над бинарным деревом.. 45

4. Реализация бинарного дерева. 47

5. Реализация основных операций над бинарным деревом.. 48

6. Дерево выражения. 51

7. Дерево поиска. 53

8. Операции над деревом поиска. 53

9. Реализация дерева поиска. 54

10. Реализация операций над деревом поиска. 54

11. Сбалансированные деревья. 57

12. Включение в сбалансированное дерево. 58

Лабораторная работа 3. Бинарные деревья. 64

Тема 4. Графы... 68

1. Основные понятия и определения. 68

2. Операции над графом.. 70

3. Реализация графа. 71

4. Реализация основных операций над ориентированным графом.. 73

5. Обход ориентированного графа. 78

6. Вычисление расстояния между узлами ориентированного графа. 80

Лабораторная работа 4. Ориентированные графы.. 82

Библиографический список 85

Введение

1. Терминология

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

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

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

Физическая структура – способ представления данных в машинной памяти.

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

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

2. Классификация структур данных по различным признакам

Всю совокупность данных можно разделить на две большие группы: данные статической структуры и данные динамической структуры.

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

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

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

v По отношению к месту хранения:

Ø оперативные структуры (во внутренней памяти);

Ø файловые структуры (во внешней памяти).

v По наличию связей между элементами данных:

Ø несвязные (векторы, массивы);

Ø связные (списковые структуры):

· односвязные (списки);

· двусвязные (списки, бинарные деревья);

· многосвязные (деревья, графы).

v По признаку изменчивости (возможность изменения числа элементов и связей между ними):

Ø статические (векторы, массивы);

Ø полустатические (стеки, очереди, реализованные с помощью статических физических структур);

Ø динамические (стеки, очереди, реализованные с помощью динамических физических структур, списки).

v По признаку упорядоченности элементов структуры:

Ø линейные (массивы, стеки, очереди, списки);

Ø нелинейные (деревья, графы).

3. Типовые операции над структурами данных

1. Операция «создать» создает соответствующую структуру данных. Например, в Паскале переменная и массив могут быть созданы с помощью соответствующих операторов описания, что приводит к выделению адресного пространства для переменной и массива. Процедура New приводит к созданию переменной типа указателя.

2. Операция «уничтожить» приводит к уничтожению созданной структуры данных.

Например, в Паскале структуры данных, созданные внутри блока (процедуры), уничтожаются после выхода из этого блока. Процедура Dispose уничтожает переменную типа указателя.

3. Операция «выбрать» осуществляет доступ к данным внутри самой структуры. Выполнение этой операции зависит от структуры данных. Обращение, например, к переменной или элементу массива в операторе присваивания делает доступной соответствующую область памяти.

4. Операция «обновить» приводит к изменению данных в структуре.

4. Эффективность алгоритмов. O-обозначения

Эффективность алгоритмов зависит от двух факторов:

1) память, требуемая для реализации алгоритма на ПК;

2) время, необходимое для выполнения алгоритма.

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

1) постоянные множители не имеют значения для определения порядка сложности, т.е. O (k · f) = O (f);

2) порядок сложности произведения двух функций равен произведению их сложностей: О (f · g) = O (f)· O (g);

3) порядок сложности суммы функций равен порядку доминанты слагаемых, например: .

Приведем список функционального доминирования:

если N и L – переменные, a, b, c, d – константы, то

доминирует над ;

доминирует над ;

доминирует над , если a > b;

доминирует над , если а > 0;

доминирует над , если c > d;

N доминирует над , если a > 1.

Любой терм с одной переменной N не доминирует ни над каким термом с одной независимой переменной L.

Сложность алгоритма может быть определена исходя из анализа его управляющих структур. Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность. Поэтому определение сложности алгоритма сводится в основном к анализу циклов и рекурсивных вызовов. Рассмотрим алгоритм удаления k -го элемента из массива размером n, состоящий из перемещения элементов массива от (k +1)-го до n -го на одну позицию назад к началу массива и уменьшения числа элементов n на единицу. Сложность цикла обработки массива составляет О (n – k), т.к. тело цикла (операция перемещения) выполняется n – k раз и сложность тела цикла равна О (1), т.е. является константой. Тип цикла (for, while, repeat) не влияет на сложность. Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью. Вложенность повторений является основным фактором роста сложности. В качестве примера приведем сложность хорошо известных алгоритмов поиска и сортировки для массива размером n:

a) последовательный поиск: ;

b) бинарный поиск: ;

c) пузырьковая сортировка: .

При изучении алгоритмов в последующих темах будут приведены оценки их сложности.

Тема 1. Стеки, очереди, деки

1. Стек

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

Здесь A, B,... – элементы стека, каждый из которых может содержать одно или несколько полей. Стек функционирует по принципу LIFO (Last In – First Out – «последним пришел – первым исключается»). Известный пример стека – винтовочный патронный магазин. Число элементов стека не ограничено. Стек, в котором нет ни одного элемента, называется пустым.

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

2. Операции над стеком

Над стеком s могут быть выполнены следующие операции:

1) включение нового элемента со значением v в стек – Push (s, v);

2) исключение и возвращение значения верхнего элемента стека – Pop (s);

3) выработка признака «стек пуст» – Empty (s) (возвращает значение «истина», если стек пуст, и «ложь» – в противном случае);

4) считывание значения верхнего элемента без его исключения – TopValue (s);

5) возвращение числа элементов стека – Size (s);

6) очистка стека – Clear (s).

Первые три операции над стеками являются основными.

3. Реализация стека

Возможны два способа реализации стека – с помощью последовательного и связанного хранения элементов в памяти ЭВМ.

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

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

Использование связанного хранения элементов стека в памяти ЭВМ позволяет избежать этих недостатков.

Реализация стека с помощью динамических переменных:

Каждый элемент стека состоит из двух частей: содержательной и ссылки на ранее включённый элемент. Переменная Head ссылочного типа указывает на верхний элемент стека (содержит адрес этого элемента). За первым включенным элементом стека (последним от Head) нет следующего элемента, поэтому в поле ссылки этого элемента записывается значение nil.

Описание класса tStack с элементами, имеющими вещественные значения, может быть выполнено следующим образом:

Type

tValue = Real; // тип значения элемента стека - вещественный

pItem = ^tItem; // тип указателя на элемент стека

tItem = record // тип элемента стека

Value: tValue; // содержательная часть элемента стека

Next: pItem; // указатель на следующий элемент стека

end; // tItem

tStack = class // класс–стек