• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Методи обчислення адреси

М-блоковий пошук

Цей спосіб зручний при індексному збереженні списку. Передбачається, що вихідний упорядкований список В довжини N розбитий на М підсписків B=B₁,B₂,..,B_m довжини N₁, N₂,...,N_m, таким чином, що B=B₁,B₂,..,B_m.

Для знаходження ключа V, треба спочатку визначити перший зі списків В_i, і=1,...,М, останній елемент якого більше V, а потім застосувати послідовний пошук до списку В_і.

Збереження списків В_і може бути зв'язним чи послідовним. Якщо довжини всіх підсписків приблизно рівні і M=N, то Мах М-блокового пошуку дорівнює 2N. При однаковій частоті використання елементів Avg M- блокового пошуку дорівнює N.

Описаний алгоритм ускладнюється, якщо не відомо, чи дійсно в списку є елемент, що збігається з ключем V. При цьому можливі випадки: або такого елемента в списку немає, або їх кілька.

Якщо замість ключа V є упорядкований список ключів, то послідовний чи М-блоковий пошук може виявитися зручнішим, ніж бінарний, оскільки нетреба повторної ініціалізації для кожного нового ключа зі списку V.

Нехай у кожному з М елементів масиву Т міститься елемент списку (наприклад, ціле позитивне число). Якщо є деяка функція Н(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

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

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

Читайте також:

1. IP-адреси
2. Автододавання та автообчислення.
3. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
4. Автономні ІР-адреси
5. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
6. Адаптовані й специфічні методи дослідження у журналістикознавстві
7. Адміністративні (прямі) методи регулювання.
8. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.
9. Адміністративні методи управління
10. Адміністративні, економічні й інституційні методи.
11. Адміністративно-правові (організаційно-адміністративні) методи мотивації
12. Адміністративно-правові методи забезпечення економічного механізму управління охороною довкілля

Переглядів: 1143