72781

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

Курсовая

Информатика, кибернетика и программирование

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

Русский

2014-11-28

820.5 KB

2 чел.

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

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

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

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

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

Кафедра  –  ОСУ    

  

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

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

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

                Подпись             Дата                     

 

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

   должность         Подпись             Дата                     

2014 год

Оглавление:

[1] Оглавление:

[2] Литература

  1.  Задание на выполнение курсовой работы.

Вариант 10.

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

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

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

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

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

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

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

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

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

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

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

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

  •  Insert (x, e) – вставляет элемент е в позицию х
  •  Locate (e) – возвращает позицию элемента е в списке
  •  Retrieve (x) – возвращает элемент, находящийся в позиции x
  •  Delete (x) – удаляет элемент с позиции х
  •  Next (е) – возвращает следующую позицию после е
  •  Previous (е) – возвращает предыдущую позицию перед е
  •  Makenull() – делает список пустым
  •  Head() – возвращает первую позицию в списке
  •  Tail() – возвращает последнюю позицию в списке
  •  Printlist() – печатает элементы списка в порядке их расположения

Примеры АТД:

  1.  Список
  2.  Стек
  3.  Очередь
  4.  Ассоциативный массив
  5.  Очередь с приоритетом

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1)                2)

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

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

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

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


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

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

Длина подстроки

Время (мс)

10

4

20

17

50

22

100

18

300

34

500

62

800

108

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

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

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

  •  Провести экспериментальный сравнительный анализ различных методов сортировки. Для чистоты эксперимента сортировка должна проводиться на одинаковых наборах входных данных, которые генерируются случайным образом.     Для более полного анализа методов сортировка должна проводиться для различных размерностей данных, например: 500, 1000, 3000, 5000, 8000, 10000, 30000, 60000.
  •  Исходные наборы данных – массивы или файлы соответствующего типа (по № варианта).
  •  Проследить динамику роста требуемого для сортировки времени.   
  •  Проверить, как ведут себя методы на различных входных данных: упорядоченных в прямом порядке, упорядоченных в обратном порядке и случайных.
  •  Сравнить теоретические оценки времени сортировки и числа требуемых операций с экспериментальными.
  •  Построить соответствующие таблицы и графики сравнительного анализа различных методов сортировки (по времени, размерности и исходной упорядоченности)
  •  Провести исследования o для выбранных алгоритмов внутренней сортировки (один из методов вставки и один из методов обменной сортировки)   

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

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

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

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

  •  Время — характеризует быстродействие алгоритма. Эквивалентно вычислительной сложности. Для типичного алгоритма средняя сложность — O(n log n) и высокая — O(n2). Идеальное поведение для упорядочения — O(n).
  •  Память —временное хранение данных. Обычно эти алгоритмы требуют O(log n) памяти. Алгоритмы сортировки, которые не потребляют дополнительной памяти, относят к сортировкам на месте.

  1.  Сортировка выбором

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

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

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

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

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

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

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

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

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

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

  1.  Сортировка вставками

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

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

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

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

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

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

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

  1.  Сортировка Шелла.


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

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

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

  1.  Быстрая сортировка

 

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

  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.  Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

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

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

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

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

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

  1.  Stooge Sort

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

  •  Если значение элемента в конце списка меньше, чем значение элемента в начале, то поменять их местами.
    •  Если есть 3 или более элементов в текущем подмножестве списка, то:
  •  Рекурсивно вызвать Stooge sort для первых 2/3 списка
  •  Рекурсивно вызвать Stooge sort для последних 2/3 списка
  •  Рекурсивно вызвать Stooge sort для первых 2/3 списка снова
    •  Иначе: return

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

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

Количество элементов

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

Сортировки пузырьком

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Удаление: 

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

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

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

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

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

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

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

  •  Выбор ключа для соответствующей базы данных.
  •  По крайней мере, 3 различных функции хеширования для конкретных данных.
  •  Заполнение таблицы для каждой функции.
  •  Добавление новых данных для каждой функции.
  •  Удаление данных.
  •  Поиск данных по ключу.
  •  Оценку качества хеширования для каждой функции.
  •  Сравнение функций хеширования.

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

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

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

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

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

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

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

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

Количество элементов

Коллизии(хэш сложением)

Коллизии(хэш умножением)

Коллизии(хэш пирсона)

5

9

6

7

10

19

18

17

15

35

36

39

20

54

61

59

25

76

86

83

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

