Bài giảng Ngôn ngữ lập trình C/C++ - Vũ Song Tùng

ác toán tử 
Kế thừa 
77 
V. Kiểu dữ liệu trừu tượng 
78 
• Kiểu dữ liệu trừu tượng (ADT) – kiểu được 
định nghĩa để mô tả cho một sự vật 
Các tính chất 
• Đóng gói – các biến và các hàm được khai báo trong 
một khối, cho phép che dấu các thành viên 
• Kế thừa – ADT (dẫn xuất) được xây dựng trên nền 
một ADT khác (cơ sở), có thể sử dụng lại các thành 
phần của ADT cơ sở 
• Đối tượng – một biến thuộc một ADT 
V. Kiểu dữ liệu trừu tượng 
79 
• Ví dụ: 
• Một hình chữ nhật (Rectangle) được xác định bởi: 
– tọa độ góc trên bên trái: x1, y1 
– tọa độ góc dưới bên phải: x2, y2 
– tính diện tích: Area = (y2 – y1) * (x2 – x1) 
• Một hình ô van (Elipse) nội tiếp trong hình chữ nhật: 
– tính diện tích: Area = Rectagle::Area *  / 4 
V. Kiểu dữ liệu trừu tượng 
80 
• Ví dụ (struct): 
struct Rectangle 
{ 
 double x1, y1; 
 double x2, y2; 
 double Area() { return (y2 - y1) * (x2 - x1); } 
}; 
struct Elipse : public Rectangle 
{ 
 double Area() 
 { 
 return Rectangle::Area() * 3.14 / 4; 
 } 
}; 
V. Kiểu dữ liệu trừu tượng 
81 
• Ví dụ (class): 
class Rectangle 
{ 
public: 
 double x1, y1; 
 double x2, y2; 
 double Area() { return (y2 - y1) * (x2 - x1); } 
}; 
class Elipse : public Rectangle 
{ 
public: 
 double Area() 
 { 
 return s = Rectangle::Area() * 3.14 / 4; 
 } 
}; 
V. Kiểu dữ liệu trừu tượng 
82 
• Ví dụ (các đối tượng): 
void main() 
{ 
 Rectangle r = { 1, 1, 6, 3 }; 
 Elipse e; 
 e.x1 = 12; e.y1 = 2; 
 e.x2 = 17; e.y2 = 7; 
 cout << r.Area() << ' ' << e.Area(); 
} 
V. Kiểu dữ liệu trừu tượng 
83 
• Các vùng truy cập 
protected public private 
V. Kiểu dữ liệu trừu tượng 
84 
• Cấu trúc của ADT 
 class tên_ADT 
 { 
 private|protected|public: 
 // các biến thành viên (các thuộc tính) 
 private|protected|public: 
 // các hàm tạo 
 public: 
 // hàm hủy 
 private|protected|public: 
 // các hàm thành viên khác (các phương thức) 
 public: 
 // các toán tử thành viên 
 // các hàm và các toán tử friend 
 }; 
V. Kiểu dữ liệu trừu tượng 
85 
• Cấu trúc của ADT 
• Các hàm đơn giản (không chứa các vòng lặp hoặc rất 
ngắn) có thể định nghĩa inline 
 class tên_ADT 
 { 
 kiểu tên_hàm(danh sách tham số) 
 { 
 // các biểu thức 
 } 
 }; 
V. Kiểu dữ liệu trừu tượng 
86 
• Cấu trúc của ADT 
• Các hàm phức tạp nên định nghĩa ngoài khối khai 
báo ADT 
 class tên_ADT 
 { 
 kiểu tên_hàm(danh sách tham số); 
 }; 
 kiểu tên_ADT::tên_hàm(danh sách tham số) 
 { 
 // các biểu thức 
 } 
