|
Stek, navbat va deklarni bog’langan ro’yhat ko’rinishida ifodalash
|
| bet | 2/5 | | Sana | 23.01.2024 | | Hajmi | 1,27 Mb. | | #144058 |
Bog'liq Nishonov Ma\'lumotlar tuzilmasi va algoritmlar 1-chi Mus Stek, navbat va deklarni bog’langan ro’yhat ko’rinishida ifodalash
Steklar
Stek - chiziqli ma’lumotlar tuzilmasi bo’lib, ma’lumotlarni kiritish va chiqarish uning bir tomonidan amalga oshiriladi. Bunday stek kafeteriyadagi tarelkalar to’plamini eslatadi. Yangi elementlar stekning uchiga qo’yiladi va yuqori qismidan olinadi. Oxirgi qo’yilgan element stek uchidan birinchi bo’lib olinadi. Shu sababli, stek LIFO (last in first out) tuzilishidagi ma’lumotlar tuzilmasi bo’ladi, ya’ni, “oxirgi kelgan birinchi ketadi” prinsipi bo’yicha ishlaydi.
Stek o’lchami cheklangan bo’lsa, elementni stekka qo’yilishi stekda kamida bitta elementga joy bo’lgan holdagina amalga oshiriladi. Shuning uchun stek ustida amal bajarishdan oldin stek holatini tekshirish lozim bo’ladi,ya’ni
Stekka element kiritilishidan oldin joy borligini tekshirish;
Stekdan elementni o’chirishdan oldin element borligini tekshirish.
Steklar bilan ishlash uchun C++ tilida tayyor kutubxona mavjud bo’lib, unga dastur boshida #include deb murojaat qilish kerak. Dasturda stek e’lon qilish uchun quyidagicha yozish kerak.
_stek_nomi;"> Stack <toifa> stek_nomi;
Misol uchun,
_stek1;"> Stack stek1;
Stekda quyidagi amallar o’rinli:
Clear() - Stekni tozalash.
isEmpty() – Stekni bo’shlikka tekshirish
push(el) - stekka element kiritish.
pop() – Stekdan element o’chirish.
topEl() - stekni uchidagi elementni o’chirmasdan o’qib olish.
Ulardan foydalanish esa quyidagicha:
stek1.push(x) – x ni stekka tashlash;
Stekka element qo’shish va chiqarish amallari quyidagi 4.1 – rasmda ko’rsatib berilgan.
– rasm. Stekda bajarilgan amallar ketma – ketligi.
Unda bo’sh stekka 10 soni kiritilgan. Keyin stekka 5 soni kiritilgan, bu son 10 ni ustiga joylashadi, undan keyin chiqarish amali bajarilganda, stekdan 5 soni o’chiriladi. Chunki u 10 sonining yuqorisida joylashgan edi va 5 soni stekdan chiqariladi. Stekka 15 va 7 soni ketma - ket qo’yilgandan so’ng, eng yuqorida 7 soni bo’ladi. Natijada chiqarish operatsiyasi amalga oshirilganda 7 soni stekni tark etadi. Chiqarish amalidan keyin stekda 10 soni 15 ning ostida qoladi.
Umuman olganda, stek ma’lumotlar saqlashda va ma’lumotlar to’plamidan elementlar teskari tartibda chiqarib olinadigan holatlarda ko’p foydalaniladi.
Stekning qo’llanilishlariga misol qilib dasturda ajratkichlarni moslashtirishni olish mumkin. Bu juda ham muhim masala. Chunki, ajratkichlar ixtiyoriy kompilyatorning qismi hisoblanadi. Agar ajratkichlar bir– biriga moslashtirilmagan bo’lsa, hech bir dastur to’g’ri ishlamaydi.
C++ dasturlash tilida biz quyidagi ajratkichlarga egamiz: oddiy qavslar “(“va”)”, kvadrat qavslar “[“va”]”, figurali qavslar “[“va”]”, va izoh ajratkichlar “/*” va “*/”. Quyida C++ dasturlash tilida ajratkichlar to’g’ri qo’llanilganligiga misol keltirilgan.
a = b + (c - d) * (e - f);
g[10] = h[i[9]] + (j + k) * l;
while (m < (n[8] + o)) { p = 7; /* initialize p */ r = 6; }
Quyidagi misol moslashtirilmagan ajratkichlarga misol bo’la oladi:
a = b + (c - d) * (e - f));
g[10] = h[i[9]] + j + k) * l;
while (m < (n[8) + o]) { p = 7; /* initialize p */ r = 6; }
Konkret ajratgich o’z juftligidan boshqa ajratgichlar bilan ajratilishi mumkin, ya’ni ajratkichlar ichma – ich qo’yilgan bo’lishi mumkin. Shunday qilib, ajratkich o’z juftligi bilan moslashganmi yoki yo’qligini, barcha ajratkichlar juftliklari aniqlangandan keyin bilish mumkin.
Masalan, sikldan foydalanilganda boshlang’ich qavs o’z juftligiga ega ekanligini barcha ichki qavslar juftliklari yopilgandan keyin aniqlash mumkin.
while (m < (n[8] + o))
Ajratkichlarni qiyoslash algoritmi quyidagicha:
belgilar C++ dastur matnidan o’qiladi va u ochuvchi ajratkich bo’lsa, ular stekka tashlanadi. Agar yopuvchi ajratkich bo’lsa, u ochuvchi ajrakich bilan solishtiriladi va stekdan chiqariladi.
Agar ular mos tushsa, qayta ishlash davom etadi, mos tushmasa qayta ishlash hatolik haqidagi habar bilan to’htatiladi.
Dastur ohiriga yetganda C++ dasturini qayta ishlash muvoffaqiyatli tugatilgan hisoblanadi va stek bo’sh bo’ladi. Ushbu algoritmni quyida psevdokodini keltiramiz.
Ajratkichlarning moslashuvini tekshirish kodi.
read character ch from file; while not end of file
if ch is ‘(’, ‘[’, or ‘{’ push(ch);
else if ch is ‘)’, ‘]’, or ‘}’
if ch and popped off delimiter do not match failure;
else if ch is ‘/’
read the next character; if this character is ‘*’
skip all characters until “*/” is found and report an error if the end of file is reached before “*/” is encountered; else ch = the character read in;
continue; // go to the beginning of the loop;
// else ignore other characters; read next character ch from file; if stack is empty
success; else failure;
rasmda yuqoridagi algoritmni quyidagi ifodani qayta ishlashga qo’llanganda hosil bo’lgan qayta ishlash ko’rsatilgan
s=t[5]+u/(v*(w+y));
rasmdagi birinchi ustunda sikl ohiridan keyingi belgigacha bo’lgan stek tarkibi ko’rsatilgan. Birinchi qator fayldagi va stekdagi boshlang’ich holatni ko’rsatilgan. Ch o’zgaruvchi s yozuv faylining birinchi simvoliga initsializatsiya qilinadi, siklning birinchi iteratsiyasida simvol qabul qilinmaydi. Bu holat 4.2 rasmning ikkichi qatorida ko’rsatilgan. Undan keyin tenglik belgisi o’qiladi. U ham qabul qilinmaydi, chunki u ajratkich emas. Birinchi ajratkich (kvadrat qavs ) 5-qadamda o’qiladi va stekka birinchi element bo’lib joylashadi. Ifodaning barcha
elementlari o’qib chiqilgandan so’ng ajratkichlar birin – ketin stekka joylanadi, va bu jarayon oxirgi nuqta vergulgacha davom etadi.
.
4.2-rasm. Ajratkkichlar moslashtirish algoritmi yordamida s=t[5]+u/(v*(w+y)); ifodani tekshirish
Stekni qo’llanilishiga boshqa misol qilib, juda katta sonlarni qo’shish masalasini ko’rish mumkin. Bunday sonlar butun toifadagi o’zgaruvchilar uchun mumkin bo’lgan chegaralardan chiqib ketadi. Shuning uchun ularni qo’shish to’g’risida gap ham bo’lishi mumkin emas. Masalan, 18,274,364,583,929,273,748,459,595,684,373 va 8,129,498,165,026,350,236
sonlari berilgan. Ularni qo’shish muammosini sonlarni raqamlar qatori sifatida tasvirlab, raqami bo’yicha ikkita stekka ketma – ket joylab qo’shish mumkin bo’ladi. Bunda raqam sifatida sonlarni tartib xonalari (birlar , o’nlar, yuzlar…) olinadi. Bu algoritmning psevdokodi quyidagicha:
|
| |
