Алгоритмы поиска и сортировки данных
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?оследнем случае шаблон смещается на одну позицию вправо, и сравнение символов продолжается, начиная с первого символа шаблона и символа в соответствующей позиции в тексте. Заметим, что последняя позиция в тексте, которая еще может выступать в роли начала искомой подстроки - п - т (если позиции в тексте индексируются значениями от 0 до п - 1). После этой позиции в тексте остается слишком мало символов, чтобы они могли соответствовать шаблону. Следовательно, по достижении указанной позиции алгоритм не должен делать никаких сравнений.
Алгоритм BruteForceStriny Match (Т[0..п - 1], Р[0..т - 1])
// Алгоритм реализует поиск подстроки методом грубой силы
// Входные данные: массив Т[0..п - 1] из п символов, представляющий
// текст; массив P[0..m - 1] из т символов, представляющий шаблон
// Выходные данные: позиция первого символа в тексте, с которой
// начинается первая искомая подстрока, соответствующая шаблону;
// если подстрока не найдена, возвращается - 1
for i = 0 to п - т do= 0j < т and P[j] = Т[i + j] do= j + 1j = mi
return - 1
Работа алгоритма проиллюстрирована на рис. 2.7.
Рис. 2.7. Пример поиска подстроки с применением грубой силы
Обратите внимание, что в данном примере алгоритм практически всегда смещает шаблон после первого же сравнения символа. Однако наихудший случай намного неприятнее: алгоритм может выполнять все m сравнений перед сдвигом шаблона, и это происходит в каждой из п - m + 1 попыток. Однако в случае типичного поиска слова в тексте на естественном языке можно ожидать, что большинство сдвигов будет выполняться после небольшого количества сравнений (взгляните на приведенный пример). Таким образом, эффективность в среднем случае должна быть существенно выше эффективности в худшем случае.
3. Разработка программного средства и руководство пользователя
3.1 Описание процесса создания программного средства
Программа будет разрабатываться при помощи программного средства Borland Delphi 7.
Программа будет состоять из одной формы, на которой и будут производиться все действия.
Для удобства работы форма будет разделена на три области (для ввода данных, для вызова действий и для вывода результатов). Для визуального разделения областей используем компоненты TGroupBox.
Для ввода исходных данных и вывода результатов используем компоненты ТMemo и компонент TLabeledEdit.
Для выбора действий используем компоненты TButton и TCheckBox.
Внешний вид формы на этапе разработки показан на рис. 3.1. (Приложение 2).
Для массива, с которым будем работать, используем тип данных String - это позволить осуществлять сортировку и поиск строк.
Изначально все кнопки, кроме кнопки Принять данные, переключатель для показа времени сортировки и поле для ввода шаблона поиска должны быть недоступны. Для этого на этапе разработки установим им свойство Enabled в значение false.
Для того чтобы эти компоненты стали доступны пользователь должен ввести в левую область данные, с которыми должна работать программа и нажать кнопку Принять данные.
В обработчике данной кнопки предусмотрим проверку на то, чтобы соответствующее поле при нажатии кнопки было не пустым. Для этого используем следующую проверку:
then">if Memo1.Text <> then
begin
…………………………………………………………..(Не введен список!, mtWarning, [mbOK], 0);
Если же поле непустое, то произведем считывание данных в специальный массив и разблокируем все элементы. Для этого используем следующий фрагмент кода:
for i := 1 to Memo1.Lines.Count do
mas[i] := Memo1.Lines[i-1];:= Memo1.Lines.Count;.Enabled := true;.Enabled := true;.Enabled := true;.Enabled := true;.Enabled := true;.Enabled := true;.Enabled := true;.Enabled := true;_Shablon.Enabled := true;1.Enabled := true;
Обработчики всех кнопок, предназначенных для сортировки, имеют практически идентичную структуру, которая отличается только реализацией алгоритма сортировки. Типичная структура обработчика приведена ниже:
QueryPerformanceFrequency(iCounterPerSec);
QueryPerformanceCounter(T1);
// реализация используемого алгоритма сортировки
QueryPerformanceCounter(T2);CheckBox1.Checked = true then(Время сортировки + FormatFloat(0.00000000000, (T2 - T1) / iCounterPerSec) + сек., mtInformation, [mbOK], 0);.Lines.Clear;i := 1 to kol do.Lines.Add(mas[i]);
В программе предусмотрена возможность отображать время, за которое была выполнена сортировка. Для этого предназначены функции QueryPerformanceFrequency и QueryPerformanceCounter и функция MessageDlg, которая выводит эти данные на экран (если пользователь поставил соответствующую галочку).
Приведем код одного из используемых алгоритмов сортировки (сортировка вставками):
for i:=1 to kol do:= mas[i];:= i-1;(j >= 0) and (mas[j] > temp) do[j+1] := mas[j];:= j-1;[j+1] := temp;;
Структура обработчиков на каждый из алгоритмов поиска отлична друг от друга, поэтому рассмотрим их более подробно.
При последовательном поиске используются данные из левой части формы, предусмотрены проверки на наличие списка и на наличие ключа поиска:
then">if Memo1.Text <> then
……………………………………(Не введен список!, mtWarning, [mbOK], 0);LE_Shablon.Text = then(Не задан шаблон поиска, mtWarning, [mbOK], 0)
Затем считывается шаблон и производится поиск. Для этого используется следующий код:
str := LE_Shablon.Text;i := 1 to kol dotemp[i] = str then;
Проверка на результат поиска проводится путем сравнения значения переменной i и числа строк в списке. Если результат положителен, то в левой части формы происходит выделение найденной строки. Для этого используется следующий фрагмент кода:
if i <= kol then
begin
Memo1.SelStart := Memo1.Perform(EM_LINEINDEX, i-1, 0);.SelLength := Length(Memo1.Lines[i-1]);.SetFocus;(Шаблон поиска не найден!,mtWarning,[mbOK],0);
При бинарном поиске вначале