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

Результат программы
n=6
1 2 3 4 5 6
введите искомый элемент=6 искомый элемент находится в 6 позиции, и он был найден в 3 сравнениях
2.2 ИЗМЕНИТЬ ПОРЯДОК ТАБЛИЦЫ ПОИСКА
В общем, вероятность поиска каждого элемента в таблице можно объяснить каким-то значением. Предположим, в таблице есть искомый элемент. Тогда таблицу, в которой выполняется поиск, можно рассматривать как систему с дискретным состоянием, а вероятность нахождения в ней искомого элемента – как вероятность i-го состояния системы p(i).
n
p(i)1
i1
Когда мы рассматриваем таблицу как дискретную систему, количество сравнений в ней представляет собой математическое ожидание значений дискретных случайных величин.
Z=Q=1*p(1)+2*p(2)+3*p(3)+…+n*p(n)
Данные должны быть отсортированы в таблице в следующем виде:
p(1)p(2) p(3) …p(n).
Это условие увеличивает эффективность за счет уменьшения количества сравнений. Причина в том, что, поскольку последовательный поиск начинается с первого элемента, наиболее часто упоминаемый элемент должен быть помещен первым. Есть два наиболее часто используемых способа изменить порядок таблицы поиска.
Соедините их в один пучок
рассмотрим на примере списков.
1. Переупорядочить найденный элемент, поместив его в начало ro„yhat.
2. Метод транспонирования.
Поместив найденный элемент в начало списка
перестановка
Рисунок 2. Переупорядочить список
Найденный элемент помещается сразу в начало списка, как на рисунке 2. Каждый раз, когда элемент ищется в структуре, и он продолжает перемещаться в начало ro„yhat, в результате последние искомые элементы попадают в начало списка
и у нас есть возможность быстро найти элементы, которые мы искали в последнее время
будем.
В начале q-указатель, а P-начало списка; когда P указывает на второй элемент, Q указывает на первый. Индикатор заголовка списка (table) показывает Первый элемент. Когда элемент с ключевым словом находится в списке, он обозначается указателем P, а элемент перед ним-указателем Q. Тот же найденный элемент P помещается в начало списка.
Программный код
node *q=NULL;
node *p=table;
while (p !=NULL){
if (key == p->k){
if (q == NULL) { //o‘rinlashtirish shart emas
search = p;
exit(0);
}
q->nxt = p->nxt;
p->nxt=table;
table=p;
exit(o);
}
q=p;
p=p->nxt;
}
Search=NULL;
exit(o);