O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Guruh:061-19
Topshirdi:Abdusattarova Gulchehra
Qabul qildi:Dilfuza G’anixodjayeva
Fan: MA’LUMOTLAR TUZILMASI VA ALGORITMLAR
MUSTAQIL ISH
Mavzu: Yarim statik ma’lumotlar tuzilmalari
Yarim statik ma’lumotlar tuzilmalari.
Stek - massiv tuzilmasidan farqli ravishda, elementlarni kiritish yoki
chiqarib tashlashga imkon beradigan o’zgaruvchan o’lchamning chiziqli
tuzilmasidir, ya’ni stekda ma’lumotlar hajmi dasturning bajarilishi vaqtida uyg’un
ravishda oshishi va kamayishi mumkin.
Stekli tuzilmaning xususiyati shundan iboratki, elementlardan erkin
foydalanish, elementlarni kiritish va chiqarib tashlash faqat tuzilmaning bir
tomonidan - stek cho’qqisidan mumkin bo’ladi. SHuning uchun stekka oxirida
kiritilgan element birinchi bo’lib o’qiladi yoki tanlanadi. Bunday tuzilmada
axborot «oxirida keldi, birinchi ketdi» tamoyili bo’yicha qayta ishlanadi. Stekning
tuzilmasini ba’zan LIFO (inglizcha Last In, First Out) tipidagi tuzilma deyiladi, bu
qachonki faqat yuqoridagi likobchani olish mumkin bo’lgan likobchalar to’plami
misolida yaxshi tushuniladi. Avval yuqoridagi likobchani, so’ngra keyingisini
olish mumkin. Likobchalar to’plamning yuqori qismiga bittadan qo’shiladi.
26
Stekning tuzilmasi erkin foydalanish cheklangan ma’lumotlar tuzilmasi
hisoblanadi, chunki faqat stekning cho’qqisida joylashgan elementdan erkin
foydalanish mumkin bo’ladi. Bu element joriy element deb ataladi. Joriy
elementning joyi to’g’risidagi axborot odatda stekning bosh uyasida joylashadigan
stek cho’qqisining ko’rsatkichi (SCHK)da saqlanadi.
Steklarni saqlash uchun ma’lumotlarni ham ketma-ket, ham bog’langan
taqdim etishidan foydalanish mumkin. Ketma-ket taqdim etishdan foydalanganda
stekning eng oxirgi o’lchamini bilish zarur. Ko’zda tutiladigan ushbu eng chekka
o’lcham uchun moslab xotira zahiraga olinadi va uning ichida stek oshadi va
qisqaradi. Blokning birinchi uyasi stek cho’qqisining ko’rsatkichini o’z ichiga
oladi. Stek bo’sh bo’lganida ko’rsatkich o’zini-o’zi ko’rsatadi. Har bir yangi
elementning kiritilganida cho’qqi ko’rsatkichi bir birlikka ko’payadi. 1.2-
chizmada xotira bloki va unda joylashgan boshlang’ich stek, shuningdek kiritilgan
va chiqarib tashlangan elementli steklar tasvirlangan. Stekdan erkin foydalanishni
shunday qilib tashkil etish mumkinki, bunda cho’qqi ko’rsatkichining qiymati stek
mavjud bo’lgan hamma vaqt davomida o’zgarmas bo’lib qoladi. Bunday holatda
erkin foydalanish har doim stek uchun moslab zahiraga olingan xotira blokining
bitta uyasiga amalga oshiriladi. Shu uyaga cho’qqi ko’rsatkichi o’rnatiladi, unda
stekning joriy (eng yuqori) elementi saqlanadi. Element kiritilganida yoki chiqarib
1.2.1 chizma. Stekni ketma-ket taqdim etganda uning oshishi va kamayishi
Bo’sh makon
A
n-1
…
A
2
A
1
Cho’qqi ko’rsatkichi
Bo’sh makon
A
n-1
A
n-1
…
A
2
A
1
Cho’qqi ko’rsatkichi
Bo’sh makon
A
n-1
A
n-1
A
n-1
…
A
2
A
1
Cho’qqi ko’rsatkichi
27
tashlanganida stekning barcha elementlari xotira blokining ichida mos ravishda
pastga yoki yuqoriga siljiydi. Bunday holatda kiritish operatsiyasini «itarib
kirgizish», chiqarib tashlash operatsiyasini esa - «itarib chiqarish»
deyiladi.Shuning uchun tuzilmaning buzilishi uning xususiyatlari yo’qolishiga va
oqibatda obyektning nomuvofiq ta’riflanishiga olib keladi.
Ketma-ket taqdim etishning kamchiligi shundan iboratki, stekning to’lib
ketishi xavfi hamisha bo’ladi; aks holda zahiraga olingan xotiraning bir qismi
ishlatilmay qoladi. Ma’lumotlarni bog’langan taqdim etishdan foydalanganda stek
uchun moslab xotirani oldindan zahiraga olishning zarurati bo’lmaydi. Stekning
barcha elementlari xotira bo’yicha yoyib tashlanadi va o’zaro ko’rsatkichlar bilan
bog’lanadi. SCHK stekning eng yuqoridagi elementi joylashgan uyaga ko’rsatadi.
Elementlar kiritilganida yoki chiqarib tashlanganida cho’qqi ko’rsatkichining
qiymati o’zgaradi. Yangidan kiritilayotgan element xotiraning ixtiyoriy bo’sh
uyasiga joylashtiriladi va u mos ravishda bog’langan ro’yxat ko’rsatkichlarini
o’zgartirish yo’li bilan stekka qo’shiladi. Ma’lumotlarni bog’langan taqdim etishda
stek cheksiz oshishi mumkin. Ma’lumotlar mazmuniy mohiyatini baholashsiz
kiritish va chiqarib tashlash operatsiyalarini tezlik bilan bajarish talab etilgan
SChK
A
n-1
…..
A1
A
n+1
A
n
…..
A1
A
n
A
n-1
…..
A1
SChK
A
n+1
SChK
Bo’sh makon
Bo’sh makon
Bo’sh makon
1.2.2-chizma O’zgarmas ko’rsatkich bilan stekning oshishi va kamayish.
28
vaziyatlarda stekning tuzilmasi juda qulay keladi. Asosiy ro’yxatdan o’chirilgan
ixtiyoriy uya bo’sh xotira stekining cho’qqisiga qo’shiladi. Bo’sh xotira stekiga
kiritilgan so’nggi uya asosiy ro’yxatning yangi yozuvini joylashtirish uchun
birinchi bo’lib ishlatiladi. Bo’shagan uyalarni bo’sh xotira stekiga kiritilishini
boshqaradigan algoritm ko’pincha «axlat yig’uvchi» deb ataladi.
Stekli tuzilmalar ichiga qo’yilgan kichik dasturlar va ko’p pog’onali
uzilishlarni amalga oshirishda translyatorlarda, shuningdek algoritmlari rekursiv
usul bilan eng yaxshi ta’riflanadigan vazifalarni echishda keng qo’llaniladi.
Navbat bu o’zgaruvchan o’lchamdagi chiziqli tuzilmadir. Elementlarni
navbatdan chiqarib tashlashga bir tomondan - navbatning boshidan ruxsat beriladi.
Elementlarni kiritish faqat teskari tomonga - navbatning oxiriga bo’lishi mumkin.
Bunday tuzilmadagi ma’lumotlar ular kelib tushishiga qarab «birinchi keldi,
birinchi ketdi» tamoyili bo’yicha qayta ishlanadi. Adabiyotda navbat tuzilmasini
FIFO (inglizcha First In, First Out) tipidagi tuzilma deyiladi. Svetoforning
ochilishini kutayotgan avtomobillar navbati an’anviy misol hisoblanadi.
Svetoforga birinchi bo’lib kelgan avtomobil chorrahadan birinchi bo’lib o’tib
ketadi, ya’ni navbatdan chiqariladi. Oxirida kelgan va navbatning oxirida o’tib
ketishni kutayotgan avtomobilb chorrahadan oxirgi bo’lib o’tadi.
Navbat elementlaridan erkin foydalanish boshlanish va tugash ko’rsatkichi
bo’yicha amalga oshiriladi. Boshlanish ko’rsatkichi birinchi bo’lib chiqarib
tashlanadigan yoki o’qiladigan navbat elementini ko’rsatadi. Tugash ko’rsatkichi
navbatdagi so’nggi yozuvdan keyin keladigan xotiraning bo’sh uyasiga o’rnatiladi.
Yangi kelgan yozuv, ya’ni navbatning yangi elementi aynan shu uyaga
joylashadi. Navbat tuzilmasini amalga oshirish uchun KOMPYUTER xotirasida
ma’lumotlarni ham ketma-ket, ham bog’langan taqdim etishdan foydalaniladi.
29
1.2.3-chizma. Navbat
Navbatga ketma-ket taqdim etishda stekdagi kabi xotira bloki z ahiraga
olinadi, uning ichida navbat oshishi va kamayishi mumkin. Har bir yangi element
kiritilishi bilan tugash ko’rsatkichi birlikka o’zgaradi. Yangi elementlarni kiritish
natijasida navbat tugashi ko’rsatkichi zahiraga olingan xotira blokining oxiriga
etsa, u blokning boshiga ko’chiriladi. Agar tugash ko’rsatkichi boshlanish
ko’rsatkichiga etib olsa, bu xotira bloki to’lganligini anglatadi.
Elementni chiqarib tashlashda boshlanish ko’rsatkichi birlikka o’zgaradi.
Agar boshlanish ko’rsatkichi tugash ko’rsatkichi bilan mos tushsa, navbat bo’sh
bo’ladi. Ma’lumotlarni ketma-ket taqdim etishda zahiraga olingan xotira bloki
ichidagi navbatni joylashtirish sxemasi 1.2.3-chizmada tasvirlangan. Shu yerning
o’zida navbat elementlarini kiritish va chiqarib tashlashda ko’rsatkichlar qanday
30
o’zgarishi ham ko’rsatilgan.
Navbatni bog’langan taqdim etishda xotirani oldindan zahiraga olish talab
etilmaydi. Navbatni shakllantiruvchi yozuvlar ixtiyoriy bo’sh xotira uyalarida
joylashadi va o’zaro ko’rsatkichlar bilan bog’lanadi. Bunday navbat cheksiz
oshishi mumkin. Elementlarni kiritish va chiqarib tashlashda faqat boshlanish va
tugash ko’rsatkichlarining qiymati va aloqa ko’rsatkichlarining qiymati (AS)
o’zgaradi, xolos.
Navbat tuzilmasi ma’lumotlarni qayta ishlashning turli vazifalarini echishda
ishlatiladi. Masalan, vaqtni taqsimlash bilan hisoblash tizimini modellash navbat
tuzilmasi ishlatiladigan an’anviy vazifalardan biri hisoblanadi. Bunday tizimda
ko’pchilik foydalanuvchilar bir vaqtning o’zida bitta asosiy xotiradan foydalanib
yagona markaziy protsessor bilan ishlaydi. Bajarilishni kutayotgan foydalanuvchilarning
dasturlari navbatni tashkil etadi. Navbatni tashkil etish va
unga xizmat ko’rsatishning ishlab chiqilgan tamoyili ko’p jihatdan bunday tizim
ishlashining samaradorligini belgilab beradi.
Ko’rsatkichlar ishtirok etadigan dasturlarga misollar.
Stekka element qo’shish, olib tashlash
procedure udals; begin
top:=top
^
.next
end.
Stek elementlarini qo’shish
procedure rasps;
{elementlarni teskari tartiblab chiqarish} begin
kop:=top;
while kop
<>NIL do
begin
writeln (kop
^
.INF);
kop:=kop
^
.next
end;
31
Stekni ishlatganda quyidagi xolatlar yuzaga kelishi mumkin:
1.
stekning tulib ketishi, ya’ni stek xotirasida joy kolmaslik.
2.
Tulmaslik xolati stekdan u bush bulganda ukishga xarakat
kilish. Navbat-ma’lumotlarning shunday tuzilmasiki, uning bir tomonida
element qo’shib borilsa, ikkinchi tomonidan olib tashlanadi.
Bunday tuzilmani tashkil kilish uchun LEFT va RIGHTo’zgaruvchilari
ishlatiladi.
Navbatga
element kushilayotganda,
elementlar
RIGHT
o’zgaruvchisining qiymatiga mos xotiraga joylashadi. SHunday kilib, RIGHT
xotiraning bush joyini kursatadi. Navbatdan elementlarni tanlash navbatning
keyingi elementini kursatuvchi qiymat orqali amalga oshadi. Agar LEFT qiymati
RIGHT qiymatiga teng bo’lsa, u xolda navbat bush xisoblanadi.
Navbat ustida xam quyidagi amallarni bajarish mumkin:
navbatni tashkil kilish;
navbatga kushish;
navbatdan olib tashlash;
navbatga elementlarini kurish.
Shunday qilib, navbat aylana shaklidagi ro’yxatdan iboratdir.
Do'stlaringiz bilan baham: |