WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
Министерство общего и профессионального образования Российской федерации РОСТОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Чекулаева А.А.

Структуры данных. Сортировка. Поиск.

Методические указания для студентов вечернего и дневного отделения механико-математического факультета Ростов - на - Дону 2001 2 Печатается по решению учебно-методической комиссии механикоматематического факультета РГУ от 2001г.

АННОТАЦИЯ Данные методические указания предназначены для изучения темы:

структуры данных, сортировка, поиск. Уделяется внимание алгоритмам поиска образца в строке а также алгоритмам, работающим с динамическими структурами данных: топологическая сортировка и генератор перекрёстных ссылок.

Методические указания предназначены для студентов вечернего и дневного отделения механико-математического факультета РГУ и могут быть использованы как в контактных, так и в дистанционных формах обучения.

Автор : Чекулаева А.А.

© Чекулаева А.А. 2001 3 СОДЕРЖАНИЕ 1. Поиск образца в строке…………………………………4 1.1 Линейный поиск…………………………………….4 1.2 Алгоритм Кнута, Мориса и Пратта… ……………5 1.3 Алгоритм Боуэра и Мура…………………………...6 1.4 Алгоритм Рабина…………………………………..10 2. Топологическая сортировка…………………………..12 3. Таблица перекрёстных ссылок…………… ………….22 Литература……………………………………… ………..26 4 1. ПОИСК ОБРАЗЦА В СТРОКЕ Одна из наиболее часто встречающихся в программировании задач - задача поиска. Это идеальная задача, которую можно испытывать с использованием различных структур данных. Создано много различных алгоритмов поиска. Задача поиска подстроки в строке (образца в тексте) очень часто встречается в программировании, например, при трансляции (при поиске лексем или при распознавании операторов). Отсюда и очевидная заинтересованность в эффективном алгоритме поиска.

Задачу поиска образца в тексте определим следующим образом. Пусть задан массив S из N символов (текст) и массив P из M символов (образец или отыскиваемое слово), причём 0

Var S : string[N]; P : string[M];

Мы хотим найти первое вхождение слова P в текст S. Будем считать результатом поиска индекс (номер) К, указывающий на первое с начала строки совпадение с образом. Если строка не содержит образец, то К получает значение 0.

1.1 Л и н е й н ы й п о и с к Прежде чем обратить внимание на эффективность алгоритма разберём сначала прямолинейный алгоритм поиска (прямой поиск подстроки в строке). Для обозначения номеров (индексов) сравниваемых символов в строках S и P будем использовать переменные i и j соответственно.

i:=0;

repeat i:=i+1; j:=1;

while (j<=m) and (s[i+j-1]=p[j]) do j:=j+until (j=m+1) or (i=n-m+1);

if j=m+1 then k:=i else k:=0;

Условие j=m+1 соответствует результату “найден”. Условие i=n-m+соответствует тому, что нигде в строке совпадения с образцом нет.

Достаточная эффективность этого алгоритма достигается, если всего лишь после нескольких сравнений пары символов во внутреннем цикле фиксируется их несовпадение. Или, если образец расположен в строке, но не в конце текста. В худшем случае (если слово в тексте отсутствует или присутствует в самом конце текста) при поиске потребуется выполнить M*(N-M+1) сравнений.

1.2 А л г о р и т м К н у т а, М о р и с а и П р а т т а Алгоритм, изобретённый авторами приблизительно в 1970 году, требует порядка N+M сравнений символов даже в самом плохом случае.

Основной принцип алгоритма – не уничтожать ценную информацию. После частичного совпадения начальной части образа с символами строки при каждом несовпадении двух символов образ сдвигается на всё пройденное расстояние, поскольку меньшие сдвиги не могут привести к полному совпадению, и сравнение строки с образом (с начала образа) продолжается.

КМП–алгоритм даёт выигрыш, лишь когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образ сдвигается более чем на одну позицию.

Пример:

Hoola-Hoola girls like Hooligans Hooligan Hooligan- Hooligan Hooligan … Hooligan 1.3 А л г о р и т м Б о у е р а и М у р а Алгоритм Боуэра и Мура (БМ - поиск), предложенный в 1975 году, не только улучшает обработку самого плохого случая, но и даёт выигрыш в промежуточных ситуациях.

