Savollar variant №11 Saralash va uning usullari. Yarimstatik ma’lumotlar tuzulmasi. Stek

SAVOLLAR Variant №11

1.Saralash va uning usullari.

2.Yarimstatik ma’lumotlar tuzulmasi.Stek

3.Statik turdagi ma’lumotlar.Ma’ssivlar va ular ustidagi amallar

JAVOB:
2.Yarimstatik ma’lumotlar tuzulmasi.Stek
Фараз қилайлик, стек, дек ва навбатлар дастурда массив кўринишида ифодаланган бўлсин, у ҳолда мазкур маълумотлар тузилмаси яримстатик маълумотлар тузилмасига мисол бўлади.

Яримстатик тузилма нима???

Нима сабабдан яримстатик тузилма дейилади???

Бундай тузилма узунликлари олдиндан берилади (статиклик шарти), лекин тузилмани ташкил этувчи элементлар сони дастур бажарилиши мобайнида вақтга ва рўйхат узунлигига боғлиқ равишда ўзгариб туриши мумкин (динамиклик шарти).

Yarimstatik ma’lumotlar tuzilmasini quyidagicha tavsiflash mumkin:  
-- o’zgaruvchan  uzunlikka  ega  va  uni  o’zgartiruvchi  oddiy  funksiyalariga 
ega; 
--tuzilmaning uzunligini o’zgartirish ma’lum bir chegarada, ya’ni qandaydir 
bir maksimal qiymatdan oshmagan holda amalga oshirilishi mumkin; 
Agar  yarimstatik  tuzilmani  mantiqiy  jihatdan  qaraydigan  bo’lsak,  u  holda 
chiziqli  ro’yhat  munosabati  bilan  bog’langan  ma’lumotlar  ketma-ketligi 
tushuniladi.  Xotirada  yarimstatik  ma’lumotlar  tuzilmasini  fizik  jihatdan 
tasvirlaydigan bo’lsak, bu xotirada slotlarning oddiy ketma-ketligidir, ya’ni har bir 
element  xotirada  navbatdagi  slotlarda  joylashadi.  Yarimstatik  MTni  fizik 
tasvirlashning  yana  bir  ko’rinishi  bir  tomonlama  bog’langan  ro’yhat  (zanjir) 
ko’rinishida ifodalash mumkin, ya’ni bunda har bir navbatdagi elementning adresi 
joriy elementda ko’rsatiladi. Bunday tasvirlashda tuzilmaning uzunligiga 34 
cheklanish unchalik qattiq qo’yilmaydi. Bunday tuzilmalarga – navbat, stek, 
dek va satrlar kiradi.

Stek – massiv tuzilmasidan farqli ravishda, elementlarni kiritish yoki chiqarib tashashga imkon beradigan o’zgaruvchan o’lchamning chiziqli tuzilmasidir, ya’ni stekda ma’lumotlar hajmi dasturning bajarilishi vaqtida uyg’un ravishda oshishi vakamayishi 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 “oxoroda keldi, birinchi ketdi” tamoyili bo’yicha qayta ishlanadi. Stekning tuzilmasini ba’zan LIFO (inglizcha Last In, First Out) tipidagi tuzilma deyiladi, bu qachonki faqat yuqoridai 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. Stekning tuzilmasi erkin foydalanish cheklangan ma’lumotlar tuzilmasi hisoblanadi, chunki faqat stekning cho’qqisida joylashkan elementdan erkin fordalanish 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’rsatkichida(SCHK) 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 zahira xotiraga olinadi, 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 element kiritilganda cho’qqi ko’rsatkichi bir birlikka ko’payadi. Yuqoridagi rasmda xotira bloke 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 tashlanganida stekning barcha elementlari xotira blokining ichida mos ravishda pastga yoki yuqoriga siljiydi. Bunday holatda kiritish operatsiyasini “itarib kirgizish”, chiqarish operatsiyasini esa “itarib chiqarish” deyiladi.