Рис.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); //вызов метода удаления, начиная с корня

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

   }

   private Node delete(Node h, Key key) //удаление узла с ключом key, начиная с корня h

   {

    if (key.compareTo(h.key) < 0) //если ключ этого узла меньше ключа корня, то

    {

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

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

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

       }

       else 

       {

           if (isRed(h.left)) //если узел слева красный, то

               h = rotateRight(h); //вызываем правое вращение

           if (key.compareTo(h.key) == 0 && (h.right == null)) //если значение ключа искомого узла равно значению ключа текущего узла и правый узел пустой, то

               return null; //ничего не возвращать

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

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

           if (key.compareTo(h.key) == 0) //если значение ключа искомого узла равно значению ключа текущего узла, то

           {

               Node x = min(h.right); //находим минимальный узел справа

               h.key = x.key; //переприсваиваем удаленному  узлу ключ минимального

               h.val = x.val; //переприсваиваем удаленному узлу значение минимального

               h.right = deleteMin(h.right); //удаляем минимальный узел

           }

           else h.right = delete(h.right, key); //иначе сделать то же самое для узла справа

       }

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

   }

   private Node rotateRight(Node h) //правое вращение узла h

   {

       Node x = h.left; //текущему узлу присваиваем левый узел узла h

       h.left = x.right; //левому узлу h присваиваем правый узел текущего узла

       x.right = h; //правому узлу текущего узла присваиваем узел h

       x.color = x.right.color; //перекрашиваем текущий узел в цвет узла справа

       x.right.color = RED; //узлу справа текущего узла х присваиваем красный цвет

       x.N = h.N; //переприсваиваем значение числа узлов

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

       return x; //возвращаем текущий узел

   }

   private Node rotateLeft(Node h) //левое вращение

   {

       Node x = h.right; //текущему узлу присваиваем правый узел узла h

       h.right = x.left; //правому узлу h присваиваем левый узел текущего узла

       x.left = h; //левому узлу текущего узла присваиваем узел h

       x.color = x.left.color; //перекрашиваем текущий узел в цвет узла слева

       x.left.color = RED; //узлу слева текущего узла х присваиваем красный цвет

       x.N = h.N; //переприсваиваем значение числа узлов

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

       return x; //возвращаем текущий узел

   }

   

   private void flipColors(Node h) //перекрашивание узлов

   {

       h.color = !h.color; //меняем цвет текущего узла на противоположный

       h.left.color = !h.left.color; //меняем цвет левого узла на противоположный

       h.right.color = !h.right.color; //меняем цвет правого узла на противоположный

   }

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

   {

       flipColors(h); //перекрасить узел h и его дочерние узлы

       if (isRed(h.right.left))  //если левый узел правого узла h красный, то

       {

           h.right = rotateRight(h.right); //правый узел - результат правого вращения

           h = rotateLeft(h); //узел - результат левого вращения

       }

       return h; //вернуть узел

   }

   // Предполагая, что узел h красный и правый узел и левый узел правого узла черные, сделать правый узел h или один из дочерних узлов красным

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

   {

       flipColors(h);  //перекрасить узел h и его дочерние узлы

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

           h = rotateRight(h); //узел - результат правого вращения

       return h; //вернуть узел

   }

   

   private Node balance(Node h) //восстановление красно-черного дерева

   {

       if (isRed(h.right))                      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 int height() //высота дерева 

   {

    return height(root); //вызов метода с ссылкой на корень дерева

   }

   

   

   private int height(Node x) //метод вычисления высоты дерева

   {

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

        return -1; //вернуть -1

       return 1 + Math.max(height(x.left), height(x.right)); //вернуть 1 + (максимальная высота из левого и правого поддеревьев)

   }

   

   public Key min() //минимальное значение ключа

   {

       if (isEmpty()) //если дерево пустое, вернуть

        return null; //null

       return min(root).key; //вызвать метод поиска минимального ключа

   }

   private Node min(Node x) //поиск минимального ключа  

   {

       if (x.left == null) //если узла слева нет, то  

        return x; //вернуть текущий узел

       else //иначе                

        return min(x.left); //вызываем рекурсивно метод для узла слева  

   }

   public Key max() //максимальное значение ключа

   {

       if (isEmpty()) return null; //если дерево пустое, вернуть null

       return max(root).key; //вызвать метод поиска максимального ключа

   }

   private Node max(Node x) //поиск максимального ключа

   {

       if (x.right == null) return x; //если узла справа нет, то вернуть текущий узел

       else                 return max(x.right);  //иначе вызвать рекурсивно этот метод для узла справа

   }

 

   public int rank(Key key) //количество ключей, меньших или = заданному

   {

       return rank(key, root); //вызов метода

   }

   private int rank(Key key, Node x) //количество ключей, меньших или = заданному, начиная с х

   {

       if (x == null) return 0; //если узел пустой, вернуть 0

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

       if      (cmp < 0) return rank(key, x.left); //если заданный меньше, то вызываем рекурсивно метод для левого узла

       else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right); //иначе если заданный больше, то вызываем рекурсивно метод для правого узла

       else              return size(x.left);  //иначе возвращаем количество

   }

   public Iterable<Key> keys() //все ключи

   {

       return keys(min(), max()); //вернуть все ключи

   }

   public Iterable<Key> keys(Key lo, Key hi) //все ключи

   {

       Queue<Key> queue = new LinkedList <Key>(); //очередь для добавления ключей в порядке возрастания

       keys(root, queue, lo, hi); //добавление ключей в очередь

       return queue; //вернуть очередь

   }

   public void keys(Node x, Queue<Key> queue, Key lo, Key hi) //добавление ключей в очередь, начиная с узла х, между минимальным и максимальным

   {

       if (x == null) return; //если узел пустой, выйти из метода

       int cmplo = lo.compareTo(x.key);  //сравнение с меньшим

       int cmphi = hi.compareTo(x.key);  //сравнение с большим

       if (cmplo < 0) keys(x.left, queue, lo, hi);  //если меньше меньшего, выполнить рекурсивно метод для левого узла

       if (cmplo <= 0 && cmphi >= 0) queue.add(x.key); //если меньше или = меньшему или больше или = большему, то просто добавить в очередь

       if (cmphi > 0) keys(x.right, queue, lo, hi); //если больше большего, то выполнить рекурсивно метод для правого узла

   }

   public int size(Key lo, Key hi) //количество ключей между меньшим и большим ключами

   {

       if (lo.compareTo(hi) > 0) return 0; //если разница между наименьшим и наибольшим больше 0, то вернуть 0

       if (contains(hi)) return rank(hi) - rank(lo) + 1; //если дерево содержит наибольший, то вернуть количество ключей между наибольшим и наименьшим +1

       else              return rank(hi) - rank(lo); //иначе вернуть количество ключей между наибольшим и наименьшим

   }

   

   private boolean isBalanced(Node x, int black) //сбалансированно ли дерево

   {

       if (x == null) return black == 0; //если текущая узел пустой, вернуть 0 черных узлов

       if (!isRed(x)) black++; //если узел черный, пересчитать черные узлы

       return isBalanced(x.left, black) && isBalanced(x.right, black); //вернуть, сбалансированно ли дерево справа и слева

   }

   

}