V. Kiểu dữ liệu trừu tượng 
87 
• Hàm tạo và hàm hủy 
Hàm tạo (constructor) 
• Dùng để thiết lập giá trị cho các biến hoặc cấp phát 
bộ nhớ cho các mảng động 
• Được gọi trong các biểu thức khai báo đối tượng 
hoặc cấp phát bộ nhớ 
Hàm hủy (destructor) 
• Dùng để giải phóng bộ nhớ đã cấp phát 
• Được gọi khi kết thúc khối khai báo đối tượng hoặc 
trong biểu thức giải phóng bộ nhớ 
V. Kiểu dữ liệu trừu tượng 
88 
• Hàm tạo và hàm hủy 
class tên_ADT 
{ 
public: 
 tên_ADT(); // hàm tạo mặc định 
 tên_ADT(danh sách tham số); // hàm tạo thiết lập 
 tên_ADT(const tên_kiểu &); // hàm tạo copy 
 ~tên_ADT(); // hàm hủy 
}; 
V. Kiểu dữ liệu trừu tượng 
89 
• Định nghĩa hàm tạo (inline) 
class tên_ADT 
{ 
public: 
 tên_ADT(danh sách tham số) 
 : tên_biến(biểu thức) 
 , ... 
 { 
 // các biểu thức 
 } 
}; 
V. Kiểu dữ liệu trừu tượng 
90 
• Ví dụ (class Time) 
class Time 
{ 
 long ticks; 
public: 
 Time() { ticks = 0; } 
 Time(long value) : ticks(value) { } 
 Time(const Time & t) : ticks(t.ticks) { } 
 ~Time() { } 
public: 
 long Seconds() { return ticks / 1000; } 
 long Minutes() { return Seconds() / 60; } 
 long Hours() { return Seconds() / 3600; } 
}; 
V. Kiểu dữ liệu trừu tượng 
91 
• Ví dụ (class Time) 
void main() 
{ 
 Time *p; 
 Time t1; // gọi Time() 
 Time t2(1000); // gọi Time(long) 
 Time t3 = t2; // gọi Time(const Time &) 
 p = new Time(100); // gọi Time(long) 
 cout << t2.Seconds() << endl; 
 cout Seconds() << endl; 
 delete p; // gọi ~Time() của *p 
} // gọi ~Time() của t3, t2 và t1 
V. Kiểu dữ liệu trừu tượng 
92 
• Ví dụ (class String) 
– Các biến thành viên và các hàm static 
class String 
{ 
 char *data; // Vùng dữ liệu chứa các ký tự 
 int len; // Số ký tự 
public: 
 // Lấy độ dài xâu src 
 static int GetLength(const char * src); 
 // copy xâu src vào dst 
 static void Copy(char * dst, const char * src); 
V. Kiểu dữ liệu trừu tượng 
93 
• Ví dụ (class String) 
– Các hàm private 
private: 
 // Hàm tạo đối lượng chứa được n ký tự 
 String(int n) { createData(n); } 
 // copy xâu src vào data 
 void copyData(const char * src) { Copy(data, src); } 
 // Tạo vùng dữ liệu chứa n ký tự 
 void createData(int n) 
 { 
 len = n; 
 data = new char[n + 1]; 
 data[n] = 0; 
 } 
V. Kiểu dữ liệu trừu tượng 
94 
• Ví dụ (class String) 
– Các hàm tạo và hàm hủy 
public: 
 String() { createData(0); } 
 String(const char * src) { 
 createData(GetLength(src)); 
 copyData(src); 
 } 
 String(const String & src) { 
 createData(src.len); 
 copyData(src.data); 
 } 
 ~String() { delete[] data; } 
V. Kiểu dữ liệu trừu tượng 
95 
• Ví dụ (class String) 
– Các hàm public 
public: 
 // Lấy số ký tự 
 int Length() { return len; } 
 // So sánh với đối tượng src 
 int Compare(const String & src) const 
 { 
 return Compare(src.data); 
 } 
 // So sánh với xâu src 
 int Compare(const char * src) const; 
V. Kiểu dữ liệu trừu tượng 
96 
• Ví dụ (class String) 
– Các toán tử 
public: 
 String operator=(const char * src); 
 String operator=(String & src); 
 // Các toán tử khác 
}; // class String 
V. Kiểu dữ liệu trừu tượng 
97 
• Ví dụ (class String) 
– Định nghĩa các hàm 
int String::GetLength(const char * src) 
{ 
 register int i = 0; 
 while (src[i]) ++i; 
 return i; 
} 
void String::Copy(char *dst, const char * src) 
{ 
 for (register int i = 0; src[i]; i++) 
 dst[i] = src[i]; 
} 
V. Kiểu dữ liệu trừu tượng 
98 
• Ví dụ (class String) 
– Định nghĩa các hàm 
int String::Compare(const char *src) const 
{ 
 for (int i = 0; i <= len; i++) 
 { 
 if (data[i] != src[i]) 
 return (data[i] > src[i]? 1: -1); 
 } 
 return 0; 
} 
V. Kiểu dữ liệu trừu tượng 
99 
• Toán tử gán 
{ 
 Time t1, t2; 
 String s1, s2; 
 t1 = t2; 
 s1 = s2; 
} 
t1.ticks = t2.ticks 
s1.len = s2.len 
s1.data = s2.data 
delete[] s2.data 
delete[] s1.data sinh ra lỗi vì s1.data đã bị xóa 
V. Kiểu dữ liệu trừu tượng 
100 
• Toán tử gán 
// Bổ sung toán tử gán cho String 
String& operator=(const String & right) 
{ 
 delete [] data; // xóa vùng dữ liệu cũ 
 createData(right.len); // tạo vùng dữ liệu mới 
 copyData(right.data); // copy dữ liệu từ src 
 return *this; // trả về bản thân đối tượng 
} 
V. Kiểu dữ liệu trừu tượng 
101 
• Các toán tử số học 
// Bổ sung toán tử số học cho Time 
Time operator+(const Time right) 
{ 
 return Time(ticks + right.ticks); 
} 
// Bổ sung toán tử số học cho String 
String operator+(const String & right) 
{ 
 String s(len + right.len); 
 copy(s.data, data); 
 copy(s.data + len, right.data); 
 return s; 
} 
(const Time right) 
(const String & right) 
Có gì khác nhau ? 
V. Kiểu dữ liệu trừu tượng 
102 
• Các toán tử kết hợp 
// Bổ sung toán tử kết hợp cho Time 
Time & operator+=(const Time right) { 
 ticks += right.ticks; 
 return *this; 
} 
// Bổ sung toán tử kết hợp cho String 
String operator+=(const String & right) { 
 String s(len + right.len); 
 copy(s.data, data); 
 copy(s.data + len, right.data); 
 len = s.len; 
 char *p = data; data = s.data; s.data = p; 
 return *this; 
} 
V. Kiểu dữ liệu trừu tượng 
103 
• Các toán tử so sánh 
// Bổ sung toán tử so sánh cho Time 
int operator==(const Time right) const 
{ 
 return (ticks == right.ticks); 
} 
// Bổ sung toán tử so sánh cho String 
int operator==(const String & right) const 
{ 
 return (Compare(right.data) == 0); 
} 
V. Kiểu dữ liệu trừu tượng 
104 
• Toán tử chỉ số 
// Bổ sung toán tử chỉ số cho String 
char & operator[](int index) 
{ 
 return data[index]; 
} 
V. Kiểu dữ liệu trừu tượng 
105 
• Toán tử hàm 
kiểu operator()(danh sách tham số) { ... } 
Ví dụ 
 Lấy giá trị của hàm theo một tập các đối số 
 Truy cập phần tử của mảng n chiều 
