Реферат Розробка комплексу програм і реалізація алгоритмів пошуку підрядка

Тема: Курсовые проекты

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

Розробка комплексу програм і реалізація алгоритмів пошуку підрядка

Пояснювальна записка

Пояснювальна записка містить 37 сторінок, 7 малюнків, 1 таблицю, 4 джерела, 2 додатки.

Метою розробки є програмний комплекс, що забезпечує можливість пошуку підрядка в тексті.

У процесі розробки на базі аналізу проблеми проведено обгрунтування і вибір засобів розробки програмного комплексу.

У результаті розроблена структура, програмного комплексу, клас абстрактного типу даних - список (далі АТД - список). На програмному рівні комплекс реалізований на мові С ++ в середовищі розробки Visual Studio.

При розробці програмного комплексу була використана сучасна технологія об'єктно-орієнтованого програмування і проектування графічного інтерфейсу користувача, така, як Windows Forms.

Зміст

Введення

Постановка завдання

Опис структури даних

Розробка детальних алгоритмів вирішення

Розробка структури програми

Опис програми

Експериментальна частина

Висновок

Список літератури

Додаток А. Графічна частина

Додаток Б. Вихідний код програми

Введення

У процесі виконання курсового проекту повинен бути реалізований комплекс програм пошуку підрядка в тексті алгоритмом прямого пошуку і алгоритмом Кнута-Морріса-Пратта. Повинен бути розроблений АТД або з поданням опису. Повинна бути розроблена програма тестування трудомісткості операцій. Ефективність роботи алгоритмів повинна бути представлена ??на графіках. Повинен бути виконаний порівняльний аналіз теоретичних та експериментальних оцінок ефективності алгоритмів. Робота алгоритмів повинна бути представлена ??скріншотами інтерфейсу програми. ПЗ повинно бути розроблене на мові програмування С ++.

Постановка завдання

Швидкий пошук точно заданого підрядка в рядку є однією з самих найпростіших завдань пошуку інформації. Однак це завдання є надзвичайно важливою. Дана функція вбудована в різні текстові редактори і бази даних, що істотно прискорює процес пошуку інформації та редагування (заміну) фрагментів.

В даний час функції пошуку підрядка в рядку інкапсульовані в багато високорівневі мови програмування. Але варто пам'ятати, що стандартні функції далеко не найоптимальніші та ефективні, і якщо основним завданням програми є знаходження підрядка в рядку, то необхідно знати принципи організації функцій пошуку. Також не потрібно забувати, що область застосування функцій пошуку не обмежується одними текстовими редакторами і базами даних. Алгоритми пошуку використовуються різними пошуковими роботами при індексації сторінок, і від швидкості знаходження необхідних ключових слів у тексті залежить актуальність інформації. Спам-фільтр поштових сервісів також займається пошуком в тексті листів певних фраз. Все це говорить про актуальність проблеми пошуку підрядка в рядку.

Опис структури даних.

АТД - масив структур struct line, містить int id - ідентифікатор рядки, char str [255] - рядок. line * arr - покажчик на сам масив. Масив відразу створюється з розміром n=0. Розмір n змінюється при наступному додаванні елементів. АТД - список має компонентні функції: завантаження даних з файлу, додавання елемента, видалення елемента. Виклик функцій АТД реалізований в інтерфейсі програми. Вихідний код АТД див. Додаток 1.

Дані:

Параметри: id - ідентифікатор елемента масиву структур; str [255] - рядок.

Структура даних:

Масив структур розміром n.

Операції:

Завантаження з файлу:

Вхід: ім'я файлу з вхідними даними wchar_t file [255];

Процес: формування масиву з файлу;

Вихід: новий розмір списку n;

Додати рядок:

Вхід: String ^ str - рядок для додавання;

Процес: включення отриманого рядка в масив, виконується функцією Addline ();