O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI FARG’ONA FILIALI
“DASTURLASH - 2” FANIDAN
MUSTAQIL ISHI
2-KURS D-I 751-22 GURUH TALABASI
BAJARDI: Qodirov R.
QABUL QILDI: Asrayev M. A.
Mavzu: Konteynerlar bilan ishlaydigan algoritimlar.
Reja:
Konteynerlar bilan ishlash.
C++ dasturlash tilida STL bilan tanishish.
C++ dasturlash tilida xususiy konteynerlar yaratish.
Xulosa.
Foydanilgan adabiyotlar.
Konteynerlar bilan ishlash.
Konteynerlar (containers) – bu boshqa elementlarni saqlovchi ob’ektlar.
Masalan, vektor, chiziqli ro‘yxat, to‘plam.
Umumlashgan yoki unifikasiyalangan dasturlashning maqsadi tartiblash
kabi ko‘p qo‘llaniluvchi algoritmlar va sinflar saqlanuvchi universal
kutubxonalar yaratish orqali dasturlash jarayonini avtomatlashtirishdan
iboratdir. Shu bilan birga, bu kutubxonaga kiruvchi funksiyalar universal
xarakterga ega bo‘lishi, ya’ni ixtiyoriy turdagi ma’lumotlar ustida amallar
bajarish imkonini berishi lozim.
Shablonlarga asoslangan umumlashgan dasturlashga misol Stepanov
va Target tomonidan yaratilgan va C++ tili standartiga kiritilgan STL (Standart
Template Library) kutubxonasidir. Kutubxona yadrosi uchta elementdan iborat:
Konteynerlar,
Algoritmlar
Iteratorlar.
Konteynerlar — bu boshqa elementlarni saqlash uchun mo‘ljallangan sinflar
shablonlaridir. Konteynerlar asosiy xususiyati shundaki ular ixtiyoriy tipdagi
elementlarni o‘zida saqlash uchun mo‘ljallangan. To‘g‘rirog‘i, har bir tur uchun
shablon nusxasi kerak bo‘lganda, kompilyator tomonidan avtomatik tarzda
yaratiladi. Algoritmlar konteyner elementlari ustidan operasiyalar bajaradi.
Bibliotekada qidirish, saralash va almashtirish uchun algoritmlar mavjud.
Algoritmlar elementlar ketma_ketligi bilan ishlash uchun mo‘ljallangan.
Algoritmlar asosiy xususiyati shuki ular ixtiyoriy konteynerlar bilan ishlay
oladi.
Konteynerlar asosiy va hosila konteynerlarga ajratiladi. Asosiy
konteynerlarga quyidagilar kiradi:
• vector — dinamik massiv
• list — chiziqli ro‘yxat
• deque — ikki tarafli tartib
• set — to‘plam
• multiset — har bir elementi noyob bo‘lishi shart emas to‘plam
• map — kalit/ qiymat juftlikni saqlash uchun assosiativ ro‘yxat. Bunda har bir
kalit bitta qiymat bilan bog‘langan.
• multimap — har bir kalit bilan ikkita yoki ko‘proq qiymatlarbog‘langan
Hosila konteynerlarga quyidagilar kiradi:
• stack — stek
• queue — tartib
• priority_queue — prioritetli tartib
STL kutubxonasidagi standart shablonlardan foydalanish uchun kerakli
header fayllarni dasturga ulash lozim.
vector
Birinchi bo’lib STL dagi vector bilan ishlaymiz. Buning uchun vector
header faylini dasturga ulaymiz.
Vector tipidagi o’zgaruvchi yaratamiz. Buning uchun
vector var_name
Bu yerda
type – vector tarkikibiga kiruvchi o’zgaruvchilarning toifasi
var_name – vectorning nomi
STL kutubxonasidagi maxsus vectorning ichiga ma’lumot qo’shish uchun
quyidagi funksiyadan foydalaniladi.
push_back( value )
- value –vectorga qo’shiluvchi qiymat
#include
#include
using namespace std
int main()
{
vector vc; // vectorni e’lon qilish
int a;
cin>>a;
vc.push_back(a);
while(a)
{
cin>>a;
vc.push_back(a);
}
for(int i=0;i
cout << vc[i] << endl;
return 0;
}
Ro’yxat
STL kutubxonasidagi list konteyneri bilan ishlash. Buning uchun eng
avvalo list header faylini dasturimizga ulaymiz.
List tipidagi o’zgaruvchini yaratish:
list list_name;
STL kutubxonasidagi maxsus vectorning ichiga ma’lumot qo’shish uchun
quyidagi funksiyalardan foydalaniladi.
push_back( value ) – listning oxiriga qo’shish
push_front( value ) – listning boshiga qo’shish
List elementlariga murojatni amalga oshirish uchun iteratorlardan
foydalanish zarur. Iteratorlar — bu konteyner hamma elementlarini ko‘rib chiqish va qayta
ishlashga imkon beruvchi obyektlardir. Iteratorlar algoritmlar universalligini
ta’minlovchi asosiy vositadir.
Iteratorlardan foydalanish uchun ma’lum list konteyneriga most
iteratorlar yaratish lozim.
list::iterator iterator_name
#include
#include
using namespace std;
int main()
{
list lst;
lst.push_back(12);
lst.push_back(23);
lst.push_front(44);
list::iterator it;
for(it=lst.begin();it!=lst.end();it++)
cout<<*it<<="" p="">
return 0;
}
LIFO (Last in first out) ya'ni navbatning oxirgi bo’lib kirgan elеmеntiga
birinchi bo’lib xizmat ko’rsatiladi. Bu eng ko’p ishlatiladigan ma'lumotlar tuzilmalaridan biri bo’lib, turli xil masalalarni hal qilishda ancha qulay va
samarali xisoblanadi. Xizmat ko’rsatishni kеltirilgan tartibiga ko’ra, stackda
faqatgina bitta pozitsiyaga murojaat qilish mumkin. Bu pozitsiya stackning uchi
dеyilib unda stackka vaqt bo’yicha eng oxirgi kеlib tushgan elеmеnt nazarda
tutiladi. Biz stackga yangi elеmеnt kiritsak, bu elеmеnt oldingi stack uchida
turgan elеmеnt ustiga joylashtiriladi xamda stackni uchida joylashib qoladi.
Elеmеntnifaqatgina stack uchidan tanlash mumkin; bunda tanlangan elеmеnt
stackdan chiqarib tashlanadi va stack uchini esa chiqarib tashlangan elеmеntdan
bitta oldin kеlib tushgan elеmеnt tashkil qilib qoladi. (bunday tuzilmaga
ma'lumotlarga chеklangan murojaat tuzilmasi dеyiladi)
Stack ko’rinishidagi konteynerlar bilan ishlash. Buning uchun stack
header faylini dasturga ulash lozim.
Stack ustida amalga oshiriladigan amallar:
1. PUSH( i ) - stackga elеmеnt kiritish i - stackga kiritiladigan elеmеnt;
2. POP ( ) - stackdan elеmеntni tanlash. Elеmеnt tanlanayotganda o’zi egallab
turgan ishchi xotiraga joylashtiriladi;
3. EMPTY ( ) - stackni bo’sh yoki bo’sh emasligini tеkshirish (true - bo’sh,
false bo’sh emas);
4. TOP ( ) - stack yuqori elеmеntini o’chirmasdan o’qish.
Stack tipidagi o’zgaruvchini quydagicha e’lon qilishimiz lozim.
stack stack_name;
#include
#include
using namespace std;
int main()
{
stack sc;
sc.push(12);
sc.push(33);
sc.push(66);
while(!sc.empty())
{
cout<
sc.pop();
}
}
|