V. Kiểu dữ liệu trừu tượng 
106 
• Các toán tử tăng/giảm 
// Bổ sung toán tử ++ cho Time 
// Trường hợp toán tử ở bên phải 
Time & operator++() { 
 ticks++; 
 return *this; 
} 
// Trường hợp toán tử ở bên trái 
friend Time & operator++(Time & right) { 
 right.ticks++; 
 return right; 
} 
V. Kiểu dữ liệu trừu tượng 
107 
• Các toán tử luồng vào/ra 
// Bổ sung toán tử luồng ra cho Time 
friend ostream & operator<<(ostream & left, Time & right) 
{ 
 left << right.Hours() << ':' 
 << right.Minutes() % 60 << ':' 
 << right.Seconds() % 60 << '.' 
 << right.ticks % 1000; 
 return left; 
} 
// Bổ sung toán tử luồng ra cho String 
friend ostream & operator<<(ostream & left, Time & right) 
{ 
 return left << right.data; 
} 
V. Kiểu dữ liệu trừu tượng 
108 
• Các toán tử ép kiểu 
// Bổ sung toán tử ép sang kiểu long cho Time 
operator long() { return ticks; } 
// Bổ sung toán tử ép sang kiểu xâu ký tự cho String 
operator char*() { return data; } 
V. Kiểu dữ liệu trừu tượng 
109 
• Xây dựng class PhanSo mô tả kiểu phân số gồm các thành phần sau: 
– Hai biến a, b chứa tử số và mẫu số 
– Các hàm tạo 
– Các toán tử cộng, trừ, nhân, chia và kết hợp 
– Toán tử luồng ra 
VD. PhanSo a(2, 4); cout << a + 1;  3/2 
• Xây dựng class Complex mô tả kiểu số phức gồm các thành phần sau: 
– Hai biến r, i chứa phần thực và phần ảo 
– Các hàm tạo 
– Các toán tử cộng, trừ, nhân, chia và kết hợp 
– Toán tử hàm để lấy mô-đun 
– Toán tử luồng ra 
VD. Complex z(1, 3); cout << z + 1;  (2, 3i) 
V. Kiểu dữ liệu trừu tượng 
110 
• Mô hình 
class ADT_cơ_sở { 
protected|public: 
 virtual void foo() { ... } 
}; 
class ADT_dẫn_xuất : public|protected|private ADT_cơ_sở { 
protected|public: 
 void foo() 
 { 
 // phần mở rộng 
 ADT_cơ_sở::foo(); 
 // phần mở rộng 
 } 
}; 
ADT_dẫn_xuất : public ADT_cơ_sở 
V. Kiểu dữ liệu trừu tượng 
111 
• Các vùng truy cập 
ADT_cơ_sở 
protected public private 
V. Kiểu dữ liệu trừu tượng 
112 
• Ví dụ về sự kế thừa 
class B { 
protected: int x; 
public: 
 B(int a = 0) : x(a) { } 
 virtual void Print() { cout << x; } 
 void Inc() { x++; } 
}; 
class D : public B { 
 int x; 
public: 
 D(int a, int b) : x(a), B(b) { } 
 void Print() { 
 cout << x << ", "; 
 B::Print(); 
 } 
}; 
V. Kiểu dữ liệu trừu tượng 
113 
• Ví dụ về sự kế thừa 
void main() 
{ 
 B b(5); 
 D d(1, 2); 
 d.Inc(); 
 B *p = &b; 
 p->Print(); // gọi B::Print() -> 5 
 p = &d; 
 p->Print(); // gọi D::Print() -> 1, 3 
} 
V. Kiểu dữ liệu trừu tượng 
114 
• Lớp cơ sở trừu tượng 
class ADT_cơ_sở { 
... 
 virtual void foo() = 0; 
}; 
class ADT_dẫn_xuất : public|protected|private ADT_cơ_sở { 
... 
 void foo() 
 { 
 // ... 
 } 
}; 
V. Kiểu dữ liệu trừu tượng 
115 
• Lớp cơ sở trừu tượng 
class Shape 
{ 
 String _name; 
public: 
 Shape(const char *name) : _name(name) { } 
 void Print() 
 { 
 cout << _name << ": Area = " << Area() << endl; 
 } 
 virtual double Area() = 0; 
}; 
V. Kiểu dữ liệu trừu tượng 
116 
• Kế thừa từ lớp cơ sở trừu tượng 
class Rectangle : public Shape 
{ 
 int _w, _h; 
public: 
 Rectangle(int a, int b) 
 : Shape("Rectangle"), _w(a), _h(b) { } 
 double Area() { return _w * _h; } 
}; 
V. Kiểu dữ liệu trừu tượng 
117 
• Kế thừa lớp cơ sở trừu tượng 
class Triangle : public Shape 
{ 
 int _a, _b, _c; 
public: 
 Triangle(int a, int b, int c) 
 : Shape("Triangle"), _a(a), _b(b), _c(c) { } 
 double Area() 
 { 
 double s = (_a + _b + _c) / 2; 
 return sqrt(s * (s - _a) * (s - _b) * (s - _c)); 
 } 
}; 
V. Kiểu dữ liệu trừu tượng 
118 
• Ví dụ 
void main() 
{ 
 Shape *s[2]; 
 s[0] = new Rectangle(2, 5); 
 s[1] = new Triangle(3, 4, 5); 
 for (int i = 0; i < 2; i++) 
 { 
 s[i]->Print(); 
 delete s[i]; 
 } 
} 
Rectangle: Area = 10 
Triangle: Area = 12 
VI. Các cấu trúc dữ liệu cơ bản 
119 
• ADT mẫu 
template class Shape 
{ 
 _T edge[n]; // các cạnh 
public: 
 _T Bound(); 
}; 
template _T Shape::Bound() 
{ 
 int c = 0; 
 for (int i = 0; i < n; i++) c += edge[i]; 
 return c; 
} 
void main() 
{ 
 Shape tamGiac; // tạo ra class Shape có 3 cạnh kiểu int 
 Shape tuGiac;// tạo ra class Shape có 4 cạnh kiểu double 
} 
V. Kiểu dữ liệu trừu tượng 
120 
• class Matrix mô tả một ma trận được cho dưới đây 
template class Matrix { 
 _T **data; 
 int rows, cols; // số hàng và số cột 
 void createData(); // tạo vùng dữ liệu từ rows và cols 
 void createData(int m, int n); // tạo vùng dữ liệu m hàng, n cột 
 void deleteData(); // xóa dữ liệu 
public: 
 Matrix() : data(0) { } 
 Matrix(int m, int n = 0); // tạo ma trận mxn hoặc mxm 
 Matrix(int m, int n, const _T*); // tạo ma trận mxn kiểu ưu tiên 
 // hàng từ mảng 1 chiều 
 Matrix(const Matrix& M); 
 ~Matrix() { deleteData(); } 
 _T& operator()(int i, int j) { return data[i][j]; } 
}; 
V. Kiểu dữ liệu trừu tượng 
121 
• Định nghĩa các hàm của Matrix 
template void Matrix::createData() 
{ 
 data = new _T *[rows]; 
 for (int i = 0; i < rows; i++) 
 data[i] = new _T[cols]; 
} 
template void Matrix::deleteData() 
{ 
 if (data == 0) return; 
 for (int i = 0; i < rows; i++) 
 delete []data[i]; 
 delete data; 
} 
V. Kiểu dữ liệu trừu tượng 
122 
• Các yêu cầu: 
– Hoàn thành tất cả các hàm của class Matrix 
– Bổ sung toán tử gán, và cộng ma trận 
– Xây dựng class Graphic mô tả đồ thị có hướng không trọng số kế 
thừa từ Matrix và có thể sử dụng trong đoạn biểu thức sau: 
int M[] = { 
 0, 1, 1, 0, 1, 
 1, 0, 1, 0, 0, 
 1, 0, 0, 1, 1, 
 0, 0, 1, 0, 1, 
 0, 1, 0, 1, 0 
}; 
Graphic g(5, M); 
g.DFT(2); // in ra màn hình chỉ số các đỉnh 
 // theo chiều sâu bắt đầu từ đỉnh 2 
