В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 4
Текст из файла (страница 4)
2. Полноесовпадение: шаблон в тексте найден. 3. Сдвиг на длину шаблона; символа последней позициинет в шаблоне вообще – сдвиг возможен на всю длину шаблона. 4. Совпадения последнегосимвола снова нет, но сам символ есть в шаблоне, сдвиг на одну позицию (аналогично шагу1). 5. Полное совпадение – шаблон найден.В этом довольно тривиальном примере шаблон весьма прост и никакие его части в нёмне повторяются.
Если символ первого несовпадения в шаблоне отсутствует, сдвиг вправобудет максимален – на длину шаблона. Если же это не так, сдвиг должен быть меньше, анасколько – зависит от того, как часто в строке встречается совпавшая часть. Возможно,что мы натолкнулись на неё, нужно быть «осторожнее», и сдвиг будет меньше.Алгоритм Бойера-Мура предполагает использование двух вспомогательных таблиц (они18строятся по содержимому шаблона заранее, до начала поиска), первой из них мы фактически воспользовались в приведённом выше простом примере поиска.
Это так называемаятаблица стоп-символов , содержащая последнюю позицию каждого символа в шаблоне(кроме последнего), либо 0.Б РСимволы:Позиция:1остальные02Сдвиг шаблона после сравнения последнего символа будет меньше длины шаблона на величину из этой таблицы для несовпавшего символа текста. Т.е., при таком шаблоне посленесовпадения сдвиг будет почти всегда на три позиции (длина шаблона – три символа), заисключением букв Б и Р, когда сдвиг должен быть на две или одну позицию соответственно,чтобы буква совпала.Из-за крайней простоты шаблона поиска (БРА) таблица стоп-символов оказалась весьманесложной; вот как она будет выглядеть для шаблона АБРАКАДАБРА (т.е., если бы мыхотели искать в тексте это слово):Символы:Позиция:А Б Р К Д891057остальные0Видно, что в случае несовпадения последнего символа сдвиги будут не такими впечатляющимидля букв из шаблона (несмотря на его внушительную длину – 11), только для К и Д сдвигбудет примерно на половину длины шаблона; буквы же Б, Р и особенно А слишком частовстречаются в нём.Простота предыдущего примера (поиск подстроки БРА в строке АБРАКАДАБРА) проявляется ещё и в том, что шаблон ни в одной из позиций не совпал частично, а потому вторая таблица нам не понадобилась.
Эта вторая таблица называется таблицей суффиксов(завершающих символов шаблона) и содержит наименьшую величину, на которую надосдвинуть шаблон, чтобы он снова совпал с этим суффиксом. Для поиска шаблона АБРАКАДАБРА в каком-либо тексте это существенно, т.к. он немножко «самоповторяется» ипо этой причине сдвиги не должны быть большими, чтобы не пропустить совпадение.Суффикс:Сдвиг:–1. .
. А . . . РА . . . БРА . . . АБРА . . . ДАБРА (и более)377711Если произошло частичное совпадение суффикса шаблона с текстом, то необходимый сдвигшаблона надо узнавать на основе такой таблицы, показывающей повторяемость суффиксав теле шаблона. Если такая повторяемость есть, сдвиг будет меньше максимального и еговеличина уже содержится в таблице суффиксов!195.Алгоритмы сортировкиПод сортировкой числовых таблиц (массивов) понимается перестановка их элементов вопределённом порядке, например, по убыванию или возрастанию. После такой перестановки многие операции поиска осуществляются проще и эффективнее.
Важна сортировка идля обработки символьной информации, поскольку в этом случае достигается расположение элементов в алфавитном порядке (из-за «правильно» присвоенных символам числовыхкодов).В принципе, алгоритмов сортировки существует довольно много, а различаются они своими характеристиками, такими, как сложность выполнения, эффективность использованияпамяти и другими. Далее мы рассмотрим реализации нескольких часто используемых алгоритмов: пузырьковой сортировки, сортировки выбором, быстрой сортировки (Quicksort).Общим для всех этих алгоритмов является то, что они не используют дополнительную память: сортировка происходит в рамках сортируемого массива, про который предполагается, что он полностью помещается в оперативную память. Элементы массива для простотыбудем считать целыми числами, а сортировать его будем по возрастанию.Для записи алгоритмов на языке C будем использовать два макроопределения, которыепозволят нам сделать всё проще и нагляднее.
Вот эти макроопределения:#define Less(x,y) x < y#define Swap(x,y) {int t = x; x = y; y = t;}В первом результат сравнения является истинным, если первый элемент строго меньшевторого. Во втором осуществляется перестановка двух указанных элементов, причём дляэтого используется временная (локальная) переменная t.Сами алгоритмы будем записывать в виде функции, которой передаются: сортируемыймассив и необходимые размеры, указывающие область, где должна происходить сортировка.Для пузырьковой сортировки и сортировки выбором достаточно одного параметра размера:размера самого массива, поскольку «область воздействия» – весь массив, возможно ограничиваемый с одной из сторон.
Для быстрой сортировки (Quicksort) нужны два параметра размера,поскольку в процессе сортировки всего массива таким же способом рекурсивно сортируютсяего подмножества.Для создания тестовой программы каждого из алгоритмов сортировки ещё понадобятся:главная функция, в которой будет вызываться необходимая функция сортировки, а также вспомогательная функция отображения массива. На них – в силу их простоты – мыостанавливаться не будем.5.1.Пузырьковая сортировкаПросматриваем пары соседних элементов (например, справа) и элементы пары переставляем, если порядок «неестественный».
Делаем несколько проходов, завершая перестановкина каждом последующем проходе всё раньше и раньше (поскольку минимальные элементыуже попали на своё место).20Пусть i обозначает позицию, до которой в принципе может дойти после перестановок(оставшийся) минимальный элемент, j – индекс (правого) элемента из пары соседних элементов; пара не может затронуть элементы левее позиции i. Тогда функцию для реализации алгоритма можно записать так:void BubbleSort(int a[], int size){for (int i = 0; i < size-1; i++)for (int j = size-1; j > i; j--)if (Less(a[j],a[j-1]))Swap(a[j],a[j-1]);}Запись алгоритма включает цикл по всем конечным положениям первого (левого) элемента пары и вложенный в него цикл осуществления перестановок.
Этот вложенный циклне затрагивает элементы с индексами менее i, поскольку ранее на эти места уже былипомещены элементы с минимальными значениями.Вот как, например, в соответствии с приведённым кодом, протекает процесс сортировкинебольшого массива из пяти чисел, расположенных изначально не по возрастанию (какхотелось бы), а по убыванию:5555111111144415552222331444255332133324435412222333445Наблюдение за процессом сортировки массива, изначально расположенного «наоборот», даётвозможность увидеть, как «всплывают» меньшие значения, перемещаясь по массиву, и какна последнем месте оказываются по очереди все элементы этого массива, что, конечно, затратно для этого метода сортировки, поскольку там должен стоять максимальный элемент.По этой причине пузырьковая сортировка используется только тогда, когда скорость работыне является критичной.5.2.Сортировка выборомПеребираем все позиции в массиве (кроме, быть может, последней): это места, где можетстоять очередной минимальный элемент (из всех оставшихся).
Для каждой позиции еговозможного нахождения нужно также обнаружить этот минимальный элемент, для чегоперебираются все оставшиеся элементы на предмет обнаружения минимального. Найдяего, мы переместим его на место – путём перестановки – и продолжим перебор позицийдалее. К моменту достижения последней позиции окажется, что ничего перемещать будетуже не нужно, поскольку все минимальные элементы уже стоят на своих местах.Введём обозначения: i – позиция, где будет стоять очередной минимальный (среди оставшихся) элемент, k – это позиция, где он будет найден; пока он не найден (а он может бытьи не найден), полагаем, что k=i, т.е., что это – минимальный; j – текущий элемент дляанализа; если выполняется условие a[j]<a[k], значит, найден ещё меньший, чем тот, чтостоит в позиции минимального.21void SelectionSort(int a[], int size){for (int i = 0; i < size-1; i++){int k=i;for (int j = i+1; j < size; j++)if (Less(a[j],a[k]))k = j;if (i != k)Swap(a[i],a[k]);}}Внешний цикл – просмотр по очереди всех позиций (кроме последней) и перемещение вэту позицию минимального из оставшихся элементов (последняя позиция не нужна, поскольку последний оставшийся элемент в ней и будет находиться), внутренний – поискминимального элемента из остающихся; если таковой нашёлся, производится обмен: найденный минимальный элемент попадает на своё место, а на его бывшее место попадаетэлемент из текущей позиции.5.3.QuicksortИдея алгоритма: выбираем некоторый опорный элемент, по величине которого разделяеммассив на два подмассива, в одном – все элементы, не превышающие опорный, в другом– все, что не меньше опорного.
Затем для каждого из подмассивов (если в них более двухэлементов) рекурсивно запускаем ту же процедуру. В конце получаем отсортированныйпервоначальный массив.Реализация разделения может быть такой. Вводим два индекса-«указателя» позиции в массиве: i и j.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
