Поиск в таблицах
Поиск в массиве называется поиском в таблице, если ключ сам является структурой, такой как массив чисел или символов.
String=array[0..N-1] of char; для установления факта совпадения, мы должны убедиться, что символы сравниваемых строк соответственно равны один другому. Должны разумно сформировать и все это свести к поиску равных частей. Если части не равны, то говорим о неравности.
Когда конец массива можем записать дополнительных элемент х , который сыграет роль барьера.
String=array[0..n]
of char;
var
a:string;
begin
a[N]=x;
i:=0;
while
a[i]<> x do i:=i+1;
Предположим, что строки имеют переменный размер. Размер необходимо указывать в каждой отдельной строке. Используется 2 способа строк.
1) Размер неявно указывается путем добавление #0 (терминальный 0). Из всех возможных это минимальный код.
2) Размер явно хранится путем добавления первого элемента массива (0 для статических). a:string[30]; ord(a[0]);
Пусть имеем первую схему. Построим алгоритм сравнения строк
X,y:string;
i:=0; while (x[i]=y[i]) and (chr(x[i])<>#0) do i:=i+1;
При поиске в таблице я имею вложенные поиски. Поиск по строкам в таблице и для каждой строки последовательное сравнение между компонентами.
T:array
[0..N-1] of string;
x:string;
N - Допустим велико и таблица упорядочена в алфавитном порядке. Воспользуемся делением пополам и сравнение строк как внутренний поиск в строке таблицы.
L=0
R=N
R<N L<R Совп.нет i=0 Tr=xi And |x|<>#0
i=i+1 Совп.есть конец
-
m=(L+R)div
2; i=0
+
Tmi=xi And Tmi≠#0
i=i+1
+
Tmi<xi
R=m-1
- -
L=m+1
+
После частичного совпадения соответствующего символа строки и можем продвинуть по тексту на все совпавшие символы. Дальнейшее совпадение ищем начиная с первого не совпавшего символа.
Классический алгоритм необходимо добавить сдвиг на определенную величину.
БМ – в нем сравнение символов начинается с конца образа, а не с начала
Алгоритмы сортировки
Сортировка – перегруппировка заданного множества объектов в некотором определенном порядке.
Цель – оптимизация последующего поиска. Выбор алгоритма зависит от структуры обрабатываемых данных. Поэтому методы сортировки разбиты на 2 класса. Сортировка массивов и сортировка файлов. Файл - это динамическая внешняя структура, массив внутренняя структура.
Метод сортировки называется устойчивым, если в процессе сортировки элементов с равными ключами не изменяется. Устойчивость желательна если имеем дело уже с отсортированными элементами, но по некоторым вторичным ключам.
Сортировка массивов
Основное условие: Выбранный метод должен экономно расходовать доступную память. Следовательно, перестановка элементов должна иметь на том же месте, где расположен исходный массив.
Классифицируем по их экономичности. Оценивается двумя значениями С-число сравнений M- число перестановок. Хорошие алгоритмы сортировок требуют n*log2n сравнений, но существует базовые алгоритмы. В базовых алгоритмах n2 . В соответствие с определяющими эти базовыми методами принципами разбивают на 3 группы.
By insertion сортировка с помощью включений
By selection С помощью выделения, выбора
By exchange обмен
1) Сортировка с помощью прямого включения. Идея: мысленно делятся на уже готовую последовательность a1,..,ai-1,ai,..,an На каждом шаге начиная с i=2 и увеличивая i+1 из исходной последовательности извлекаем I элемент и перекладываем в готовую последовательность вставляя элемент на требуемое по логике место.
For
I:=2 to N
do begin
X:=a[i]; «вкл» х на соответствующее место среди a1 до ai end;
Х будем сравнивать с элементом aj, либо х вставляем на свободное место, либо aj двигаем в право, а процесс уходит влево. Процесс включения х при выполнение условия:
Найдем элемент ai С ключем меньше чем ключ х
Достигнут левый конец готовой последовательности
Воспользуемся приемом барьера, выставим брьер х в элемент а0.
A:array
[0..n] of integer;
{ai}1÷N,N I=2÷N aj=aj-1 j=j-1 aj=x
Массив
отсортирован
x=ai
j=i a0=x
x<aj-1
Идентификация прямого включения, двоичное включение.
Готовая последовательность уже упорядочена.
Применить двоичный поиск для поиска места вставки х.
I=2÷N j=i÷(R+1)
x=ai
R=i L=1 aj=aj-1
Двоичный
поиск среди a<ar
ar=x
+