В поиске БМ сравнение символов начинает с конца образца. Перед фактическим поиском образ трансформируется в некоторую таблицу. В этой таблице d для каждого символа х алфавита d[x] - обозначает расстояние от самого правого в образе вхождения х до его конца (число букв в образце справа от последнего вхождения буквы). Для остальных символов d[x]=m, где m - длина образа. Если символ P[m] в образе содержится один раз - в конце, то d[P[m]] также получает значение равное m. Если символ P[m] встречается в образе несколько раз, то расстояние для него определяется по правилу, которое используется для любого символа образа. Рассмотрим несколько примеров.

Образец Hooligan имеет длину 8 символов.

d[H]=7, d[o]=6, d[o]=5, d[l]=4, d[i]=3, d[g]=2, d[a]=1, d[n]=8.

Для всех остальных символов х d[x]=8.

Образец предел имеет длину 6 символов.

d[п]=5, d[р]=4, d[е]=1, d[д]=2, d[л]=6.

Для остальных символов d[x]=6.

Образец радуга имеет длину 6 символов.

d[р]=5, d[а]=4, d[д]=4, d[у]=3, d[г]=1.

Для остальных символов d[x]=6.

Образец тиктак имеет длину 6 символов.

d[т]=2, d[и]=4, d[к]=3, d[а]=1.

Для остальных символов d[x]=6.

Образец ababab имеет длину 6 символов.

d[a]=1, d[b]=2.

Для остальных символов d[x]=6.



Если в процессе сравнения строки и образца обнаружено расхождения между строкой S(… si -1si ) и образцом P( p1 p2...pm ), образец сдвигается вправо так, чтобы а)если символ si в образце не встречается, то сдвиг осуществляется на длину образца;

б)если символ si в строке имеется, то сдвиг осуществляется на d[s[i]] позиций.

Проследим за процессом поиска на примере 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.Ho o l a – H oo l a g i r l s l i k e H o o l i g a n s Ho o l i g a n H o o l i g a n Ho o l i g a n H o o l i g a n H o o l i g a n Приведём алгоритм поиска БМ.

i:=m+1;

Repeat k:=i;

j:=m+1;

repeat j:=j-1;

k:=k- until (j<1) or (p[j]<>s[k]);

If j=0 then nom:=i-m Else i:=i+d[s[i-1]] Until (i>n) or (j=o);

If j>0 then nom:=Алгоритм требует

Запишем алгоритм в виде программы на Паскале.

var s, p : string;

i,j,m,n,k,nom : integer;

d : array[chr(0)..chr(255)] of integer;

c : char;

begin readln(s);

n:=length(s);

readln(p);

m:=length(p);

writeln(s,' ',n:5);

writeln(p,' ',m:5);

for c:=chr(0) to chr(255) do d[c]:=m;

for j:=1 to m-1 do d[p[j]]:=m-j;

for j:=1 to m-1 do write(d[p[j]]:5) ;

writeln(d[p[m]]:5);

i:=m+1;

repeat j:=m+1;

k:=i;

repeat k:=k-1;

j:=j- 1;

until (j<1) or (p[j]<>s[k]);

if j=0 then nom:=i-m else i:=i+d[s[i-1]] until (j<1) or (i>n+1);

if j<1 then writeln(nom) else writeln(0);

end.

Приведём результаты тестирования программы.

Образец - труд, строка - затруднение, nom=3.

Образец - грамм, строка - килограмм, nom=5.

Образец - туктук, строка - тактуктуктук, nom=4.

Образец - тиктак, строка - туктактиктак, nom=7.

Образец - предел, строка - распределение, nom=4.

Образец - ababab, строка - abcdabcdababab, nom=9.

1.4 А л г о р и т м Р а б и н а Алгоритм Рабина основан на следующей идее. Вырежем окошечко длины m, будем двигать его по входному тексту и смотреть, не совпадёт ли текст в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого создаём некоторую функцию, определённую на словах длины m. Если значение этой функции на тексте в окошечке и на образце различны, то совпадений нет. Если значения одинаковы, проверяем совпадение по буквам.