VI. Các cấu trúc dữ liệu cơ bản 
Array, BoundStack và 
BoundQueue 
LinkedList 
Binary Search Tree 
123 
Link đến file code đầy đủ: 
https://docs.google.com/open?id=0B4vBa0QnLWSraGRyVkJKaFUwekE 
VI. Các cấu trúc dữ liệu cơ bản 
124 
template class Array { 
protected: 
 T *data; 
 int size; 
public: 
 Array(); 
 Array(int length); 
 Array(const Array& a); 
 ~Array(); 
public: 
 void CopyFrom(T *); 
 int Size(); 
public: 
 T& operator[](int index); 
 Array& operator=(const Array& a); 
}; 
VI. Các cấu trúc dữ liệu cơ bản 
125 
template class BoundStack : protected Array { 
 int top; 
public: 
 BoundStack(); 
 BoundStack(int size); 
public: 
 void Push(T value); 
 T Pop(); 
 T Top(); 
 int IsEmpty(); 
 int IsFull(); 
 int Count(); 
 T operator[](int index); 
}; 
VI. Các cấu trúc dữ liệu cơ bản 
126 
template class BoundQueue : protected Array { 
 int front, rear; 
 int count; 
 void Inc(int &i); 
public: 
 BoundQueue(); 
 BoundQueue(int size); 
public: 
 void Enqueue(T value); 
 T Dequeue(); 
 int IsEmpty(); 
 int IsFull(); 
 int Count(); 
 T operator[](int index); 
}; 
VI. Các cấu trúc dữ liệu cơ bản 
127 
• Ứng dụng stack trong QuickSort 
template class Sort { 
 class Segment { 
 public: 
 int Lb, Ub; 
 Segment() { } 
 Segment(int l, int r) : Lb(l), Ub(r) { } 
 void Swap(T &a, T &b) { T t = a; a = b; b = t; } 
 int DoPart(Array &); // Phân đoạn Array 
 // Sắp xếp Array trong đoạn [Lb, Ub] bằng InsertSort 
 void DoSort(Array &); 
 }; // Segment 
public: 
 static void DoSort(Array &); 
}; 
VI. Các cấu trúc dữ liệu cơ bản 
128 
• Ứng dụng stack trong QuickSort 
template void Sort::DoSort(Array &a) 
{ 
 int n0 = 10, len = a.Size(); 
 BoundStack s(len/n0 + 1); 
 s.Push(Segment(0, len - 1)); 
 while (!s.IsEmpty()) { 
 Segment b = s.Pop(); 
 if (b.Ub - b.Lb + 1 > n0) { 
 int j = b.DoPart(a); 
 if (b.Lb < j - 1) s.Push(Part(b.Lb, j - 1)); 
 if (b.Ub > j + 1) s.Push(Part(j + 1, b.Ub)); 
 } else 
 b.DoSort(a); 
 } 
} 
VI. Các cấu trúc dữ liệu cơ bản 
129 
• Sử dụng class Sort 
#include "stdafx.h" 
#include "ds.h" 
#include 
using namespace std; 
int main() 
{ 
 int v[] = { 7, 5, 4, 8, 9, 1, 3, 2, 0, 6 }; 
 Array a(10); 
 a.CopyFrom(v); 
 Sort::DoSort(a); 
 for (int i = 0; i < a.Size(); i++) cout << a[i] << ' '; 
} 
VI. Các cấu trúc dữ liệu cơ bản 
130 
• class LinkedList 
template class LinkedList 
{ 
protected: 
 // Đoạn định nghĩa các lớp con // 
 baseList h; 
 int n; 
public: 
 LinkedList() : n(0) { } 
 ~LinkedList() { h.makeEmpty(); } 
 int IsEmpty() { return n == 0; } 
 int Count() { return n; } 
 _Ti PopBegin(); 
 _Ti PopEnd(); 
 void RemoveAll() { h.makeEmpty(); n = 0; } 
 void PushBegin(const _Ti& i); 
 void PushEnd(const _Ti& i) 
}; 
VI. Các cấu trúc dữ liệu cơ bản 
131 
• Các lớp con 
class baseList { 
public: 
 baseList *next, *prev; 
 baseList() { next = prev = this; } 
 void insertAfter(const _Ti& info); 
 void remove(); 
 void makeEmpty(); 
}; 
class infoList : public baseList { 
public: 
 _Ti info; 
 infoList(const _Ti& i) : info(i) { } 
}; 
VI. Các cấu trúc dữ liệu cơ bản 
132 
• Ứng dụng – đổi cơ số đếm 
std::string IntToBin(int x) 
{ 
 std::string s; 
 LinkedList stack; 
 do { 
 char c = (char)((x & 1) + 48); 
 x >>= 1; 
 stack.PushBegin(c); 
 } while (x); 
 while (!stack.IsEmpty()) 
 s += stack.PopBegin(); 
 return s; 
} 
VI. Các cấu trúc dữ liệu cơ bản 
133 
• class cơ sở 
template class baseBST { 
public: 
 baseBST() { } 
 virtual baseBST * insert(const _Ti& ) = 0; 
 virtual baseBST * contents(const _Ti& ) { return 0 ; } 
 virtual baseBST * remove(const _Ti& ) { return this; } 
 virtual baseBST * getSuccessor() { return 0; } 
 virtual void makeEmpty() { } 
 virtual _Ti * Info() { return 0; } 
}; 
template 
int _compare(const _Ti& a, const _Ti& b) 
{ 
 return (a b); 
} 
VI. Các cấu trúc dữ liệu cơ bản 
134 
• class BST 
template 
class BST { 
 // Đoạn định nghĩa các class con // 
 nullBST nullBST; 
 baseBST * root; 
public: 
 BST() { root = (baseBST *)&nullBST; } 
 ~BST() { root->makeEmpty(); } 
 void Insert(const _Ti& info) { 
 root = root->insert(info); 
 } 
 void Delete(const _Ti& i) { 
 root = root->remove(i); 
 } 
 bool Contents(const _Ti& i) { 
 return root->contents(i); 
 } 
}; 
VI. Các cấu trúc dữ liệu cơ bản 
135 
• Định nghĩa các class con 
class nullBST : baseBST { 
public: 
 baseBST * insert(const _Ti& i) { return new infoBST(i, this); } 
}; 
class infoBST : baseBST { 
 _Ti info; 
 baseBST *left, *right; 
public: 
 infoBST(const _Ti& i, baseBST *nullBST) : info(i) { 
 left = right = nullBST; 
 } 
 void makeEmpty(); 
 baseBST * insert(const _Ti& ); 
 baseBST * contents(const _Ti& ); 
 baseBST * remove(const _Ti& ); 
 baseBST * getSuccessor(); 
}; 
VI. Các cấu trúc dữ liệu cơ bản 
136 
• Ứng dụng – kiểm tra khai báo biến 
#include "ds.h" 
#include 
using namespace std; 
class VarDef 
{ 
public: 
 string name; 
 int line; 
 VarDef() { } 
 VarDef(const char* s, int l) : name(s), line(l) { } 
 static int compare(const VarDef& a, const VarDef& b) 
 { 
 return a.name.compare(b.name); 
 } 
}; 
VI. Các cấu trúc dữ liệu cơ bản 
137 
• Ứng dụng – kiểm tra khai báo biến 
void main() 
{ 
 char vars[][100] = 
 { "x", "y", "a", "b", "x", "k", "i", "k", "m", "n" }; 
 BST bst; 
 BoundQueue e(10); 
 for (int i = 0; i < 10; i++) { 
 VarDef v(vars[i], i + 1); 
 if (!bst.Contents(v)) bst.Insert(v); 
 else e.Enqueue(v); 
 } 
 for (int i = 0; i < e.Count(); i++) { 
 VarDef v(e[i]); 
 cout << "redefinition variable " << v.name.data() 
 << " in line " << v.line << endl; 
 } 
}