|
Toshkent axborot texnologiyalari universiteti samarqand filiali mustaqil ish
|
| bet | 1/8 | | Sana | 25.04.2022 | | Hajmi | 69 Kb. | | #20278 |
Bog'liq ISHLAB CHIQARISH
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI
MUSTAQIL ISH
FANNING NOMI:”Ma’lumotlar tuzilmasi va algoritmi”
Bajardi : Nazarov Kamoliddin
REJA:
Ketma-ket qidiruv usullari orqali ro’yxatdagi eng kata elementtni toppish dasturini tuzing va samaradorligini tahlil qiling?
Hashlashda ideal hesh funksiyasi haqida ma’lumot bering va misollar keltiring, o’zingizni F.I.SH ni hesh qiymatini qaytaruvchi dastur tuzing?
Chiziqli (Ketma-ket) qidiruv
Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz yoki 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).
Psevdokodi :
For i:=1 to n
If k(i)=key then
Search= i
return
EndIf
Next i
Search= 0
return
Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin. Mmin = 1, Mmax = n. Agar ma’lumotlar massiv yacheykasida bir hil extimollik bilan taqsimlangan bo’lsa, u holda Msr » (n + 1)/2 bo’ladi.
Agar kerakli element jadvalda bo’lmasa va mazkur elementni jadvalga qo’shish lozim bo’lsa, u holda yuqoridagi dasturdagi oxirgi ikkita operator quyidagiga almashtiriladi:
Paskalda
n:=n+1;
k[n]:=key;
r[n]:=rec;
search:=n;
exit;
Umuman olganda ketma-ket qidiruv samaradorligini oshirish mumkin.
2. Indeksli ketma-ket qidiruv
Mazkur ko’rinishdagi qidiruv amalga oshirilayotganda 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.
|
| |
