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: Stack sinfini takomillashtirish;
C++ ning vector sinfi;
vector sinfidan foydalanib massivlarni almashtirish;
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 int getSize() 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:
