Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 2: Ngăn xếp

iệu chỉnh này, người sử dụng sẽ 
không thể gây ra rác khi để một đối tượng ngăn xếp không rỗng ra khỏi tầm vực. 
Destructor được khai báo như một phương thức của lớp, không có thông số và 
không có trị trả về. Tên của destructor là tên lớp có thêm dấu ~ phía trước. 
 Stack::~Stack(); 
Do phương thức pop được lập trình để loại một phần tử ra khỏi ngăn xếp, 
chúng ta có thể hiện thực destructor cho ngăn xếp bằng cách lặp nhiều lần việc 
gọi pop: 
template 
Stack::~Stack() // Destructor 
/* 
post: ngăn xếp đã được làm rỗng. 
*/ 
{ 
 while (!empty()) 
 pop(); 
} 
Chương 2 – Ngăn xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 31
Đối với mọi cấu trúc liên kết chúng ta cần viết destructor để dọn dẹp các đối 
tượng trước khi chúng ra khỏi tầm vực. 
2.4.3.2. Định nghĩa lại phép gán 
Ngay khi chúng ta đã bổ sung destructor cho ngăn xếp liên kết, người sử dụng 
cũng có thể tạo rác khi viết vòng lặp tựa như ví dụ sau. 
Stack outer_stack; 
for (int i=0; i < 1000000; i++) { 
 Stack inner_stack; 
 inner_stack.push(some_data); 
 inner_stack = outer_stack; 
} 
Đầu tiên là đối tượng outer_stack được tạo ra, sau đó vòng lặp được thực hiện. 
Mỗi lần lặp là một lần tạo một đối tượng inner_stack, đưa dữ liệu vào 
inner_stack, gán outer_stack vào inner_stack. Lệnh gán này gây ra một vấn đề 
nghiêm trọng cho hiện thực ngăn xếp liên kết của chúng ta. Thông thường, C++ 
thực hiện phép gán các đối tượng bằng cách chép các thuộc tính của các đối tượng. 
Do đó, outer_stack.top_node được ghi đè lên inner_stack.top_node, làm cho dữ liệu 
cũ tham chiếu bởi inner_stack.top_node trở thành rác. Cũng giống như phần 
trước, nếu hiện thực ngăn xếp liên tục được sử dụng thì không có vấn đề gì xảy 
ra. Như vậy, lỗi là do hiện thực ngăn xếp liên kết còn thiếu sót. 
Hình 2.7 cho thấy tác vụ gán không được thực hiện như mong muốn. Sau phép 
gán, cả hai ngăn xếp cùng chia xẻ các node. Cuối mỗi lần lặp, destructor của 
inner_stack sẽ giải phóng mọi dữ liệu của outer_stack. Việc giải phóng dữ 
liệu của outer_stack còn làm cho outer_stack.top_node trở thành tham 
chiếu treo, có nghĩa là tham chiếu đến vùng nhớ không xác định. 
Hình 2.7- Ứng dụng chép ngăn xếp. 
Chương 2 – Ngăn xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 32
Vấn đề sinh ra bởi phép gán trên ngăn xếp liên kết là do nó chép các tham 
chiếu chứ không phải chép các trị. Phép gán trong trường hợp này được gọi là 
phép gán có ngữ nghĩa tham chiếu (reference semantics) . Ngược lại, khi phép gán 
thực sự chép dữ liệu trong CTDL chúng ta gọi là phép gán có ngữ nghĩa trị (value 
semantics). Trong hiện thực lớp ngăn xếp liên kết, hoặc chúng ta phải cảnh báo 
cho người sử dụng rằng phép gán chỉ là phép gán có ngữ nghĩa tham chiếu, hoặc 
chúng ta phải làm cho trình biên dịch C++ thực hiện phép gán có ngữ nghĩa trị. 
Trong C++, chúng ta hiện thực một phương thức đặc biệt gọi là phép gán được 
định nghĩa lại (overloaded assignment) để định nghĩa lại cách thực hiện phép 
gán. Khi trình biên dịch C++ dịch một phép gán có dạng x = y, nó ưu tiên chọn 
phép gán được định nghĩa lại trước nếu như lớp x có định nghĩa. Chỉ khi không có 
phương thức này, trình biên dịch mới dịch phép gán như là phép gán từng bit đối 
với các thuộc tính của đối tượng (nếu thuộc tính là con trỏ thì phép gán trở thành 
phép gán có ngữ nghĩa tham chiếu). Chúng ta cần định nghĩa lại để phép gán cho 
ngăn xếp liên kết trở thành phép gán có ngữ nghĩa trị. 
Có một vài cách để khai báo và hiện thực phép gán được định nghĩa lại. Cách 
đơn giản là khai báo như sau: 
 void Stack::operator= ( const Stack &original ); 
Phép gán này có thể được gọi như sau: 
 x.operator = (y); 
hoặc gọi theo cú pháp thường dùng: 
 x = y; 
