4-ma’ruza mavzu: konteynerlarning adapterlari. Reja
Download 0.66 Mb.
|
4-ma’ruza mavzu konteynerlarning adapterlari. Reja
4-MA’RUZAMAVZU: KONTEYNERLARNING ADAPTERLARI. Reja:Stack, queue, priority_queue, deque. Konteynerlar bilan ishlash algoritmlari. Funktorlarning qo‘llanilishi. Kalit so‘zlar: . Konteyner, adapter, shablon, sinf, moslashtirish, stack,(stek), queue (navbat), priority_queue (ustuvor bilan navbat), deque (ikki tomonlama navbat), maʻlumotlar tuzilmasi, push_back, pop_back, pop_front, LIFO, FILO, LIFO, for_each(), find(), funksional obʻyektlar, Operator(), Standart ML va funktor, Haskell va funktor. KIRISh Adapterlar standarti shablon kutubxonasining alohida toifasidir (vakilidir). Adapterlar yangi tushunchalar yoki ilovalar emas, balki mavjud kutubxona tushunchalarining o‘ziga xos, tez-tez ishlatiladigan maqsadlar uchun moslashtirishlari. Bu moslashtirish (adaptatsiyalash) ko‘pincha adapterning so‘rovlarnnig asosiy tushunchasiga asoslanib, funksiyalarini cheklash orqali amalga oshiriladi. Kutubxona konteynerlarning adapterlari, iteratorlar va funksiyalarni o‘z ichiga oladi. Konteynerlarning adapterlari. Konteynerlarning adapterlari asosida adapterlarni hosil qilishning eng oson yo‘li misol orqali tushuntirishdir. Bular stack (stek), queue (navbat), priority_queue (ustuvor bilan navbat) misol bo‘ladi. Bu misollardan tushunarli bo‘ldiki, adapterlar: juda keng va tez-tez ishlatiladigan maʻlumotlar tuzilmalari; har qanday realizatsiyani alohida bajarilishi kerak emas. Ularning funksiyalarini taʻminlash uchun STL standart konteyneri har qanday moslashtirishda tayanch sifatida push_back, pop_back, yoki pop_front amallardan (adapter turiga qarab) foydalanish mumkin; adapter uchun tayanch konteynerning to‘plamidan qo‘shimcha amallar chiqarib tashlanishi kerak (vahimalar yaratmaslik uchun, masalan, indekslash amali uchun, konteyner vektor bo‘lsa, stek moslashtirish ishlatiladi); Konteynerlarning adapterlari uchun sintaktik taʻriflar misollar orqali qarab chiqish yaxshi natija beradi, shuning uchun misollar bilan tushntirib o‘tamiz. Birinchi navbvtda konteynerlarning adapterlari uchun <stack>, Stek (stack, maʻlumotlar yig‘indisi): stekda uning elementlariga faqat bir uchidan murojaat qilish mumkinligi bilan xarakterlanadi va stekning yuqori qismi deb ataladi. Bu LIFO (Last In — First Out , birinchi kirgan oxiri chiqadi) tamoyili bo‘yicha faoliyat ko‘rsatuvchi maʻlumotlar to‘plamidir. Stack stack Juda ko‘p holarda stekni vektor ko‘rinishida initsializatsiya qilinda, ammo bu faqat C++11 variantida mavjud. 4.1-dasturda emplace() funksiyasidan stekka element qo‘shish uchun foydalanilgan. Keyingi fragmentlarda, deyarli barcha amallarni (usullarini) ko‘rish mumkin: stack:push() – stekka bitta element qo‘shish, top() – stekning eng yuqorida turgan elementiga ko‘rsatkich olish, pop() – yuqori elementini chiqarib tashlash, size() – stekning joriy hajmi, empty() – stekning bo‘shligini tekshirish, swap() – ikki stekning almashtirish, operatop= stekni qiymat qilib boshqa bir tekka berish (o‘zlashtirish). Dasturdan ko‘rish mumkinki, stek adapteri tayanch konteynerga xos usullarni yo‘qotdi (at(), operator[] va hokazo.), lekin push(), pop() funksiyalarni qayta aniqlash orqali orttirilgan hisoblanadi. Stekni tushinib olib, o‘xshash funksiyalarni navbatga joriy qilish qiyin masala emas. Stekdan farqli o‘laroq, navbat FIFO (First In — First Out birinchi kirgan birinchi chiqadi) tamoyili bo‘yicha faoliyat yuritadigan maʻlumotlar to‘plamidir. (Bu usulni bir uchiga oqib kirish, keyin boshqa uchidan oqib chiqadigan quvurga o‘xshatish mumkin). 4.1- dasturda til semantikasi talabi bo‘yicha tahrirlarni qilib navbat uchun deyarli o‘zgarishsiz qoldiramiz va 4.2 dasturni olamiz. 4.2-dastur. Navbat sinfining funksiyalari.
navbatda pop_front() usuli vektor konteyner ustiga qurib bo‘lmaydi, , lekin uni ro‘yxat konteyner uchun qurish mumkin. Deque sinfi uchun front(), push_back(), pop_front()), usullari har qanday konteynerlarda ishlatiladi (faqat pop_front() usuli borlarida). shuning uchun navbat uchun yasaladigan obʻyektda, yaʻni deque sinfida top() usuli o‘rniga front() usuli ishlatiladi. Maʻlum bir tartibda qayta ishlanishi kerak maʻlumotlarni uchun umumiy maʻlumotlar tuzilishiga asoslangan to‘plami bu – stek va navbatdir (stack, deque). Masalan, biror funksiya o‘z navbatida uchinchi funksiyani chaqiradigan boshqa funksiyani chaqirsa, uchinchi funksiya birinchi funksiyani emas, ikkinchi funksiyaga qaytishi muhimdir. Bu maʻlumotlarni qayta ishlash tartibini amalga oshirish uchun dasturchi o‘zining navbat funksiyasi tashkil qilish lozim. Stekka qo‘shilgan oxirgi qiymat birinchi bajariladi va aksincha, stekka qo‘shilgan birinchi qiymat oxirgi bajariladi. Shunday qilib, maʻlumotlar tuzilmasining o‘zi chaqirishlarning to‘g‘ri belgilangan tartibda berilishini taʻminlaydi. Konseptual, maʻlumotlar tuzilishi - stek juda oddiy: u maʻlumotlarni kiritish yoki chiqarish uchun maʻlum bir tartibni belgilaydi Har safar bir element qo‘shiladi, bu stekka yuqori element bo‘lib tugaydi. Stekdan olib tashlanadigan yagona element stekning yuqori qismida joylashgan elementdir. Shunday qilib, stekka “birinchi kirish, oxirgi chiqish — FILO” yoki “oxiri kirish, birinchi chiqish — LIFO” deb ham aytiladi. Demak, Stekka qo‘shilgan birinchi element undan oxirgi chiqariladi. Xo‘sh, bu nima? Nima uchun stek kerak? Yuqorida aytib o‘tganimizdek, funksiyalarni (qiymatlarni) chaqirishni tashkil qilish uchun qulay yo‘lidir. Aslida, stek chaqirish (call stack) tez- tez ishlaydigan yoki boshqa funksiyalarning qaytish qiymatini kutayotgan funksiyalar ro‘yxatiga murojaat qilish uchun ishlatiladigan atamadir. Shuningdek, stek informatika faning fundametntal tilining bir qismidir. Agar birinchi kelib, oxirish ketish tamoyili asosida fikrlasangiz, unda stek terminini ishlatish lozim. Bundan tashqari, bunday (stek kabi) navbatlar ko‘p jarayonlarda ishtirok etadi, nazariy informatikadan tortib, bunday push-down funksiyalari va juda ham ko‘p bag usullarida. Stek assosiativ usullarga ega: Push – stekka element qo‘shish.. Pop – stekdan element o‘chirish Top – elementni ko‘rish. LIFO - stek xarakati. FILO - stek xarakati (ekvivalet LIFO ga). Stack (stek) maʻlumotlar tuzilmasini amalga kutubxona yaratish masalani qaraymiz. Umumlashgan dasturlash usuliga mos keladigan umumiy stack, yaʻni Stack sinfi uchun shablon yaratish degani. Agar shablonlar bilan tanish bo‘lmasangiz, funksiya shablonlariga oid nazariy maʻlumotlarga qarang, shablonlar bilan ishlash mexanizmi batafsil bilish lozim. Agar shablonlar bilan tanish, lekin sinf shablonlari bilan ishlashni unutgan bo‘lsangiz, sinf shablonlari haqida nazariy materiallarni o‘qib o‘rganing. Bu stack shablonlari bilan amalga oshirildigan kutubxonani deyarli har qanday maʻlumotlar tipi uchun foydalanish mumkin. Bundan tashqari, stack hajmi dastur ijrosi davomida jadal belgilanadi. Stackga qo‘shimcha funksiya ham qo‘shildi peek(), bu stackning yuqori qismidan n- elementini qaytaradi. 4.3-dastur. Stack shablon sinfi
Stack shablon sinfi *.h (header) faylda yaratildi. Shablon sinf interfeysi va amalga oshirish ham bir xil faylda bo‘lishi kerak, bo‘lmasa, shunga o‘xshash mazmun bilan xato berishi mumkin.
Yaʻni, xatolik, shablon sinf usullari havolalarda aniqsizlik. Shablon sinf interfeysining fragmentlarida 9 -dan 28gacha yangilandi. Sinfning barcha usullari izohlarni o‘z ichiga oladi va mening fikrimcha, ularning funkiyalarini alohida taʻriflash mantiqiy to‘g‘ri emas. Stack shablon sinfning barcha usullari inline funksiyalari sifatida eʻlon qilinadi. Bu sinf ishini tezlashtirish maqsadida amalga oshiriladi. Sinfning ajralmas funksiyalari tashqi funsiyalarga qaraganda tezroq ishlaydi. Shablon interfeysidan so‘ng, stack sinf usullari amalga oshiriladi, kutubxona fragmentlarida 32-117gacha yangilandi. Agar stack sinf, shablonlar va sinflar usullarini amalga oshirish haqida bilsangiz shablon sinfni yaratishda murakkab hech narsa yo‘q. Sinfda ikkita konstrkutor bor, birinchisi fragmentning 32-33 qatorlarida - bu standart konstruktor hisoblanadi. Fragmentning 41-50 qatordagi nusxa konstruktor hisoblanadi. Bir obʻyektni boshqasiga nusxalash uchun kerak. Peek usuli (funksiyasi), fragmentning 80-88 fatorlarida stack elementlarni ko‘rish imkonini beradi. Faqat element raqamini kiritishingiz kerak, hisoblash stack yuqorisidagi elementdan boshlanadi va keraklisini qaytaradi. Boshqa funksiyalari xizmatchi funksiyalar hisoblanadi, ular tashqi sinfdna foydalanish uchun mo‘ljallangan, yaʻni prinstack() funksiyasidan tashqari, bu funksiya stack elementlarini ekranga chiqaradi. Endi stack shablon sinf uchun dastur tuzaylik va har doimgidek, stack sinf shablonni sinov bo‘ladi hamda asosiy funksiyalaridan foydalanishni ko‘ramiz. 4.4-dastur. Shablon sinfdan foydalanish.
4.4-dasturda Bir stack obʻyektini yaratilgan, stack hajmi 5ga teng va stack ko‘pi o‘z ichiga olishi mumkin bo‘lgan elementlar soni 5 ga teng. stackni while takrorlanish operatori bilan to‘ldiriladi. Ekranda stack elementlarini chiqariladi, keyin stackdan bir elementi o‘chiriladi va yana ekranda stack elementlarini chiqariladi. Natija asosida u o‘zgardi, aniq bir element o‘chirildi. Shuningdek, dasturda nusxa konstruktor ishlatiladi. Peek() funksiyasi stackning ikkinchi elementini qaytardi. Stack shablon sinf yaxshi yaratildi va to‘g‘ri ishlamoqda. uni, masalan, int maʻlumotlar turida sinab ko‘rcangiz bo‘ladi. Ishonchim komilki, hamma narsa to‘g‘ri ishlaydi. Navbat (queue). Navbat maʻlumotlar tuzilmasi bo‘lib (yuqorida aytib o‘tilganidek) bu LILO tamoyilini qo‘llab quvvatlaydi (last in-last out: oxirgi kirgan oxirgi chiqadi). C++ allaqachon tayyor STL konteyner-navbat (queue) mavjud. Navbatda, birinchi elment kiritilgan bo‘lsa, u ham birinchi chiqariladi. 4 ta elementni qo‘shsangiz, birinchi qo‘shilgan element birinchi, ikkinchi qo‘shilgan element ikkinchi chiqadi. Navbat qanday ishlashini tushunish uchun do‘kon navbatini tasavvur qilishingiz mumkin. Siz esa uning o‘rtasida turibsiz, shunda kassaning oldida turibsiz, avval oldingizdagi barcha odamlarga xizmat qilinishi. Lekin oxirgi navbatda o‘tgan kishi uchun, o‘zi tashqari barcha odamlarga xizmat qilish kerak emas.
Bu yuqorida keltirilgan ro‘yxatga qarang. Bulardan birortasini chiqarish uchun shu ketma- ketlik asosida chiqarib, keraklisiga to‘xtaladi. Masalan, 0 sonnini chiqarish, uchun avvl 3 ta son chiqariladi so‘ng kerakli son. Stack shablon sinfida bir peek() (bu indeks bo‘yicha elementni qaytaradi), bu navbat shablonida muayyan elementni ko‘rish mumkin emas. Agar barcha navbat elementlarga kirish kerak bo‘lsa, lekin, navbatda buni amalga oshirish mumkin. Keyinroq bu qanday amalga oshirishni ko‘rsatib o‘tamiz. C++da navbat yaratish. Agar C++ da navbat shablonini ishlatmoqchi bo‘lsangiz, avval Keyin navbatni eʻlon qilish uchun quyidagi sintaktikni ishlatishingiz kerak:
Birinchi queue so‘zini yozishimiz kerak. Type ga navbatni to‘ldirish uchun kerakli tipni ko‘rsatishimiz lozim. Navbat obʻyektining nomini ko‘rsatishamiz kerak. Masalan,
Navbat usullari va funksiyalari: Navbatda funksiya bu bir xil funksiyadir, lekin u faqat STL konteynerlari bilan ishlaydi. Bu funksiyalarga push(), pop(), front(), back(), empty() funksiyalar kiradi. push() – navbatga yangi element qo‘shish. pop() – navbatdan birinchi elementni o‘chirish, ikkinchi element birinchi element o‘rniga suriladi. front() – navbatdagi birinchi elemeniga murojaat back() - navbatdagi birinchi elemeniga murojaat empty() – navbat bo‘sh yoki bo‘shmasligini tekshiradi. Agar bo‘sh bo‘lsa true, aks holda false qiymat qaytaradi. Bu keltirilgan funksiyalarga doir 4.5-dasturini keltiramiz. 4.5-dastur. Navbat funksiyalaridan foydalanish.
Download 0.66 Mb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling