Muhammad Al-Xorazmiy nomidagi
Toshkent Axborot texnalogiyalari universiteti
Kompyuter injineringi fakulteti 211-20 guruh
Talabasi Ibragimov Muhammadalining
Malumotlar tuzimasi fanidan
2-topshirig’i
Mavzu: QIDIRUV USULLARINI TADQIQ QILISH
Ketma-ket qidiruv algoritmi
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 tartib raqamini saqlaydi).
Ketma-ket qidiruv algoritmi C++ tilida quyidagicha bo’ladi:
int qidiruv(int key){
for (int i=0;i
if (k[i]==key) { search = i;return search;}
search = -1;
return search;}}
Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin. Mmin = 1, Mmax = n. Agar ma’lumotlar massiv yacheykasida bir xil ehtimollik bilan taqsimlangan bo’lsa, u holda Mo‘rt (n + 1)/2 bo’ladi.
Agar kerakli element jadvalda yo’q bo’lib, uni jadvalga qo’shish lozim bo’lsa, u holda yuqorida keltirilgan algoritmdagi oxirgi ikkita operator quyidagicha almashtiriladi.
n=n+1;
k[n-1]:=key;
r[n-1]:=rec;
search:=n-1;
return search;
Agar ma’lumotlar jadvali bir bog’lamli ro’yhat ko’rinishida berilgan bo’lsa (5.1-rasm), u holda ketma-ket qidiruv ro’yhatda amalga oshiriladi.
5.1-rasm. Bir bog’lamli ro’yhatning ko’rinishi
Dostları ilə paylaş: |