Kompyuter injinering

Topshiriq 

---

 
AMALIY MASHG’ULOT- 2 
Mavzu: Qidiruv algoritmlari: chiziqli va binary qidiruv. Xesh 
funksiyalar va xesh algoritmlarini tuzish. 
 
Ishdan maqsad: Ushbu laboratoriya ishining maqsadi talabalar qanday 
qidirish usullari va algoritmlari mavjudligini va ularning samaradorliklarini 
baholashni o’rganishlari kerak. Shu asosda qidirish usullarini qiyosiy tahlil 
qilishlari, C++ dasturlash tilida qidirish bilan islashni va ularga oid dasturlar 
tuzishni o’zlashtirishlari kerak. 
Qo’yilgan masala: Talabalar topshiriq variantiga mos qidirish usuli yordamida 
masalani yechish dasturini yaratish ko’nikmasiga ega bo’lishlari kerak. 
Ish tartibi: 
1.Tajriba ishi nazariy ma’lumotlarini o’rganish; 
2.Berilgan topshiriqning algoritmini ishlab chiqish; 
3. C++ dasturlash muhitida dasturni yaratish; 
4. Natijalarni tekshirish; 
5.Hisobotni tayyorlash va topshirish. 
Aytaylik bizga massiv berilgan: 
a[]={15, 23, 7, 45, 87, 16}; 
Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan 
dastur tuzish sharti qo'yilgan. Ushbu masalani yechishda eng birinchi xayolga 

---

keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu 
usul: 
Chiziqli qidiruv - Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda: 
#include  
usingnamespace std; 
int linearSearch(int array[], int size, int searchValue) 
{ 
for(int i =0; i < size; i++) 
{ 
if(searchValue == array[i]) 
{ 
return i; 
} 
} 
return-1; 
} 
int main() 
{ 
int a[]={15, 23, 7, 45, 87, 16}; 
int userValue; 
cout<<"Enter an integer: "<< endl; 
cin>> userValue; 
int result = linearSearch(a, 6, userValue); 
if(result >=0) 
{ 
cout<<"The number "<< a[result]<<" was found at the" 
" element with index "<< result << endl; 
} 
else 
{ 
cout<<"The number "<< userValue <<" was not found. "<< endl; 
} 
} 

---

Ko'rib turganingizdek, funksiyamiz 2 ta parametr qabul qiladi, birinchisi 
massivni o'zi, ikkinchisi esa biz qidirayotgan element. Agar uni topa olmasak, "-1" 
qiymatni qaytaramiz. 
Endi bundan optimal bo'lgan usul - binar(ikkilik) qidiruvni ko'rib chiqsak. 
Bu usulda ham funksiyaga 2 ta parametr, birinchisi massiv o'zi keyin esa biz 
qidirayotgan elementni parametr sifatida beriladi. Qidiruv esa quyidagicha: Dastlab 
biz massiv boshi va oxirini o'zimiz uchun o'zgaruvchilarda belgilab olamiz, mening 
kodimda bu left va right o'zgaruvchilaridir: 
left := 0 right := len(a) 
so'ngra quyidagi shart bajarilgan holda 
left< right 
quyidagi ketma-ket operatsiyalarni amalga oshiramiz 
1. 
left va right index lari markazidagi elementni topamiz (left + right) / 2 
2. 
topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid 
elementni javob sifatida qaytaramiz 
3. 
agar a[mid] elementimiz biz qidirayotgan elementdan kichkina bo'lsa biz left = 
mid deb belgilaymiz va shunda a[mid:right] bo'lagida qidiruv davom etadi. 
4. 
agar a[mid] elementimiz biz qidirayotgan elementdan katta bo'lsa demak right 
= mid deb belgilaymiz shunda qidiruv a[left:mid] bo'lagida qidiruv davom 
etadi. 
Shu zaylda qidiruv left < right shart bajarilmagunicha davom etadi, agar bu 
jarayonda biz qidirgan element topilmasa u xolda -1 javob qaytariladi, quyida dastur 
kodi keltirilgan: 
#include  
Using namespace std; 
int binarySearch(int array[], int size, int searchValue) 
{ 
int low =0; 
int high = size -1; 
int mid; 
while(low <= high) 
{ 
mid =(low + high)/2; 
if(searchValue == array[mid]) 
{ 

---

return mid; 
} 
elseif(searchValue > array[mid]) 
{ 
low = mid +1; 
} 
else 
{ 
high = mid -1; 
} 
} 
return-1; 
} 
int main() 
{ 
int a[]={12, 22, 34, 47, 55, 67, 82, 98}; 
int userValue; 
cout<<"Enter an integer: "<< endl; 
cin>> userValue; 
int result = binarySearch(a, 8, userValue); 
if(result >=0) 
{ 
cout<<"The number "<< a[result]<<" was found at the" 
" element with index "<< result << endl; 
} 
else 
{ 
cout<<"The number "<< userValue <<" was not found. "<< endl; 
} 
} 
Bu usul binar qidiruvni iterativ usuli deyiladi, shuningdek bu algoritmni 
rekursiya usulida ham yozish mumkin, rekursiv usulni erinmasangiz o'zingiz yozib 
ko'ring. Bitta urinishda ko'pchilik dasturchilar bu narsani to'g'ri yoza olishmaydi va 
bu normal holat, chunki xato bor joyda o'z ustida ishlash uchun imkoniyat bo'ladi. 
Endi bu qidiruv usullarini ayrim jihatlarini keltirib o'tamiz: 

