2. 9-ma’ruza Ro’yxat, Stek va Navbat

http://acm.tuit.uz/forum

• Misol

• Masala: [], {} va () uchta tiplardan tashkil topgan satr berilgan. Qavslar to’g’ri qo’yilganligini tekshiring (boshqa simvollarga qaramagan holda). Masalan:
• [()]{} ][ [({)]}
• Yechim: qavslar ichma ichligini hisoblagich. Agarda hisoblagich 0 bo’lsa, qavs to’gri qo’yilgan bo’ladi.

• Bu masalani uchta hisoblagich bilan qilsa bo’ladimi?

• ?

• [ ( { ) ] }
• (: 0 1 0
• [: 0 1 0
• {: 0 1 0

• [ ( { ) ] }

• ( ( ) ) ( )
• 1 2 1 0 1 0

• ( ( ) ) ( )

• ( ( ) ) ) (
• 1 2 1 0 -1 0

• ( ( ) ) ) (

• ( ( ) ) (
• 1 2 1 0 1

• ( ( ) ) (

• Qavslar masalasi

• Algoritm:
• Boshida stek bo’sh;
• Sikl boshida satr barcha simvollarini tartib bo’yiicha ko’rib chiqamiz;
• Agar navbatdagi simvol ochiladigan qavs bo’lsa, uni stek boshiga o’tkazamiz;
• Agar simvol yopiladigan qavs bo’lsa, stek boshini tekshiramiz: u yerda berilgan qavsga mos ochiluvchi qavs bo’lishi lozim (agarda bunday bo’lmasa, u holda xatolik);
• Agar stek oxiri bo’sh bo’lmasa, u holda ifoda noto’g’ri.

• [ ( ( ) ) ] { }

• [

• [

• (

• [

• (

• (

• [

• (

• (

• [

• (

• [

• {

• {

• Struktura-stek:

• const MAXSIZE = 100;
• struct Stack {
• char data[MAXSIZE]; // 100 ta simvolli stek
• int size; // elementlar soni
• };

• Element qo’shish:

• int Push ( Stack &S, char x )
• {
• if ( S.size == MAXSIZE ) return 0;
• S.data[S.size] = x;
• S.size ++;
• return 1;
• }

• xatolik: stekni to’ldirish

• Element qo’shish

• Xatolik yo’q

• Stekni amalga oshirish (massiv)

• Stekni amalga oshirish (massiv)

• char Pop ( Stack &S )
• {
• if ( S.size == 0 ) return char(255);
• S.size --;
• return S.data[S.size];
• }

• Boshidan elementni o’chirish:

• Bo’shmi yoki yo’q?

• int isEmpty ( Stack &S )
• {
• if ( S.size == 0 )
• return 1;
• else return 0;
• }

• xatolik: stek bo’sh

• int isEmpty ( Stack &S )
• {
• return (S.size == 0);
• }

• Dastur

• void main()
• {
• char br1[3] = { '(', '[', '{' };
• char br2[3] = { ')', ']', '}' };
• char s[80], upper;
• int i, k, error = 0;
• Stack S;
• S.size = 0;
• printf(“Qavsli ifodani kiriting > ");
• gets ( s );
• ... // qayta ishlovchi asosiy sikl
• if ( ! error && (S.size == 0) )
• printf("\nIfoda to’g’ri\n");
• else printf("\nnIfoda noto’g’ri\n");
• }

• Ochuvchi qavslar

• Yopuvchi qavslar

• U holda stekdan chiqarish

• Xatolik belgisi

• Satrni qayta ishlash (asosiy sikl)

• for ( i = 0; i < strlen(s); i++ )
• {
• for ( k = 0; k < 3; k++ )
• {
• if ( s[i] == br1[k] ) // agar ochilivchi qavs bo’lsa
• {
• Push ( S, s[i] ); // stekka kiritish
• break;
• }
• if ( s[i] == br2[k] ) // agar yopilivchi qavs bo’lsa
• {
• upper = Pop ( S ); // yoqori elementni olish
• if ( upper != br1[k] ) error = 1;
• break;
• }
• }
• if ( error ) break;
• }

• s satr barcha simvollari bo’yicha sikl

• Barcha qavslar bo’yicha sikl

• xatolik: stek bo’sh yoki kerakli qavs emas

• Xatolik bormi: u holda tekshirishga xojat yo’q

• Stekni amalga oshirish (ro’yxat)

• Element qo’shish:

• Struktura tuguni:

• struct Node {
• char data;
• Node *next;
• };
• typedef Node *PNode;

• void Push (PNode &Head, char x)
• {
• PNode NewNode = new Node;
• NewNode->data = x;
• NewNode->next = Head;
• Head = NewNode;
• }

• Boshidan elementni olish:

• char Pop (PNode &Head) {
• char x;
• PNode q = Head;
• if ( Head == NULL ) return char(255);
• x = Head->data;
• Head = Head->next;
• delete q;
• return x;
• }

• Asosiy dasturni o’zgartirish:

• Stack S;
• S.size = 0;
• ...
• if ( ! error && (S.size == 0) )
• printf("\Ifoda to’g’ri\n");
• else printf("\nIfoda noto’g’ri \n");

• PNode S = NULL;

• (S == NULL)

• stek bo’sh

• Stekni amalga oshirish (ro’yxat)

• Navbat

• Biz navbat bilan ko’p joylarda duch kelamiz: magazinda, o’qishda, ishda va hokazo. Odatda biz unga e’tibor bermaymiz. Dasturiy tizimlarda ham bu navbat tushunchasi ishlatiladi.
• Masalan, hujjatni chop etish uchun printerga jo’natsak, u navbatga turadi.

• http://acm.tuit.uz/forum

• Navbat bizga nima uchun kerak!

• !

• Alabatta navbat 1-o’rinda tartib o’rnatish uchun zarur.

• Navbat qanday ishlaydi!

• !

• Navbat

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

• http://acm.tuit.uz/forum

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

• Navbat har ikkala tomondan ochiq bo’ladi.

• Navbat

• http://acm.tuit.uz/forum

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

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

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

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

• Navbat (asosiy funksiyalar)

• http://acm.tuit.uz/forum

• 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.