Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

высшего профессионального образования

Национальный исследовательский

Томский политехнический университет

Институт - Институт кибернетики

Направление - Прикладная информатика

Кафедра - ОСУ

Курсовая работа

по курсу «Типы и структуры данных»

Выполнила студентка гр. 8К21 К.Н. Кириллова_

Проверил доцент кафедры ОСУ О.Б.Фофанов

2014 год

Оглавление

• 1. Задание на выполнение курсовой работы
• 2. Моделирование абстрактных типов данных (АТД) для различных реализаций
• 2.1 Постановка задачи
• 2.2 Краткое теоретические положения
• 2.3 Результат работы программы
• 3. Поиск информации в файлах данных
• 3.1 Постановка задачи
• 3.2 Краткое теоретическое описание
• 3.3 Результаты работы программы
• 3.2 Краткое теоретическое описание
• 3.3 Результаты работы программы
• 4. Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных
• 4.1 Постановка задачи
• 4.1.1 Сортировка выбором
• 4.1.2 Сортировка простыми обменами, сортировка пузырьком
• 4.1.3 Гномья сортировка
• 4.1.4 Сортировка вставками
• 4.1.5 Сортировка слиянием
• 4.1.6 Блочная сортировка
• 4.1.7 Сортировка Шелла
• 4.1.8 Быстрая сортировка
• 4.1.9 Пирамидальная сортировка
• 4.1.10 Stooge Sort
• 4.2 Результаты работы программы
• 5. Реализация структур данных типа дерево и типовые алгоритмы их обработки
• 5.1 Постановка задачи
• 5.2 Теоретические положения
• 5.3 Результаты работы программы
• 6. Реализация функций расстановки (хеширование) и различных методов разрешения коллизий
• 6.1 Постановка задачи
• 6.2 Краткое теоретическое положение
• 6.3 Описание сферы практического применения используемого типа данных
• 6.4 Результаты работы программы
• Литература
• 1. Задание на выполнение курсовой работы
• абстрактный данные алгоритм сортировка
• Вариант 10.

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

Курсовая работа включает следующие разделы:

1. Моделирование абстрактных типов данных (АТД) для различных реализаций (табличное, списковое, комбинированное и т.д.).

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

3. Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных.

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

5. Реализация функций расстановки (хеширование) и различных методов разрешения коллизий.

2. Моделирование абстрактных типов данных (АТД) для различных реализаций

2.1 Постановка задачи

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

2.2 Краткое теоретические положения

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

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

· Insert (x, e) - вставляет элемент е в позицию х

· Locate (e) - возвращает позицию элемента е в списке

· Retrieve (x) - возвращает элемент, находящийся в позиции x

· Delete (x) - удаляет элемент с позиции х

· Next (е) - возвращает следующую позицию после е

· Previous (е) - возвращает предыдущую позицию перед е

· Makenull() - делает список пустым

· Head() - возвращает первую позицию в списке

· Tail() - возвращает последнюю позицию в списке

· Printlist() - печатает элементы списка в порядке их расположения

Примеры АТД:

1. Список

2. Стек

3. Очередь

4. Ассоциативный массив

5. Очередь с приоритетом

§ Стек -- абстрактный контейнер, доступ к элементам которого организован по принципу «последним вошёл -- первым вышел»

§ Стек может быть реализован на односвязном списке. Стек также можно реализовать на массиве. Основное ограничение, связанное с подобной реализацией, -- конечный размер стека, переполнение которого нужно дополнительно отслеживать. Кроме того, при реализации на статических массивах стек будет всегда занимать объём памяти, пропорциональный максимальному количеству элементов (так как внутри стека объявлен массив фиксированного размера).

2.3 Результат работы программы

Рис. 1. Пример работы 1-ой части программы

3. Поиск информации в файлах данных

3.1 Постановка задачи

1. Создать файл данных, описывающий данную предметную область. Выбрать одно из полей как ключ поиска.

1. На основе файла создать словарь, состоящий из пар: КЛЮЧ- № записи.

2. Упорядочить словарь по возрастанию ключей.

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

4. Сравнить времена поиска со словарем и без словаря (графики и таблицы)

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

3.2 Краткое теоретическое описание

Ассоциативный массив (словарь) -- абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу:

· INSERT(ключ, значение)

· FIND(ключ)

· REMOVE(ключ)

Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами.

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

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

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

Существует множество различных реализаций ассоциативного массива.

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

