Алгоритмы сортировки и поиска

Организация возможности просмотра текстовых файлов и осуществления поиска нужных слов в тексте. Редактирование текста (шрифт, размер). Алгоритм поиска подстроки в строке (метод Кнута-Морриса-Пратта). Загрузка текста из файла (с расширением .txt).
Краткое сожержание материала:

Размещено на

Размещено на

Министерство образования и науки РФ

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

ГОУ ВПО Череповецкий Государственный Университет

Институт информационных технологий

Кафедра ПО ЭВМ

Алгоритмы сортировки и поиска

Расчетно-пояснительная записка к курсовой работе

Исполнитель: студентка гр.1ПО-31

Сатюкова Д.А.

Руководитель: Селивановских В.В.

2009г.

Введение

Данный программный продукт представляет собой программу «Текстовый редактор». Она предназначена для широкого круга пользователей и не требует особых знаний, кроме базовых навыков работы на компьютере. Эта программа позволяет загружать текст из файла и сохранять текст в файл, а также имеет своей возможностью осуществление поиска слова в тексте методом Кнута-Морриса-Пратта.

1. Общие сведения

Delphi - универсальная среда разработки, позволяющая создавать программы любого типа:

- программы для дома (например, мультимедийные с использованием графики, анимации);

- программы для офисов (базы данных, в том числе клиент-серверные приложения);

- программы для работы в Интернете и т.д.

Для написания нашей курсовой работы как раз и была использована среда Delphi7, как самая простая и удобная среда программирования. Преимущества Delphi - комбинация нескольких важнейших технологий:

· высокопроизводительный компилятор в машинный код;

· объектно-ориентированная модель компонент;

· Delphi - одна из наиболее мощных систем визуальной разработки программ;

· возможность обнаружения ошибок на этапе компиляции;

· простой и ясный синтаксис.

Программа работает под управлением операционной системы семейства Windows корпорации Microsoft.

2. Функциональное назначение

Данная программа обеспечивает выполнение следующих задач:

1) Загрузка текста из файла (с расширением .txt);

2) Сохранение в файл;

3) Некоторые возможности редактирования текста (Вырезать/Копировать/Вставить/Очистить/Выделить всё/Шрифт/Выравнивание);

4) Поиск и замена слов в тексте методом Кнута-Морриса-Пратта.

Элементы входных данных представляют собой текстовые файлы (с расширением .txt), и если необходим поиск, то слово для поиска и замены.

Элементы выходных данных представляют собой также текстовые файлы с расширением .txt. При поиске без замены, если слово найдено, оно выделяется в тексте; при поиске с заменой найденное слово заменяется на новое слово, введенное пользователем.

3. Описание логической структуры программы

Алгоритм Кнута -- Морриса -- Пратта (КМП-алгоритм) -- алгоритм поиска образца (подстроки) в строке. Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они опубликовали совместно в 1977 году. Этот алгоритм основывается на том соображении, что после частичного совпадения начальной части слова с соответствующими символами текста фактически известна пройденная часть текста и можно «вычислить» некоторые сведения (на основе самого слова), с помощью которых затем быстро продвинуться по тексту. Основным отличием КМП-алгоритма от алгоритма прямого поиска является выполнение сдвига слова не на один символ на каждом шаге алгоритма, а на некоторое переменно количество символов. Таким образом, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим.

Перед началом фактического поиска можно вычислить вспомогательную таблицу Shift; эти вычисления сводятся к некоторой предтрансляции слова. Если j определяет позицию в слове, содержащую первый несовпадающий символ (как в алгоритме прямого поиска), то величина сдвига определяется:

Shift[j] = j - LenSuff - 1. Значение LenSuff определяется как размер самой длинной последовательности символов слова, непосредственно предшествующих позиции j (суффикс), которая полностью совпадает с началом слова. LenSuff зависит только от слова и не зависит от текста.

Рис.1. Пример работы КМП-алгоритма

Приведенный на рис.1 пример поиска слова ABCABD показывает принцип работы такого алгоритма. Символы, подтвергшиеся сравнению, здесь подчеркнуты.



Рис.2. Обобщенный алгоритм работы программы

4. Спецификация программных модулей

Таблица 1

Название процедуры или функции	параметры	Действие
UNIT1
procedure OPEN1;	нет	Открытие файлов
procedure Create1;	нет	Создание нового файла
procedure SAVE1;	нет	Сохранение в файл
procedure TForm1.N2Click	(Sender: TObject)	Вызов процедуры Create1
procedure TForm1.N4Click	(Sender: TObject)	Вызов процедуры SAVE1
procedure TForm1.N3Click	(Sender: TObject)	Вызов процедуры OPEN1
procedure TForm1.N13Click	(Sender: TObject)	Выход из программы
procedure TForm1.N7Click	(Sender: TObject)	Вырезание выделенного текста в буфер обмена
procedure TForm1.N10Click	(Sender: TObject)	Копирование текста в буфер обмена
procedure TForm1.N11Click	(Sender: TObject)	Вставка текста из буфера обмена
procedure TForm1.N12Click	(Sender: TObject)	Выделение всего текста
procedure TForm1.ApplicationEventsHint	(Sender: TObject)	Осуществление всплывающих подсказок
procedure TForm1.N15Click	(Sender: TObject)	Спрятать/Показать панель инструментов
procedure TForm1.N16Click	(Sender: TObject)	Спрятать/Показать строку состояния
procedure TForm1.N17Click	(Sender: TObject)	Очистка рабочего поля
procedure TForm1.ToolButton8Click	(Sender: TObject)	Вызов процедуры Create1
procedure TForm1.ToolButton1Click	(Sender: TObject)	Вызов процедуры OPEN1
procedure TForm1.ToolButton2Click	(Sender: TObject)	Вызов процедуры SAVE1
procedure TForm1.ToolButton3Click	(Sender: TObject)	Вырезание выделенного текста в буфер обмена
procedure TForm1.ToolButton4Click	(Sender: TObject)	Копирование текста в буфер обмена
procedure TForm1.ToolButton5Click	(Sender: TObject)	Вставка текста из буфера обмена
procedure TForm1.ToolButton6Click	(Sender: TObject)	Выделение всего текста
procedure TForm1.ToolButton7Click	(Sender: TObject)	Очистка рабочего поля
Другие файлы: Алгоритмы поиска и сортировки данных Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиск... Алгоритм быстрой сортировки Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация... Алгоритмические языки: обработка одномерных массивов 1. Изучить способы описания и использования массивов, алгоритмы сортировки массивов, сортировку выбором, вставками и обменную сортировку. Так же алгор... Структуры и алгоритмы обработки данных В данной методичке описаны основные принципы работы со структурами и построение алгоритмов. Также здесь представлены примеры на языке Pascal. Основные... Структуры и алгоритмы обработки данных: Примеры на языке Си Рассмотрены структуры данных, их представление и алгоритмы обработки, без знания которых невозможно современное компьютерное программирование. Приведе...