Приложение Д

Класс main()

import java.util.Scanner;

public class main

{

 public static void main (String args[])

 {

 Scanner scan = new Scanner(System.in); //создание объекта для ввода с клавиатуры

       System.out.println("Тестирование хеш-таблицы\n\n");  

       System.out.println("Введите размер таблицы");

       HashTable ht = new HashTable(scan.nextInt()); //создание экземпляра таблицы

 

       char ch; //символ при вводе "n" или "у"

       do    //действия при нажатии "y" (да)

       {

           System.out.println("\nОперации хеш-таблицы\n");

           System.out.println("1. Вставка ");

           System.out.println("2. Удаление");

           System.out.println("3. Найти по ключу");

           

           int choice = scan.nextInt(); //считывание номера операции           

           switch (choice) //варианты:

           {

           case 1 : //при нажатии "1"

               System.out.println("Введите ключ и значение");

               ht.insert(scan.next(), scan.nextInt()); //считывание ключа и значения

               break; //прерывание действия

           case 2 : //при нажатии "2"

               System.out.println("Введите ключ");

               ht.remove(scan.next()); //удаление по ключу 

               break; //прерывание

           case 3 : //при нажатии "3"

            System.out.println("Введите ключ");

               System.out.println("Значение искомого ключа = "+ ht.get(scan.next())); //вывод значения ключа 

               break; //прерывание

               

           default : //при вводе некорректного символа

               System.out.println("Ошибка \n ");

               break; //прерывание

           }

 

           ht.printHashTable(); //отображение хеш-таблицы  

 

           System.out.println("\nХотите продолжить? (Введите y или n)\n");

           ch = scan.next().charAt(0); //чтение символа у или n

       }

       

       while (ch == 'Y'|| ch == 'y');  //условие при выполнении действий с хеш-таблицей

   

 }

}

Класс HashTable

public class HashTable //класс хеш-таблицы

{

   private int TABLE_SIZE; //размер таблицы для создания объекта HashEntry