Поиск - нахождение какой-либо конкретной информации в большом объеме ранее собранных данных.

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

Целью поиска является нахождение всех записей подходящих к заданному ключу поиска.

Алгоритм Кнута-Морриса-Пратта

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

Если j определяет позицию в слове-образце, содержащую первый несовпадающий символ то величина сдвига определяется как j-d_j. Значения D - таблица сдвигов определяется как размер самой длинной последовательности символов слова, непосредственно предшествующих позиции j (суффикс), которая полностью совпадает с началом слова (префикс). D зависит только от слова и не зависит от текста. Для каждого j будет своя величина D, которую обозначим d_j. Перед поиском осуществляется формирование D.

Алгоритм КМП результативно находит подстроку в строке. Поиск информации -- одно из основных использований компьютера. Одна из простейших задач поиска информации -- поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна -- она применяется в текстовых редакторах, СУБД, поисковых машинах…

3.3 Результаты работы программы

1) 2)

8540 символов145100 символов

Время поиска по ключу: 8 мсВремя поиска по ключу: 26 мс

Время поиска со словарем: 3 мсВремя поиска со словарем: 18 мс

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



Рис. 2 . Поиск с использованием словаря

Рис. 3. Поиск с использование ключа

Таблица 1. Алгоритм Кнута-Морриса-Пратта

Длина подстроки	Время (мс)
10	4
20	17
50	22
100	18
300	34
500	62
800	108

4. Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных

4.1 Постановка задачи

· Провести экспериментальный сравнительный анализ различных методов сортировки. Для чистоты эксперимента сортировка должна проводиться на одинаковых наборах входных данных, которые генерируются случайным образом. Для более полного анализа методов сортировка должна проводиться для различных размерностей данных, например: 500, 1000, 3000, 5000, 8000, 10000, 30000, 60000.

· Исходные наборы данных - массивы или файлы соответствующего типа (по № варианта).

· Проследить динамику роста требуемого для сортировки времени.

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

· Сравнить теоретические оценки времени сортировки и числа требуемых операций с экспериментальными.

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

· Провести исследования o для выбранных алгоритмов внутренней сортировки (один из методов вставки и один из методов обменной сортировки)

Теоретические положения.

Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, ?, ?.

Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа.

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

· Время -- характеризует быстродействие алгоритма. Эквивалентно вычислительной сложности. Для типичного алгоритма средняя сложность -- O(n log n) и высокая -- O(n2). Идеальное поведение для упорядочения -- O(n).

· Память --временное хранение данных. Обычно эти алгоритмы требуют O(log n) памяти. Алгоритмы сортировки, которые не потребляют дополнительной памяти, относят к сортировкам на месте.

4.1.1 Сортировка выбором

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

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

4.1.2 Сортировка простыми обменами, сортировка пузырьком

Для понимания и реализации этот алгоритм -- простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(nІ).

Метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает -- массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

4.1.3 Гномья сортировка

Алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков, описанного на странице Дика Груна Гномья сортировка.

Алгоритм концептуально простой, не требует вложенных циклов. Время работы . На практике алгоритм может работать так же быстро, как и сортировка вставками.

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

4.1.4 Сортировка вставками

Сортировка вставками -- достаточно простой алгоритм. Массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и включается в отсортированную. Имеет высокую вычислительную сложность O(nІ). Отсортировано начало массива A1, A2, ….,Ai-1. Остаток массива Ai,…An не отсортирован. На очередном шаге Ai включается в отсортированную часть на соответствующее место. Пример такой сортировки - сортировка с помощью двоичного дерева.

4.1.5 Сортировка слиянием

Сортировка слиянием -- алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например -- потоки) в определённом порядке. Эта сортировка -- хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

4.1.6 Блочная сортировка

Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) --алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.

Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).

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

4.1.7 Сортировка Шелла

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

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

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

4.1.8 Быстрая сортировка

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.

2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного -- справа от него. Обычный алгоритм операции:

1. Два индекса -- l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.

2. Вычисляется индекс опорного элемента m.

3. Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.

4. Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

5. Если r = l -- найдена середина массива -- операция разделения закончена, оба индекса указывают на опорный элемент.

6. Если l < r -- найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.

3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

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

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

4.1.9 Пирамидальная сортировка

Пирамида -- двоичное дерево, в котором значение каждого элемента больше либо равно значений дочерних элементов.

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

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

4.1.10 Stooge Sort

Aлгоритм сортировки списка элементов заключается в следующем:

