Структуры данных. Сортировка. Поиск. Методические указания для студентов вечернего и дневного отделения механико-математического факультета

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

Чекулаева А.А.

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

Методические указания для студентов вечернего и дневного отделения механико-математического факультета

Ростов - на - Дону 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<M ≤ N.Описаны они так: Var S : string[N]; P : string[M]; Мы хотим найти первое вхождение слова P в текст S. Будем считать результатом поиска индекс (номер) К, указывающий на первое с начала строки совпадение с образом. Если строка не содержит образец, то К получает значение 0. 1.1 Л и н е й н ы й п о и с к Прежде чем обратить внимание на эффективность алгоритма разберём сначала прямолинейный алгоритм поиска (прямой поиск подстроки в строке). Для обозначения номеров (индексов) сравниваемых символов в строках S и P будем использовать переменные i и j соответственно. i:=0; repeat i:=i+1; j:=1;

5

while (j<=m) and (s[i+j-1]=p[j]) do j:=j+1 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+1 соответствует тому, что нигде в строке совпадения с образцом нет. Достаточная эффективность этого алгоритма достигается, если всего лишь после нескольких

сравнений пары символов во внутреннем цикле

фиксируется их несовпадение. Или, если образец расположен в строке, но не в конце текста. В худшем случае (если слово в тексте отсутствует или присутствует в самом конце текста) при поиске потребуется выполнить M*(N-M+1) сравнений. 1.2 А л г о р и т м К н у т а, М о р и с а и П р а т т а Алгоритм, изобретённый авторами приблизительно в 1970 году, требует порядка N+M сравнений символов даже в самом плохом случае. Основной принцип алгоритма – не уничтожать ценную информацию. После частичного совпадения начальной части образа с символами строки при каждом несовпадении двух символов образ сдвигается на всё пройденное расстояние, поскольку меньшие сдвиги не могут привести к полному совпадению, и сравнение строки с образом (с начала образа) продолжается. КМП–алгоритм даёт выигрыш, лишь когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образ сдвигается более чем на одну позицию.

6

Пример: Hoola-Hoola girls like Hooligans Hooligan HooliganHooligan 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 символов.

7

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 p 2 ... 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.242526272829303132 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 Hool i g a Ho o l

i

n g a n H o o l

i g a n Ho o l i g a n

8

Приведём алгоритм поиска БМ. i:=m+1; Repeat k:=i; j:=m+1; repeat j:=j-1; k:=k-1 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:=0 Алгоритм требует
: string;

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

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

begin readln(s); n:=length(s); readln(p);

9

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. Приведём результаты тестирования программы.

10

Образец - труд, строка - затруднение, 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);

11

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+1 else nom:=0; writeln(nom); end. Данная программа проверяет только совпадение текстов в окошечке. Одной этой проверки в некоторых случаях может оказаться недостаточно. Например, имеется строка asdfgh и образец fgh. Коды используемых символов имеют следующие значения:

12

a

s

d

f

g

h

65

83

68

70

71

72

Значение функции на образце 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.

13

Транзитивность. Если 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

3

4

10

8

9

5 7 Рис.1. Частично упорядоченное множество.

Цель топологической сортировки

- преобразовать частичный порядок в

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

14

7

9

1

2

4

6

3

5

8

10

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

ссылку на элемент-последователь (id)

следующий элемент в списке последователей.

и

ссылку (next1) на

15

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

Id Next1 Рис. 4. Структура элемента подсписка последователей. Опишем структуры данных Type Link = ^ elem; Link1 = ^ elem1; Elem = record Inf, count : integer; Next

: link;

List1

: link1

End; Elem1 = record

End;

Id

: link;

Next1

: link1

16

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

X и y ищутся в

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

tail

X

1 0

2 1

4 2

6 1

10 2

8 2

3 2

5 2

7 0

9 1

Рис. 5. Список, построенный на фазе ввода. Вторая часть. Все построения, происходящие во второй части алгоритма, осуществляются на базе исходной цепочки.

Последовательно

17

выбираются элементы с нулевыми значениями счётчика предшественников. Поле

next

используется

повторно

для

связывания

элементов

без

предшественников. Вначале в цепочку собираются все такие элементы исходного списка. Это элементы 1 и 7. Новая цепочка строится в обратном порядке. Вначале цепочка без предшественников имеет вид list 7 0

1 0 Nil

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

из

дальнейшей

обработки.

Этот

элемент

являлся

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

и в конце вывода

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

18

{текст программы на Паскале} type link = ^elem; link1 = ^elem1; elem = record inf,count : integer; next

: link;

list1

: link1

end; elem1 = record id

: link;

next1: link1 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;

19

h^.list1:=nil; h^.next:=tail end; l:=h end;

begin {инициализация списка ведущих фиктивным элементом} new(list); tail:=list; z:=0; {фаза ввода } {0 - признак конца вводимых данных} write('x=?…'); readln(x); while x<>0 do begin write('y=?…'); readln(y); p:=l(x); q:=l(y); new(t);; t^.id:=q; t^.next1:=p^.list1; p^.list1:=t; q^.count:=q^.count+1; write('x=?'); readln(x) end; {вывод элементов построенного списка со списком последователей для каждого элемента} readln; p:=list; while p<>tail do

