Deque qisqartirish d ouble- e
Download 24.68 Kb.
|
Azamat Soliyev. Mustaqil ish
|
Mavzu: Dequeni bog`langan ro`yxat ko`rinishida amalga oshirish Reja: 1. Deque tushunchasi 2. Deque ning Navbat tushunchasidan farqi 3. Statik va yarimstatik ma’lumotlar tuzilmasi Deque qisqartirish d ouble- e eded que UK. Ikkala uchli navbat - bu dinamik o'lchamlari bilan ketma-ket konteynerlar bo'lib, ular ikkala uchida (old tomoni yoki orqa tomoni) kengaytirilishi yoki qisqarishi mumkin. Muayyan kutubxonalar deklarni har xil yo'llar bilan amalga oshirishi mumkin , odatda dinamik qatorning ba'zi bir shakllari. Ammo har qanday holatda ham, ular alohida elementlarga tasodifiy kirish iteratorlari orqali to'g'ridan-to'g'ri kirishga imkon beradi, kerak bo'lganda idishni kengaytirish va kontraktatsiya qilish orqali saqlash avtomatik ravishda amalga oshiriladi. Shuning uchun ular vektorlarga o'xshash funktsiyani ta'minlaydi, lekin elementlarning samarali kiritilishi va o'chirilishi bilan ketma-ketlikning boshida va nafaqat uning oxirida. Ammo, vektorlardan farqli o'laroq , deklarning barcha elementlarini tutashgan joylarda saqlashlari kafolatlanmagan: deque ko'rsatgichni boshqa elementga almashtirish orqali elementlarga kirish aniqlanmagan xatti-harakatlarni keltirib chiqaradi . Ikkala vektor hamva deklar juda o'xshash interfeysni taqdim etadi va shu kabi maqsadlarda ishlatilishi mumkin, ammo ichki jihatdan ikkalasi ham har xil usulda ishlaydi: Vektorlar o'sish uchun vaqti-vaqti bilan qayta taqsimlanishi kerak bo'lgan bitta massivni ishlatganda, deque elementlari turli bo'laklarga tarqalishi mumkin saqlash, konteyner zarur bo'lgan ma'lumotlarni o'z ichiga olgan holda, uning har qanday elementlariga doimiy ravishda to'g'ridan-to'g'ri kirishni ta'minlash uchun va bir xil ketma-ket interfeys bilan (iteratorlar orqali). Shuning uchun deeklar vektorlarga qaraganda ichki jihatdan biroz murakkabroq , ammo bu ularga ma'lum sharoitlarda, ayniqsa, qayta taqsimlash qimmatga tushadigan juda uzoq ketma-ketliklar bilan yanada samarali o'sishga imkon beradi. 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 korinishi 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 Elementlarni boshidan yoki oxiridan boshqa joylarga tez-tez kiritish yoki olib tashlashni o'z ichiga olgan operatsiyalar uchun deklar yomonroq ishlaydi va ro'yxatlar va oldinga siljishlarga qaraganda kamroq izchil va mos yozuvlarga ega . Bog'langan ro'yxat yordamida navbatni amalga oshiruvchi dastur quyidagicha berilgan #include using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert() { cout<<"Insert the element in queue : "< cin>>val; if (rear == NULL) {
rear = (struct node *)malloc(sizeof(struct node)); rear->next = NULL;
rear->data = val; front = rear;
} else { temp=(struct node *)malloc(sizeof(struct node));
rear->next = temp; temp->data = val;
temp->next = NULL; rear = temp;
}
void Delete() { temp = front;
if (front == NULL) { cout<<"Underflow"< }
else
temp = temp->next; cout<<"Element deleted from queue is : "< free(front); front = temp;
} else { cout<<"Element deleted from queue is : "< free(front); front = NULL;
rear = NULL; }
}
if ((front == NULL) && (rear == NULL)) { cout<<"Queue is empty"< return; }
cout<<"Queue elements are: "; cout< temp = temp->next;
}
int main() { cout<<"1) Insert element to queue"< cout<<"2) Delete element from queue"< cout<<"3) Display all the elements of queue"< cout<<"4) Exit"< do {
switch (ch) {
case 1: Insert(); break;
case 2: Delete(); break;
case 3: Display(); break;
case 4: cout<<"Exit"< break;
default: cout<<"Invalid choice"< }
} while(ch!=4); return 0;
}
Yuqoridagi dasturning natijasi quyidagicha
2) Delete element from queue
3) Display all the elements of queue 4) Exit
Enter your choice : 1 Insert the element in queue : 4
Enter your choice : 1 Insert the element in queue : 3
Enter your choice : 1 Insert the element in queue : 5
Enter your choice : 2 Element deleted from queue is : 4
Enter your choice : 3 Queue elements are : 3 5
Enter your choice : 7 Invalid choice
Enter your choice : 4 Exit
Yuqoridagi dasturda Insert () funktsiyasi elementni navbatga qo'shadi. Agar orqa NULL bo'lsa, navbat bo'sh va bitta element qo'shiladi. Aks holda, kerakli element bilan orqa tomondan tugun kiritiladi va keyin u tugun orqaga o'rnatiladi. Bu quyida ko'rsatilgan int val; cout<<"Insert the element in queue : "< cin>>val; if (rear == NULL) {
rear = (struct node *)malloc(sizeof(struct node)); rear->next = NULL;
rear->data = val; front = rear;
} else { temp=(struct node *)malloc(sizeof(struct node));
rear->next = temp; temp->data = val;
temp->next = NULL; rear = temp;
}
Delete () funktsiyasida, agar navbatda elementlar bo'lmasa, u quyi oqim hisoblanadi. Agar navbatda bitta element o'chirilsa va old va orqa NULLga o'rnatilsa. Aks holda, oldingi element o'chiriladi va oldingi element keyingi elementga yo'naltiriladi. Bu quyida ko'rsatilgan - void Delete() {
temp = front; if (front == NULL) {
cout<<"Underflow"< return;
} else if (temp->next != NULL) {
temp = temp->next; cout<<"Element deleted from queue is : "< free(front); front = temp;
} else { cout<<"Element deleted from queue is : "< free(front); front = NULL;
rear = NULL; }
}
temp = front; if ((front == NULL) && (rear == NULL)) {
cout<<"Queue is empty"< return;
}
while (temp != NULL) { cout< temp = temp->next; }cout< Main ()funktsiyasi foydalanuvchiga navbatni qo'shishni, o'chirishni yoki ko'rsatishni xohlasa, tanlov imkoniyatini beradi. Foydalanuvchining javobiga ko'ra, tegishli funktsiya switch yordamida chaqiriladi. Agar foydalanuvchi yaroqsiz javobni kiritsa, u holda chop etiladi. Buning uchun kod parchasi quyida keltirilgan - int main() {
int ch; cout<<"1) Insert element to queue"< cout<<"2) Delete element from queue"< cout<<"3) Display all the elements of queue"< cout<<"4) Exit"< do {
cout<<"Enter your choice : "< cin>>ch;
switch (ch) { case 1: Insert();
break; case 2: Delete();
break; case 3: Display();
break; case 4: cout<<"Exit"< break; default: cout<<"Invalid choice"< }
return 0; |