o Если значение элемента в конце списка меньше, чем значение элемента в начале, то поменять их местами.

o Если есть 3 или более элементов в текущем подмножестве списка, то:

· Рекурсивно вызвать Stooge sort для первых 2/3 списка

· Рекурсивно вызвать Stooge sort для последних 2/3 списка

· Рекурсивно вызвать Stooge sort для первых 2/3 списка снова

o Иначе: return

4.2 Результаты работы программы

· В этой части работы происходит сортировка 500, 1000, 2000, 3000, 5000 элементов различными видами сортировки.

Рис. 4. Пример работы 3-ей части программы

Таблица 2. Зависимость времени выполнения сортировки от количества элементов

Количество элементов	Сортировка выбором	Сортировки пузырьком	Гномья сортировка	Сортировка вставками	Сортировка слиянием	Блочная сортировка	Сортировка Шелла	Пирамидальная сортировка	Быстрая сортировка	StoogeSort
500	9468	17163	12125	6704	7314	71765	5244	35311	4487	156951
1000	23975	50841	33055	15318	2069	300	1311	110200	1287	4713912
3000	212307	456311	366055	138286	7086	917	4785	990357	4803	126779531
5000	594456	1288161	807317	394908	12280	1361	8437	2733652	7646	397328583

Рис.5. Зависимость времени выполнения сортировки от количества элементов

5. Реализация структур данных типа дерево и типовые алгоритмы их обработки

5.1 Постановка задачи

Реализовать процедуры создания красно-черных деревьев (динамическое представление), поиска, удаления и добавления узлов. Реализовать малое левое вращение для решения задач балансировки

5.2 Теоретические положения

Красно-чёрное дерево -- самобалансирующееся двоичное дерево поиска, имеющее сложность О(log n), которое быстро выполняет основные операции: добавление, удаление и поиск узла. Узлы дерева имеют атрибут «цвет», что помогает сбалансировать дерево. Атрибут может принимать значения «черный» или «красный». Дерево обладает свойствами: корень и листья дерева - обязательно черные и оба потомка красного узла - черные.

Балансировка дерева - операция изменения связи предок-потомок в случае разницы высот правого и левого поддеревьев больше 1. Результат достигается путем вращения поддерева данной вершины.

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

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

Описание алгоритмов обработки дерева.

Вставка: Узел окрашивается в красный цвет, и если мы вставляем узел в лист, то добавляем в этот лист красный узел с двумя черными потомками. Затем выполнить балансировку.

Удаление:

· Если у вершины нет потомков, то изменяем указатель на неё у родителя на null.

· Если у неё только один потомок, то делаем у родителя ссылку на него вместо этой вершины.

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

· Сбалансировать дерево.

5.3 Результаты работы программы

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

Рис.6. Результат работы 4-ой части программы

6. Реализация функций расстановки (хеширование) и различных методов разрешения коллизий

6.1 Постановка задачи

Хеш-таблица представляет базу данных предметной области, соответствующей варианту. Реализовать:

· Выбор ключа для соответствующей базы данных.

· По крайней мере, 3 различных функции хеширования для конкретных данных.

· Заполнение таблицы для каждой функции.

· Добавление новых данных для каждой функции.

· Удаление данных.

· Поиск данных по ключу.

· Оценку качества хеширования для каждой функции.

· Сравнение функций хеширования.

6.2 Краткое теоретическое положение

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

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

Метод разрешения коллизий: двойное хеширование. Двойное хеширование - основан на использовании двух хеш-функций. Коллизии возникают при открытой адресации. Берется значение hash1, если значение уже использовано, то вычисляется вторая вспомогательная функция, и берется значение hash1+hash2, hash1+2*hash2 и т.д.

6.3 Описание сферы практического применения используемого типа данных

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

6.4 Результаты работы программы

Рис 7. Пример работы 5-ой части программы

Таблица 3. Зависимость количества элементов от количества коллизий

Количество элементов	Коллизии(хэш сложением)	Коллизии(хэш умножением)	Коллизии(хэш пирсона)
5	9	6	7
10	19	18	17
15	35	36	39
20	54	61	59
25	76	86	83

Рис.8. Зависимость количества элементов от количества коллизий

Литература

1. А. Ахо, Дж. Э. Хопкрофт, Д. Ульман Структуры данных и алгоритмы. М., Изд-во "Вильямс", 2000 г.

2. Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М., "Мир", 1976 г., переиздание - М.,Изд-во "Вильямс", 2000г.

3. Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. М., "Мир", 1978 г., переиздание - М.,Изд-во "Вильямс", 2000 г.

4. Н. Вирт Алгоритмы + структуры данных = программы. М., "Мир", 1985г.

5. Н. Вирт Алгоритмы и структуры данных. М., Издат-во "Вильямс", 1998г.

6. У. Топп, У. Форд. Структуры данных в С++. М., Изд-во "Бином", 2000 г.

Приложение А

namespace Nastya_Kurs_01

{

class Program

{

static void Main(string[] args)

{

LinkedList L = new LinkedList();

L.AddListElement(); L.AddListElement();

Stack S = Program.List_Stack(L);

//Console.WriteLine(S.Pop().Value);

L = Program.Stack_List(S);

Console.WriteLine(L.GetListElement(0).Value);

Console.ReadKey();

}

static Stack List_Stack(LinkedList List)

{

Stack Stack = new Stack(List.GetSize());

for (int i = 0; i < List.GetSize(); i++)

{

Stack.Push(new StackElement(List.GetListElement(i).Value));

}

return Stack;

}

static LinkedList Stack_List(Stack Stack)

{

LinkedList LinkedList = new LinkedList();

int n = Stack.GetSize();

for (int i = 0; i < n; i++)

{

LinkedList.AddNode(Stack.Pop().Value);

}

return LinkedList;

}

}

class ListElement

{

public ListElement(int value)

{

this.value = value;

}

private int value;

public int Value

{

get { return this.value; }

set { this.value = value; }

}

private ListElement next;

public ListElement Next

{

get { return next; }

set { next = value; }

}

}

class LinkedList //Класс связного списка

{

public LinkedList()

{

this.size = 0;

this.head = null;

this.tail = null;

this.thisList = this;

}

private int size;

private ListElement head;

private ListElement tail;

private LinkedList thisList;

public int GetSize() { return size; } // метод получить размер

public void AddListElement() // метод добавить

{

ListElement newElement = new ListElement(size);

this.size++;

if (this.head == null)

{

this.head = newElement;

this.tail = newElement;

}

else

{

this.tail.Next = newElement;

this.tail = newElement;

}

}

public void AddNode(int value)

{

ListElement newElement = new ListElement(value);

this.size++;

if (this.head == null)

{

this.head = newElement;

this.tail = newElement;

}

else

{

this.tail.Next = newElement;

this.tail = newElement;

}

}

public ListElement GetListElement(int number)

{

if (number > this.size)

{

Console.WriteLine("Данного элемента не существует");

return null;

}

else

{

ListElement Element = this.head;

for (int i = 0; i < number; i++)

{

Element = Element.Next;

}

return Element;

}

}

public void DeleteList() // метод удалить лист

{

this.thisList = new LinkedList();

}

}

class StackElement{

public StackElement(int value)

{

this.value = value;

}

private int value;

public int Value

{

get { return this.value; }

set { this.value = value; }

}

}

class Stack

{

private StackElement[] This;

private int topIndex;

public Stack(int size)

{

this.This = new StackElement[size];

}

public int GetSize()

{

return this.This.Length;

}

public bool IsEmpty()

{

return This[0] == null;

}

public void Push(StackElement item)

{

if (This[0] == null)

{

This[0] = item;

topIndex = 0;

}

else

{

topIndex = topIndex + 1; This[topIndex] = item;

}

}

public StackElement Pop()

{

if (IsEmpty())

{

Console.WriteLine("Стек пустой");

return null;

}

else

{

StackElement e = This[topIndex];

if (topIndex != 0)

topIndex = topIndex-1;

return e;

}

}

}

}

Приложение Б

Класс main()

import java.util.Dictionary;

import java.util.Hashtable;

public class part2

{

public static void main (String[] args)

{

String KEY="Интернет магазин"; //ключ, по которому будем искать в тексте

Dictionary<Integer, String> dict=new Hashtable <Integer, String>(); //создаем словарь

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

//текст, в котором будет реализован поиск

try

{

file.WriteObject(S);

dict.put(4, "Интернет магазин"); //ключ 4

System.out.println (file.ReadObject().length()+" символов"); //длина текста (=7710)

long t1=System.currentTimeMillis(); //засекаем время начала поиска по ключу

KMP.KnuthMorrisPratt(file.ReadObject(), KEY); //используя чтение из файла, находим по ключу KEY

long t2=System.currentTimeMillis(); //окончание времени поиска по ключу

long t3=System.currentTimeMillis(); //засекаем время начала поиска по ключу

int key=4; //ищем подстроку Интернет магазин

KMP.KnuthMorrisPratt(file.ReadObject(), dict.get(key)); //используя чтение из файла, находим строки по ключам из словаря

long t4=System.currentTimeMillis(); //окончание времени поиска по ключу

System.out.println ("Время поиска по ключу: "+(t2-t1) +" мс"); // вывод результата

System.out.println ("Время поиска со словарем: "+(t4-t3) +" мс"); // вывод результата

}

catch (Exception e) //если файл не найден, бросаем исключение

{

e.getMessage();

}

}

}

Класс KMP, в котором описан алгоритм поиска ключа

public class KMP

{

public static int KnuthMorrisPratt (String where, String what)

{

int n=where.length(); //длина строки, в которой происходит поиск

int m=what.length(); //длина подстроки

//формирование таблицы сдвигов

int[] table=new int [m]; //таблица сдвигов (массив)

table[0]=0; //значение первого элемента =0

int shift=0; //сдвиг равен 0

for (int q=1; q<m; q++)//проходим по количеству букв, которое находится в ключе (подстроке)

{

while (shift > 0 && (what.charAt(shift) != what.charAt(q))) //ищем совпадающее начало кусочка текста и подстроки

shift = table[shift-1]; //меняем сдвиг

if (what.charAt(shift)==what.charAt(q)) shift++; //считаем количество вхождений символов

table[q]=shift; //записываем значения в таблицу - создаем префиксную функцию

}

//поиск с использованием таблицы сдвигов

shift=0; //сдвиг равен 0

for (int i=0; i<n; i++) //прохождение по всему тексту

{

while (shift>0 && what.charAt(shift)!=where.charAt(i)) //если первые символы не совпали, то

shift=table[shift-1]; //двигаем текст на максимально возможное знаечение

if (what.charAt(shift)==where.charAt(i)) //если символы совпадают, то

shift++; //увеличиваем количество совпавших символов

if (shift==m) //если длина совпадения равна длине подстроки

return i-m+1; //подстрока найдена

}

return -1; //если ничего не найдено, возвращаем некорректное значение

}

}

Класс file, позволяющий создать и использовать файл

import java.io.*;

public class file //создание - чтение файла

{

public static void WriteObject (String S) throws IOException //создание файла, на вход идет строка (в нашем случае текст)

{

FileOutputStream fileOutput=new FileOutputStream ("file.dat"); //открываем файловый поток

ObjectOutputStream objectOutput=new ObjectOutputStream (fileOutput); //открываем поток, в который будем записывать объект (в нашем случае текст)

objectOutput.writeObject(S); //записываем в файл строку

fileOutput.close(); //закрываем поток

objectOutput.close(); //закрываем поток

}

public static String ReadObject() throws IOException, ClassNotFoundException //извлечение файла

{

FileInputStream fileInput=new FileInputStream ("file.dat"); //открываем файловый поток

ObjectInputStream objectInput=new ObjectInputStream(fileInput); //открываем поток, из которого будем читать объект (в нашем слкчае текст)

String s=(String) objectInput.readObject(); //создаем переменную, в которую записываем текст

fileInput.close(); //закрываем поток

objectInput.close(); //закрываем поток

return s; //возвращаем строку (текст)

}

}

Приложение В

using System;

