Методи обчислення адреси. Нехай у кожному з М елементів масиву Т міститься елемент списку (наприклад, ціле позитивне число)

Нехай у кожному з М елементів масиву Т міститься елемент списку (наприклад, ціле позитивне число). Якщо є деяка функція Н(V), що обчислює однозначно по елементі V -ого адресу- ціле позитивне число з інтервалу [0,М-1 ], то V можна зберігати в масиві T з номером H(V) тобто V=T(H(V)). При такому збереженні пошук будь-якого елемента відбувається за постійний час, не залежний від М.

Масив Т називається масивом хешування, а функція Н- функцією хешування.

При конкретному застосуванні хешування зазичай є визначена область можливих значень елементів списку V і деяка інформація про них. На основі цього вибирається розмір масиву хешування М і будується функція хешування. Критерієм для вибору М і Н є можливість їхнього ефективного використання.

Нехай треба зберігати лінійний список з елементів K₁,K₂,..,K_n, таких, що при К_i=К_j, mod(K_i,26)= mod(K_j,26). Для збереження списку виберемо масив хешування T(26) із простором адрес 0-25 і функцію хешування H(V)= =mod(V,26). Масив Т аповнюється елементами Т(Н(К_i))=К_i і Т(j)=0, якщо j є у (H(K₁), Н(К₂),..,Н(К_n)).

Пошук елемента V y масиві Т із присвоюванням Z його індексу, якщо V міститься в Т, чи -1, якщо V не міститься в Т, здійснюється так:

int t[26],v,z,i;

i=(int)fmod((double)v,26.0);

if(t[i]= =v) z=i;

else z= -1;

Додавання нового елемента V y список з поверненням у Z індексу елемента, де він буде зберігатися, реалізується фрагментом

z=(int)fmod((doule)v,26.0);

t[z]=v;

а виключення елемента V зі списку присвоєнням

t[(int)fmod((double)v,26)]=0;

Тепер розглянемо складніший випадок, коли умова Ki=Kj H(Ki)=H(Kj) не виконується. Нехай V— множина можливих елементів списку (цілі позитивні числа), у якому максимальна кількість елементів дорівнює 6. Візьмемо М=8 і як функцію хешування виберемо функцію H(V)=mod(V,8).

Контрольні питання

1. Наведіть приклади використання алгоритмів пошуку.

2. Поясність особливості алгоритмів пошуку рядків.

3. Порівняйте алгоритми лінійного та бінарного пошуку.

4. Навіть алгоритми пошуку рядків.

5. Назвіть найефективніші методи пошуку рядків.

Тести для закріплення матеріалу

1. Перерахувати алгоритми пошуку

а) бульбашки;

б) лінійний;

в) ортогональний;

г) бінарний;

д) інтерполяційний.

2. Перерахувати алгоритми пошуку

а) бульбашки;

б) лінійний;

в) Боуера і Мура;

г) бінарний;

д) Кнута-Моріса-Прата.

3. Перерахувати алгоритми пошуку в стрічках

а) Боуера і Мура;

б) бінарний;

в) Кнута-Моріса-Прата;

г) прямий пошук;

д) паралельний пошук.

4. За фраґментом програми визначте метод пошуку:

L:=0;R:=N;

while L<R do begin

m:=(L+R) div 2; i:=0;

while (T[m,i]=x[i]) and (x[i]<>00h) do i:=i+1;

if T[m,i]<x[i] then L:=m+1 else R:=m

end;

if R<N then begin

i:=0;

while (T[R,i]=x[i]) and (x[i]<>00h) do i:=i+1

end

а) Боуера і Мура;

б) бінарний;

в) Кнута-Моріса-Прата;

г) прямий пошук;

д) паралельний пошук.

ЛЕКЦІЯ № 7

Тема: Алгоритми сортування: методи внутрішнього сортування

Ціль: розглянути методи внутрішнього сортування та їх застосування

План