04 mavzu shokirov shodmon shoyimovich informatika asoslari kafedrasi assistenti Mа’ruza rejasi

Navbatni amalga oshirish(xalqali massiv)

• 1

• 2

• Head

• Tail

• 1

• 2

• 3

• 2

• 3

• 2

• 3

• 4

• 3

• 4

• Bunday navbatda nechta element saqlash mumikin?

• ?

• «navbat bo’sh» va «navbat to’la» qanday farqlash mumkin?

• ?

• 3

• 4

• 5

• Navbatni amalga oshirish(xalqali massiv)

• const MAXSIZE = 100;
• struct Queue {
• int data[MAXSIZE];
• int head, tail;
• };

• Ma’lumotlar strukturasi:

• Navbatga qo’shish:

• int PushTail ( Queue &Q, int x )
• {
• if ( Q.head == (Q.tail+2) % MAXSIZE ) return 0;
• Q.tail = (Q.tail + 1) % MAXSIZE;
• Q.data[Q.tail] = x;
• return 1;
• }

• xalqani berkitish

• % MAXSIZE

• Navbat to’la, qo’shib bo’lmaydi

• Muvaffaqiyatli qo’shildi

• Navbatni amalga oshirish(xalqali massiv)

• Navbatdan tanlash:

• int Pop ( Queue &Q )
• {
• int temp;
• if ( Q.head == (Q.tail + 1) % MAXSIZE )
• return 32767;
• temp = Q.data[Q.head];
• Q.head = (Q.head + 1) % MAXSIZE;
• return temp;
• }

• navbat bo’sh

• birinchi elementni olish

• uni navbatdan o’chirish

• Ustuvor Navbat (Priority_queue)

• Biz hammamiz “Metan”da navbatda turganmiz. Navbatni har xil turlari mavjud. Masalan, prioritet bo’yicha navbat.
• Hayotdan misol: veteranlar va nogironlar navbatsiz o’tkaziladi (ularni prioriteti yuqori).

• Klassik navbatni ko’rib chiqamiz:
• birinchi kelgan birinchi ketadi (FIFO – first input, first output)

• Navbat har ikkala tomondan ochiq bo’ladi.

• Ustuvor Navbat (Priority_queue)

• Universal navbat har bir tuguni axborot qismi void turidagi ko’rsatkichdan iborat strukturadir:

• Bu yerda beg birinchi tugunga ko’rsatkich, end oxirgi tugunga ko’rsatkich, width ma’lumot hajmi, size navbatdagi elementlar soni

• struct slist_node
• {
• void* info;
• struct slist_node* next;
• };

• struct que
• {
• struct slist_node* beg;
• struct slist_node* end;
• int size;
• int width;
• };

• Ustuvor Navbat (asosiy funksiyalar)

• void pop(struct que*p) – navbat oxiridagi elementni o’chirish.
• void push(struct que*p, void* val) –navbat boshiga element qo’shish. Bu yerda val kiritilayotgan ma’lumotga ko’rsatkich.
• char* top(struct que p) – navbat boshidagi tugun axborot qismiga ko’rsatkich qaytarish.
• int empty(struct que p) – navbat bo’shligini tekshirish.
• int size (struct que p) – navbat elementlari soni.
• Bundan tashqari navbatni inisiallash uchun quyidagi sarlavhali funksiya kiritilgan.
• void ini_que(struct que* p,int n) – Bu yerda n kiritilayotgan ma’lumotlar hajmi.

• DEK(deque)

• Dek(deque = double ended queue, ikki tomonlama navbat) – bu ham chiziqli struktura bo’lib unda yangi elementni ikki tomonidan qo’shish mumkin.

• 1

• 2

• 3

• 4

• 5

• 6

• Dek ustida amallar:
• Boshidan element qo’shish (Push);
• Boshidan element o’chirish (Pop);
• Oxiridan element qo’shish (PushTail);
• Oxiridan element o’chirish (PopTail).

• Funktorlar

• Funktorlar - bu funksiyalar kabi murojaat qilish (chaqirish) mumkin bo’lgan ixtiyoriy tipdagi obyektlardir. Ya’ni () amali qayta yuklangan obyektlardir.

• 1.Funktorlarga oid dastur

• Davomi…

• 2.Funktorlarga oid dastur

• Davomi…