Guruh talabasi karimovNuralining Ma’lumotlar tuzilmasi va algaritimlash fanidan
Download 33.38 Kb.
|
Masharipov Sanatbek Ma\'lymotlar tuzilmasi va algaritimlash № 2
- Bu sahifa navigatsiya:
- Mustaqil ishi Mavzu: Protsessorlarning tuzlishi va xususiatlari Bajardi: Kompyuter injineringi fakulteti
|
O‘ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI URGANCH FILIALI KOMPYUTER INJINERINGI FAKULTETI 961-20 GURUH TALABASI KarimovNuralining Ma’lumotlar tuzilmasi va algaritimlash FANIDAN Mustaqil ishi Mavzu: Protsessorlarning tuzlishi va xususiatlari Bajardi: Kompyuter injineringi fakulteti 961-20 guruh talabasi S.Masharipov Reja: 1 Sinf shablonlar 2. Kompilyatsiya modellari 3 Shablonlar sinflari va standart kutubxona 1.Sinf shablonlar Butun sonlarning bog'langan ro'yxatini amalga oshiradigan sinfda ro'yxatga yangi element qo'shish va kerakli elementni qidirish algoritmlari ro'yxat elementlarining butun son ekanligiga bog'liq emas. Xuddi shu algoritmlar belgilar ro'yxati, satrlar, sanalar, o'yinchilar sinflari va boshqalar uchun qo'llaniladi. template< class T > class List { /* ... */ public: void Add( const T& Element ); bool Find( const T& Element ); /* ... */ }; Sinf shablonini ishlatish uchun uning parametrlarini ko'rsatish kerak: List List Shablon parametrlari quyidagilar bo'lishi mumkin: tip parametrlari, oddiy turdagi parametrlar, shablon parametrlari. Har qanday turdagi parametrlar uchun standart qiymatlarni belgilashingiz mumkin. shablon< sinf T1, // parametr turi toifa nomi T2, // parametr turi int I,
// normal turdagi parametr
T1 DefaultValue, // normal turdagi parametr shablon< sinf > sinf T3, // shablon parametri sinf Belgi = belgi // standart parametr >
Agar sinf yoki funktsiya shablonida bir xil shablonni ishlatish kerak bo'lsa, lekin har xil parametrlarga ega bo'lsa, shablon parametrlaridan foydalaniladi. Masalan: shablon< sinf Turi, shablon< sinf > sinf Konteyner > sinf CrossReferences {
Container CrossReferences< Sana, vektor > cr1; CrossReferences< string, set > cr2; Funktsiya shablonlarini shablon parametrlari sifatida ishlatib bo'lmaydi. Sinf shablonlari a'zolari Sinf shablonining a'zolari shablonlar bo'lib, sinf shabloni bilan bir xil parametrlarga ega. Xususan, bu a'zo funktsiyalarining ta'rifi shablon sarlavhasidan boshlanishi kerakligini anglatadi: shablon< sinf T > sinf A { void f( T ma'lumotlari ); bekor g (bo'sh); ommaviy: A();
};
shablon< sinf T > void A shablon< class T > void A Shablon doirasida spetsifikatorni takrorlash shart emas. Bu shuni anglatadiki, masalan, A Agar shablon parametri ma'lumotlar turi bo'lgan a'zoga ega bo'lgan sinf bo'lsa, u holda ushbu elementdan foydalanish uchun typename kalit so'zidan foydalanish kerak. Masalan: sinf konteyneri {
ommaviy: int massivi[ 15 ]; typedef int* iterator; /* ... */ iterator begin() { massivni qaytarish; } }; andoza< class C > void f( C& vektor ) {
C::iterator i = vektor.begin(); // xato turi nomi C::iterator i = vector.begin(); }
Shablon a'zolari bilan ham muammolar mavjud. Agar o'z navbatida shablon parametri bo'lgan sinf a'zosi bo'lgan shablon ushbu shablonda ishlatilsa va parametrlarni chiqarishga ruxsat bermasa, shablon kvalifikatoridan foydalanish kerak: sinf A
{
/* ... */ ommaviy: andoza< class T > T& ConvertTo(); shablon< class T > void ConvertFrom( const T& data ); }; shablon< sinf T > void f( T konteyneri ) {
int i1 = Container.template ConvertTo }
Tabiiyki, alohida kompilyatsiya deb ataladigan bu yondashuv o'z-o'zidan e'tiroz bildirishi mumkin emas. Muvaffaqiyatli va asosli bo'linish (loyiha, keyinroq matn) dasturning alohida tarkibiy qismlarga bo'linishi uning ishonchliligini oshirish va jamoaviy rivojlanishni tashkil etish imkonini beradi. Bundan tashqari, alohida kompilyatsiya qayta foydalanish mumkin bo'lgan komponentlarni yaratishga imkon beradi. Bitta ta'rif qoidasiga ko'ra, ko'rsatilgan ob'ektlar dasturda ko'pi bilan bir marta paydo bo'lishi mumkin. Biroq, ushbu qoidaning bajarilishini nazorat qilish uchun kompilyator dasturni tashkil etuvchi barcha tarjima birliklarini tahlil qilishi kerak edi, bu esa ushbu printsipni C tilidan olingan shaklda alohida kompilyatsiya qilish printsipiga zid keladi. Shu sababli, standartni ishlab chiquvchilar bitta tavsif qoidasiga, agar u buzilgan bo'lsa, "diagnostika kerak emas" degan band bilan birga borishga majbur bo'lishdi. Bunday taxmin, mohiyatiga ko'ra, bitta tavsif qoidasini bekor qiladi, chunki amalda bu bir xil nomdagi ob'ektlarni bir nechta tarjima birliklarida ko'rsatish mumkinligini anglatadi; bunday xato tashxis qo'yilmaydi va butun dastur doirasida bunday ob'ektlardan foydalanishning ta'siri til va uning kompilyatori tomonidan hech qanday tarzda aniqlanmaydi va butunlay "razvedka" va bog'lovchini amalga oshirish xususiyatlariga bog'liq. Ushbu kamchilikni qisman qoplash sifatida modullararo o'zaro ta'sirni tashkil qilish uchun amalda sarlavha fayllari qo'llaniladi. Har bir tarjima birligi uchun maxsus matn ("interfeys") yaratiladi, unda ushbu tarjima birligining tashqi bog'lanishiga ega bo'lgan shaxslar deklaratsiyasi joylashtiriladi. Bunday matn oldindan ishlov berish mexanizmi orqali ushbu ob'ektlardan foydalangan holda boshqa tarjima birliklariga kiritiladi. Ushbu yondashuvni to'liq yechim deb hisoblash mumkin emas; Bu modullikning o'rnini bosuvchi vositadir. Keling, ushbu holatni oddiy misol bilan ko'rib chiqaylik. Funktsiyaning tavsifi bo'lsin: bekor f (char* t ) {...} va bu funksiya tasvirlangan tarjima birligidan tashqarida mavjud bo'lishi kerak bo'lsin; bu imkoniyat boshqaruv komponentlari o'rtasidagi bog'lanishni ta'minlaydi va real dasturlashda xosdir. Muntazam funktsiyalar uchun standart yechim quyidagicha. Funktsiya tavsifi bitta tarjima birligida joylashgan va uning e'lonlari #include direktivasi yordamida ushbu funktsiyadan foydalanadigan barcha tarjima birliklariga kiritilgan sarlavha faylida joylashgan. Endi funksiya shabloni uchun xuddi shunday vaziyatni ko'rib chiqing: template bekor f (T t) {. . . } Agar bunday shablondan foydalanish bir nechta tarjima birliklarida bo'lishi kerak bo'lsa, u holda funktsiyalar uchun tavsiflangan texnika kerakli natijani bermaydi. Ushbu muammoning to'g'ridan-to'g'ri echimi juda aniq: shablonning to'liq tavsifini sarlavha fayliga qo'ying va uni ushbu shablondan foydalanadiganlarning barchasida ushbu shaklga qo'shing. kompilyatsiya birliklari. Aynan shu yondashuv (keling, uni "inklyuziv" deb ataymiz) amalda keng qo'llaniladi va sarlavhali fayllarning "shishishi" ning salbiy tendentsiyasini shakllantiradi: ba'zi hisob-kitoblarga ko'ra, shablon mexanizmidan faol foydalanish quyidagi faktlarga olib keladi: Dastur matnining 40 foizi sarlavhalarda jamlangan. C++ tilini standartlashtirish jarayonida shablon mexanizmini alohida kompilyatsiya prinsipiga “qo‘shish” muammosi uzoq va qizg‘in muhokamalarga sabab bo‘ldi. Birinchidan, "inklyuziv" tamoyili maqbul deb tan olindi; Shu maqsadda yagona tavsif qoidasi mos ravishda o'zgartirildi (sinflarga qo'shimcha ravishda va sanab o'tilgan turlar, bir xil "shablon" deklaratsiyasi endi turli kompilyatsiya birliklariga kiritilishi mumkin). Shunday qilib, dastur matnining katta qismini sarlavha fayllariga o'tkazishning keng tarqalgan amaliyoti aslida qonuniylashtirildi. Ikkinchidan, shablon deklaratsiyasi va deklaratsiyalarini alohida kompilyatsiya qilishni qo'llab-quvvatlash uchun shablon mexanizmiga yaxshilanishlar kiritildi (bu imkoniyat, "inklyuziv" dan farqli o'laroq, ba'zan "alohida" yondashuv deb ataladi). Asosiy g'oya eksport kalit so'zini joriy qilishdir, undan shablon deklaratsiyasini u paydo bo'lgan tarjima birligidan tashqarida mavjud qilish uchun foydalanish mumkin. Umuman olganda, “eksport” mexanizmi quyidagicha. Standartda aytilishicha, agar shablon deklaratsiyasidan oldin eksport kalit so'zi bo'lsa, bu deklaratsiya sodir bo'lgan tarjima birligini qayta ishlash uchun etarli. Masalan, quyidagi parchada eksport shabloni . . .
f(1);
. . .
f('a');
. . .
shablon deklaratsiyasidan oldin eksport so'zining mavjudligi ushbu birlikni tarjima qilish, shu jumladan ushbu andoza sozlamalarini qayta ishlash imkonini beradi. Bunday sozlamalar f shablonining (to'liq) tavsifini talab qilganligi sababli, kompilyator uni qandaydir tarzda olishi kerak. Maxsus qidiruv usullari standartda belgilanmagan. Natijada, standart manba kodini tashkil etishning ikkala shaklini qo'llab-quvvatlaydi - "alohida" va "inklyuziv".
Shablon ixtisosligi Masalan, eng oddiy shablon sinfi 'A' quyidagicha aniqlanishi mumkin: Bir muncha vaqt o'tgach, biz sinfimiz barcha turlar uchun bir xil ishlashini xohlaymiz, lekin int kabi qiyin sinf uchun boshqacha. Bema'ni savol, biz ixtisoslikni yozamiz: u deklaratsiya bilan bir xil ko'rinadi, lekin biz burchakli qavslar ichida shablon parametrlarini ko'rsatmaymiz, o'rniga uning nomidan keyin maxsus shablon argumentlarini ko'rsatamiz: shablon<> sinf A Bajarildi, siz int uchun maxsus amalga oshirish usullari va maydonlarini yozishingiz mumkin. Bunday ixtisoslashuv odatda to'liq (to'liq ixtisoslik yoki aniq ixtisoslik) deb ataladi. Agar siz ISO C++ standartini diqqat bilan o'qib chiqsangiz, qiziqarli bayonotni topishingiz mumkin: maxsus shablon sinfini yaratish orqali biz yangi shablonni yaratamiz. Sinf. Ixtisoslashgan shablonlar sinfi biz ixtisoslashgan shablon sinfida maydonlari yoki tur deklaratsiyasi mavjud bo'lmagan usullarni o'z ichiga olishi mumkin. Faqat ma'lum bir mutaxassislik uchun ishlash uchun shablon sinfi usuli kerak bo'lganda qulay - faqat ushbu mutaxassislik bo'yicha usulni e'lon qilish kifoya, qolganini kompilyator bajaradi: Ixtisoslashtirilgan shablon sinfining butunlay, mutlaqo yangi va alohida sinf ekanligi, albatta, qiziq, ammo bunda sehrli kam narsa bor. Va kichik oqibatda sehr bor - agar bu alohida shablon sinfi bo'lsa, unda u biron-bir tarzda ixtisoslashgan bo'lmagan shablon sinfiga bog'liq bo'lmagan alohida parametrlarga ega bo'lishi mumkin (parametrlar shablondan keyin burchakli qavslar ichida). Ya'ni, shablon sinfini ixtisoslashtirish orqali biz uni yangi parametrlar orqali ixtisoslashtirishimiz mumkin: shablon< tip nomi S, tip nomi U > sinf A< std::map< S, U > > {}; Olingan shablon sinfini std::map bilan ishlatganda, ixtisoslashuv qo'llaniladi, bu erda kalit turi std::map yangi S shablonining parametri sifatida va std::map qiymati U sifatida mavjud bo'ladi. Shablonning bunday ixtisoslashuvi, unda yangi parametrlar ro'yxati ko'rsatilgan va ushbu parametrlar orqali ixtisoslashuv uchun argumentlar ko'rsatilgan, qisman ixtisoslashuv deyiladi. 3. Ba'zan dasturlarni yozishda siz parametrlarga bog'liq bo'lgan sinflarni - boshqa sinflarni yaratishingiz kerak. Masalan, agar biz stek sinfini yaratadigan bo'lsak, bu sinf uchun parametr - stek elementining turi bo'lishi juda mantiqiy. Shunday qilib parametrli bitta sinfni yozish orqali biz bir vaqtning o'zida bir nechta konkret stek sinflarini olishimiz mumkin (reallar steklari, butun sonlar, foydalanuvchi tomonidan aniqlangan turlar va boshqalar). Si tili bu maqsadda makro ta'riflardan foydalangan. parametrlari bilan. Ushbu yondashuvning kamchiliklari shundaki, preprotsessor o'z makrosini chaqirish o'rniga o'rnini bosadi. matn, hech narsani tekshirmaydi, bu ko'plab xatolarning manbai. Bu xatolarni topish oson emas, chunki dasturchi faqat makroga qo'ng'iroqni ko'radi, u kengaytirilgandan keyin olingan matnni emas. Parametrli sinflarni yaratish uchun C++ da xatolarni aniqlash nuqtai nazaridan xavfsizroq muqobil mavjud - shablon sinflari deb ataladi. Shablon sinfi sintaksisi quyidagicha: andoza sinf sinfi_nomi mumkin_meros { class_body }; Shablon parametrlarining uch turi mavjud: 1) int nomi butun sondir. 2) sinf nomi - tur (nafaqat sinf, balki o'rnatilgan turlarga ham ruxsat beriladi) 3) template sinf nomi boshqa shablondir. Shablon parametrlari ham oddiy funksiyalar kabi standart qiymatlarga ega bo'lishi mumkin. Masalan, stek shablonlari sinfi quyidagicha yaratilishi mumkin: shablon Stack sinfi { Tma'lumotlar [lar]; int c; ommaviy: Stack() { c = 0; } void push(T x) { if(c { if(!empty()) ma'lumotlarni qaytaradi[--c]; Aks holda T(); } bool empty() { qaytish c==0; } }; Endi qandaydir stek yaratish uchun siz shunday yozishingiz kerak: Stack Bunda biz butun sonlar stekini yaratamiz, ularning maksimal soni stekda 200 ta. Xuddi shunday. haqiqiy sonlar to'plamini, butun sonlarga ko'rsatgichlarni, har qanday struktura tipidagi ob'ektlarni va boshqalarni yaratishingiz mumkin. Vazifalar. 1. Parametri ishlatiladigan reallar turi bo‘lgan kompleks sonlarning shablon sinfini yozing. raqamlar (agar kompleks bizning shablon sinfimiz bo'lsa, unda kompleks xayoliy qismlari float o'zgaruvchilarda saqlanadi). 2. Parametri foydalaniladigan butun sonlar turi (agar kasr bo'lsa) bo'lgan kasrlarning shablon sinfini yozing. shablon sinfimiz, u holda fraction short int tipidagi o'zgaruvchilar). C++ tilining standart kutubxonasida stek (stek fayli), navbatlar uchun tayyor shablon sinflari mavjud. (navbat fayli), shuningdek quyidagi ma'lumotlar tuzilmalari uchun: 1) vektor (fayl vektori) - massiv, tipga asoslangan elementlar ketma-ketligini saqlash uchun ma'lumotlar strukturasi element shablon parametridir. Bunday holda, vektorning elementlari soni dasturning ishlashi davomida o'zgarishi mumkin. Quyidagi kabi haqiqiy elementlar bilan vektor o'zgaruvchisini yaratishingiz mumkin: vektor Vektor elementlariga kirish odatdagidek massivlar uchun indekslash operatsiyasi orqali amalga oshiriladi, lekin bir vaqtning o'zida push_back(new_element) usuli yordamida vektor oxiriga yangi element qo'shishga ruxsat beriladi. Qabul qilish vektor elementlarining joriy soni o'lcham usuli yordamida amalga oshirilishi mumkin, elementni o'chirish usuli yordamida vektordan olib tashlash mumkin (uning parametri olib tashlanadigan elementga ishora qiluvchi iterator). 2) bog'langan (aniqrog'i, ikki marta bog'langan) ro'yxat - shablon sinfi ro'yxati (ro'yxat fayli). Uning elementlariga o'ting biroz murakkabroq (iteratorlar uchun pastga qarang). Uning elementlari sonini vektor kabi o'lcham usuli yordamida olishingiz mumkin. Insert usuli yordamida elementni ma'lum joyga qo'shishingiz mumkin (uning parametrlari elementga ishora qiluvchi iterator, undan oldin kiritish sodir bo'ladi, shuningdek qo'shilayotgan elementning qiymati). Roʻyxatdagi elementni oʻchirish usuli yordamida olib tashlashingiz mumkin, bu parametr sifatida olib tashlanadigan elementga ishora qiluvchi iteratorni oladi. Oxirgi usul qaytadi olib tashlanadigan keyingi elementga ishora qiluvchi boshqa iterator. 1. Standart kutubxonadan shablon sinfi stekidan foydalanib, ifodani baholovchi dastur yozing, teskari polyak yozuvida yozilgan (bu belgida operatsiya belgisi operandlar va qo'shni raqamlardan keyin yoziladi. bo'shliqlar bilan ajratilgan va qavslar kerak emas). Masalan, teskari polyak yozuvidagi 10(2 + 5) ifodasi bo'ladi 10 2 5 + * ga o'xshaydi. 2*. Standart kutubxonadagi stek shablonlari sinfidan foydalanib, ifodani o'qiydigan dastur yozing odatiy (ular aytganidek, infix) yozuvda va bir xil ifodani chiqaradi, lekin teskari yoziladi Polsha yozuvi. Shablon sinflari, shuningdek, umumiy amalga oshirishdan farq qiladigan shablonlarning ba'zi maxsus holatlariga ega bo'lish imkonini beradi. Masalan, standart kutubxonada shablon sinfi vektorining maxsus namunasi, ya'ni vektor Vektor shablonini amalga oshirish umumiy holatdan farq qiladi va bool qiymatlari qatorini emas, balki bir oz vektorni beradi, ya'ni vektor, uning har bir elementi bir bitni egallaydi. Ushbu turdagi maxsus ishlarni amalga oshirish quyidagicha ko'rinadi: shablon<> sinf nomi {
}; Maxsus holatlarni ta'kidlash uchun yanada murakkab konstruktsiyalar ko'rib chiqilishi mumkin; masalan, agar X ikkita shablon parametrli sinf shablonlari bo'lsa, bu holatni alohida maxsus holatga ajratish mumkin. Parametrlar mos keladi: shablon sinf X { tanasi }; Shablon parametrlari to'plamiga ega bo'lish, konstruktsiyadan foydalanish shablon sinf nomi ; siz kompilyatorni shablon sinfining tegishli namunasini yaratishga majbur qilishingiz mumkin. Biroq, agar kerak bo'lsa bir nechta fayllarda bajarilganda, kompilyatsiya vaqtini sezilarli darajada oshirish mumkin. Bu sodir bo'lishining oldini olish uchun, umuman fayllar, bittasidan tashqari, ushbu konstruktsiyani almashtirishingiz kerak extern shablon sinfi nomi ; Xuddi shu narsa shablon funksiyalari uchun ham amal qiladi, faqat sinf nomi turi nomi Shablon funksiyalarini muhokama qilayotganda ko'rganimizdek, ular bir nechta funksiyalar matnlari bir-biridan faqat ishlatiladigan o'zgaruvchilarning turlari bo'yicha farq qilganda, lekin aks holda bir xil bo'lganda foydali bo'ladi. Uchun elementlar ketma-ketligi bilan ishlashda bunday bir xillik uchun iterator tushunchasi ixtiro qilingan. Iterator - bu ko'rsatkichga juda o'xshash ob'ekt. Ko'rsatkich kabi, u birini tanlash uchun xizmat qiladi qandaydir ketma-ketlik elementlaridan. U bilan bajarilishi mumkin bo'lgan operatsiyalar juda o'xshash ko'rinadi ko'rsatkich arifmetikasiga, lekin amalga oshirish juda boshqacha bo'lishi mumkin. Iterator ketma-ketlik uchun ishlatiladi ba'zi ketma-ketlik elementlarini sanab o'tish. Imkoniyatlariga ko'ra iteratorlar bir necha sinflarga bo'linadi: 1) Kirish iteratorlari. Bu iteratorning eng oddiy turi. Bunday iteratorlar sizga faqat uchtasini bajarishga imkon beradi harakatlar: havolani bekor qilish (agar ketma-ketlik elementi strukturaviy turdagi bo'lsa, * va -> dan foydalanish), siljitish bir pozitsiya oldinga, va ikki qo'shni smenalar o'rtasida, bekor qilish operatsiyasining bir martadan ortiq chaqiruviga yo'l qo'yilmaydi va tenglik uchun taqqoslash. Bunday iteratorlar eng umumiy shakldagi ketma-ketliklarni tavsiflaydi. Masalan, bunday iteratorlardan foydalanib, siz hatto klaviaturadan elementlarni kiritish jarayonini tasvirlashingiz mumkin, nima uchun aslida bunday iteratorlar va kiritish iteratorlari deyiladi. Kirish iteratorlari singari, chiqish iteratorlari ham mavjud (hammasi bir xil, bundan mustasno, bekor qilish operatsiyasi o'rniga faqat ko'rsatilgan elementni kiritishga ruxsat beriladi, ya'ni *i=... ko'rinishidagi ifoda, bu erda i iterator). 2) Bir yo‘nalishli iteratorlar ham kirish, ham chiqish iteratorlarining xususiyatlarini birlashtiradi; Bundan tashqari Bundan tashqari, ikki smena o'rtasida siz iterator tomonidan ko'rsatilgan elementni xohlagancha ko'p marta o'qishingiz va yozishingiz mumkin. Bunday iteratorlar odatda bitta bog'langan ro'yxat elementlarini takrorlash uchun ishlatiladi. 3) Ikki yo‘nalishli iteratorlar bir yo‘nalishli iteratorlar qila oladigan hamma narsani qilishlari mumkin, lekin ular ham orqaga qaytishlari mumkin. bir pozitsiya (kamaytirish operatsiyasi -−). Ikki marta bog'langan ro'yxat elementlarini takrorlash uchun javob beradi. 4) Nihoyat, eng aqlli iteratorlar tasodifiy kirish iteratorlari bo'lib, ular ko'rsatkich arifmetikasining barcha imkoniyatlarini amalga oshiradilar. Massivga asoslangan ma'lumotlar tuzilmalari elementlarini va ko'p hollarda takrorlash uchun javob beradi ichki tuzilish nuqtai nazaridan ular oddiy ko'rsatkichlardir. Iteratordan foydalanishga misol butun sonlar ro'yxatini chop etish uchun quyidagi funksiya tomonidan berilgan: Download 33.38 Kb. Do'stlaringiz bilan baham: 
|