Axborot texnologiyalari va kommunikatsiyalarini rivojlantirish


Download 15.79 Kb.
Sana02.01.2022
Hajmi15.79 Kb.
#188472
Bog'liq
Ma'lumotlar strukturasi va algoritmlar


 AXBOROT TEXNOLOGIYALARI VA 

KOMMUNIKATSIYALARINI RIVOJLANTIRISH 

VAZIRLIGI

TOSHKENT AXBOROT TEXNOLOGIYALARI

UNIVERSITETI SAMARQAND FILIALI 

 

 



“Kompyuter injiniring” fakulteti 

“Ma'lumotlar strukturasi va algoritmlar” fanidan 


MUSTAQIL ISH

 

 



 

  Bajardi:  Hamdamov Javohir

 

SAMARQAND-2021
Ketma-ket qidiruv usulidan foydalanib, ro’yxatda berilgan kalitdan katta elementlarni topish.
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. 

 

 



2.1-rasm. Bir bog’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. 
Download 15.79 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling