Reja qidiruv tushunchasi va uning vazifasi Chiziqli qidiruv (kerma –ket ) Indeksli ketma ket qidiruv

• 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

• 3-Mavzu: Ma’lumotlarni qidirish usullari, algoritmlar va ularning 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)

• Algoritm g‘oyasi

• Ma’lumotlar butun jadval bo‘yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha ketma-ket qarab chiqiladi.

• Eslatma

• 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.

• Izoh

• Agar ma’lumotlar jadvali massiv ko‘rinishda bo‘lsa, u holda, asosan, algoritm natijasi sifatida topilgan element o‘rni qaytariladi.

• Chiziqli qidiruvni amalga oshirish protsedurasi

• 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

• Eslatma

• Indeksli ketma-ket algoritmdan, agar ma’lumotlar jadvali tartiblangan bo‘lsa, foydalanish mumkin bo‘ladi.