• Boshlanish ko’rsatkichi
  •  Yarim statik ma’lumotlar tuzilmalari




    Download 1.28 Mb.
    Pdf ko'rish
    bet8/22
    Sana29.10.2022
    Hajmi1.28 Mb.
    #28506
    1   ...   4   5   6   7   8   9   10   11   ...   22
    Bog'liq
    Yarim Statik malumotlar

    1.2.2 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

    A

    Cho’qqi 
    ko’rsatkichi
    Bo’sh 
    makon
    A
    n-1
    A
    n-1 

    A

    A

    Cho’qqi 
    ko’rsatkichi
    Bo’sh 
    makon
    A
    n-1
    A
    n-1
    A
    n-1 

    A

    A

    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

    ….. 
    A1 
    A

    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. 

    Download 1.28 Mb.
    1   ...   4   5   6   7   8   9   10   11   ...   22




    Download 1.28 Mb.
    Pdf ko'rish

    Bosh sahifa
    Aloqalar

        Bosh sahifa



     Yarim statik ma’lumotlar tuzilmalari

    Download 1.28 Mb.
    Pdf ko'rish