Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 18: Ứng dụng danh sách liên kết và bảng băm

iều này bằng cách xét 
mọi ô có trong lưới chứa cấu hình grid, tính các ô kế cận chung quanh cho mỗi ô 
để xác định trạng thái kế tiếp của nó. Các thông tin này được chứa trong biến cục 
bộ new_grid và sau đó được chép vào grid. 
Chúng ta sẽ lặp lại những công việc này ngoại trừ việc phải xét mọi ô có thể 
có trong cấu hình do đây là một lưới không có giới hạn. Thay vào đó, chúng ta 
nên giới hạn tầm nhìn của chúng ta chỉ trong các ô có khả năng sẽ sống trong 
trạng thái kế. Đó có thể là các ô nào? Rõ ràng đó chính là các ô đang sống trong 
trạng thái hiện tại, chúng có thể chết đi nhưng cũng có thể tiếp tục sống trong 
Chương 18 – Ứng dụng danh sách liên kết và bảng băm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 411
trạng thái kế. Ngoài ra, một số ô đang chết cũng có thể trở nên sống trong trạng 
thái sau, nhưng đó chỉ là những ô đang chết nằm kề những ô đang sống (các ô có 
màu xám trong hình 9.18). Những ô xa hơn nữa không có khả năng sống dậy do 
chúng không có ô nào kế cận đang sống. 
Trong phương thức update, biến cục bộ Life new_configuration dùng để 
chứa cấu hình mới: chúng ta thực hiện vòng lặp cho tất cả những ô đang sống và 
những ô kế cận của chúng, đối với mỗi ô như vậy, trước hết cần xác định xem nó 
đã được thêm vào new_configuration hay chưa, chúng ta cần phải cẩn thận để 
tránh việc thêm bị lặp lại hai lần cho một ô. Nếu quả thật ô đang xét chưa có 
trong new_configuration, chúng ta dùng hàm neighbor_count để quyết định 
việc có thêm nó vào cấu hình mới hay không. 
Ở cuối phương thức, chúng ta cần hoán đổi các thành phần List và 
Hash_table giữa cấu hình hiện tại và cấu hình mới new_configuration. Sự 
hoán đổi này làm cho đối tượng Life có được cấu hình đã được cập nhật, ngoài 
ra, nó còn bảo đảm rằng các ô, danh sách, và bảng băm trong cấu hình cũ của đối 
tượng Life sẽ được giải phóng khỏi bộ nhớ cấp phát động (việc này được thực 
hiện do trình biên dịch tự động gọi destructor cho đối tượng cục bộ 
new_configuration). 
void Life::update() 
/* 
post: Đối tượng Life chứa cấu hình ở trạng thái kế. 
uses: Lớp Hash_table và lớp Life và các hàm phụ trợ. 
*/ 
{ 
 Life new_configuration; 
 Cell *old_cell; 
Hình 18.6 – Cấu hình Life với các ô chết viền chung quanh. 
Chương 18 – Ứng dụng danh sách liên kết và bảng băm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 412
 for (int i = 0; i size(); i++) { 
 living->retrieve(i, old_cell); // Lấy một ô đang sống. 
 for (int row_add = -1; row_add < 2; row_add ++) 
 for (int col_add = -1; col_add < 2; col_add++) { 
 int new_row = old_cell->row + row_add, 
 new_col = old_cell->col + col_add; 
// new_row, new_col là toạ độ của ô đang xét hoặc ô kế cận của nó. 
 if (!new_configuration.retrieve(new_row, new_col)) 
 switch (neighbor_count(new_row, new_col)) { 
 case 3: // Số ô sống kế cận là 3 thì ô đang xét trở thành sống. 
 new_configuration.insert(new_row, new_col); 
 break; 
 case 2: // Số ô sống kế cận là 2 thì ô đang xét giữ nguyên trạng thái. 
 if (retrieve(new_row, new_col)) 
 new_configuration.insert(new_row, new_col); 
 break; 
 default: // Ô sẽ chết. 
 break; 
 } 
 } 
 } 
// Tráo dữ liệu trong configuration với dữ liệu trong new_configuration. 
new_configuration sẽ được dọn dẹp bởi destructor của nó. 
 List *temp_list = living; 
 living = new_configuration.living; 
 new_configuration.living = temp_list; 
 Hash_table *temp_hash = is_living; 
 is_living = new_configuration.is_living; 
 new_configuration.is_living = temp_hash; 
} 
In cấu hình 
Để in được tất cả các ô đang sống, chúng ta có thể liệt kê lần lượt mỗi dòng 
một ô với tọa độ row, col của nó. Ngược lại nếu muốn biểu diễn đúng vị trí row, 
col trên lưới, chúng ta nhận thấy rằng chúng ta không thể hiển thị nhiều hơn là 
một mẩu nhỏ của một cấu hình Life không có giới hạn lên màn hình. Do đó 
chúng ta sẽ in một cửa sổ chữ nhật để hiển thị trạng thái của 20 x 80 các vị trí ở 
trung tâm của cấu hình Life. 
Đối với mỗi ô trong cửa sổ, chúng ta truy xuất trạng thái của nó từ bảng băm 
và in một ký tự trắng hoặc khác trắng tương ứng với trạng thái chết hoặc sống 
của nó. 
void Life::print() 
/* 
post: In một trạng thái của đối tượng Life. 
uses: Life::retrieve. 
*/ 
Chương 18 – Ứng dụng danh sách liên kết và bảng băm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 413
{ 
 int row, col; 
 cout << endl << "The current Life configuration is:" << endl; 
 for (row = 0; row < 20; row++) { 
 for (col = 0; col < 80; col++) 
 if (retrieve(row, col)) cout << '*'; 
 else cout << ' '; 
 cout << endl; 
 } 
 cout << endl; 
} 
Tạo và thêm các ô mới 
Phương thức insert tạo một ô mới với tọa độ cho trước và thêm nó vào bảng 
băm is_living và vào danh sách living. 
ErrorCode Life::insert(int row, int col) 
/* 
pre: Ô có tọa độ (row,col) không thuộc về đối tượng Life (ô đang chết) 
post: Ô có tọa độ (row,col) được bổ sung vào đối tượng Life (ô trở nên sống). Nếu việc 
thêm vào List hoặc Hash_table không thành công thì lỗi sẽ được trả về. 
uses: Các lớp List, Hash_table, và cấu trúc Cell. 
*/ 
{ 
 Error_code outcome; 
 Cell *new_cell = new Cell(row, col); 
 int index = living->size(); 
 outcome = living->insert(index, new_cell); 
 if (outcome == success) 
 outcome = is_living->insert(new_cell); 
 if (outcome != success) 
 cout << " Warning: new Cell insertion failed" << endl; 
 return outcome; 
} 
Constructor và destructor cho các đối tượng Life 
Chúng ta cần cung cấp constructor và destructor cho lớp Life của chúng ta để 
định vị và giải phóng các thành phần cấp phát động của nó. Constructor cần thực 
hiện toán tử new cho các thuộc tính con trỏ. 
Life::Life() 
/* 
post: Các thuộc tính thành phần của đối tượng Life được cấp phát động và được khởi tạo. 
uses: Các lớp Hash_table, List. 
*/ 
{ 
 living = new List; 
 is_living = new Hash_table; 
} 
Chương 18 – Ứng dụng danh sách liên kết và bảng băm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 414
Destructor cần giải phóng mọi phần tử được cấp phát động bởi bất kỳ một 
phương thức nào đó của lớp Life. Bên cạnh hai con trỏ living và is_living 
được khởi tạo nhờ constructor còn có các đối tượng Cell mà chúng tham chiếu 
đến đã được cấp phát động trong phương thức insert. Destructor cần giải phóng 
các đối tượng Cell này trước khi giải phóng living và is_living. 
Life::~Life() 
/* 
post: Các thuộc tính cấp phát động của đối tượng Life và các đối tuợng do chúng tham chiếu 
được giải phóng. 
uses: Các lớp Hash_table, List. 
*/ 
{ 
 Cell *old_cell; 
 for (int i = 0; i size(); i++) { 
 living->retrieve(i, old_cell); 
 delete old_cell; 
 } 
 delete is_living; // Gọi destructor của Hash_table. 
 delete living; // Gọi destructor của List. 
} 
Đối với những cấu trúc có nhiều liên kết bằng con trỏ như thế này, chúng ta luôn 
phải đặt vấn đề về khả năng tạo rác do những sơ suất của chúng ta. Thông 
thường thì destructor của một lớp luôn làm tốt nhiệm vụ của nó, nhưng nó chỉ dọn 
dẹp những gì thuộc đối tượng của nó, chứ không biết đến những gì mà đối tượng 
của nó tham chiếu đến. Nếu chúng ta chủ quan, việc dọn dẹp không diễn ra đúng 
như chúng ta tưởng. Khi chạy, chương trình có thể là quên dọn dẹp, cũng có thể 
là dọn dẹp nhiều hơn một lần đối với một vùng nhớ được cấp phát động. Đây cũng 
là một vấn đề khá lý thú mà sinh viên nên tự suy nghĩ thêm. 
Hàm băm 
Hàm băm ở đây có hơi khác với những gì chúng ta đã gặp trong những phần 
trước, thông số của nó có đến hai thành phần (row và col), nhờ vậy chúng ta có 
thể dễ dàng sử dụng một vài dạng của phép trộn. Trước khi quyết định nên làm 
như thế nào, chúng ta hãy xét trường hợp một mảng chữ nhật nhỏ có ánh xạ một 
một dưới đây chính là một hàm chỉ số. Có chính xác là maxrow phần tử trong mỗi 
hàng, các chỉ số i, j được ánh xạ đến i + maxrow*j để đặt mảng chữ nhật vào 
một chuỗi các vùng nhớ liên tục, hàng này kế tiếp hàng kia. 
Chúng ta nên dùng cách ánh xạ tương tự cho hàm băm của chúng ta và sẽ thay 
thế maxrow bằng một số thích hợp, chẳng hạn như một số nguyên tố, để việc 
phân phối được rải đều và giảm sự đụng độ. 
Chương 18 – Ứng dụng danh sách liên kết và bảng băm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 415
const int factor = 101; 
int hash(int row, int col) 
/* 
post: Trả về giá trị hàm băm từ 0 đến hash_size - 1 tương ứng với tọa độ (row, col). 
*/ 
{ 
 int value; 
 value = row + factor * col; 
 value %= hash_size; 
 if (value < 0) return value + hash_size; 
 else return value; 
} 
Các chương trình con khác 
Các phương thức còn lại của Life như initialize, retrieve, và 
neighbor_count đều được xem xét tương tự như các hàm vừa rồi hoặc như các 
hàm tương ứng trong phiên bản thứ nhất. Chúng ta dành chúng lại như bài tập. 
Chương 18 – Ứng dụng danh sách liên kết và bảng băm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 416