15-ma’ruza. Qidiruv usul va algoritmlarini tadqiq qilish Reja

1. Ketma-ket qidiruv 
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 raqamini 
saqlaydi).

---

C++ tilida dastur quyidagicha bo’ladi: 
#include  
#include  
int search(int a[], int N, int key) 
{ 
int i=0; 
while (i!=N) 
if (a[i]==key) return i; 
else i++; 
return -1; 
} 
main () 
{ 
int i, N, mas[1000], key, P; 
cout<<”Masiv uzunligini kiriting!”<cin>>N; 
cout<<”Massiv elementlarini kiriting!”<for (i=0; icin>>mas[i]; 
cout<<”Qidiruv elementini kiriting!”<cin>>key; 
P=search(mas,N,key); 
if (P==-1) cout<<”Bunday element massivda yoq”;
else cout<<”Bunday element bor”<
getch(); 
return 0; 
} 
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 hil extimollik bilan taqsimlangan bo’lsa, u 
holda M
sr

(n + 1)/2 bo’ladi.
Agar kerakli element jadvalda bo’lmasa va mazkur elementni jadvalga 
qo’shish lozim bo’lsa, u holda yuqoridagi dasturdagi oxirgi ikkita operator 
quyidagiga almashtiriladi. 
Paskalda 
n:=n+1; 

---

k[n]:=key; 
r[n]:=rec; 
search:=n; 
exit; 
Agar ma’lumotlar jadvali bir bog’lamli ro’yxat ko’rinishida berilgan bo’lsa, 
u holda ketma-ket qidiruv ro’yxatda amalga oshiriladi. 
Algoritmlar varianti: 
#include  
#include  
#include  
#include  
struct TNode { 
int value; 
TNode* pnext; 
TNode(int val): pnext(0), value(val) {} 
}; 
//Ro'yhatga element qo'shish 
void add2list(TNode **pphead, int val) { 
TNode **pp = pphead, *pnew; 
//while(*pp) { 
//if(val < (*pp)->value) 
// break; 
//else 
// pp = &((*pp)->pnext); 
//} 
pnew = new TNode(val); 
pnew->pnext = *pp; 
*pp = pnew; 
} 
//Ro'yhat elementlarini ekranga chiqarish 
void print(TNode *phead) { 
TNode* p = phead; 
while(p) { 
cout <<""<< p->value<<"|" <<" "<<"|"<
"; 
p = p->pnext; 
} 
cout << endl; 
} 
// Ro'yhatda element qidirish, C++ 
TNode* Find(TNode *phead, int x) 

---

{ 
TNode *p=phead; 
while(p) 
if (p->value==x) return p; 
else p = p->pnext; 
return 0; 
} 
//Ro'hat elementini o'chirish 
void deleteList(TNode *phead) { 
if(phead) { 
deleteList(phead->pnext); 
if(phead) 
delete phead; 
} 
} 
//Asosiy qism 
int main() {int mas[1000], N, key; TNode* T; 
clrscr(); 
TNode *phead = 0; 
//srand(time(0)); 
cout<<"Royhat uzunligini kirit"<cin>>N; 
cout<<"Elementlarni kirit!"<for(int j=0; jcin>>mas[j]; 
for(int i = 0; i < N; ++i) 
add2list(&phead,mas[i]); 
cout<<"Qidiruv elementni kiriting!"<cin>>key; 
// rand() % 100); 
cout << "Elements of the list:" << endl; 
print(phead); 
T=Find(phead,key); 
if (T==0) cout <<"Bunday element yoq"<else cout <<"Bunday element bor"<<" "<value<<" "<//deleteList(phead); 
getch(); 
} 
Ro’yxatli tuzilmaning afzalligi shundan iboratki, ro’yxatga 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 
taxminan barcha elementlarni yarimini siljitishni talab qiladi. Ro’yxatda qidiruvni 
samaradorligi taxminan massivniki bilan bir hil bo’ladi. 
Umuman olganda ketma-ket qidiruv samaradorligini oshirish mumkin. 
Faraz qilaylik, kun davomida ma’lumotlar yig’ilib, kechqurun ular qayta 

---

ishlansin. Ma’lumotlar to’plangandan keyin ular saralanadi.