|
Binar qidiruv usulidan foydalanib massiv elementlari orasida
belgilangan elementni qidirish dasturi quyida keltirilgan:
1-usul.
#include
#include
int Binsearch(int a[], int N, int key, int *t)
{
int l=0, r=N-1, mid=(l+r)/2;
while (l<=r)
{ *t+=1;
if (a[mid]==key) return mid;
TOSHKENT if (a[mid]>key) r=mid-1;
else l=mid+1;
mid=(l+r)/2;
}
a[N]=key;
return N;
} main ()
{
int i, N, mas[1000], key, P, t=0;
cout<
cin>>N;
cout<<"Massiv elementlarini kiriting!"<
for (i=0; i
cin>>mas[i];
cout<<"Qidiruv elementini kiriting!"<
cin>>key;
P=Binsearch(mas,N,key, &t);
if (P==N) cout<<"Bunday elementni massivga qo'shis
lozim"<<"
"<
bor"<<"
"<
getch();
return 0;
}
#include
#include
int InSeqsearch(int realArray[], int N, int
kind[2][1000],int m,int key, int *t)
{
int i=0,
low = 0,
hi = 0;
while ((i
{
i++;
(*t)++;
}
(*t)++;
if (i==0)
low=0;
else
low=kind[1][i-1];
if (i==m)
hi=N;
else
TOSHKENT
hi=kind[1][i]-1;
for (int j=low; j<=hi; j++)
{
(*t)++;
if( key==realArray[j] )
{
return j;
} }
return -1;
}
main ()
{
int i = 0 ,
N = 0,
mas[1000] = {0},
kind[2][1000] = {0},
key = 0,
P = 0,
index = 0,
kindIndex = 0,
t = 0;
cout<
cin>>N;
cout<<"Massiv elementlarini kiriting!"<
for (i=0; i
cin>>mas[i];
cout<<"Qidiruv elementini kiriting!"<
cin>>key;
cout<<"Boshlangich qadamni kiriting! "<
cin>>P;
i = P-1;
while(i
{
kind[0][kindIndex] = mas[i];
kind[1][kindIndex++] = i;
i += P;
}
index = InSeqsearch(mas,N,kind,kindIndex,key, &t);
if (index == -1)
cout<<"Bunday element massivda yuq "<< index <<"
"<
else
cout<<"Bunday element bor"<<" "<
"<
getch();
return 0;
}
TOSHKENT
3-usul.
#include
#include
#include
#include
struct TNode {
int value;
TNode* pnext;
};
//Ro'yhatga element qo'shish
void add2list(TNode **pphead, int val) {
TNode **pp = pphead, *pnew;
pnew = new TNode;
pnew->value=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'yhat 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();
TOSHKENT AXBOROT
TNode *phead = 0;
cout<<"Ro‟yhat uzunligini kirit"<
cin>>N;
cout<<"Elementlarni kirit!"<
for(int j=0; j
cin>>mas[j];
for(int i = 0; i < N; ++i)
add2list(&phead,mas[i]);
cout<<"Qidiruv elementni kiriting!"<
cin>>key;
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();
return 0;
}
4-usul.
#include
#include
int search(int a[], int N, int key, int *t)
{
int i=0;
while (i!=N)
{*t+=1;
if (a[i]==key) return i;
else i++;
}
//a[N]=key;
return -1;
}
main ()
{
int i, N, mas[1000], key, P, t=0;
cout<
cin>>N;
cout<<"Massiv elementlarini kiriting!"<
for (i=0; i
cin>>mas[i];
cout<<"Qidiruv elementini kiriting!"<
cin>>key;
P=search(mas,N,key,&t);
if (P==-1) cout<<"Bunday elementni massivga qo'shis
lozim"<<"
TOSHKENT AXBOROT "<
else cout<<"Bunday element bor"<<" "<
"<
getch();
return 0;
}
Xash jadvali
Xash jadvali - bu ba'zi funktsiyalar (xash funktsiyasi) tomonidan ko'rsatilgan maxsus manzilga ega oddiy qator.
Hash funktsiyasi
Element kalitini jadvaldagi ba'zi indekslarga o'zgartiradigan funktsiya ( xash jadvali) deyiladi xeshlash funktsiyasi yoki xash funktsiyasi :
i = h (kalit );
qayerda kalit- konvertatsiya qilinadigan kalit; i- natijada jadvalning indeksi, ya'ni. kalit to'plamda ko'rsatiladi, masalan, butun sonlar ( xash manzillari ), keyinchalik ma'lumotlarga kirish uchun ishlatiladi.
Shu tarzda xashlash - bu maxsus jadvalda o'z o'rnini aniqlash uchun kalit qiymatidan foydalanishni o'z ichiga olgan usul.
Biroq, joylashtirish funktsiyasi mumkin bir nechta yagona kalit qiymatlari bir xil pozitsiya qiymatini beradi i xash jadvalida. Ikki yoki undan ortiq kalit bir xil indeksni (xash manzilini) oladigan holat deyiladi to'qnashuv (qarama -qarshilik) xeshlashda .. Shuning uchun xesh sxemasi o'z ichiga olishi kerak nizolarni hal qilish algoritmi pozitsiya bo'lsa, harakatlar tartibini belgilash i=h(kalit) boshqa kalit bilan allaqachon band bo'lgan rekord bo'lib chiqadi.
Ko'p xash sxemalari mavjud, ular ishlatilgan xash funktsiyasidan farq qiladi h(kalit) va nizolarni hal qilish algoritmlari.
Xash funktsiyasini o'rnatishning eng keng tarqalgan usuli: Bo'linish usuli.
Dastlabki ma'lumotlar quyidagilardir: - butun sonli kalit kalit va stol o'lchami m... Bu funktsiyaning natijasi - bu kalitni jadval kattaligiga bo'linishi. C / C ++ dasturlash tilida bunday funksiyaning umumiy ko'rinishi:
int h (int kalit , int m ) {
Uchun m= 10 xash funktsiyasi kalitning eng kichik raqamini qaytaradi.
M = 100 uchun xash funktsiyasi kalitning eng muhim ikkita raqamini qaytaradi.
Ko'rib chiqilgan misollarda, hash funktsiyasi i=h(kalit) faqat kalit bilan yozuvni qidirish (yoki dastlab - jadvalga joylashtirish) pozitsiyasini aniqlaydi kalit... Keyinchalik, siz hashing sxemasidan (algoritm) foydalanishingiz kerak.
Xash sxemalari
Ko'pgina vazifalarda, ikki yoki undan ortiq kalit bir xil tarzda ajratiladi, lekin ular xash jadvalidagi bitta katakchani egallay olmaydi. Ikki bor mumkin bo'lgan variantlar: yoki yangi kalit uchun boshqa pozitsiyani toping yoki xesh jadvalining har bir indeksi uchun alohida ro'yxat tuzing, unda ushbu indeksga mos keladigan barcha kalitlar mavjud.
Bu variantlar ikkita klassik xesh sxemasini ifodalaydi:
chiziqli tekshirish yordamida ochiq manzil usuli bilan xeshlash - chiziqli zond ochiq murojaat qilish.
zanjirlar usuli bilan xeshlash (ro'yxatlar bilan) yoki ko'p o'lchovli xash deb ataladigan - zanjirlash bilan alohida ro'yxatlar;
Chiziqli tekshirish yordamida manzilni aniqlashning ochiq usuli . Dastlab, oddiy o'lchamli massiv bo'lgan xash jadvalining barcha katakchalari band bo'lmagan deb belgilanadi. Shuning uchun, yangi kalit qo'shganda, bu hujayraning bandligi tekshiriladi. Agar hujayra band bo'lsa, algoritm bo'sh joy topilmaguncha ("ochiq manzil") dumaloq skanerlashni amalga oshiradi.
Bular. bir hil kalitlarga ega elementlar olingan indeks yaqinida joylashtiriladi.
Bundan tashqari, qidiruvni amalga oshirayotganda, joy birinchi navbatda kalit bilan topiladi i jadvalda va agar kalit mos kelmasa, keyingi qidiruv pozitsiyadan boshlab nizolarni hal qilish algoritmiga muvofiq amalga oshiriladi. i. .
Zanjirlash usuli strategiyasi ustunlik qiladi . Ushbu holatda i tanlangan xash funktsiyasidan olingan h(kalit)=i, ro'yxatlar xesh jadvalidagi indeks sifatida talqin qilinadi, ya'ni. birinchi kalit kalit Keyingi yozuv pozitsiyaga joylashtiriladi i = h(kalit) jadvallar. Agar pozitsiya bo'sh bo'lsa, unda kalitli element joylashtiriladi kalit, agar u band bo'lsa, ziddiyatlarni hal qilish algoritmi qayta ishlanadi, natijada bunday kalitlar ro'yxatda joylashtiriladi. i-xash jadvalining uchinchi katakchasi. Masalan
Natijada, bizda bog'langan ro'yxatlar yoki daraxtlar majmuasi mavjud.
Xash -jadvalni to'ldirish (o'qish) jarayoni oddiy, lekin elementlarga kirish uchun quyidagi amallar kerak:
Indeksni hisoblash i;
Tegishli zanjirda qidiring.
Yangi element qo'shganda qidiruvni yaxshilash uchun siz kiritish algoritmini ro'yxatning oxirida emas, balki buyurtma berishda ishlatishingiz mumkin, ya'ni. ga element qo'shing To'g'ri joy.
To'g'ridan -to'g'ri murojaat qilish usulini chiziqli tekshirish yordamida amalga oshirishga misol ... Dastlabki ma'lumotlar e'lon qilingan tuzilish turidagi 7 ta yozuv (soddaligi uchun, ma'lumot qismi faqat butun ma'lumotlardan iborat):
int kaliti; // kalit
int ma'lumotlari; // Ma `lumot
(59.1), (70.3), (96.5), (81.7), (13.8), (41.2), (79.9); xash jadval o'lchami m = 10.
Hash funktsiyasi i=h(ma'lumotlar) =ma'lumotlar.kalit%o'n; o'sha. 10 ga bo'lingandan keyin qolgan qismi i.
Dastlabki ma'lumotlarga asoslanib, biz jadvalni ketma -ket to'ldiramiz.
Birinchi beshta kalitni aralashtirish turli indekslarni beradi (xash manzillari):
Birinchi to'qnashuv 81 va 41 tugmachalari o'rtasida sodir bo'ladi - 1 -indeksli joy olinadi. Shuning uchun, biz eng yaqin bo'sh joyni topish uchun xash jadvaliga qaraymiz, bu holda i = 2.
Keyingi 79 -kalit ham to'qnashuvni keltirib chiqaradi: 9 -pozitsiya allaqachon olingan. Algoritmning samaradorligi keskin pasayadi, chunki bo'sh joy topish uchun 6 ta test (taqqoslash) kerak bo'ldi, indeks bepul bo'lib chiqdi i= 4.
Bu usul namunalarining umumiy soni har bir element uchun 1 dan n-1 gacha namunalarni tashkil etadi, bu erda n-xash jadvalining o'lchami.
Zanjirlash usulini amalga oshirish oldingi misol uchun. Biz ro'yxat elementi uchun tuzilgan turni e'lon qilamiz (bir tomonlama):
int kaliti; // kalit
int ma'lumotlari; // Ma `lumot
zap * Keyingi; // Ro'yxatdagi keyingi bandga ko'rsatgich
Dastlabki ma'lumotlarga asoslanib, biz jadvalni ketma -ket to'ldiramiz, agar bo'sh joy allaqachon olingan bo'lsa, ro'yxatning oxiriga yangi element qo'shamiz.
Xash yoki Xash nima?
Men shartlardan boshlayman.
Hash funktsiyasi, konvertatsiya funktsiyasi ixtiyoriy uzunlikdagi matnlarni belgilangan uzunlikdagi kodga aylantirishga imkon beradigan maxsus funktsiya turi (odatda qisqa harfli -raqamli yozuv).
Hashing manba matnlarini aylantirish jarayonidir.
Xash, Xash kodi, Hash qiymati, Hash summasi bu Hash funktsiyasining chiqish qiymati, ya'ni aniqlangan uzunlikdagi blok.
Ko'rib turganingizdek, atamalar biroz obrazli tavsifga ega, ulardan bu nima uchun kerakligini tushunish qiyin. Shuning uchun, men darhol kichik bir misol keltiraman (qolgan ilovalar haqida birozdan keyin gaplashaman). Aytaylik, sizda 10 Gb bo'lgan 2 ta fayl bor. Sizga qaysi biri kerakligini tezda qanday aniqlash mumkin? Fayl nomidan foydalanish mumkin, lekin uni qayta nomlash oson. Siz sanalarni ko'rishingiz mumkin, lekin fayllarni nusxalashdan keyin sanalar bir xil yoki boshqa ketma -ketlikda bo'lishi mumkin. O'lcham, siz tushunganingizdek, yordam bera olmaydi (ayniqsa, o'lchamlari bir xil bo'lsa yoki siz baytlarning aniq qiymatlariga qaramagan bo'lsangiz).
Bu erda bu Hash kerak, bu faylning manba matnidan tuzilgan qisqa blok. Bu 10 gigabaytli ikkita fayl ikki xil, lekin qisqa Hashcodlarga ega bo'ladi ("ACCAC43535" va "BBB3232A42" kabi). Ulardan foydalanib, siz tezda bilib olishingiz mumkin kerakli fayl, nomlarni nusxalash va o'zgartirgandan keyin ham.
Eslatma: Hash kompyuter dunyosida va Internetda juda mashhur tushuncha bo'lgani uchun, ko'pincha Xash bilan bog'liq bo'lgan hamma narsa shu so'zga qisqartiriladi. Masalan, tarjimada "Men MD5 xashidan foydalanaman" iborasi sayt yoki boshqa joyda MD5 standartining xesh algoritmini ishlatishini bildiradi.
Hash funktsiyasining xususiyatlari
Endi men Hash funktsiyalarining xususiyatlari haqida gaplashaman, shunda sizga Hash qaerda ishlatilishini va nima uchun kerakligini tushunish osonroq bo'ladi. Lekin, birinchi navbatda, yana bir ta'rif.
To'qnashuv bu ikki kishilik vaziyat turli matnlar bir xil xash summasi olinadi. O'zingiz tushunganingizdek, sobit uzunlikdagi blokdan beri u cheklangan miqdordagi mumkin bo'lgan qiymatlarga ega va shuning uchun takrorlash mumkin.
Va endi Hash funktsiyalarining o'ziga xos xususiyatlari:
1. Kirish har qanday o'lchamdagi matn bo'lishi mumkin, va chiqish aniqlangan uzunlikdagi ma'lumotlar bloki. Bu ta'rifdan kelib chiqadi.
2. Xuddi shu matnlarning xash-summasi bir xil bo'lishi kerak. Aks holda, bunday funktsiyalar shunchaki foydasiz - bu tasodifiy songa o'xshaydi.
3. Yaxshi funksiya konvulsiyalar yaxshi taqsimotga ega bo'lishi kerak. Qabul qiling, agar Hash chiqishining o'lchami, masalan, 16 bayt bo'lsa, agar funksiya har qanday matn uchun atigi 3 xil qiymatni qaytarsa, unda bunday funksiyada hech qanday ma'no yo'q va bu 16 bayt (16 bayt - 2 ^ 128 variant, bu taxminan 3, 4 * 10 ^ 38 daraja).
4. Funktsiya dastlabki matndagi eng kichik o'zgarishlarga qanchalik yaxshi javob beradi. Oddiy misol. 10 GB hajmdagi faylda 1 ta harf o'zgartirildi, funktsiya qiymati boshqacha bo'lishi kerak. Agar bunday bo'lmasa, unda bunday funktsiyadan foydalanish juda muammoli.
5. To'qnashuv ehtimoli. Muayyan sharoitlarda hisoblangan juda murakkab parametr. Ammo, uning mohiyati shundan iboratki, agar xash yig'indisi tez -tez bir -biriga to'g'ri kelsa, xash funktsiyasining ma'nosi nima.
6. Xashni hisoblash tezligi. Agar hisoblash uchun uzoq vaqt kerak bo'lsa, konvulsion funktsiyadan nima foyda? Yo'q, chunki fayl ma'lumotlarini solishtirish yoki boshqa yondashuvdan foydalanish osonroq.
7. Hash qiymatidan dastlabki ma'lumotlarni tiklashning murakkabligi. Bu xususiyat umumiydan ko'ra o'ziga xosdir, chunki bu har doim ham talab qilinmaydi. Biroq, eng mashhur algoritmlar uchun bu xususiyat taxmin qilinadi. Masalan, asl fayl siz bu funktsiyadan deyarli chiqa olmaysiz. Ammo, agar to'qnashuv muammosi bo'lsa (masalan, siz bunday Xashga mos keladigan matnni topishingiz kerak bo'lsa), unda bunday xarakteristikaning ahamiyati katta bo'lishi mumkin. Masalan, parollar, lekin keyinroq ular haqida.
8. Bunday funksiyaning ochiq yoki yopiq manba kodi. Agar kod ochiq manba bo'lmasa, ma'lumotlarni qayta tiklashning murakkabligi, ya'ni kriptografik kuch, savol ostida qoladi. Bu qisman shifrlash bilan bog'liq muammo.
Nega Xash kerak?
Hash funktsiyalarining faqat uchta asosiy maqsadi bor (aniqrog'i, ularning maqsadi).
1. Ma'lumotlarning yaxlitligini tekshirish. Bunday holda, hamma narsa oddiy, bunday funktsiyani tezda hisoblash kerak va, masalan, Internetdan yuklangan fayl uzatish paytida buzilmaganligini tekshirishga imkon beradi.
2. Ma'lumotlarni olish tezligining oshishi. Ruxsat etilgan blok o'lchami qidiruv muammolarini hal qilishda ko'p afzalliklarga ega bo'lish imkonini beradi. Bunday holda, nuqta shundaki, texnik jihatdan xash funktsiyalaridan foydalanish ishlashga ijobiy ta'sir ko'rsatishi mumkin. Bunday funktsiyalar uchun to'qnashuv ehtimoli va yaxshi taqsimot juda muhimdir.
3. Kriptografik ehtiyojlar uchun. Bu ko'rinish Konvulsion funktsiyalar xavfsizlik sohalarida qo'llaniladi, bu erda natijalarni o'zgartirish qiyin yoki olish vazifasini iloji boricha qiyinlashtirish kerak. foydali ma'lumotlar Xashdan.
Xash qayerda va qanday ishlatiladi?
Siz taxmin qilganingizdek, Xash ko'p vazifalarda ishlatiladi. Mana ulardan bir nechtasi:
1. Parollar odatda aniq matnda emas, balki hash-sum shaklida saqlanadi, bu esa yuqori darajadagi xavfsizlikni ta'minlaydi. Axir, agar tajovuzkor bunday ma'lumotlar bazasiga kirsa ham, u bu hash kodlarga mos matnlarni topish uchun ko'p vaqt sarflashga majbur bo'ladi. Bu erda "Hash qiymatlaridan asl ma'lumotlarni tiklashning murakkabligi" xususiyati muhimdir.
Eslatma: Men sizga parolni himoyalashni yaxshilash bo'yicha bir necha maslahatlar uchun ushbu maqolani o'qishni maslahat beraman.
2. Dasturlashda, shu jumladan ma'lumotlar bazalarida. Albatta, ko'pincha biz ruxsat beradigan ma'lumotlar tuzilmalari haqida gapiramiz tezkor qidiruv... Aniq texnik jihat.
3. Ma'lumotni tarmoq orqali uzatishda (shu jumladan Internet). Ko'p protokollar, masalan, TCP / IP, maxsus xabar maydonlarini o'z ichiga oladi, agar biror joyda xato bo'lsa, bu ma'lumot uzatishga ta'sir qilmaydi.
4. Har xil xavfsizlik bilan bog'liq algoritmlar uchun. Masalan, Hash elektron raqamli imzoda ishlatiladi.
5. Fayllarning yaxlitligini tekshirish uchun. Agar siz e'tibor bergan bo'lsangiz, Internetda tez -tez fayllarni topishingiz mumkin (masalan, arxivlar) qo'shimcha tavsiflar xash kodi bilan. Bu o'lchov nafaqat Internetdan yuklash paytida buzilgan faylni tasodifan ishga tushirmaslik uchun, balki xostingda ham nosozliklar bo'lishi uchun ishlatiladi. Bunday hollarda, siz Hash-ni tezda tekshirishingiz va agar kerak bo'lsa, faylni qayta yuklashingiz mumkin.
6. Ba'zida xash funktsiyalari noyob identifikatorlarni yaratish uchun ishlatiladi (bir qismi sifatida). Masalan, rasmlarni yoki fayllarni saqlashda ular odatda Hash -ni ism va sana bilan birga ishlatadilar. Bu xuddi shu nomdagi fayllarni qayta yozishdan saqlaydi.
Aslida, qancha uzoqlashsangiz, xesh funktsiyalari shunchalik tez ishlatiladi axborot texnologiyalari... Asosan, bu ma'lumotlarning miqdori va eng kuchliligi bilan bog'liq oddiy kompyuterlar juda ko'p o'sdi. Birinchi holda, bu ko'proq qidiruv, ikkinchisida xavfsizlik masalalari haqida.
Taniqli hash funktsiyalari
Quyidagi uchta hash funktsiyalari eng mashhur.
Do'stlaringiz bilan baham: |
