2.2Сортировка Шелла
Постановка задачи: Написать программу, которая реализует сортировку Шелла.
В 1959 г. Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. После первого прохода элементы перегруппировываются— теперь каждый элемент группы отстоит от другого на две позиции — и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка.
Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает. Так же очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Все t расстояний обозначаются соответственно hi, h2, ..., ht, для них выполняются условия
ht = l. hJ+1<h
Каждая h-сортировка программируется как сортировка с помощью прямого включения. Причем простота условия окончания поиска места для включения обеспечивается методом барьеров.
2.3 Trie-дерево
Постановка задачи: В Trie-дереве определить количество слов, содержащих букву А.
Деревом называется связный ориентированный граф без циклов, каждая вершина которого имеет только одно входящее ребро.
Узел и поддеревья связаны между собой ветвями. Число ветвей, выходящих из узла, определяют его арность. Если все узлы имеют одинаковую арность, равную n, то такая структура называется n-арным деревом. Если n = 2, то дерево называется бинарным.
Одним из видов сильно ветвящихся деревьев является Trie-дерево. Название Trie-дерево происходит от искусственно образованного слова trie, от полного слова retrieval (поиск). Такое дерево используется тогда, когда ключами поиска являются достаточно короткие слова. Чем больше коротких слов содержится в Trie-дереве, тем эффективнее соотношение количества слов к количеству памяти, расходуемой под хранение элементов в Trie-дереве. Каждый ключ в Trie-дереве можно рассматривать как список символов, а все списки вместе — как дерево поиска. В такой структуре узлу уровня i + 1 ставится в соответствие i-ый символ слова, поэтому каждый узел содержит лишь один символ. Методы поиска по такому дереву экономны по памяти и по времени.
Чтобы найти элемент в таком дереве, нужно, пройдя первый куст дерева, собрать слово. Затем, используя любой из методов поиска, найти в этом слове нужную нам подстроку. Если она существует, то функция поиска возвращает значение строки, в которой содержится заданная подстрока. Если запустить цикл, в котором найденные слова мы будем удалять, то мы удалим все слова из дерева, которые содержат указанную подстроку.
2.4 Обработка текстовых данных, хранящихся в текстовом файле
Постановка задачи: подсчитать число слов с чётной длиной.
В настоящее время текстовые файлы получили огромное распространение. Реализация программ представляет собой определенный алгоритм, где данные хранятся не в самой программе, а в отдельном файле. Программа в ходе работы к текстовуму файлу обращается в течение работы два раза, для получения обрабатываемых данных и для вывода результата работы. В основе программы лежит отсортировывание слов четной и нечетной длины. Это происходит по средствам сравнивания длин слов.
Заключение
В курсовой работе рассмотрены методы обработки больших массивов натуральных и действительных чисел. Этот вопрос очень актуален в наше время, потому что в настоящее время размер обрабатываемых данных постоянно увеличивается.
Также помня о задачах современности, не стоит забывать и о логических задачах, которые решаются только по средствам вычислительных машин. Программ о пяти ферзях именно такая. Еще вовремя наших дедушек задумывались о ее решение, но только сейчас она стала реализуемой.
В этой курсовой работе так же рассмотрены такие задачи, как: сортировка Шелла, нахождение элементов в Trie-дереве и задачу с текстовыми данными.
Эти задачи очень часто применяемы и программисты часто используют их для решения более сложных и комплексных задач. Поэтому решение этих задач является большим шагом на пути к тому, чтобы разрабатывать новые способы для обработки данных.
Список литературы
1. Вирт Н. Алгоритмы и структуры данных. — СПб.: Невский диалект, 2001. 352 с.
2. Дмитриева М. В.. Кубенский А. А. Турбо Паскаль и Турбо Си: построение и обработка структур данных: Учебное пособие. — СПб.: Изд-во С.- Петербургского университета, 1995. — 245 с.
3. Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск: Пер. с англ. — М.: Вильяме, 2000. — 822 с.
4. Мейер Д., Бодуэн К. Методы программирования. Т. 1,2.— М.: Мир, 1985.
5. Вирт Н. Алгоритмы и структуры данных+программы. — СПб.: Невский диалект, 2001. - 406 с.