O`qituvchi: A.A.Avezov AT va RT kafedrasi katta o`qituvchisi Reja: - Massivlar va ro'yxatlarda qidirish
- Chiziqli qidiruv
- Ikkilik qidiruv
- Qator osti qidiruvi
- Oddiy qator osti qidiruvi
- Rabin-Karp algoritmi
- Boyer-Mur algoritmi
- Knut-Moris-Prat algoritmi
Massivlar va ro'yxatlarda qidirish - Massiv (ro'yxat) elementlarining qiymatlari kalit va ixtiyoriy ma'lumotlar tuzilmasi KeyData { K kalitiga bo'linadi; Tma'lumotlar; };
- Kalitni ma'lumotlar ma'lumotlarini (ixtiyoriy murakkablikdagi) tahlil qilish asosida kalit kalitni hisoblaydigan T -> K funktsiyasining qiymati deb hisoblash mumkin.
- Massiv (ro‘yxat)dagi qidiruv algoritmi berilgan kalitga ega bo‘lgan massiv elementi indeksini (ro‘yxat elementining manzili) topadi.
Chiziqli ketma-ket qidiruv - Ketma-ket yacheyka ko'rinishi
- Agar kerakli kalit topilsa yoki boshqa yacheykalar bo'lmasa, to'xtating
- Eng yomon holatda taqqoslashlar soni O (hujayralar soni)
- Qo'llash shartlari
- Yoki kalitlar to'plamida chiziqli tartib yo'q
- Yoki qidiruv vaqti dasturchi nuqtai nazaridan ahamiyatli emas (hujayralar soni aniq kichik, 1 marta qidirish va hk).
- Ko'p sonli kataklarda bir nechta qidiruv - massivni saralash + ikkilik qidiruv yoki DDP
Ro`yxatda chiziqli qidiruv place_t linear_search (list_t L, K key) { place_t p; for (p = begin(L); p != end(); p = next(p)) if (get_value(p).key == key) return p; return end(); // Element topilmadi! } Tartiblangan massivda ikkilik qidiruv - Har bir qadamda biz massivni yarmiga bo'lamiz va keyingi bosqichda kerakli elementni o'z ichiga olishi kerak bo'lgan yarmida qidirishni davom ettiramiz.
- Tartiblangan massivlar uchun amal qiladi
- Taqqoslashning eng yomon holatlari soni O(log2(massiv hajmi))
- Kalitlar to'plamida chiziqli tartibni talab qiladi
- Katta massivlar uchun amal qiladi
Do'stlaringiz bilan baham: |
