Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм поиска




Поиск в упорядоченной таблице

Алгоритм последовательного поиска

Последовательный поиск

Введение в поиск

Алгоритмы поиска занимают важное место в прикладных алгоритмах. Обычно данные хранятся в определенном образом упорядоченном наборе. Найти некоторую запись из этого набора — вот классическая задача программирования, вокруг которой сгенерировано множество идей [1, 3, 9, 10, 13].

Пусть мы имеем таблицу, состоящую из записей (табл. 3.1). Первое поле каждой записи содержит ключ (например, табельный номер); второе — фамилию и так далее. Ключом может любое поле записи.

Таблица 3.1

 

  Иванов  
  Андреев  
  Сидоров  
     
  Петров  

Основная задача поиска — найти запись с заданным ключом.

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

Наиболее примитивный, а значит, и наименее эффективный, способ поиска— это обычный последовательный просмотр записей таблицы [9,11]. Метод применяется к таблице, организованной как массив. Предложим, что к — массив из п ключей; г — массив записей такой, что k(i) — ключ для записи r(i); key — аргумент поиска. Запишем в переменную search наименьшее целое число /, такое, что k(i) = key, если такое / существует, и -1 в противном случае.

 

for (search=-l, i=0; i<n; i + +)
if(key == k[i])    
{    
search=i;    
break;    
}    

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

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

Все реально применяемые методы поиска относятся к отсортированным таблицам. Для упорядоченной таблицы наиболее эффективными являются: 1) индексно-последовательный поиск и 2) бинарный поиск.

Индексно-последовательный поиск. В дополнение к отсортированной таблице заводится вспомогательная таблица, называемая индексной [9, 11]. Каждый элемент индексной таблицы состоит из ключа и указателя на запись в основной таблице, соответствующую этому ключу kindex. Элементы в индексной таблице, так же как элементы в основной таблице, должны быть отсортированы по этому ключу. Если индекс имеет размер, составляющий одну восьмую от размера основной таблицы, то каждая восьмая запись основной таблицы будет представлена в индексной таблице (рис. 3.1).

Алгоритм индексно-последовательного поиска прост. Предположим, что к — массив из п ключей; г — массив записей такой, что k(i) является ключом для записи r(i); key — аргумент поиска. Пусть — массив ключей в индексе; pindex — массив указателей в индексе на записи. Размер основной таблицып. Размер индексной таблицыindsize.

 

i = 0;        
while (( i < ind size) && (kindex [i] <= key))
i + +;        
/^установить low на наименьшую возможную позицию
элемента в массиве*/    
if(i == 0)      
low= 0;      
else        
low = pindex[i^ ;    
/^установить high на наибольшую возможную
позицию элемента в массиве*/  

if (i==ind_size)

high=n; else

high=pindex[i];

/*поиск в массиве от low до high*/


for (j=low, search= if (k[j]==key)

{

search=j; breake;


■1; j<high; j+ +


Основная таблица


Индексная таблица

kindex pindex


I L


 

k r i ключ запись I
8 ] - ^------- ч------ >
14 ] i ^--------- т--------- s
26,s \ ------------ ^----------- <.
38 1У v--------- ^-------- ^ i s
72 ] S
I PJ 115 I oo ^------------ ^----------- ч i
306 I I ^------------ ^----------- ч
• 321 ]
329 1 ^------------ т----------- >
387 I ----------------------------------- -> i
.409. ]|
LS12 L)]
540 1 I ч------------ ч----------- ч
567 ) \ ------------- *------------ 4
1 583 1 *----------------- *---------------- * i
5d2 1 ^----------- ^----------- ^
1--------- 1-------- h ' ■ ■ ■ i ч--------- ^------- гУ i

Рис. З.1. Схема хранения информации при индексно-последовательном поиске


Достоинство алгоритма заключаются в том, что сокращаются время поиска, так как последовательный поиск первоначально ведется в индексной таблице, имеющей меньший размер, чем основная таблица; когда найден правильный индекс, второй последовательный поиск выполняется по небольшой части записей основной таблицы.

Бинарный поиск. Аргумент сравнивается с ключом среднего элемента в массиве [9, 11]. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой и правой частях массива. Алгоритм определяется рекурсивно, однако на практике применяется нерекурсивная версия ввиду её большой эффективности.




Поделиться с друзьями:


Дата добавления: 2014-11-29; Просмотров: 1712; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.014 сек.