Ma`lumotlar tuzilmasi va algoritmlash fanidan Mavzu: Eng oddiy qatorlarni qayta ishlash algoritmlari

Ketma-ket qidiruv algoritm 

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 u holda 

ketma-ket qidiruv ro`yhatda amalga oshiriladi.

 

 

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.