|
Algoritmlar va berilganlar strukturalari
|
| bet | 2/14 | | Sana | 23.11.2023 | | Hajmi | 0,65 Mb. | | #104360 |
Bog'liq Algoritmlar va berilganlar strukturalari Mavzu Oʻquvchilarning texnik ijodkorligini rivojlantirish Reja -fayllar.orgDeklar
chetga ega navbat degan ma‟noni bildiradi. Dekning o„ziga xos xususiyati shuki,
unga elementlar har ikkala tomondan – chapdan va o„ng tomondan kiritilis hi va
chiqarilishi mumkin (2.3-rasm). 2.3-rasm. Dek tuzilmasi
Dek ustida bajariladigan amallar:
Chapdan element kiritish. 2.
O„ngdan element kiritish. 3.
Chapdan element chiqarish.
42
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„rinishid a
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.
++; agar i
i
4-qadamga o„tiladi. 3.
gar in/2
A
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;
} 43
bool isFull(){
if(R>=10) return true; else return false;
}
int kirit_left(int s){ if(isFull()){cout<<"\ndek to'ldi";n=R;return EXIT_SUCCESS;}
for(int i=R;i>0;i--)
a[i]=a[i-1];
a[0]=s;R++;
}
int olish_left(){
if(isEmpty()){cout<<"\ndek bo'sh";return EXIT_SUCCESS;}
int t=a[0];
for(int i=0;i i="">
a[i]=a[i+1];
R--;
return t;
}
int kirit_right(int s){
if(isFull()){cout<<"\ndek to'ldi";n=R;return EXIT_SUCCESS;}
a[R]=s;R++;
}
int olish_right(){
if(isEmpty()){cout<<"\ndek bo'sh";return EXIT_SUCCESS;}
R--;
return a[R];
}
int print(){
cout< ele-tlari=";
for(int i=0;i i="">
cout< i="">
44
}
int main(int argc, char *argv[])
{ int n,s;cout<<"n="; cin>>n;
for(int i=0;i i="">
if(!isFull()){
cout<<"kirit=";cin>>s;
if(i>=n/2) kirit_right(s);
else kirit_left(s);}
else {cout<<"dek to'ldi\n";break;}
}
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 i="">
kirit_right(b[i]);
i++;
}
print();
system("PAUSE");
return EXIT_SUCCESS;
}
Dastur natijasi
n=8
45
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
Dinamik berilganlar tuzilmasi. - Динамик тузилмалар (руйхат, дарахт)
Uzellar (elementlar) va ularning munosabatlaridan iborat elementlar toplamining ierarxik tuzilmasiga daraxtsimon ma’lumotlar tuzilmasi deyiladi. Daraxt – bu shunday chiziqsiz
bog'langan ma’lumotlar tuzilmasiki, u quyidagi belgilari bilan tavsiflanadi: - daraxtda shunday bitta element borki, unga boshqa elementlardan murojaat yo’q. Bu element daraxt ildizi deyiladi; - daraxtda ixtiyoriy element chekli sondagi ko’rsatkichlar yordamida boshqa tugunlarga murojaat qilishi mumkin; - daraxtning har bir elementi faqatgina o’zidan oldingi
kelgan bitta element bilan bog’langan. Binar daraxtlarni qurish Binar daraxtda har bir tugun- elementdan ko’pi bilan 2 ta shox chiqadi. Daraxtlarni xotirada tasvirlashda uning ildizini
ko’rsatuvchi ko’rsatkich berilishi kerak. Daraxtlarni kompyuter xotirasida tasvirlanishiga ko’ra har bir element (binar daraxt tuguni) to’rtta maydonga ega yozuv shaklida bo’ladi, ya’ni kalit maydon, informatsion maydon, ushbu elementni o’ngida va chapida joylashgan elementlarning xotiradagi adreslari saqlanadigan maydonlar. Daraxt hosil qilinayotganda,
otaga nisbatan chap tomondagi o’g’il qiymati kichik kalitga, o’ng tomondagi o’g’il esa katta qiymatli kalitga ega bo’ladi. Har safar daraxtga yangi element kelib qo’shilayotganda u avvalambor daraxt ildizi bilan solishtiriladi. Agar element ildiz kalit qiymatidan kichik bo’lsa, uning chap shoxiga, aks holda o’ng shoxiga o’tiladi. Agar o’tib ketilgan shoxda tugun mavjud 4-
Amaliy mashg’ulot. Daraxtsimon ma’lumotlar tuzilmasini e’lon qilish va ular ustida bajariladigan amallarga doir masalalar yechish. bo’lsa, ushbu tugun bilan ham solishtirish
amalga oshiriladi, aks holda, ya’ni u shoxda tugun mavjud bo’lmasa, bu element shu tugunga joylashtiriladi.
Dinamik ma‟lumotlar tuzilmasi
Statik ma‟lumotlar tuzilmasi
vaqt o„tishi bilan o„z o„lchamini
o„zgartirmaydi. Biz har doim dastur kodidagi statik ma‟lumotlar tuzilmasiga qarab ularning o„lchamini bilishimiz mumkin. Bunday ma‟lumotlarga teskari ravishda dinamik ma‟lumotlar tuzilmasi mavjud bo„lib, bunda dastur bajarilishi davomida dinamik ma‟lumotlar tuzilmasi o„lchamini o„zgartirishi mumkin. Dinamik ma’lumotlar tuzilmasi – bu qandaydir bir qonuniyatga asoslanib shakllangan, lekin elementlari soni, o„zaro joylashuvi va o„zaro aloqasi dastur bajarilishi davomida shu qonuniyat asosida dinamik o„zgaruvchan bo„lgan ma‟lumotlar tuzilmasidir.
Dasturlarda dinamik ma‟lumotlar tuzilmasidan ko„pincha chiziqli ro„yhatlar, steklar, navbatlar va binar daraxtlar ishlatiladi. Bu tuzilmalar bir-biridan elementlarning bog„lanish usuli va ular ustida bajarilishi mumkin bo„lgan amallari
bilan farqlanadi. Dinamik tuzilmalar massiv va yozuvdan farqli ravishda operativ xotirada ketma-
ket sohalarda joylashmaydi. Ixtiyoriy dinamik tuzilma elementi 2 ta maydondan tashkil topadi: tuzilma tashkil etilishiga sabab bo„layotgan
Dinamik ma‟lumotlat tuzilmasi fayllar
matnli toifalashtirilgan toifalashtirilmagan Bog„lanmagan dinamik tuzilmalar Statik MT kabi klassifikasiyalanadi Bog„langan dinamik tuzilmalar
chiziqli tuzilmalar Halqasimon tuzilmalar chiziqsiz tuzilmalar Bir bog„lamli navbat stek
dek ro„yhat
ko„p bog„lamli bir bog„lamli hal-
qasimon ro„yhatlar ko„p bog„lamli hal- qasimon ro„yhatlar daraxtlar
graflar Ikkilik (binar)
tarmoqlanuvchi ko
„
p bog
„
lamli chiziqli ro
„
yhatlar
informatsion maydon va elementlarning o„zaro aloqasini ta‟minlovchi ko‘rsatkichli maydon. Chiziqli ro„yhatlarda har bir element o„zidan keyingisi yoki oldingisi bilan ham bog„langan bo„lishi mumkin. Birinchi holatda, ya‟ni elementlar
o„zidan keyingi element bilan bog„langan bo„lsa, bunday ro„yhatga bir bog‘lamli ro‘yhat deyiladi. Agar har bir element o„zidan oldingi va o„zidan keyingi element bilan bog„langan bo„lsa, u holda bunday ro„yhatlarga 2 bog‘lamli ro‘yhatlar deyiladi. Agar oxirgi element birinchi element ko„rsatkichi bilan bog„langan bo„lsa, bunday ro„yhatga halqasimon ro‘yhat deyiladi. Ro„yhatning har bir elementi shu elementni identifikatsiyalash uchun kalitga ega bo„ladi. Kalit odatda butun son yoki satr ko„rinishida ma‟lumotlar maydonining bir qismi sifatida mavjud bo„ladi. Ro„yhatlar ustida quyidagi amallarni bajarish mumkin.
-
ro„yhatni shakllantirish (birinchi elementini yaratish);
-
ro„yhat oxiriga yangi element qo„shish;
-
berilgan kalitga mos elementni o„qish;
-
ro„yhatning ko„rsatilgan joyiga element qo„shish (berilgan kalitga mos elementdan oldin yoki keyin)
-
berilgan kalitga mos elementni o„chirish;
-
kalit bo„yicha ro„yhat elementlarini tartibga keltirish.
Ro„yhatlar bilan ishlashda dasturda boshlang„ich elementni ko„rsatuvchi ko„rsatkich talab etiladi. Chiziqli bir bog„lamli ro„yhatlar ustida turli amallar bajarish algoritmlari va dasturlarini ko„rib chiqamiz.
Chiziqli bir bog’lamli ro’yhatlar va ular ustida amal bajarish algotirmlari.
Chiziqli bir bog‘lamli ro‘yhatlar
Bir bog‘lamli ro‘yhat deb elementlarning shunday tartiblangan ketma-ketligiga aytiladiki, har bir element 2 ta maydonga: informatsion maydon info va ko‘rsatkich maydoni ptr ga ega bo‘ladi (3.2-rasm).
Mazkur ko‘rinishdagi ro‘yhat elementi ko‘rsatkichining o‘ziga xosligi shundan iboratki, u faqatgina ro‘yhatning navbatdagi (o‘zidan keyin keluvchi) elementi adresini ko‘rsatadi. Bir tomonlama yo‘naltirilgan ro‘yhatda eng so‘ngi element ko‘rsatkichi bo‘sh, ya’ni NULL bo‘ladi.
Lst – ro‘yhat boshi ko‘rsatkichi. U ro‘yhatni yagona bir butun sifatida ifodalaydi. Ba’zan ro‘yhat bo‘sh bo‘lishi ham mumkin, ya’ni ro‘yhatda bitta ham element bo‘lmasligi mumkin. Bu holda lst = NULL bo‘ladi. Hozir chiziqli bir bog‘lamli ro‘yhat hosil qilish dasturini ko‘rib chiqsak. Buning uchun biz foydalanuvchi tomonidan yaratiladigan nostandart toifa yaratib olishimiz kerak. Buning bir qancha usullari mavjud, ya’ni klasslar yoki strukturalar bilan amalga oshirish mumkin. Masalan,
class Node{
public://klass ma’lumotlariga tashqaridan bo‘ladigan murojaatga ruxsat berish int info; // informatsion maydon Node* next;// ko‘rsatkichli maydon
};
Bu yerda biz Node nomli toifa yaratdik va ro‘yhatimiz butun sonlardan iborat. Endi ro‘yhat elementlarini shu toifa orqali e’lon qilsak bo‘ladi, ya’ni
Node *lst = NULL;// ro‘yhat boshi ko‘rsatkichi Node *last = NULL;// ro‘yhatga oxirgi kelib tushgan elementning ko‘rsatkichi
Endi shu belgilashlar orqali ro‘yhat hosil qilamiz Node * p = new Node; int numb = -1;
cout<<"son kiriting: "; cin>>numb;
p->info = numb;
p->next = NULL;
if (lst == NULL) {
lst = p;
last = p;
}
Chiziqsiz malumotlar tuzilmasi haqida tushuncha va klassifikatsiyasi.
|
| |
