Mavzu: Qidiruv algoritmlari: chiziqli va binar qidiruv Reja: Kirish 2

2.2.  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<="" p="">

  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’

(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 (2.1-

rasm), u holda ketma-ket qidiruv ro’yhatda amalga oshiriladi.

Birbog’lamli ro’yhatning ko’rinishi Chiziqli  bir  bog’lamli  ro’yhatdan  key  kalitga  mos  elementni  ketma-ket qidiruv usuli yordamida izlab topish dasturi.

Node *q=NULL;  

Node *p=lst;  

while (p !=NULL){   

      if (p->k == key){  

          search = p;  

          return search;  

          }  

  q = p;  

  p = p->nxt;  

}  

Node *s=new Node;;  

s->k=key;  

s->r=rec;  

s->nxt= NULL;  

if (q == NULL){ s->nxt=lst; lst = s; }  

               else q->nxt = s;  

search= s;  

return search;  

Ro’yhatli  tuzilmaning  afzalligi  shundan  iboratki,  ro’yhatga  elementni qo’shish 

yoki o’chirish tez amalga oshadi, bunda qo’shish yoki o’chirish element soniga  

bog’liq  bo’lmaydi,  massivda  esa  elementni  qo’shish  yoki  o’chirish  o’rta 

hisobda  barcha  elementlarning  yarmini  siljitishni  talab  qiladi.  Ro’yhatda 

qidiruvning samaradorligi taxminan massivniki bilan bir xil bo’ladi.