---

1. 
funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish tartibida 
bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay 
tartibda bo'lishini ahamiyati yo'q 
2. 
chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa 
algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali 
bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki 
ko'pi bilan O(log n) 
"Xesh" so'zi ingliz tilidagi «hash» so’zidan olingan bo’lib, uning ma'nosi 
“shovqin” yoki “aralash” kabi ta'riflanadi. Aslida, bular atamaning haqiqiy 
ma'nosini to'liq ifodalaydi. 
1. Xesh jadvalni tashkil etish: asosiy tushunchalar 
• Xeshlash – bu ma'lum bir turdagi va ixtiyoriy uzunlikdagi kirish ma'lumotlari 
massivini fiksirlangan uzunlikdagi chiquvchi bitlar qatoriga (butun son) aylantirish. 
Bunday akslantirish (aylantirish) xesh-funksiya deb ham ataladi. Xesh-funksiya – bu 
kirish ma’lumotlarini sonlarga aylantiruvchi funksiya bo’lib, bir xil ma’lumotlar 
to’plami hamma vaqt bir xil natija beradi. 
•Xesh-jadval – bu elementlari “kalit-qiymat” juftliklari bo'lgan assotsiativ massiv 
shaklidagi ma'lumotlar tuzilmasi. 
• Xeshlash assotsiativ massivlarni tashkil qilish uchun qo’llaniladi, bunda indekslari 
sonlar emas, balki ixtiyoriy qiymatlar bo’ladi. Xeshlashdan odatda matnlardan 
nusxalarning takrorlanishini qidirishda, ya'ni xesh-funksiyalarining bir xil qiymatiga 
ega bo'laklarni qidirishda foydalaniladi. Bundan tashqari, xeshlash ko'pincha 
parollarni saqlash uchun ishlatiladi; shu bilan birgalikda noyob identifikatorlarni 
yaratish uchun, masalan, agar fayl o'ziga xos nomni talab qilsa, siz ushbu faylni 
xeshlash natijasini hisoblab chiqishingiz va natijani faylga nom sifatida 
ishlatishingiz mumkin. Shuningdek, bu matnlarning nazorat summasini hisoblash 
uchun juda muhimdir. Aytaylik, foydalanuvchi tarmoq orqali bir nechta matn 
yuborishi kerak. Tekshirish summasi matn bilan birga uzatiladi, olinganidan keyin 
asl nusxasi bilan tekshiriladi. Agar summasi mos kelmasa, demak matnni uzatishda 
qandaydir xatolik bo’lganligi haqida xulosa qilish mumkin bo’ladi. 

---