   private int size; //размер таблицы 

   private HashEntry[] table; //таблица

   private int primeSize; //размер таблицы (для вычисления хеш-функции)

 

 

   public HashTable(int ts) //конструктор 

   {

       size = 0;

       TABLE_SIZE = ts;

       table = new HashEntry[TABLE_SIZE];

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

           table[i] = null;

       primeSize = getPrime();       

   }

   

   public int size()

   {

    return this.size;

   }

   public int getPrime() //получить число, меньшее, чем размер таблицы для вычисления функции myhash2

   {

       for (int i = TABLE_SIZE - 1; i >= 1; i--) //рассматриваем весь размер таблицы

       {

           int fact = 0; //счетчик

           for (int j = 2; j <= (int) Math.sqrt(i); j++) //рассматриваем числа от 2 до корень(i)

               if (i % j == 0)//если от деления нет остатка, то

                   fact++; //прибавляем 1

           if (fact == 0) //если в счетчике ничего не было,

               return i; //вернуть размер таблицы-1

       }

       return 3; //вернуть 3

   }

   public int get(String key) //получить значение по ключу

   {

       int hash1 = myhash1( key ); //вычисление функции myhash1

       int hash2 = myhash2( key ); //вычисление функции myhash2

 

       while (table[hash1] != null) //пока просмотр таблицы не окончится

       {

        if (table[hash1].key.equals(key)) //если значение ключа равно искомому,

         return table[hash1].value; //возвратить значение найденного ключа

       

           hash1 += hash2; //вычисляем хеш-функцию

           hash1 %= TABLE_SIZE; //вычисляем хеш-значение

       }

       return -1; //ключ не найден

   }

   public void insert(String key, int value) //добавление в таблицу пары ключ-значение 

   {

       if (size == TABLE_SIZE) //если размер таблицы равен уже заданному размеру, то

       {

           System.out.println("Таблица заполнена");

           return;

       }           

       int hash1 = myhash1( key ); //вычисление функции myhash1

       int hash2 = myhash2( key ); //вычисление функции myhash2

       while (table[hash1] != null) //пока просмотр таблицы не окончится

       {

           hash1 += hash2; //вычисляем хеш-функцию

           hash1 %= TABLE_SIZE; //вычисляем хеш-значение

       }

       table[hash1] = new HashEntry(key, value); //создаем новое значение таблицы

       size++; //увеличиваем размер на 1

   }

 

 

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

   {

       int hash1 = myhash1( key ); //вычисление функции myhash1

       int hash2 = myhash2( key ); //вычисление функции myhash2  

       while (table[hash1] != null && !table[hash1].key.equals(key)) //пока просмотр таблицы не окончится и значение ключа не равно искомому,

       {

           hash1 += hash2; //вычисляем хеш-функцию

           hash1 %= TABLE_SIZE; //вычисляем хеш-значение

       }

       table[hash1] = null; //очищаем значение таблицы

       size--; //уменьшаем размер таблицы на 1

   }

   

   

   private int myhash1(String x ) //хеш-функция, которая дает хеш-значение для ключа (String)

   {

       int hashVal = x.hashCode( ); //получение хеш-кода

       hashVal %= TABLE_SIZE; //хеш-значение

       if (hashVal < 0) //если хеш-значение меньше нуля, то

           hashVal += TABLE_SIZE; //прибавим к нему размер таблицы

       return hashVal; //вернуть хеш-значение

   }

   

   private int myhash2(String x ) //хеш-функция для двойного хеширования

   {

       int hashVal = x.hashCode( ); //получение хеш-кода

       hashVal %= TABLE_SIZE; //хеш-значение

       if (hashVal < 0) //если хеш-значение меньше нуля, то

           hashVal += TABLE_SIZE; //прибавим к нему размер таблицы

       return primeSize - hashVal % primeSize; //вернуть хеш-значение (размер таблицы - остаток от деления хеш-значения на размер таблицы)

   }

   

   private int hashFunc2 (String key) //хеш-функция умножением

   {

    float f; //индекс в таблице (массиве)

    float A=(float) 0.6180339887499; //любое число в диапазоне 0..1

    int sss=key.length(); //получение длины ключа

    f = sss * A; //умножить ключ на константу А=(sqrt(5)-1)/2

    f = f - (int) f; // взять дробную часть

       return (int) (size*f); // возвратить число в диапазоне 0...size-1

  }

   

   private int hashFunc3 (String key) //хеш-функция делением с остатком

   {

    int len=key.length(); //получение длины ключа

    int j=len%TABLE_SIZE; //остаток от деления на размер таблицы

    return j; //вернуть значение

   }

   

   

   public void printHashTable() //вывод хеш-таблицы

   {

       System.out.println("\nХеш-таблица");

       for (int i = 0; i < TABLE_SIZE; i++) //рассматриваем весь размер таблицы

           if (table[i] != null) //если таблица не пуста, то

               System.out.println(table[i].key +" "+table[i].value); // вывести ключ и значение ключа

   }

}

Класс HashEntry

public class HashEntry //класс для создания таблицы

{

   String key; //ключ

   int value; //значение ключа

 

   public HashEntry(String key, int value) //конструктор при создании таблицы 

   {

       this.key = key;

       this.value = value;        

   }

}


 

А также другие работы, которые могут Вас заинтересовать

73299. Лизинг: понятие, виды, правовое регулирование 221.5 KB
  ля такой перестройки промышленности России необходимы инвестиции, которых в настоящее время остро не хватает. Поэтому наряду с традиционными формами инвестирования представляет интерес и ее особая форма - лизинг, который в силу присущих ему возможностей может стать импульсом технического перевооружения, создания необходимых мощностей промышленных предприятий и структурной перестройки экономики в целом.
73300. Формирование cметной стоимости строительства автомобильной дороги 287 KB
  Под сметной нормой рассматривают совокупность ресурсов (затрат труда рабочих-строителей и машинистов, времени работы строительных машин, механизмов и автотранспортных средств, потребность в строительных материалах, изделиях и конструкциях), установленная на принятый измеритель строительно-монтажных и других работ.
73301. Great Britain. The United Kingdom of Great Britain and Northern Ireland 30.5 KB
  The British Isles consist of two lrge islnds – Gret Britin nd Irelnd – seprted by the Irish Se nd lot of smll islnds the min of which re the Isle of Mn in the Irish Se the Hebrides – group of islnds off the northwestern cost of Scotlnd: the Orkney Islnds nd the Shetlnd Islnds. Gret Britin is situted in the temperte zone of Europe. The nture of Gret Britin is gretly ffected by the se: there is no plce situted more thn 100120 km from the seshore in the northern prts only 4060 km.
73302. Планирование в физическом воспитании и его виды, требования к составлению планирования и характеристика документов планирования 157.5 KB
  Содержание Введение Одной из актуальных тем физического воспитания в образовательной школе является планирование учебной работы по физической культуре так как оно значительно отличается по своему содержанию от планирования по другим учебным предметам. Учитывая массовый характер физического воспитания которое осуществляется во всех регионах страны и в различных звеньях его оптимизация является важной народнохозяйственной задачей страны. учитывать при разработке процесса физического воспитания. Качественное планирование невозможно без знания...
73303. Использование информационных систем управления предприятием в оперативно-производственном планировании (на примере информационной системы “Галактика”) 139 KB
  Возникло множество частных компаний крупных холдингов и корпораций. Однако применяемые многими российскими предприятиями методы управления до сих пор уходят своими корнями во времена централизованной экономики. Для того чтобы достичь мирового уровня конкурентоспособности российским предприятиям...
73304. Технология работ при создании лесных культур на вырубке 1.38 MB
  Рубки ухода с заготовкой древесины. Механизация и технология лесосечных работ на рубках ухода за лесом. Тракторы для вывозки сортиментов на рубках ухода. Исследование сменной производительности Псм малогабаритных колесных тракторов при вывозке сортиментов на рубках ухода.
73305. РЕГУЛИРОВАНИЕ ИНФЛЯЦИОННЫХ ПРОЦЕССОВ ИНСТРУМЕНТАМИ ФИСКАЛЬНОЙ ПОЛИТИКИ 562 KB
  Влияние фискальной политики на инфляционные процессы: разные подходы в теории Кейнсианский подход. Анализ показателей этапов и факторов инфляции в экономике РБ. Влияние фискальной политики РБ на инфляционные процессы ВВЕДЕНИЕ Разработка комплекса мер позволяющих обуздать инфляционные процессы является одним из дискуссионных вопросов современной макроэкономической политики государства.
73307. Особенности продвижения сайта с помощью социальных сетей на примере интернет ресурса Программы двойных дипломов 7.24 MB
  Именно ввиду того, что Интернет в наше время является едва ли не ключевым источником какой-либо информации, веб-технологиям уделяется большое внимание. Каждая крупная организация сегодня для привлечения своей ключевой аудитории в большей степени использует именно Интернет и Интернет-ресурсы. Одним из таких ресурсов является сайт организации, то есть место в Интернете