O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

9- amaliy mashg’ulot
Qidiruv usullarini tadqiq qilish va unga doir misollar
Ixtiѐriy ma’lumotlar majmuasi jadval ѐki fayl deb ataladi. Ixtiѐriy ma’lumot (ѐki tuzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noѐb bo’lishi, ya’ni mazkur kalitga ega ma’lumot jadvalda yagona bo’lishi mumkin. Bunday noѐb kalitga boshlang’ich (birinchi) kalit deyiladi. Ikkinchi kalit bir jadvalda takrorlansada u orqali xam qidiruvni amalga oshirish mumkin.

Ma’lumotlar kalitini bir joyga yig’ish (boshqa jadvalga) ѐki ѐzuv sifatida ifodalab bitta maydonga kalitlarni ѐzish mumkin. Agar kalitlar ma’lumotlar jadvalidan ajratib olinib alohida fayl sifatida saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Aks holda, ya’ni ѐzuvning bir maydoni sifatida jadvalda saqlansa ichki kalit deyiladi.

Kalitni berilgan argument bilan mosligini aniqlovchi algoritmga berilgan argument bo’yicha qidiruv deb ataladi. Qidiruv algoritmi vazifasi kerakli ma’lumotni jadvalda topish ѐki yo’qligi aniqlashdan iboratdir

. Agar kerakli ma’lumot yo’q bo’lsa, u holda ikkita ishni amalga oshirish mumkin:

1. ma’lumot yo’qligini indikasiya (belgilash) qilish

2. jadvalga ma’lumotni qo’yish.

Faraz qilaylik, k – kalitlar massivi. Har bir k(i) uchun r(i) – ma’lumot mavjud. Key – qidiruv argumenti. Unga rec - informasion ѐzuv mos qo’yiladi. Jadvaldagi ma’lumotlarning tuzilmasiga qarab qidiruvni bir necha turlari mavjud.

1. Ketma-ket qidiruv

Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz ѐki ular tuzilishi noaniq bo’lganda qo’llaniladi. Bunda ma’lumotlar butun jadval bo’yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha ketma- ket qarab chiqiladi. Massivda ketma-ket qidiruv (search o’zgaruvchi topilgan element raqamini saqlaydi).

2. Indeksli ketma-ket qidiruv

Mazkur ko’rinishdagi qidiruv amalga oshirilaѐtganda ikkita jadval tashkil qilinadi: o’z kalitiga ega ma’lumotlar jadvali (o’sish tartibida tartiblangan) va indekslar jadvali, bu xam ma’lumotlar kalitidan iborat- u, lekin bu kalitlar asosiy jadvaldan aniq bir interval orqali olingan. (2-chizma). Boshida berilgan argument bo’yicha ketma-ket qidiruv indekslar jadvalida amalga oshiriladi. Qachonki, biz berilgan kalitdan kichik kalitni aniqlaganimizda, asosiy jadvalda qidiruvni quyi chegarasini o’rnatamiz - low, keyin esa yuqori chegarani - hi, ya’ni ( kind > key ). Masalan, key = 101. Qidiruv to’la jadval bo’yicha emas, balki low dan hi gacha davom etadi.

3. Ketma-ket qidiruvni samaradorligi

Ixtiѐriy qidiruvning samaradorligi jadvaldagi ma’lumotlarning kalitlari bilan solishtirish soni – S bilan baxolanishi mumkin. Agar taqqoslashlar (solishtirish) soni qancha kichik bo’lsa, qidiruv algoritmi samaradorligi shuncha yaxshi bo’ladi. Massivda ketma-ket qidiruvning samaradorligi quyidagicha bo’ladi: C = 1 n, C = (n + 1)/2. Umuman olganda ro’yxatda xam samaradorlik yuqoridagi kabi bo’ladi. Garchi massivda xam bog’langan ro’yxatda xam qidiruv samaradorligi bir xil bo’lsada, ma’lumotlarni massiv va ro’yxat ko’rinishda tasvirlashning o’ziga xos kamchilik va afzalliklari mavjud.

Qidiruvning maqsadi - quyidagi jaraѐnlarni bajarilishidan iborat:

1) Topilgan ѐzuvni o’qish.

2) Qidirilaѐtgan ѐzuv topilmasa, uni jadvalga qo’yish.

3) Topilgan ѐzuvni o’chirish.

Birinchi jaraѐn (qidiruvning o’zi) massiv uchun ham ro’yxat uchun ham bir xil bo’ladi. Ikkinchi va uchinchi jaraѐnda esa qidiruv ro’yxatli tuzilmada samaraliqroq bo’ladi (sababi massivda elementlarn siljitish lozim). Agar k massivda elementlarni siljitishlar soni bo’lsa, u xolda k = (n + 1)/2 bo’ladi.

4. Indeksli ketma-ket qidiruvni samaradorligi

Agar bo’lishi mumkin barcha xolatlar teng extimolli deb olinsa, u holda qidiruv samaradorligini quyidagicha xisoblash mumkin: Belgilashlar kiritib olamiz: m – indeks o’lchovi; m = n / p; p – qadam o’lchovi Q = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1 (*) Q ni p bo’yicha differensiallab uni nolga tenglashtiramiz: dQ/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p 2 + 1/2 = 0

Bu yerdan p 2 =n ; n p opt
Transpozisiya usuli

Ushbu usulda topilgan element ro’xatda bitta oldingi element bilan o’rin almashtiriladi. Agarda mazkur elementga ko’p murojaat qilinsa, bittadan oldinga surilib borib natijada ro’yxat boshida bo’ladi.

Chizma. Qo’shni elementlarni o’rnini almashtirish r – ishchi ko’rsatkich q – ѐrdamchi ko’rsatkich, r dan bitta qadam orqada bo’ladi s - ѐrdamchi ko’rsatkich, q dan ikkita qadam orqada bo’ladi.