“Маълумотлар тузилмаси ва алгоритмлар” фанига кириш

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.