using System.Diagnostics;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace PersonnelDepartmentApp {

public class Sorting {

public void swap(int[] arr, int i, int j) {

int t = arr[i];

arr[i] = arr[j];

arr[j] = t;

}

public void swap(int[] arr, int i) {

int temp;

temp = arr[i];

arr[i] = arr[i - 1];

arr[i - 1] = temp;

}

public int maxValue(int[] arr) {

int maxValue = int.MinValue;

for (int i = 0; i < arr.Length; i++) {

if (arr[i] > maxValue) {

maxValue = arr[i];

}

}

return maxValue;

}

public int[] selectionSort(int[] mass) {

int[] a = (int[]) mass.Clone();

int len = a.Length;

for (int i = 0; i < len - 1; i++) {

int min = i;

for(int j = i + 1; j < len; j++) {

if(a[j] < a[min]) {

min = j;

}

}

if(min != i) {

int t = a[i];

a[i] = a[min];

a[min] = t;

}

}

return a;

}

public int[] bubbleSort(int[] mass){

int[] arr = (int[]) mass.Clone();

for(int i = arr.Length-1 ; i > 0 ; i--){

for(int j = 0 ; j < i ; j++){

if( arr[j] > arr[j+1] )

swap(arr, j, j+1);

}

}

return arr;

}

public int[] gnomeSort(int[] mass) {

int[] a = (int[]) mass.Clone();

int size = a.Length, i = 1,j = 2;

while (i < size) {

//для сортировки по убыванию поменяйте знак сравнения на <

if (a[i - 1] > a[i]) {

i = j;

j = j + 1;

} else {

swap(a, i);

i = i - 1;

if (i == 0) {

i = j;

j = j + 1;

}

}

}

return a;

}

public int[] insertionSort (int[] mass) {

int[] m = (int[]) mass.Clone();

int t, i, j;

for (i = 0; i < m.Length; i++) {

t = m[i];

for ( j=i-1; j>=0 && m[j] > t; j--)

m[j+1] = m[j];

m[j+1] = t;

}

return m;

}

public void merge(int[] Mas, int left, int right, int medium) {

int j = left;

int k = medium + 1;

int count = right - left + 1;

if (count <= 1)

return;

int[] TmpMas = new int[count];

for (int i = 0; i < count; i++) {

if (j <= medium && k <= right) {

if (Mas[j] < Mas[k])

TmpMas[i] = Mas[j++];

else

TmpMas[i] = Mas[k++];

} else {

if (j <= medium)

TmpMas[i] = Mas[j++];

else

TmpMas[i] = Mas[k++];

}

}

j = 0;

for (int i = left; i <= right; i++) {

Mas[i] = TmpMas[j++];

}

}

public void mergeSort(int[] a, int l, int r) {

int m;

// Условие выхода из рекурсии

if(l >= r)

return;

m = (l + r) / 2;

// Рекурсивная сортировка полученных массивов

mergeSort(a, l, m);

mergeSort(a, m + 1, r);

merge(a, l, r, m);

}

public int[] bucketSort(int[] mass) {

int[] items = new int[mass.Length];

// Предварительная проверка элементов исходного массива

if (items == null || items.Length < 2) {

return mass;

}

int maxValue = items[0];

int minValue = items[0];

for (int i = 1; i < items.Length; i++) {

if (items[i] > maxValue)

maxValue = items[i];

if (items[i] < minValue)

minValue = items[i];

}

List<int>[] bucket = new List<int>[maxValue - minValue + 1];

for (int i = 0; i < bucket.Length; i++) {

bucket[i] = new List<int>();

}

// Занесение значений в пакеты

for (int i = 0; i < items.Length; i++) {

bucket[items[i] - minValue].Add(items[i]);

}

int position = 0;

for (int i = 0; i < bucket.Length; i++)

{

if (bucket[i].Count > 0)

{

for (int j = 0; j < bucket[i].Count; j++)

{

items[position] = (int) bucket[i][j];

position++;

}

}

}

return items;

}

public int[] shellSort(int[] mass) {

int[] a = (int[]) mass.Clone();

int i, j, k, h, m=0, b=a.Length;

int[] d = { 1, 4, 10, 23, 57, 145, 356, 911, 1968, 4711, 11969, 27901,

84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,

58548857, 157840433, 410151271, 1131376761, 2147483647 };

while (d[m] < b) {

++m;

}

while (--m >= 0) {

k = d[m];

for (i=k; i<b; i++) { // k-сортировка

j=i;

h=a[i];

while ((j >= k) && (a[j-k] > h)) {

a[j]=a[j-k];

j = j-k;

}

a[j] = h;

}

}

return a;

}

public int[] heapSort(int[] mass) {

int[] a = (int[]) mass.Clone();

int n = a.Length, i, sh = 0, b = 0;

while (true) {

b = 0;

for (i = 0; i < n; ++i) {

if (i*2 + 2 + sh < n) {

if (a[i+sh] > a[i*2 + 1 + sh] || a[i + sh] > a[i*2 + 2 + sh]) {

if (a[i*2+1+sh] < a[i*2+2+sh]) {

int t = a[i+sh];

a[i+sh] = a[i*2+1+sh];

a[i*2+1+sh] = t;

b = 1;

} else if (a[i*2+2+sh] < a[i*2+1+sh]) {

int t = a[i+sh];

a[i+sh] = a[i*2+2+sh];

a[i*2+2+sh] = t;

b = 1;

}

}

} else if (i * 2 + 1 + sh < n) {

if (a[i+sh] > a[i*2+1+sh]) {

int t = a[i+sh];

a[i+sh] = a[i*2+1+sh];

a[i*2+1+sh] = t;

b=1;

}

}

}

if (b == 0) {

sh++;

}

if (sh+2==n)

break;

}

return a;

}

public int partition (int[] array, int start, int end) {

int marker = start;

for ( int i = start; i <= end; i++ ) {

if ( array[i] <= array[end] ) {

int temp = array[marker];

array[marker] = array[i];

array[i] = temp;

marker += 1;

}

}

return marker - 1;

}

public void quickSort (int[] array, int start, int end) {

int pivot;

if ( start >= end ) {

return;

}

pivot = partition (array, start, end);

quickSort (array, start, pivot-1);

quickSort (array, pivot+1, end);

}

public void stoogeSort(int[] item, int left,int right) {

int tmp, k;

if(item[left] > item[right]) {

tmp=item[left];

item[left]=item[right];

item[right]=tmp;

}

if((left+1)>=right)

return;

k = (int) ((right - left + 1) / 3);

stoogeSort(item,left, right-k);

stoogeSort(item, left+k, right);

stoogeSort(item, left, right-k);

}

public void executeTest(int[] quantity) {

Random random = new Random();

Sorting sorter = new Sorting();

for (int i = 0; i < quantity.Length; i++) {

Console.WriteLine("Отчёт по массиву из " + quantity[i] + " элементов:");

int[] mass = new int[quantity[i]];

for (int j = 0; j < quantity[i]; j++) {

mass[j] = random.Next(10000);

}

long start = 0, end = 0;

Console.Write("Сортировка выбором:");

try {

start = Stopwatch.GetTimestamp();

sorter.selectionSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Сортировка простыми обменами, сортировка пузырькa:");

try {

start = Stopwatch.GetTimestamp();

sorter.bubbleSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Гномья сортировка:");

try {

start = Stopwatch.GetTimestamp();

sorter.gnomeSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Сортировка вставками:");

try {

start = Stopwatch.GetTimestamp();

sorter.insertionSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Сортировка слиянием:");

try {

start = Stopwatch.GetTimestamp();

sorter.mergeSort((int[]) mass.Clone(), 0, mass.Length - 1);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Блочная сортировка:");

try {

start = Stopwatch.GetTimestamp();

sorter.bucketSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Сортировка Шелла:");

try {

start = Stopwatch.GetTimestamp();

sorter.shellSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Пирамидальная сортировка:");

try {

start = Stopwatch.GetTimestamp();

sorter.heapSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Быстрая сортировка:");

try {

start = Stopwatch.GetTimestamp();

sorter.quickSort((int[]) mass.Clone(), 0, mass.Length - 1);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Stooge Sort:");

try {

start = Stopwatch.GetTimestamp();

sorter.stoogeSort((int[]) mass.Clone(), 0, mass.Length - 1);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

}

}

}

}

\

Приложение Г

Класс main()

import java.util.Random;

public class main

{

public static void main(String[] args)

{

Random r=new Random(); //для случайных значений ключей и значений ключей

RedBlackBST<Integer, Integer> st = new RedBlackBST<Integer, Integer>(); //создание экземпляра дерева

for (int i=0; i<10; i++) //10 узлов дерева (пример)

st.put(r.nextInt(100), r.nextInt(100)); //добавление узлов в дерево

for (Integer s : st.keys()) //среди всех ключей

System.out.println("Ключ: "+s + "; значение: " + st.get(s)); //вывести информацию по ключу (ключ-значение)

System.out.println("Содержит ключ 34: "+st.contains(34));

System.out.println("Размер дерева: "+st.size());

System.out.println("Высота дерева: "+st.height());

System.out.println("Получить значение ключа 56: "+st.get(56));

System.out.println("Максимальный ключ: "+st.max());

}

}

Класс RedBlackBST (Red-Black Binary Search Tree)

import java.util.LinkedList;

import java.util.NoSuchElementException;

import java.util.Queue;

public class RedBlackBST<Key extends Comparable<Key>, Value> //класс красно-черного дерева

{

private static final boolean RED = true; //красный узел - true

private static final boolean BLACK = false;//черный узел - false

private Node root; // корень дерева

private class Node //класс узлов дерева

{

private Key key; // ключ узла

private Value val; // значение ключа

private Node left, right; // ссылки на левый и правый элементы

private boolean color; // атрибут цвет

private int N; // счетчик

public Node(Key key, Value val, boolean color, int N) //конструктор

{

this.key = key;

this.val = val;

this.color = color;

this.N = N;

}

}

private boolean isRed(Node x) //является ли узел красным

{

if (x == null) //если в дереве ничего нет

return false; //возвращаем false

return (x.color == RED); //является ли узел красным

}

private int size(Node x) //число узлов в дереве

{

if (x == null) //если корень пустой,

return 0; //то вернуть 0

return x.N; //вернуть число узлов

}

public int size() //число узлов (ключ-значение)

{

return size(root); //вызов метода, начиная с корня

}

public Key search (Key key)

{

return search(root, key);

}

private Key search (Node current, Key key)

{

if (current == null)

return null;

if (current.key == key)

return current.key;

return search(key < current.key ? current.left : current.right, key);

}

public boolean isEmpty() //является ли дерево пустым

{

return root == null;//вернуть true или false

}

public Value get(Key key) //вернуть значение по ключу

{

return get(root, key); //вызов метода с передачей дерева в нем

}

private Value get(Node x, Key key) //получение значение

{

while (x != null) //пока узел не будет пустым,

{

int cmp = key.compareTo(x.key); //сравниваем значение ключа с текущим узлом

if (cmp < 0) x = x.left; //если значение меньше, идем влево

else

if (cmp > 0) x = x.right; //иначе если значение больше, идем вправо

else return x.val; //иначе вернуть искомое значение

}

return null; //если ничего не найдено, вернуть null

}

public boolean contains(Key key) //содержит ли дерево такой ключ

{

return (get(key) != null); //вернуть результат через метод get (Key key)

}

public void put(Key key, Value val) //вставка узла с ключом и значением

{

root = put(root, key, val); //создание узла с передачей в другой метод (private)

root.color = BLACK; //окрашивание корня в черный цвет (для того, чтобы мы могли далее добавлять узлы любого цвета)

}

private Node put(Node h, Key key, Value val)

{

if (h == null) //если узел пустой,

return new Node(key, val, RED, 1); //то окрашиваем его в красный

int cmp = key.compareTo(h.key); //сравниваем вставляемый узел с текущим

if (cmp < 0) h.left = put(h.left, key, val); //если меньше, то вызываем этот метод рекурсивно для вставки слева

else

if (cmp > 0) h.right = put(h.right, key, val); //иначе вызываем метод рекурсивно для вставки справа

else h.val = val; //иначе перезаписываем это значение

if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); //если узел справа красный и узел слева черный, то вызываем левое вращение узла

if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); //если узел А слева красный и левый узел В узла А красный, то вызываем правое вращение

if (isRed(h.left) && isRed(h.right)) flipColors(h); //если узел слева красный и узел справа красный, то меняем их цвета на черные (красные узлы имеют только черные дочерние узлы)

h.N = size(h.left) + size(h.right) + 1; //считаем общее количество узлов

return h; //возвращаем узел

}

public void deleteMin() //удаление минимального элемента

{

if (isEmpty()) throw new NoSuchElementException("BST underflow"); //если дерево пустое, выбросить exception

if (!isRed(root.left) && !isRed(root.right)) //если оба дочерних узла корня черные,

root.color = RED; //то перекрасить корень в красный

root = deleteMin(root); //вызов метода для корня

if (!isEmpty()) root.color = BLACK; //если дерево не пустое, то перекрасить корень в черный

}

private Node deleteMin(Node h) //удаление минимального элемента, начиная с корня h

{

if (h.left == null)//если элемента, меньшего корня нет, то

return null; //возвратить null

if (!isRed(h.left) && !isRed(h.left.left)) //если узел слева черный и его дочерний узел слева черный, то

h = moveRedLeft(h); //перекрасить в красный цвет дочерний узел слева

h.left = deleteMin(h.left); //вызываем этот метод рекурсивно для узла слева

return balance(h); //вернуть узел в сбалансированном дереве

}

public void delete(Key key) //удаление по ключу

{

if (!contains(key)) //если такого ключа не существует, то

{

System.err.println("symbol table does not contain " + key); //написать сообщение пользователю

return; //вернуть

}

if (!isRed(root.left) && !isRed(root.right)) //если оба дочерних узла корня черные, то

root.color = RED; //перекрасить корень в красный

root = delete(root, key); //вызов метода удаления, начиная...