Ishdan maqsad: Bog'langan ro'yxat. Birgalikda bog'langan ro'yxat bilan ishlashni o’rganish va ularni tadqiq qilish.
Qo‘yilgan masala: Bog'langan ro'yxat va birgalikda bog'langan ro'yxatlar yaratish va ularga doir misollarning dasturini ishlab chiqish.
Ish tartibi:
Dek 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 (2.3-rasm).
2.3-rasm. Dek tuzilmasi
Dek ustida bajariladigan amallar: Chapdan element kiritish.
O‘ngdan element kiritish.
Chapdan element chiqarish.
O‘ngdan element chiqarish.
Dek bo‘shligini tekshirish.
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 Dekka nechta element kiritilishi aniqlanadi – n, i=0.
i++; agar i Agar in/2 bo‘lsa, dekning o‘ng tomonidan kiritiladi, 2-qadamga o‘tish.
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.
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.
b[] massiv elementlarini dekka o‘ng tomondan kiritamiz.
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<<"\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 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< cout< } int main(int argc, char *argv[]) { int n,s;cout<<"n="; cin>>n; for(int i=0;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 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