Phép gán định nghĩa lại cho ngăn xếp liên kết cần làm những việc sau: 
• Chép dữ liệu từ ngăn xếp được truyền vào thông qua thông số. 
• Giải phóng vùng nhớ chiếm giữ bởi dữ liệu của đối tượng ngăn xếp đang 
được thực hiện lệnh gán. 
• Chuyển các dữ liệu vừa chép được cho đối tượng ngăn xếp được gán. 
template 
void Stack::operator = (const Stack &original) // Overload assignment 
/* 
post: đối tượng ngăn xếp được gán chứa các dữ liệu giống hệt ngăn xếp được truyền vào qua 
thông số. 
*/ 
{ 
 Node *new_top, *new_copy, *original_node = original.top_node; 
 if (original_node == NULL) new_top = NULL; 
 else { // Tạo bản sao các node. 
 new_copy = new_top = new Node(original_node->entry); 
Chương 2 – Ngăn xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 33
 while (original_node->next != NULL) { 
 original_node = original_node->next; 
 new_copy->next = new Node(original_node->entry); 
 new_copy = new_copy->next; 
 } 
 } 
 while (!empty()) // Làm rỗng ngăn xếp sẽ được gán. 
 pop(); 
 top_node = new_top; // Ngăn xếp được gán sẽ nắm giữ bản sao. 
} 
Lưu ý rằng trong phương thức trên chúng ta tạo ra một bản sao từ ngăn xếp 
original trước, rồi mới dọn dẹp ngăn xếp sẽ được gán bằng cách gọi phương 
thức pop nhiều lần. Nhờ vậy nếu trong ứng dụng có phép gán x = x thì dữ liệu 
cũng không bị sai. 
Phép gán được định nghĩa lại như trên thỏa yêu cầu là phép gán có ngữ nghĩa 
trị, tuy nhiên để có thể sử dụng trong trường hợp: 
first_stack=second_stack=third_stack=..., phép gán phải trả về 
Stack& (tham chiếu đến lớp Stack). 
2.4.3.3. Copy constructor 
Trường hợp cuối cùng về sự thiếu an toàn của các cấu trúc liên kết là khi trình 
biên dịch cần chép một đối tượng. Chẳng hạn, một đối tượng cần được chép khi 
nó là tham trị gởi cho một hàm. Trong C++, tác vụ chép mặc nhiên là chép các 
thuộc tính thành phần của lớp. Cũng giống như minh họa trong hình 2.7, tác vụ 
chép mặc nhiên này sẽ dẫn đến việc các đối tượng cùng chia xẻ dữ liệu. Nói một 
cách khác, tác vụ chép mặc định có ngữ nghĩa tham chiếu khi đối tượng có thuộc 
tính kiểu con trỏ. Điều này làm cho người sử dụng có thể vô tình làm mất dữ 
liệu: 
void destroy_the_stack (Stack copy) 
{ 
} 
int main() 
{ 
 Stack vital_data; 
 destroy_the_stack(vital_data); 
} 
Hàm destroy_the_stack nhận một bản sao copy của vital_data. Bản sao 
này cùng chia xẻ dữ liệu với vital_data, do đó khi kết thúc hàm, destructor thực 
hiện trên bản sao copy sẽ làm mất luôn dữ liệu của vital_data. 
C++ cho phép lớp có thêm phương thức copy constructor để tạo một đối 
tượng mới giống một đối tượng đã có. Nếu chúng ta hiện thực copy constructor 
Chương 2 – Ngăn xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 34
cho lớp Stack thì trình biên dịch C++ sẽ ưu tiên chọn tác vụ chép này thay cho 
tác vụ chép mặc định. Chúng ta cần hiện thực copy constructor để có được ngữ 
nghĩa trị. 
Đối với mọi lớp, khai báo chuẩn cho copy constructor cũng giống như khai báo 
constructor nhưng có thêm thông số là tham chiếu hằng đến đối tượng của lớp: 
 Stack::Stack ( const Stack &original ); 
Do đối tượng gọi copy constructor là một đối tượng rỗng vừa được tạo mới nên 
chúng ta không phải lo dọn dẹp dữ liệu như trường hợp đối với phép gán được 
định nghĩa lại. Chúng ta chỉ việc chép node đầu tiên và sau đó dùng vòng lặp để 
chép tiếp các node còn lại. 
template 
Stack::Stack(const Stack &original) // copy constructor 
/* 
post: đối tượng ngăn xếp vừa được tạo ra có dữ liệu giống với ngăn xếp original 
*/ 
{ 
 Node *new_copy, *original_node = original.top_node; 
 if (original_node == NULL) top_node = NULL; 
 else { // Tạo bản sao cho các node. 
 top_node = new_copy = new Node(original_node->entry); 
 while (original_node->next != NULL) { 
 original_node = original_node->next; 
 new_copy->next = new Node(original_node->entry); 
 new_copy = new_copy->next; 
 } 
 a( 
} 
Một cách tổng quát, đối với mọi lớp liên kết, hoặc chúng ta bổ sung copy 
constructor, hoặc chúng ta cảnh báo người sử dụng rằng việc chép đối tượng có 
ngữ nghĩa tham chiếu. 
2.4.4. Đặc tả ngăn xếp liên kết đã hiệu chỉnh 
Chúng ta kết thúc phần này bằng đặc tả đã được hiệu chỉnh dưới đây cho ngăn 
xếp liên kết. Phần đặc tả này có được mọi đặc tính an toàn mà chúng ta đã phân 
tích. 
template 
class Stack { 
public: 
// Các phương thức chuẩn của lớp Stack: 
 Stack(); 
 bool empty() const; 
 ErrorCode push(const Entry &item); 
 ErrorCode pop(); 
 ErrorCode top(Entry &item) const; 
Chương 2 – Ngăn xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 35
// Các đặc tả đảm bảo tính an toàn cho cấu trúc liên kết: 
 ~Stack(); 
 Stack(const Stack &original); 
 void operator =(const Stack &original); 
protected: 
 Node *top_node; 
}; 
Trên đây là phần trình bày đầy đủ nhất về những yêu cầu cần có đối với ngăn 
xếp liên kết, nhưng nó cũng đúng với các cấu trúc liên kết khác. Trong các phần 
sau của giáo trình này sẽ không giải thích thêm về 3 tác vụ này nữa, sinh viên tự 
phải hoàn chỉnh khi hiện thực bất kỳ CTDL nào có thuộc tính kiểu con trỏ. 
Chương 2 – Ngăn xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 36