Mavzu: Qidiruv algoritmlari: chiziqli va binary qidiriruv. Hesh funksiya va heshlash algoritmlarini tuzish

Mavzu: Qidiruv algoritmlari: chiziqli va binary qidiriruv. Hesh funksiya va heshlash algoritmlarini tuzish

2-Amaliy mashg’ulot.

Mavzu: Qidiruv algoritmlari: chiziqli va binary qidiriruv. Hesh funksiya va heshlash algoritmlarini tuzish.
Kompyuterda ma’lumotlarni qayta ishlashda qidiruv asosiy amallardan biri hisoblanadi. Uning vazifasi berilgan argument bo’yicha massiv ma’lumotlari ichidan mazkur argumentga mos ma’lumotlarni topish yoki bunday ma’lumot yo’qligini aniqlashdan iboratIxtiyoriy ma’lumotlar majmuasi jadval yoki fayl deb ataladi. Ixtiyoriy ma’lumot (yokituzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noyob bo’lishi, ya’ni mazkur kalitga ega ma’lumot jadvalda yagonabo’lishi mumkin.
Qidiruv algoritmlarining binary va chiziqli qidiruv usullarini ko’rib chiqamiz:
Aytaylik bizga massiv berilgan:
a[]={5,8,1,2,13,7,9,10,11,6};
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

using namespace std;
int chiziqli_qidiruv(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, 5, 9, 159, 98, 77};
int qid_son;
cout<<"Qidirilayotgan sonni kiriting: "<<" ";
cin>>qid_son;
int natija = chiziqli_qidiruv(a, sizeof(a), qid_son);
if(natija >=0)
{ cout<<"Qidirilayotgan son "<< a[natija]<<" "<< natija <<"- indexda joylashgan"<< endl;
}
else
{ cout<<"Qidirilayotgan son "<< qid_son <<" ushbu massivda mavjud emas. "<< endl;
}}
#include

using namespace std;
int chiziqli_qidiruv(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, 5, 9, 159, 98, 77};
int qid_son;
cout<<"Qidirilayotgan sonni kiriting: "<<" ";
cin>>qid_son;
int natija = chiziqli_qidiruv(a, sizeof(a), qid_son);
if(natija >=0)
{ cout<<"Qidirilayotgan son "<< a[natija]<<" "<< natija <<"- indexda joylashgan"<< endl;
}
else
{ cout<<"Qidirilayotgan son "<< qid_son <<" ushbu massivda mavjud emas. "<< endl;
}}
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 va right index lari markazidagi elementni topamiz (left + right) / 2
  
• 
  topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
  
• 
  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.
  
• 
  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:
  

int main()
{int a[]={12, 22, 34, 47, 55, 67, 82, 98};
int qid_son;
cout<<"Qidirilayotgan sonni kiriting: ";
cin>> qid_son;
int natija = binarqidiruv(a, sizeof(a), qid_son);
if(natija >=0)
{ cout<<"Qidirilayotgan son "<< a[natija]<<" berilgan massivada "<< natija <<"-indeksda joylashgan."<< endl; }
else
{ cout<<"Qidirilayotgan son "<< qid_son <<" berilgan massivda mavjud emas."<< endl; }}
#include
using namespace std;
int binarqidiruv(int a[], int size, int qid_son)
{
int low =0;
int high = size -1;
int mid;
while(low <= high)
{
mid =(low + high)/2;
if(qid_son == a[mid])
{ return mid; }
else if(qid_son > a[mid])
{ low = mid +1; }
else
{ high = mid -1; } }
return-1;}
"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.
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 funksiyalar – ixtiyoriy uzunlikdagi kirish ma’lumotini chiqishda belgilangan uzunlikdagi xesh qiymatga aylantirib beruvchi bir tomonlama funksiyalarga aytiladi. Xesh funksiyalar kriptografiya va zamonaviy axborot xavfsizligi sohasida ma’lumotlarni to’laligini tekshirishda foydalaniladi.
Hesh-funksiya
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.