O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUXAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI FARG'ONA FILIALI TT VA KT
FAKULTETI AKT SOHASIDA KASB TA'LIMI YO'NALISHI 620-21-
GURUH TALABASI ALIYEV MUHAMMADALINING MA'LUMOTLAR
TUZILMASI VA ALGORITMLAR FANIDAN TAYYORLAGAN
REFERATI
Topshirdi : Muhammadali Aliyev
Qabul qildi : N.Mamadaliyev
Mavzu: Statik va yarimstatik ma’lumotlar tuzilmasi.
Reja:
Yarimstatik ma’lumotlar tuzimasi.
Navbat
Stek
Dek
Yarimstatik ma’lumotlar tuzilmasi
Yarimstatik ma’lumotlar tuzilmasini quyidagicha tavsiflash
mumkin: - o’zgaruvchan uzunlikka ega va uni o’zgartiruvchi oddiy
funksiyalariga ega;
- tuzilmaning uzunligini o’zgartirish ma’lum bir chegarada, ya’ni
qandaydir bir maksimal qiymatdan oshmagan holda amalga
oshirilishi mumkin;
Agar yarimstatik tuzilmani mantiqiy jihatdan qaraydigan bo’lsak, u
holda chiziqli ro’yhat munosabati bilan bog’langan ma’lumotlar
ketma-ketligi tushuniladi. Xotirada yarimstatik ma’lumotlar
tuzilmasini fizik jihatdan tasvirlaydigan bo’lsak, bu xotirada
slotlarning oddiy ketma-ketligidir, ya’ni har bir element xotirada
navbatdagi slotlarda joylashadi. Yarimstatik MTni fizik
tasvirlashning yana bir ko’rinishi bir tomonlama bog’langan ro’yhat
(zanjir) ko’rinishida ifodalash mumkin, ya’ni bunda har bir
navbatdagi elementning adresi joriy elementda ko’rsatiladi. Bunday
tasvirlashda tuzilmaning uzunligiga
cheklanish unchalik qattiq qo’yilmaydi. Bunday tuzilmalarga –
navbat, stek, dek va satrlar kiradi.
NavbatNavbat bu FIFO (First In - First Out - "birinchi kelgan –
birinchi ketadi"), shunday o’zgaruvchan uzunlikdagi ketma-ketlik,
ro’yhatki, unda tuzilmaga elementlar faqat bir tomondan, ya’ni
navbatning oxiridan qo’shiladi va elementlarni tuzilmadan
chiqarish boshqa tomondan, ya’ni navbat boshidan amalga
oshiriladi. Navbat ustida bajariladigan asosiy amallar
- yangi elementni qo„shish,
- elementni chiqarib tashlash,
- uzunligini aniqlash,
- navbatni tozalash.
Navbatni statik xotirada vektor ko’rinishida ifodalashda 2 ta
parametr, ya’ni navbat boshini (navbatning 1-elementini) va oxirini
(navbatning oxirgi elementini) ko’rsatuvchi ko’rsatkichlar olinadi (1-
rasm).
kirish
chiqish
Navbat boshi
Navbat oxiri
R=9 1-rasm. Navbat tuzilmasi
Navbatga yangi element kiritilayotganda navbat oxiri ko’rsatkichi
ko’rsatayotgan adresga yoziladi va shundan keyin navbat oxiri
ko’rsatkichi bittaga oshiriladi. Navbatdan elementni o’chirishda
navbat boshi ko’rsatkichi ko’rsatayotgan adresdagi element
o’chiriladi va shundan keyin bu ko’rsatkichning qiymati bittaga
oshiriladi. Navbatga elementlar kiritilganda navbat oxiri ko’rsatkichi
shu navbat uchun ajratilgan xotira sohasining oxiriga yetib qoladi.
Bunda navbat to’lgan hisoblanadi.
Agar navbatdan elementlar o’chiriladigan bo’lsa, navbat boshida
bo’sh joy ajratiladi. Vaholanki, navbat oxiri ko’rsatkichi chegaraga
yetib qolganligi sababli, navbatga yangi element kiritib bo’lmaydi.
Shu sababli navbatda har safar element o’chirilganda qolgan
barcha elementlar bitta oldinga surilishi kerak bo’ladi. Natijada
navbat oxirida bo’sh joy ochiladi. Bu holatda navbat boshi
ko’rsatkichiga xojat qolmaydi. Lekin shuni aytish kerakki, bu
yondashuv bir muncha noqulay hisoblanadi. Shuning uchun har
safar elementlarni surib o’tirmaslik uchun navbatni halqasimon
shaklda tashkil etamiz. Ya’ni bunda xotirada navbat sohasining
oxiriga yetib borilganda navbat boshiga o’tib ketiladi. Ushbu
holatda navbat boshi va oxiri ko’rsatkichlari xotiradagi navbat
sohasining boshini ko’rsatadi. Bu ikkala ko’rsatkichlarning tengligi
navbatning bo’shligini anglatadi. Halqasimon navbatda element
qo’shish amali o’chirish amalidan ko’proq bajarilsa, navbat oxiri
ko’rsatkichi navbat boshi ko’rsatkichiga “yetib oladi”. Bu holat
navbat to’laligini anglatadi. Halqasimon navbatda elementni
o’chirish ikkala ko’rsatkich ko’rsatayotgan bitta adresda amalga
oshiriladi. Bunday navbatning uzunligi boshi va oxiri ko’rsatkichlari
farqi bilan aniqlanadi.
C++ tilida navbatni statik, ya’ni bir o’lchamli massiv ko’rinishda
amalga oshirishga misol: Navbat uchun 10 ta joy ajratilgan bo’lsin,
navbatni butun sonlardan iborat massiv shaklida ifodalaymiz.
Bunda navbat dastlab bo’shligi sababli, navbat oxiri ko’rsatkichi
R=0 bo’ladi. Navbatga yangi element qo’shish va navbatdan
elementni chiqarib olish algoritmi, navbat bo’shligini va to’laligini
tekshirish algoritmlari quyidagi dasturda keltirilgan.
Masala. Butun sonlardan iborat navbatning juft elementlarini
o’chirish dasturini keltiramiz.
Algoritm
1. Agar navbat to’lmagan bo’lsa unga element kiritamiz, kiritib
bo’lgach keyingi 2-qadamga o’tish, aks holda navbat to’lganligini
xabar berib, keyingi 2-qadamga o’tish.
2. Agar navbat bo’sh bo’lmasa 3-qadamga o’tamiz, aks holda 4-
qadamga o’tamiz.
3. Navbatning chiqishiga kelib turgan elementni olib, juftlikka
tekshiramiz. Agar element toq bo’lsa, uni navbatga kiritamiz. 2-
qadamga o’tish.
4. Navbat bo’sh bo’lsa, bu haqda xabar berib keyingi 5-qadamga
o’tamiz.
5. Navbat tarkibini ekranga chiqaramiz.
Dastur kodi
#include
using namespace std;
int a[10],R=0,n;//bu yerda n navbatga kiritilishi kerak bo'lgan
elementlar soni.
int kiritish(int s){
a[R]=s; R++;
}
int chiqarish(){
int t=a[0];
for(int i=0;i
a[i]=a[i+1];
R--;
return t;
}
bool isEmpty(){
if(R==0) return true; else return false;
}
bool isFull(){
if(R=10)return true;else return false;
}
int print(){
int i;
while(i
int k=chiqarish();i++;
cout
kiritish(k);}
}
int main(){
int n,s;
coutn;
for(int i=0;i
if(!isFull()){cins;
kiritish(s);}
else{cout
}
cout
print();
for(int i=0;i
s=chiqarish();
if(s%2!=0)kiritish(s);
}
cout
print();
system("PAUSE");
} Dasturning bajarilishi natijasi:
n=5
6
7
9
8
11
navbat elementlari: 6 7 9 8 11
natijaviy navbat elementlari: 7 9 11
SteklarStek bu LIFO (Last In - First Out - "oxirgi kelgan – birinchi
ketadi"), shunday o’zgaruvchan uzunlikdagi ketma-ketlik, ro’yhatki,
unda tuzilmaga elementlarni kiritish va chiqarish amallari bir
tomondan, ya’ni stek uchidan amalga oshiriladi. Stek ustida
bajariladigan asosiy amallar:
- yangi elementni qo’shish; - elementni o’chirish; - stek elementlar
sonini aniqlash; - stekni tozalash. Stekni statik xotirada vektor
ko’rinishida ifodalashda stek uzunligini ko’satuvchi ko’rsatkich
ishlatiladi. Bu ko’rsatkich stekdagi 1-bo’sh joyni ko’rsatadi. Dastlab
hali stek bo’shligida bu ko’rsatkich R=0 bo’ladi. Quyidagi rasmda
stekda 6 ta element mavjudligi uchun R=7 bo’ladi (2-rasm). Stek
tubi
Stek uchi
R=7
chiqish kirish
2-rasm. Stek tuzilmasi Stekka yangi element kiritilayotganda stek
ko’rsatkichi (R) ko’rsatayotgan adresga yoziladi va shundan keyin
bu ko’rsatkich bittaga oshiriladi. Stekdan elementni o’chirishda
ko’rsatkichning qiymati bittaga kamaytiriladi va shu adresdagi
element o’chiriladi. Stekni tozalash amalini bajarish uchun stek
Ko’rsatkichi R ga stek uchun ajratilgan xotira sohasining
boshlang’ich adresi qiymati beriladi. R stekdagi elementlar sonini
bildiradi.
C++ tilida stekni statik ko’rinishda, ya’ni bir o’lchamli massiv
ko’rinishida amalga oshirishga misol: Masalaning qo’yilishi:
Elementlari butun sonlardan iborat stekning juft qiymatli
elementlari o’chirilsin. Aytaylik, stek uchun 10 ta joy ajratilgan
bo’lsin, bunda dastlab stek bo’shligi sababli R=0 bo’ladi. Stekga
yangi element qo’shish va chiqarish, stek bo’shligini va to’laligini
tekshirish funksiyalaridan foydalanib shu masalani yechamiz.
Algoritm 1. Agar stek to’lmagan bo’lsa elementlarni kiritamiz.
Stekning toq elementlarini saqlab turish uchun yangi b[] massiv
e’lon qilamiz.
2. Agar stek bo’sh bo’lmasa, 3-qadamga o’tish, aks holda 4-
qadamga o’tish.
3. Stek uchidagi elementni olamiz va juftlikka tekshiramiz. Agar
element toq bo’lsa b massivga joylaymiz. 2-qadamga o’tish.
4. b massiv elementlarini teskari tartibda stekka joylash.
5. Stek tarkibini ekranga chiqarish.
Dastur kodi
#include
using namespace std;
int a[10],R=0,n;//bu yerda n stekka kiritilishi kerak bo'lgan
elementlar soni.
int kiritish(int s){
a[R]=s; R++;
}
int chiqarish(){
R--;
return a[R];
}
bool isEmpty(){
if(R==0) return true;
else return false;
}
bool isFull(){
if(R=10) return true;else return false;
}
int print(){
int i=0,c[n];
while(!isEmpty()){
c[i]=chiqarish();
cout
for(int j=i-1;j=0;j--) kiritish(c[j]);
}
int main(){
int n,s;
coutn;
for(int i=0;i
if(!isFull()){
cins;
kiritish(s);}
else{cout
}
cout
print();
int b[n],k=0;
for(int i=0;i
s=chiqarish();
if(s%2!=0) b[k++]=s;
}
for(int i=k-1;i=0;i--) kiritish(b[i]);
cout
print();
system("PAUSE");
} Dasturning bajarilishi natijasi:
n =5
6
7
9
8
11
stek elementlari: 11 8 9 7 6
natijaviy stek elementlari: 11 9 7
DeklarDek so’zi (DEQ - Double Ended Queue) ingliz tilidan olingan
bo’lib 2 ta chetga ega navbat degan ma’noni bildiradi. Dekning
o’ziga xos xususiyati shuki, unga elementlar har ikkala tomondan –
chapdan va o’ng tomondan kiritilishi va chiqarilishi mumkin (3-
rasm).
Dek ustida bajariladigan amallar: 1. Chapdan element kiritish.
2. O’ngdan element kiritish.
3. Chapdan element chiqarish.
4. O’ngdan element chiqarish.
5. Dek bo’shligini tekshirish.
6. Dek to’laligini tekshirish.
C++ tilida dekni statik ko’rinishda, ya’ni bir o’lchamli massiv
ko’rinishida amalga oshirishga misol: Berilayotgan butun sonlar
ketma-ketligining 1-yarmini dekning chap tomonidan, qolgan
yarmini dekning o’ng tomonidan kiriting. Dekning elementlarini bir
safar chapdan, bir safar o’ngdan juftlikka tekshirib, toq elementlari
o’chirilsin.
Algoritm
1. Dekka nechta element kiritilishi aniqlanadi – n, i=0.
2. i++; agar i
3. Agar in/2 bo’lsa, dekning o’ng tomonidan kiritiladi, 2-qadamga
o’tish.
4. Agar dek bo’sh bo’lmasa, chapdan element chiqarib olamiz.
Agar element juft bo’lsa, b[] massivga joylaymiz. 5-qadamga
o’tiladi. Agar dek bo’sh bo’lsa, 6-qadamga o’tish.
5. Agar dek bo’sh bo’lmasa, o’ngdan element chiqarib olamiz. Agar
element juft bo’lsa, b[] massivga joylaymiz. 5-qadamga o’tiladi.
Agar dek bo’sh bo’lsa, 6-qadamga o’tish.
6. b[] massiv elementlarini dekka o’ng tomondan kiritamiz.
7. Dek tarkibini ekranga chiqaramiz.
Dastur kodi
#include
#include
using namespace std;
int a[10],n,R=0;
bool isEmpty(){
if(R==0) return true; else return false;
}
bool isFull(){
if(R=10) return true; else return false;
}
int kirit_left(int s){
if(isFull()){cout
for(int i=R;i0;i--)
a[i]=a[i-1];
a[0]=s;R++;
}
int olish_left(){
if(isEmpty()){cout
int t=a[0];
for(int i=0;i
a[i]=a[i+1];
R--;
return t;
}
int kirit_right(int s){
if(isFull()){cout
a[R]=s;R++;
}
int olish_right(){
if(isEmpty()){cout
R--;
return a[R];
}
int print(){
cout
for(int i=0;i
cout
}
int main(int argc, char *argv[])
{ int n,s;coutn;
for(int i=0;i
if(!isFull()){
couts;
if(i=n/2) kirit_right(s);
else kirit_left(s);}
else {cout
}
print();
int b[n/2],k=0,c[n/2],p=0;
while(!isEmpty()){
int q=olish_left();
if(q%2==0) b[k++]=q;
if(isEmpty()) break;
int p=olish_right();
if(p%2==0) b[k++]=p;
}
int i=0;
while(i
kirit_right(b[i]);
i++;
}
print();
system("PAUSE");
return EXIT_SUCCESS;
}
Dastur natijasi
n=8
kirit=1 kirit=2
kirit=3
kirit=4
kirit=5
kirit=6
kirit=7
kirit=8
dek ele-tlari=4 3 2 1 5 6 7 8
dek ele-tlari=4 8 2 6
|
