O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

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. M_min = 1, M_max = n. Agar ma’lumotlar massiv yacheykasida bir xil ehtimollik bilan taqsimlangan bo’lsa, u holda M_o‘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