Dasturlash II 7-hafta mavzu: shablonlar, vektorlar va steklar

DASTURLASH II


7-HAFTA


MAVZU: SHABLONLAR, VEKTORLAR VA STEKLAR

Hafta	Mavzu	Mashg‘ulot turi	Soat	Mashg‘ulot mazmuni
7-hafta	Shablonlar, vektorlar va steklar	Ma’ruza 7	2	Vektor va stek tushunchalari.
		Lab_7_1	2	Vektorlarga doir oddiy dastur tuzish.
		Lab_7_2	2	Vektor elementlarini qidirish va saralashga doir dastur tuzish.
		Lab_7_3	2	Vektor elementlarini qidirish va saralashga doir dastur tuzish.
		Mustaqil ish 7	2	Topshiriqda berilgan savollarga javob yozish; test topshiriqlarini bajarish.
			6	Dastur tuzishga doir topshiriqlarni bajarish

7-MA’RUZA
Mavzu: Vektor va stek tushunchalari

Reja:

1. 
   Stack sinfini takomillashtirish;
   
2. 
   C++ ning vector sinfi;
   
3. 
   vector sinfidan foydalanib massivlarni almashtirish;
   
4. 
   Amaliy qism: Ifodalarni baholash.
   

Kalit so‘zlar:

• 
  template
  
• 
  template class
  
• 
  template function
  
• 
  template prefix
  
• 
  type parameter
  

7.1. Stack sinfini takomillashtirish
Key Point. Bu qismda dinamik stack sinfi tadbiq etiladi.
Stack sinfida bir muammo bor. Stek elementlari doimiy 100 o`lchamli massivga yozilgan (6.4-kodli ro`yxatdagi 16-qatorga qarang). Xo`sh, bu stekda 100 dan ortiq hajmda element yozib bo`lmaydi. Biz bu 100 ni kattaroq qiymatga o`zgartirishimiz mumkin, lekin agar stek kichik bo`lsa, behuda joy yo`qotilishiga olib keladi. Bu muammoli vaziyatni hal etishning birgina yo`li – talab etilgan vaqtdagiga mos keladigan dinamik xotira ajratishdir.
Stack sinfidagi size xususiyati stekdagi elementlar sonini taqdim qiladi. Bizga element yozish uchun massivning joriy o`lchamini taqdim etuvchi, capacity deb nomlangan yangi xususiyatni qo`shishimizga ruxsat beradi. Stack sinfining argumentsiz konstruktori 16 o`lchamdagi massivni hosil qiladi. Stekka yangi element qo`shganimizda, agar ushbu hajm to`lgan bo`lsa, yangi elementni yozish uchun massiv o`lchamini oshirishimiz zarur bo`lib qolishi mumkin.
Xo`sh, massiv o`lchamini qanday oshirish mumkin? MAssiv bir marotaba e’lon qilinganidan so`ng, bunday qila olmaymiz. Bu cheklovni chetlab o`tish uchun, yangi, kattaroq hajmdagi massivni yaratib, eski massiv tarkibini yangisiga nusxalab ko`chirib, eskisini o`chirib tashlashimiz mumkin.
7.1-kodli ro`yxatda takomillashtirigan Stack sinfi ko`rsatilgan.
7.1-kodli ro`yxat. ImprovedStack.h
1 #ifndef IMPROVEDSTACK_H
2 #define IMPROVEDSTACK_H
3
4 template <typename T>
5 class Stack
6 {
7 public:
8 Stack();
9 Stack(const Stack&);
10 ~Stack();
11 bool empty() const;
12 T peek() const;
13 void push(T value);
14 T pop();
15 intgetSize() const;
16
17 private:
18 T* elements;
19 int size;
20 int capacity;
21 void ensureCapacity();
22 };
23
24 template <typename T>
25 Stack::Stack(): size(0), capacity(16)
26 {
27 elements = new T[capacity];
28 }
29
30 template <typename T>
31 Stack::Stack(const Stack& stack)
32 {
33 elements = new T[stack.capacity];
34 size = stack.size;
35 capacity = stack.capacity;
36 for (int i = 0; i < size; i++)
37 {
38 elements[i] = stack.elements[i];
39 }
40 }
41
42 template <typename T>
43 Stack::~Stack()
44 {
45 delete[] elements;
46 }
47
48 template <typename T>
49 bool Stack::empty() const
50 {
51 return size == 0;
52 }
53
54 template <typename T>
55 T Stack::peek() const
56 {
57 return elements[size - 1];
58 }
59
60 template <typename T>
61 void Stack::push(T value)
62 {
63 ensureCapacity();
64 elements[size++] = value;
65 }
66
67 template <typename T>
68 void Stack::ensureCapacity()
69 {
70 if (size >= capacity)
71 {
72 T* old = elements;
73 capacity = 2* size;
74 elements = new T[size * 2];
75
76 for (int i = 0; i < size; i++)
77 elements[i] = old[i];
78
79 delete[] old;
80 }
81 }
82
83 template <typename T>
84 T Stack::pop()
85 {
86 return elements[--size];
87 }
88
89 template <typename T>
90 int Stack::getSize() const
91 {
92 return size;
93 }
94
95 #endif
Ichki massiv elementlari yaratilishida konstruktor bekorchi xotira maydoni paydo bo`lib qolmasligini ta’minlashi lozim (42-46-qatorlar). Shuni ta’kidlab o`tish kerakki, 6.4-kodli ro`yxatdagi GenericStack.h da e’lon qilingan massiv elementlari uchun xotira maydoni dinamik ajratilmagan, va u yerda konstruktorga bunday talab qo`yilmaydi.
Dastur kodining 60-65-qatorlarida keltirilgan push(T value) funksiyasi stekka yangi element qo`shadi. Bu funksiya dastlab, massivda yangi element uchun bo`sh joy bo`lishini ta’minlab beruvchi ensureCapacity() ni chaqiradi (63-qator).
ensureCapacity() funksiyasi (67-81-qatorlar) massivning to`lganligi yoki yo`qligini tekshiradi. Agar joriy massiv o`lchamini ikki marta oshiruvchi yangi massiv yaratilsa, uni joriy massiv sifatida belgilaydi, eski massivning tarkibini yangi massivga nusxalaydi va keyin, eski massivni o`chirib tashlaydi (79-qator).
Iltimos, dinamik yaratilgan massivni o`shirishning quyidagi sintaksisisga e’tibor bering:
delete[] elements; // 45-qator
delete[] old; // 79-qator
Agar buni xato qilib, quyidagicha yozsak nima yuz beradi?