Выигрыш возможен за счёт того, что при сдвиге окошечка текст в окошечке не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Эти данные следует учитывать при изменении значения функции.

При построении функции можно заменить все буквы их кодами. Тогда функция будет вычислять сумму этих чисел или значение многочлена степени m в точке х=10 или в точке х=2. Выберем последний вариант.

var s, p : string;

i,j,m,n,nom : integer;

a,b : real;

c : integer;

begin readln(s);

n:=length(s);

readln(p);

m:=length(p);

writeln(s,' ',n:5);

writeln(p,' ',m:5);

a:=0;

for i:=1 to m do a:=a*2+ord(p[i]);

b:=0;

for i:=0 to m-1 do b:=b*2+ord(s[i]);

i:=m-1;

repeat i:=i+1;

c:=ord(s[i-m];

c:=c shl (m-1);

b:=(b-c)*2+ord(s[i]);

until (i=n) or (a=b);

if a=b then nom:=i-m+else nom:=0;

writeln(nom);

end.

Данная программа проверяет только совпадение текстов в окошечке.

Одной этой проверки в некоторых случаях может оказаться недостаточно.

Например, имеется строка asdfgh и образец fgh. Коды используемых символов имеют следующие значения:

a s d f g h 65 83 68 70 71 Значение функции на образце fgh равно 494 и значение функции на тексте asd в окошечке также равно 494. А посимвольного совпадения нет.

(asd fgh).

Упражнение 1.4.1. Дополните программу проверкой совпадения по буквам в случае совпадения функций на словах длины m.

2. ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА Топологическая сортировка - это сортировка элементов, для которых определён частичный порядок, то есть упорядочение задано не на всех, а только на некоторых парах элементов. Приведём несколько примеров.

Пример 1. В университетских программах одни изучаемые курсы опираются на материал других курсов, поэтому некоторые курсы лекций должны быть прочитаны раньше других. Топологическая сортировка означает чтение курсов в таком порядке, чтобы ни один курс не читался раньше того курса, на материале которого он основан. Если курс В использует материал, читаемый в курсе А, пишут А p В (А предшествует В).

Пример 2. В программах одни процедуры могут содержать вызовы других процедур. Для обозначения того, что процедура Р1 вызывается в процедуре Р2, используется следующее обозначение Р1 p Р2.

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

В общем виде частичный порядок на множестве S это отношение между элементами этого множества. Оно обозначается символом p "предшествует" и удовлетворяет следующим свойствам (аксиомам) для любых различных элементов x, y, z из S.

Транзитивность. Если x p y и y p z, то x p z.

Ассиметричность. Если x p y, то не y p x.

Иррефлексивность. Не x p x.

Свойства 1 и 2 частичного порядка обеспечивают отсутствие циклов. Это необходимое условие, при котором возможно преобразование к линейному порядку.





Будем считать, что множество S, которое нужно топологически отсортировать, является конечным.

Отношение частичного порядка можно иллюстрировать с помощью диаграммы или графа, в котором вершины обозначают элементы множества S, а стрелки обозначают отношение порядка. Пусть множество S и отношение порядка в нём заданы в виде последовательности пар ключей во входном файле:

1 p 2, 2 p 4, 4 p 6, 2 p 10, 4 p 8, 6 p 3, 1 p 3, 3 p 5, 5 p 8, 7 p 5, 7 p 9, 9 p 4, 9 p 10.

Символы p добавлены для ясности.

1 2 6 4 8 3 5 Рис.1. Частично упорядоченное множество.

Цель топологической сортировки - преобразовать частичный порядок в линейный. Графически это означает расположить вершины графа в ряд так, чтобы все стрелки были направлены вправо.

7 9 1 2 4 6 3 5 8 Рис. 2. Частично упорядоченное множество расположено линейно.

Алгоритм одного из возможных преобразований частичного порядка в линейный можно свести к следующей последовательности действий.

Действие 1. Выбираем какой-либо элемент, которому не предшествует никакой другой. Такой элемент обязательно существует, иначе имелся бы цикл. Выбранный элемент помещается в начало списка и исключается из множества S. В нашем примере таких элементов два. Это элементы со значениями 1 и 7.

Действие 2. К оставшемуся множеству ( оно попрежнему частично упорядочено) применяем тот же алгоритм, пока множество не станет пустым.

Множество S удобно организовать в виде звязного списка. Каждому элементу поставим в соответствие следующие характеристики: значение (ключ), множество следующих за ним элементов (последователей), счётчик предшествующих элементов (предшественников) и поле, связывающее элемент со следующим элементом списка. Будем использовать следующие обозначения. Ключ обозначим inf, счётчик предшественников - count, ссылку на следующий элемент в списке - next, ссылку на список последователей данного элемента - list1.

Множество последователей каждого элемента списка представим также в виде связного списка. Каждый элемент списка последователей содержит ссылку на элемент-последователь (id) и ссылку (next1) на следующий элемент в списке последователей.

Inf Count Next ListРис. 3. Структура элемента списка.

Id Next Рис. 4. Структура элемента подсписка последователей.

Опишем структуры данных Type Link = ^ elem;

Link1 = ^ elem1;

Elem = record Inf, count : integer;

Next : link;

List1 : linkEnd;

Elem1 = record Id : link;

Next1 : linkEnd;

Первая часть программы топологической сортировки читает входные данные и строит список. Читается пара значений x, y. X и y ищутся в основном списке. Если они в списке отсутствуют, то добавляются в список.

Затем к списку последователей элемента со значением x добавляется ссылка на элемент со значением y. И, наконец, количество предшественников у элемента со значением y увеличивается на 1.

List tail X 1 2 4 6 10 8 3 5 7 0 1 2 1 2 2 2 2 0 Рис. 5. Список, построенный на фазе ввода.

Вторая часть. Все построения, происходящие во второй части алгоритма, осуществляются на базе исходной цепочки. Последовательно выбираются элементы с нулевыми значениями счётчика предшественников.

Поле next используется повторно для связывания элементов без предшественников. Вначале в цепочку собираются все такие элементы исходного списка. Это элементы 1 и 7. Новая цепочка строится в обратном порядке. Вначале цепочка без предшественников имеет вид list 7 0 Nil Рис. 6. Список ведущих элементов с нулевыми счётчиками.

Работа с цепочкой элементов, не имеющих предшественников, заключается в выполнении следующих действий.

Первое действие. Печать элемента.

Второе действие. Так как элемент напечатан (обработан), он исключается из дальнейшей обработки. Этот элемент являлся предшественником для списка последователей. Исключение его из списка сопровождается уменьшением счётчика предшественников на единицу у каждого из его последователей. При этом, если оказывается, что какой-либо счётчик count принимает значение нуль, то элемент с нулевым значением счётчика добавляется к списку без предшественниеов.

На фазе ввода подсчитывается количество элементов основного списка.

На фазе вывода количество элементов уменьшается, и в конце вывода количество элементов должно стать равным нулю. Если этого не происходит, множество не является частично упорядоченным.

Алгоритм вывода демонстрирует работу со списком, который "пульсирует". В процессе вывода элементы добавляются в список и удаляются из списка в непредсказуемом порядке. Использование списка позволяет реализовать этот процесс.

{текст программы на Паскале} type link = ^elem;

link1 = ^elem1;

elem = record inf,count : integer;

next : link;

list1 : link end;

elem1 = record id : link;

next1: link end;

var list,tail,p,q : link;

t : link1;

z : integer;

x,y : integer;

function l(w:integer) : link;

{ссылка на ведущего с ключом w} var h:link;

begin h:=list;

tail^.inf:=w;

while h^.inf<>w do h:=h^.next;

if h=tail then begin {в списке нет элементов с ключом w} new(tail);

z:=z+1;

h^.count:=0;

h^.list1:=nil;

h^.next:=tail end;

l:=h end;

begin {инициализация списка ведущих фиктивным элементом} new(list); tail:=list; z:=0;

{фаза ввода } {0 - признак конца вводимых данных} write('x=…');

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.