20

begin write(p^.inf:7); t:=p^.list1; while t<>nil do begin write(t^.id^.inf:5); t:=t^.next1 end ; writeln; p:=p^.next end; {список ведущих со счётчиком 0} p:=list; list:=nil; while p<>tail do begin q:=p; p:=p^.next; if q^.count=0 then begin q^.next:=list; list:=q; end end; {фаза вывода } q:=list; while q<>nil do begin

21

writeln(q^.inf); z:=z-1; t:=q^.list1; q:=q^.next; while t<>nil do begin p:=t^.id; p^.count:=p^.count-1; if p^.count=0 then begin {включение p^ в q - список} p^.next:=q; q:=p end; t:=t^.next1 end end; if z <> 0 then writeln('множество не является частично упорядоченным'); readln end. Построенный список со списком последователей печатается в виде 1

3

2

2

10

4

4

8

6

6

3

10 8 3

5

5

8

22

7

9

5

9

10

4

На фазе вывода печатается следующая последовательность элементов 7

9

1

2

4

6

3

5

8

10.

То есть частичный порядок преобразован в линейный. Упражнение 2.1. Будет ли программа работать правильно, если пара (x, y) встретится во входном файле более одного раза? Упражнение

2.2.

Дополните

программу,

чтобы

она

выдавала

последовательность элементов, которые образуют цикл, если он имеется. Упражнение 2.3. Напишите программу, которая находит все определения и вызовы подпрограмм и проверяет, топологическое упорядочение на подпрограммах. 3. ТАБЛИЦА ПЕРЕКРЁСТНЫХ ССЫЛОК Алгоритм поиска по дереву с включением часто применяется в трансляторах и в программах, предназначенных для работы с банками данных для организации объектов, которые нужно хранить и искать в памяти. Рассмотрим

пример

построения

таблицы

перекрёстных

ссылок

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

23

заполняется идентификаторами программы в алфавитном порядке и списком номеров строк, в которых идентификатор встречается. Каждый узел дерева поиска представим в виде записи, содержащей слово текста (inf), ссылки на левого (l) и правого (r) сыновей и ссылки на начало подсписка (list) и на конец подсписка (tail) номеров строк с данным словом . Предположим, что некоторое слово встречается в строках с номерами 1, 10 и 11. Структура узла дерева с подсписком номеров строк может быть представлена в следующем виде: L Ссыка на левого сына

list

inf слово

tail

r Ссылка на правого сына

1 10 11 Рис. 7. Структура узла дерева. В программе построения таблицы перекрёстных ссылок можно выделить две функции: процедуру поиска и вставки элемента в дерево search и процедуру обхода дерева - printtree. Ниже приведён упрощённый вариант программы. Упрощение происходит за счёт того, что входной текст представлен последовательностью слов, каждое из которых начинается с новой строки. Слова читаются в основной программе. Добавление слова в дерево перекрёстных ссылок выполняет рекурсивная процедура search с параметрами t - ссылка на корень дерева, sl - добавляемое слово, n -номер строки, в которой находится прочитанное слово.

Печать построенной

таблицы перекрёстных ссылок выполняет рекурсивная процедура printtree, которая обходит дерево и печатает содержимое в виде таблицы.

24

{Таблица перекрёстных ссылок} type link=^node; link1= ^num_str; node=record {тип - узел дерева} inf

:string;

l,r

:link;

list,tail:link1 end; num_str=record {тип - номер строки} num:integer; next:link1 end; var root:link; sl :string; k :integer; procedure search(var t:link; sl:string; n:integer); var p:link; q:link1; begin if t=nil then begin {создание корня дерева или листа } new(t);new(q); q^.num:=n; q^.next:=nil; with t^ do begin inf:=sl; l:=nil; r:=nil; list:=q; tail:=q; end end else

25

if slt^.inf then search(t^.r,sl,n) {подсоединение листа справа} else begin {добавление элемента в подсписок номеров} new(q); q^.num:=n; q^.next:=nil; t^.tail^.next:=q; t^.tail:=q end end; procedure printtree(t:link); procedure print_word(w:node); var x:link1; begin write(w.inf:8,' : '); x:=w.list; while x<>nil do begin write(x^.num, ' '); x:=x^.next end; writeln end; begin if t<>nil then begin printtree(t^.l); print_word(t^); printtree(t^.r)

26

end end; begin root:=nil; readln(sl); k:=1; while sl<>'' do {пустое слово - признак конца вводимых слов} begin search(root,sl,k); readln(sl); k:=k+1 end; printtree(root); readln end. Упражнение 3.1. Напишите программу, которая генерирует таблицу перекрёстных ссылок для любой программы на Паскале. Напомним, что идентификатор - любая последовательность букв и цифр, начинающаяся с буквы.

ЛИТЕРАТУРА 1.Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. 2. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989.