|
Sinflar qoliplarini yaratish
Sinf qolipini yaratish jarayonini misolda ko’rib chiqamiz. “Chiziqli ro’yxatlar” bo’limida ikki bog’lamli ro’yxat berilgan edi va ular bilan ishlash algoritmi keltirilgan edi. Ro’yxatlar ma’lumotlarni tashkil etish uchun ko’pincha qo’llanilgani uchun ro’yxatni sinf ko’rinishida tavsiflash qulay, chunki turli tipdagi ma’lumotlarni saqlash talab qilinishi mumkin, bu sinf parametrlashgan bo’lishi lozim.
Dastlab “ro’yxat” sinfining parametrlashmagan talqinini qaraymiz.
Ro’yxat bir-biri bilan ko’rsatgichlar orqali bog’langan tugublardan iborat. Har bir tugun ro’yxat kaliti hisoblangan butun sonni saqlaydi. Ro’yxatning bir tugunini ifodalash uchun yordamchi sinfni tavsiflaymiz.
class Node{
public:
int d; // Ma’lumotlar
Node *next; // Keyingi tugunga ko’rsatgich
Node *prev; // Oldingi tugunga ko’rsatgich
Node(int dat = 0){ // Konstruktor
d = dat; next = 0; prev = 0;
}
};
Bu sinf ro’yxatni ifodalovchi sinf ichida tavsiflangani uchun maydonlar tashqi sinfdan kirish qulayligi uchun kirishli qilingan (public). Bu kirish funksiyasiz va maydonlarni o’zgartirishsiz amalga oshirishga imkon beradi. Ro’yxat sinfini List deb ataymiz:
class List{
class Node{
…
};
Node *pbeg, *pend; // Ro’yxatning boshi va oxirgi ko’rsatgichlari
public:
List( ) {pbeg = 0; pend =0;} // Konstruktor
~Listt ( ) ; // Destruktor
void add(int d); // Ro’yxat oxiriga tugun qo’shish
Node * find(int i ); // Kalit bo’yicha tugunni izlash
// key kaliti bilan tugundan keyin d tugunni qo’shish
Node * insert(int key, int d);
bool remove(int key); // Tugunni yo’qotish
void print( ); // To’g’ri yo’nalishda ro’yxatni chop etish
void print_back( ); // Teskari yo’nalishda ro’yxatni chop etish
};
Sinf usullarini ishga tushirishni qaraymiz. add usuli Node tipidan ya’ni obyektga xotira ajratadi va uning boshi va oxiridagi ko’rsatgichlarni yangilab uni ro’yxatga birlashtiradi:
void List::add(int d){
Node *pv = new Node(d); // Yangi tugunga xotira ajratish
if (pbeg == 0)pbeg = pend = pv; // Ro’yxatning birinchi tuguni
else{
// Yangi tugunni oldingisi bilan bog’lash
pv->prev = pend;
pend->next = pv;
pend = pv;} // Ro’yxat oxirigi ko’rsatgichni yangilash
}
Saralangan ro’yxatni olish xoxishida bu usulni “Chiziqli ro’yxatlar” bo’limida keltirilgan, saralangan add_sort ro’yxatini shakllantirish funksiyasiga o’xshash usul bilan almashtirish mumkin.
find usuli berilgan kalitli tugunni izlaydi va muvaffaqiyatli izlash holida ko’rsatgichni unga qaytaradi va ro’yxatda bunday tugun bo’lmaganida 0 ni ko’rsatadi:
Node * List::find( int d ){
Node *pv = pbeg;
while (pv){
if(pv->d == d) break;
pv = pv->next;
}
return pv;
}
insert usuli key kalitli tugundan so’ng tugun quyadi va ko’rsatgichni oldingi tuguni qaytaradi. Agar bunday tugun ro’yxatda bo’lmasa qo’yish amalga oshiriladi va 0 qiymat qaytariladi.
Node * List::insert(int key, int d){
if(Node *pkey = find(key)){ // key kalitli tugunni izlash
// Yangi tugunga xotira ajratish va uni initsializatsiyalash
Node *pv = new Node(d);
// Yangi tugunni keyingisi bilan bog’lanishni o’rnatish
pv->next = pkey->next;
// Yangi tugunni oldingisi bilan bog’lanishni o’rnatish
pv->prev = ркеу;
// Keyingi tugunni yangisi bilan bog’lanishni o’rnatish
pkey->next = pv;
// Oldingi tugunni yangisi bilan bog’lanishni o’rnatish
if ( ркеу != pend) (pv->next)->prev = pv;
// Ro’yxat oxirida ko’rsatgichni yangilash
// agar tugun oxiriga qo’yilsa
else pend = pv;
return pv;
}
return 0;
}
remove usuli berilgan kalitli tugunni ro’yxatdan yo’qotadi va muvaffaqiyatli yo’qotish holida true qiymatni qaytaradi va agar bunday kalitli tugun ro’yxatda bo’lmasa false qiymat beradi:
bool List::remove(int key){
if(Node *pkey = find(key)){
if (pkey == pbeg){ // Ro’yxat boshidan yo’qotish
pbeg = pbeg->next;
pbeg->prev = 0;}
else if (pkey == pend){ // Ro’yxat oxiridan yo’qotish
pend = pend->prev;
pend->next = 0;}
else { // Ro’yxat o’rtasidan yo’qotish
(pkey->prev)->next = pkey->next;
(pkey->next)->prev = pkey->prev;}
delete pkey;
return true;}
return false;
}
Ro’yxatni to’g’ri va teskari yo’nalishda chop etish usullari tegishli murojaatlar bo’yicha ro’yxat elementlari o’tadi:
void List::print ( ){
Node *pv = pbeg;
cout << endl << "list: ";
while (pv){
cout << pv->d << ' ';
pv = pv->next;}
cout << endl;
}
void List::print_back(){
Node *pv = pend:
cout << endl << " list back: ";
while (pv){
cout << pv->d << ' ';
pv = pv->prev;}
cout << endl;
}
Ro’yxat destruktori xotirani uning barcha elementlaridan ozod qiladi:
List::~List ( ) {
if (pbeg != 0){
Node *pv = pbeg;
while (pv){
pv = pv->next;
delete pbeg;
pbeg = pv;}
}
}
List sinfidan foydalanuvchi dasturga misol keltirilgan. Dastur 116-betda keltirilgan dasturga o’xshash: u 5 ta sondan iborat ro’yxat shakllantiradi va uni ekranga chiqaradi, sonni ro’yxatga qo’shadi, sonni ro’yxatdan yo’qotadi va yana uni ekrangan chiqaradi:
int main(){
List L;
for (int i = 2; i<6; i++) L.add(i);
L.print();
L.print_back();
L.insert(2, 200);
i f (!L.remove(5))cout << "not found";
L.print();
L.print_back();
}
List sinfi butun sonlarni saqlash uchun mo’ljallangan. Unda ixtiyoriy tipdagi ma’lumotlarni saqlash uchun bu sinfni sinf sifatida tavsiflash va tipni parameter sifatida uzatish talab etiladi.
Qolipni tavsiflash sintaksisi:
template sinf_ta’rifi;
Qolip parametrlari vergul bilan sanab o’tiladi. Parametrlar sifatida tiplar, qoliplar va o’zgaruvchilardan foydalaniladi.
Tiplar standart hamda foydalanuvchi aniqlagan tiplar bo’ladi. Ularni tavsiflash uchun class kalit so’zi ishlatiladi. Qolip ichida tip parametri tip spitsifikatsiyasidan foydalanish mumkin bo’lgan har qanday joyda qo’llanilishi mumkin, masalan:
template class List{
class Node{
public:
Data d;
Node *next;
Node *prev;
Node(Data dat = 0){d = dat; next = 0; prev = 0;}
};
}
Data sinfini formal parameter sifatida qarash mumkin, uning o’rniga kompilyatsiyada ma’lumotlar konkret tipi qo’yiladi. Qolipning ixtiyoriy parametrlari uchun jimlik bo’yicha qiymatlar berilishi mumkin, masalan:
template class myarray {/*...*/};
…
tempiate class С = myarray>
class Map{
C key;
C value;
…
};
Qolip parametri amal qilish sohasi – tavsiflash nuqtasidan qolip oxirigacha, shuning uchun parametrni ulardan keyin keluvchilarni tavsiflashda foydalanish mumkin, masalan:
template class X { /* ... */ };
Sinf qolipi usullari avtomatik ravishda funksiyalar qoliplariga aylanadi. Agar usul qolipdan tashqarida tavsiflansa, uning sarlavhasi quyidagi elementlarga ega bo’lishi mumkin:
Do'stlaringiz bilan baham: | 
