- REJA
- 1.Qidiruv tushunchasi va uning vazifasi
- 2.Chiziqli qidiruv (kerma –ket )
- 3. Indeksli ketma ket qidiruv
- 4. Binar (oraliqni teng ikkiga bo‘lish orqali) qidiruv
- 5. Qidirish usullari samaradorligi
Qidiruv tushunchasi va uning vazifasi - Ma’lumotlarni qayta ishlashda qidiruv asosiy amallardan biri bo‘lib, uning vazifasi berilgan argument (kalit) bo‘yicha ma’lumotlar bazasi ichidan mazkur argumentga mos ma’lumotlarni topish yoki yo‘qligini aniqlashdan iborat.
- Agar kerakli ma’lumot yo‘q bo‘lsa, u holda ikkita ishni amalga oshirish mumkin:
- ma’lumot yo‘qligini belgilash;
- jadvalga ma’lumotni qo‘yish.
- Ixtiyoriy ma’lumotlar majmuasi jadval yoki fayl deb ataladi. Ixtiyoriy ma’lumot (yoki tuzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi.
- Kalit ikki xil bo‘lishi mumkin:
- birlamchi(takrorlanmaydi, noyob);
- ikkilamchi(takrorlanadi).
Qidiruv tushunchasi va uning vazifasi - Ta’rif. Agar kalitlar ma’lumotlar jadvalidan ajratib olinib alohida fayl sifatida saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Aks holda, ya’ni yozuvning bir maydoni sifatida jadvalda saqlansa, ichki kalit deyiladi.
- Qidiruvning maqsadi - quyidagi jarayonlarning birini bajarilishidan iborat:
- topilgan yozuvni o‘qish;
- qidirilayotgan yozuv topilmasa, uni jadvalga qo‘yish;
- topilgan yozuvni o‘chirish.
- Faraz qilaylik, k – kalitlar massivi bo‘lsin.
- Har bir k(i) uchun r(i) – ma’lumot mavjud.
- Key – qidiruv argumenti, unga rec yozuvi to’g’ri keladi.
- Jadvaldagi ma’lumotlarning tuzilmasiga qarab qidiruvni bir necha turlari mavjud.
- Chiziqli yoki ketma-ket qidiruv (massivda)
- Ma’lumotlar butun jadval bo‘yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha ketma-ket qarab chiqiladi.
- Chiziqli algoritmdan agar ma’lumotlar jadvali tartibsiz yoki ular tuzilishi noaniq bo‘lsa foydalanish tavsiya etiladi.
- Psevdokod:
- For i:=1 to n
- If k(i)=key then
- Search= i
- return
- EndIf
- Next i
- Search= 0
- return
- Search o’zgaruvchi topilgan elementning nomerini saqlaydi.
- Agar ma’lumotlar jadvali massiv ko‘rinishda bo‘lsa, u holda, asosan, algoritm natijasi sifatida topilgan element o‘rni qaytariladi.
- Indeksli ketma ket qidiruv
- Bu ko’rinishdagi qidiruvda 2ta jadval tashkil qilinadi :
- 1. O’z kalitiga ega ma”lumotlar jadvali( osish tartibida);
- 2. Indekslar jadvali – bu jadval ham kalitlardan tashkil topgan, lekin bu kalitlar asosiy jadvaldan tanlab aniq interval (m<=n) bilan olinadi.
- Dastlab qidiruv argumenti bo’yicha indekslar jadvalida ketma ket qidiruv o’tkaziladi. Tanlangan kalitdan katta kalit topilganda, biz asosiy jadvalda qidiruvning quyi – low-, va yuqori –hi- (kind > key) chegaralarini belgilab qo’yamiz.
- Masalan, key=101
- Qidiruv jarayoni butun jadval bo’yicha emas, balki low dan hi gacha o’tkaziladi.
- Indeksli ketma-ket qidiruv
- Indeksli ketma-ket algoritmdan, agar ma’lumotlar jadvali tartiblangan bo‘lsa, foydalanish mumkin bo‘ladi.
Do'stlaringiz bilan baham: |