Vektorlar va ko’p o’lchovli massivlar bilan ishlash, ro‘yxat, navbat va stek Ma’ruza rejasi

Dastur kodi

#include

#include

#include

struct Stack {

char data[100]; // 100 ta simvolli stek

int size; // elementlar soni

};

int Push ( Stack &S, char x )

{

if ( S.size == 100 ) return 0;

S.data[S.size] = x;

S.size ++;

return 1;

}

char Pop ( Stack &S )

{

if ( S.size == 0 ) return char(255);

S.size --;

return S.data[S.size];

}

int isEmpty ( Stack &S )

{

if ( S.size == 0 )

return 1;

else return 0;

}
int 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 );

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;

}

if ( ! error && (S.size == 0) )

printf("\nError\n");

else printf("\nExcelent\n");

getch();

return 0;

}
Navbat

Navbat deb shunday strukturaga aytiladiki, navbatga kelib tushgan birinchi elementga birinchi bo‘lib xizmat ko‘rsatiladi va navbatdan chiqariladi. Navbatga biz kundalik hayotda magazinda, o‘qishda, ishda har doim duch kelamiz. Buni albatta dasturlashda ham ishlatish mumkin. Masalan, siz printerga bir vaqtning o‘zida uchta hujjatni chop etish bo‘yicha buyruq berdingiz. Ular o‘z navbatida navbatida hosil qiladi va eng birinchi navbat (masalan, yuzdan bir sekun oldin) olgani birinchi chop etiladi.

Navbat boshi – massivdan o‘chiriladigan elementning raqami.

Navbat oxiri – navbatga kiritiladigan massiv elementi.

Mazkur ko‘rinishdagi xizmat ko‘rsatishni navbat, ya’ni FIFO (First input-First output, ya’ni birinchi kelgan – birinchi ketadi) nomlash qabul qilingan. Navbat har ikkala tomondan ochiq bo‘ladi.

Navbatni amalga oshirish uchun ikkita ko‘rsatkichdan foydalaniladi: h boshi va t oxiri.

Qo‘shish oxiridan va o‘chirish ro‘yxat boshidan amalga oshiriladi. Agarda navbat bo‘sh bo‘lsa, h va t ning qiymati nol ga teng bo‘ladi (ya’ni navbat bo‘sh bo‘ladi). Shuning uchun element qo‘shishda ro‘yxat o‘zgarmaydi.

Navbatlar asosan arifmetik ifodali masalalarni tahlil qilishda, prebor (ajratish)li masalalarda hamda graflardagi algoritmlarda ishlatiladi.

Navbatni eng oddiy ko‘rinishda chegaralangan massiv A[0..N-1] ko‘rinishida tasvirlash mumkin.

Navbatni oxiridan yangi element qo‘shish uchun h va t zarur. Buning uchun qiymatni yozamiz va t ni oshiramiz:

A[t] = k;

t = (t + 1) mod N;

0, 1 va 2 dan tashkil topgan navbatga yangi element qo‘shganda k = 3 ga teng bo‘ladi:

Navbat boshidan o‘chirish:

k = A[h];

h = (h + 1) mod N;

Masalan, yuqoridagi navbatdan 0 elementini o‘chirgandan so‘ng quyidagini olamiz:

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

struct slist_node

{

void* info;

struct slist_node* next;

};

Navbat o‘zi alohida struktura sifatida kiritilgan.

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.

Asosiy funksiyalar: