алення рядки з тексту, див. Рис3.
Рис3. Видалення рядка
Ріс4. Пошук і виведення результатів роботи.
Ріс5.Поіск і виведення результатів роботи
Експериментальна частина
Дослідження ефективності алгоритмів
Тестування програми проводилося на вхідних даних різного розміру. В якості вхідної інформації були використані текстові файли містять англійський текст. Залежність часу пошуку від розміру для кожного алгоритму представлено в Таблиці 1 і Рис 6.
ВремяКолічество сімволовПрямой поіскАлгорітм КМП20330.013930.0127245600.0390.0297065930.047230,03294131860,0970,1 Таблиця1.
Рис 6. Графік залежності часу від кол-ва символів.
Аналізуючи графік Рис 6 і Таблицю 1 можна стверджувати, що алгоритм КМП дає виграш в тих випадках, коли неспівпадіння передує деяке число збігів, так як в цьому випадку образ зсувається відразу на кілька позицій. Але це буває не так часто, тому виграш, в порівнянні з прямим пошуком, не завжди значний
Дослідження трудомісткості.
Для алгоритму прямого пошуку була підрахована трудомісткість операцій, під якою мається на увазі кількість елементарних операцій необхідне для вирішення певної задачі. Графік залежності трудомісткості від розмірності см. Рис 7.
Рис 7. Залежність трудомісткості від розміру.
Графік Рис 7 показує, що чим більше кількість символів в списку рядків, тим більше буде потрібно призвести операцій для отримання результату. У коді програми за кількість елементарних операцій відповідає лічильник kol.
Висновок
В результаті написання курсового проекту мною були розроблені та реалізовані: алгоритми пошуку підрядка в тексті, АТД - масив структур, програма тестування трудомісткості для алгоритму прямого пошуку. Після чого, були приведені графік ефективності алгоритмів пошуку і графік залежності трудомісткості прямого пошуку від розміру тексту. Також пояснювальна записка містить опис АТД - список і структури програми. Працездатність програми показана на малюнках. Комплекс програм розроблений на мові програмування С ++ в середовищі Visual Studio.
У розробленій програмі реалізовані наступні можливості:
Формування масиву рядків з файлу;
Додавання рядка в масив;
Видалення рядка з масиву;
Очищення масиву;
Прямий пошук;
Пошук алгоритмом Кнута-Морріса-Пратта;
Висновок результатів роботи програми в окреме поле.
Список літератури
1. Д. Макконнел. Основи сучасних алгоритмів. М .: Техносфера, 2010. 368 с.
. Н. Вірт. Алгоритми та структури даних. М .: Невський Діалект, 2009. 352 с.
. Р. Седжвік. Фундаментальні алгоритми C ++. Частини 1-4. М .: Диасофт,
ДОДАТОК А
ДОДАТОК Б
# pragma once
# include lt; iostream gt;
# include lt; fstream gt;
# include lt; string gt;
# include lt; stdlib.h gt;
# include lt; ctime gt;
# include lt; time.h gt;
# include lt; omp.h gt;
# include lt; vcclr.h gt; KursachSia_Kod {namespace System; namespace System :: Runtime :: InteropServices; namespace System :: ComponentModel; namespace System :: Collections; namespace System :: Windows :: Forms ; namespace System :: Data; namespace System :: Drawing; namespace System :: IO; namespace std; line
{str [255]; id;
}; * arr; n=- 1, m=0, choice=0, longstr=0, kol=0; _t file [255];
/// lt; summary gt;
/// Зведення для Form1
/// lt;/summary gt; ref class Form1: public System :: Windows :: Forms :: Form
{:( void)
{();
//
//TODO: додайте код конструктора
//
}:
