10-Amaliy mashgʻulot: Saralash masalasi uchun muayyan algoritmlar va ularning murakkabligini aniqlash

---

10-Amaliy mashgʻulot: Saralash masalasi uchun muayyan algoritmlar va 
ularning murakkabligini aniqlash. 
Joylashtirish 
usuli 
(xeshlashtirish) 
ALGORITMLAR 
VA 
BERILGANLAR 
STRUKTURASIda element joylashgan oʻrinni tez aniqlashga yoʻnaltirilgan usuldir. 
Joylashtirish usulida maʻlumotlar oddiy massiv sifatida ifodalangan boʻladi. Elementni jadvalga 
qoʻshishdan oldin uning adresi xesh-funksiya orqali aniqlanadi: 
A = h(K)
, bu yerda K – kalit, A 
– jadvaldagi element adresi boʻlib, 0 

A 

N-1, shart oʻrinli boʻladi.
F xesh-funksiya deb R kiruvchi elementlar toʻplamini manfiy boʻlmagan butun sonlar 
toʻplami Z ga oʻgirishga aytiladi. Z:F(r)=n, rϵR, nϵZ. Xesh-adreslash bu xesh-funksiya qiymatlar 
soxasini qandaydir bir maʻlumotlar massivining yacheykasi adresi sifatida foydalanishdan iborat. 
U holda maʻlumotlar massivi oʻlchami foydalanilayotgan xesh-funksiyaning qiymatlar soxasiga 
mos kelishi kerak.
Turli A
1
, A
2
, A
3
identifikatorlar uchun mos ravishda n
1
, n
2
, n
3
xesh-funksiya qiymatlari toʻgʻri 
kelsin. n
1
, n
2
, n
3
adreslarga mos yacheykalarda A
1
, A
2
, A
3
identifikatorlar haqida maʻlumot 
joylanadi. A
3
identifikatorni qidirishda n
3
adres qiymati hisoblanadi va tegishli jadval 
yacheykasidan maʻlumotlar tanlanadi.
Bu metod juda effektiv, elementlari jadvalga joylash vaqti xam, qidiruv vaqti ham faqat xesh-
funksiyani xisoblashga ketadi.
Bu usulning 2 ta yaqqol kamchiligi bor. Ulardan biri: identifikatorlar jadvalining xotira 
xajmidan unumsiz foydalanilishi. Massiv oʻlchami xesh-funksiya qiymatlar soxasiga mos 
kelishi kerak, ayni vaqtda real xolatda jadvalda saqlanayotgan identifikatorlar ancha kam 
boʻlishi mumkin. Ikkinchi kamchiligi mos keluvchi xesh-funksiyani tanlay bilish.
Xesh-funksiyadan natija olish - “xeshlash” simvollar zanjiri ustida oddiy arifmetik va 
mantiqiy amallarni bajarish xisobiga erishiladi. xesh-adreslashda identifikatorlar jadvalining 
bir yacheykasiga 2 ta turli xil boʻlgan identifikatorlar joylashishi mumkin emas. Bu vaziyat, 
yaʻni 2 yoki undan ortiq identifikatorlar xesh funksiyaning bir xil qiymatiga ega boʻlish 
xodisasi kolliziya deb nomlanadi. Kolliziyaning yuzaga kelishi 2 ta xar xil identifikator A
1 
va 

---

A
2
larning xesh-funksiya qiymatlari n
1
va n
2 
bir xil (n
1
=n
2
) boʻlishi xisoblanadi. Xesh-
funksiyadan natija olish - “xeshlash” simvollar zanjiri ustida oddiy arifmetik va mantiqiy 
amallarni bajarish xisobiga erishiladi. xesh-adreslashda identifikatorlar jadvalining bir 
yacheykasiga 2 ta turli xil boʻlgan identifikatorlar joylashishi mumkin emas. Bu vaziyat, yaʻni 
2 yoki undan ortiq identifikatorlar xesh funksiyaning bir xil qiymatiga ega boʻlish xodisasi 
kolliziya deb nomlanadi. Kolliziyaning yuzaga kelishi 2 ta xar xil identifikator A
1 
va 
A
2
larning xesh-funksiya qiymatlari n
1
va n
2 
bir xil (n
1
=n
2
) boʻlishi xisoblanadi.
Bu metodga koʻra, A element uchun xesh-funksiya orqali hisoblangan h(A) adresi band 
boʻlgan yacheykani koʻrsatsa, unda n
1
=h
1
(A) funksiya qiymatini hisoblash zarur va n
1
adresga 
tegishli yacheykani bandligini tekshirish kerak. Agar n
1
xam band boʻlsa, unda h
2
(A) qiymat 
hisoblanadi, shu tariqa boʻsh yacheyka torilguncha yoki h
i
(A) navbatdagi qiymat h(A) bilan 
mos kelgunga qadar davom etadi. Oxirgi xolatda identifikatorlar jadvali toʻlgan va boʻsh joy 
boshqa yoʻq degan xatolik toʻgʻrisida maʻlumot beradi.
h
i
(A) funksiyani xisoblashni eng oddiy metodi, uni h
i
(A)=(h(A)+p
i
)modN
m
asosida qurishdir, 
bu yerda p
i
qandaydir bir xisoblangan butun son, N
m
–identifikatorlar jadvalidagi 
elementlarning maksimal soni. Oʻz oʻrnida eng oddiy usul p
i 
ni oʻrniga i ni qoʻyish boʻladi. 
Unda quyidagi formulani olamiz h
i
(A)=(h(A)+i)modN
m
. Bu holda xesh-funksiyaning bir xil 
qiymatlariga mos kelgan identifikatorlarni joylash uchun boʻsh yacheykani qidirish mantiqan
xesh-funksiya h(A) koʻrsatgan joydan boshlanadi.

---

Massiv elementini indeks buyicha topish kerak boʻlsin. Buning uchun avval indeksni 
xesh adresning mos qiymatiga aylantirish lozim va shundan soʻnggina qidiruvni amalga 
oshirish mumkin.
Xeshlashtirish misolida
primary 
nomli tuzilmalar massividan foydalaniladi: 
#define MAX 260 
struct htype { 
int index; /* mantiqiy indeks */ 
int val; /* malumotlar elementining xos qiymati */ 
struct htype *next; /* Shunday xesh-adresli keyingi elemntga koʻrsatkich */ 
} primary[MAX]; 
Bu massivdan foydalanishdan avval uni inisializasiya qilish zarur.Quyidagi funksiya 
index 
maydoniga -1 qiymatini beradi; Bu qiymat boʻsh elementni bildiradi. 
NULL 
qiymati 
next
maydonidagi xeshlashtirishning boʻsh zanjiriga mos keladi. 
/* xesh-massivni inisializasiya qilish. */ 
void init(void) 
{ 
register int i; 
for (i=0; iprimary[i].index = -1; 
primary[i].next = NULL; /* boʻsh zanjir */ 
primary[i].val = 0; 
} 
} 
store() 
prosedurasi yacheyka nomini birlamchi 
primary 
massividagi xesh adresga 
aylantiradi. Xesh adresda koʻrsatilgan pozisiya band boʻlsa, prosedura bu yozuvni avtomatik 
xolda 
slstore() 
fuknsiyaning modifikasiyalangan versiyasi yordamida kolliziya roʻyxatiga 
qoʻshib qoʻyadi. Bu funksiyalar quyida keltirilgan.
/* xesh-adresni xisoblash va qiymatini saqlash */ 
void store(char *cell_name, int v) 
{ 
int h, loc; 
struct htype *p; 
/* xesh-adresni olish*/ 
loc = *cell_name - ʻAʻ; /* ustun */ 
loc += (atoi(&cell_name[1])-1) * 26; /* qator * kenglik + ustun */ 

---

h = loc/10; /* hash */ 
/* agar olingan pozisiya band boʻlmasa, uni saqlash yoki mantiqiy indekslar ustma – ust 
tushgan xolda saqlash */ 
if(primary[h].index==-1 || primary[h].index==loc) { 
primary[h].index = loc; 
primary[h].val = v; 
return; 
} 
/*aks xolda kolliziyalar roʻyxatini tuzish va unga xesh – adresni qoʻshish */ 
p = (struct htype *) malloc(sizeof(struct htype)); 
if(!p) { 
printf("xotira yetishmayapti\n"); 
return; 
} 
p->index = loc; 
p->val = v; 
slstore(p, &primary[h]); 
} 
/* Elementlarni kolliziya roʻyxatiga qoʻshish. */ 
void slstore(struct htype *i, 
struct htype *start) 
{ 
struct htype *old, *p; 
old = start; 
/* roʻyxat oxirini topish */ 
while(start) { 
old = start; 
start = start->next; 
} 
/* yangi yozuv bilan bogʻlash */ 
old->next = i; 
i->next = NULL; 
} 
Elementning qiymatini olish uchun dastur avval xesh-adresni xisoblaydi va uni 
qidirilayotgan massiv elementi indeks bilan tengligini tekshiradi.Agar teng boʻlsa yacheyka 
qiymati qaytariladi, aks xolda kolliziyalar roʻyxatida qidiruv amalga oshiriladi. Bu vazifalarni
bajaruvchi 
find()
,quyida keltirilgan: 
/* xesh-adresni xisoblash va qiymatini olish. */ 
int find(char *cell_name) 

---

{ 
int h, loc; 
struct htype *p; 
/* xesh-adres qiymatini olish */ 
loc = *cell_name - ʻAʻ; /* stolbes */ 
loc += (atoi(&cell_name[1])-1) * 26; /* qator * kenglik + ustun */ 
h = loc/10; 
/* yacheyka topilsa,qiymatni qaytarish */ 
if(primary[h].index == loc) return(primary[h].val); 
else { /* aks xolda kolliziyalar roʻyxatini koʻrish */ 
p = primary[h].next; 
while(p) { 
if(p->index == loc) return p->val; 
p = p->next; 
} 
printf("Yacheyka massivda yoʻq\n"); 
return -1; 
} 
} 
Bu dasturga oʻchirish funksiyasini qoʻyish lozim.