Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 4: Danh sách

ng liên tục và dùng chỉ số last_used 
chứa vị trí cuối vừa mới sử dụng trong mảng. Các vị trí trong mảng có chỉ số lớn 
hơn last_used là các vị trí chưa hề được sử dụng. 
Các node đang chứa dữ liệu sẽ thuộc một DSLK có đầu vào là head. Head chứa 
vị trí của phần tử đầu của DSLK trong mảng. Các node kế tiếp trong DSLK này 
được truy xuất thông qua các chỉ số trong thành phần next của các node, biểu 
diễn bởi các mũi tên bên trái của next_node trong hình 4.6. Node cuối cùng của 
DSLK có chỉ số là –1. Chúng ta đọc được danh sách có các tên sắp theo thứ tự 
alphabet bắt đầu từ head = 8, Arthur, E. nằm đầu danh sách, rồi đến các tên tại 
các vị trí 0, 5, 3, 4, 1 của mảng; Smith, A. là tên nằm cuối danh sách. 
Đối với những node đã từng sử dụng và đã được giải phóng, chúng ta sẽ dùng 
một dạng của cấu trúc liên kết để nối kết chúng lại với nhau và để có thể truy 
xuất đến, từ node này đến node kế. Do ngăn xếp liên kết là một dạng đơn giản 
nhất của cấu trúc liên kết, chúng ta sẽ dùng ngăn xếp liên kết cho trường hợp 
này. Ngăn xếp liên kết cũng được nối kết nhờ chỉ số next trong mỗi node, 
available là một chỉ số chứa top của ngăn xếp. 
Các mũi tên bên phải của next_node trong hình 4.6, với đầu vào là 
available, chỉ các node trong một ngăn xếp bao gồm các node đã từng được sử 
dụng và đã được giải phóng. Chú ý rằng chỉ số trong các vùng next của ngăn xếp 
liên kết này chính xác là các số ≤ last_used, đó cũng là các vị trí trong mảng 
hiện tại không có dữ liệu. Bắt đầu từ available = 7, rồi đến 6, 9, 10, 2. Còn các 
vị trí từ last_used+1 trở đi là các vị trí chưa hề có dữ liệu. 
Chương 4 – Danh sách 
Giáo trình Cấu trúc dữ liệu và Giải thuật 71
Khi có một node bị loại khỏi DSLK chứa dữ liệu (chẳng hạn loại tên một sinh 
viên ra khỏi danh sách), vị trí của nó trong mảng được giải phóng và được push 
vào ngăn xếp liên kết. Ngược lại, khi cần thêm một node mới vào DSLK, chúng 
ta tìm vị trí trống bằng cách pop một phần tử ra khỏi ngăn xếp liên kết: trong 
hình 4.6 thì node mới sẽ được thêm vào vị trí 7 của mảng, còn available được 
cập nhật lại là 6. Chỉ khi cần thêm một node mới vào DSLK mà available=-1 
(ngăn xếp liên kết rỗng), chúng ta mới dùng đến một node mới chưa hề sử dụng 
đến, đó là vị trí last_used+1, last_used được cập nhật lại. Khi last_used 
đạt max_list–1, mà available=-1, thì workspace đầy, danh sách của chúng ta 
không cho phép thêm node mới nữa. 
Khi đối tượng List được khởi tạo, available và last_used phải được gán -
1: available=-1 chỉ ra rằng ngăn xếp chứa các vùng nhớ đã từng được sử dụng 
và đã được giải phóng là rỗng, last_used=-1 chỉ rằng chưa có vùng nhớ nào 
trong mảng đã được sử dụng. 
Chúng ta có khai báo DSLK trong mảng liên tục như sau: 
typedef int index; 
const int max_list = 7; // giá trị nhỏ dành cho việc kiểm tra CTDL. 
template 
class Node { 
public: 
 Entry entry; 
 index next; 
}; 
template 
class List { 
Hình 4.6- DSLK trong mảng liên tục và ngăn xếp liên kết chứa các vùng có thể sử dụng. 
Chương 4 – Danh sách 
Giáo trình Cấu trúc dữ liệu và Giải thuật 72
public: 
// Methods of the list ADT 
 List(); 
 int size() const; 
 bool full() const; 
 bool empty() const; 
 void clear(); 
 void traverse(void (*visit)(Entry &)); 
 Error_code retrieve(int position, Entry &x) const; 
 Error_code replace(int position, const Entry &x); 
 Error_code remove(int position, Entry &x); 
 Error_code insert(int position, const Entry &x); 
protected: 
// Các thuộc tính 
 Node workspace[max_list]; 
 index available, last_used, head; 
 int count; 
// Các hàm phụ trợ 
 index new_node(); 
 void delete_node(index n); 
 int current_position(index n) const; 
 index set_position(int position) const; 
}; 
Các phương thức public trên được đặc tả hoàn toàn giống với các hiện thực khác 
của List trước đây. Điều này có nghĩa là hiện thực mới của chúng ta có thể thay 
thế bất kỳ một hiện thực nào khác của CTDL trừu tượng List trong các ứng 
dụng. Một số hàm phụ trợ protected được bổ sung để quản lý các node trong 
workspace. Chúng được sử dụng để xây dựng các phương thức public nhưng 
không được nhìn thấy bởi người sử dụng. Các hàm new_node và delete_node 
thay thế cho các tác vụ new và delete của C++. Chẳng hạn, new_node trả về chỉ 
số của một vùng đang trống của workspace (để thêm phần tử mới cho danh 
sách). 
template 
index List::new_node() 
/* 
post: Trả về chỉ số của phần tử đầu tiên có thể sử dụng trong workspace; các thuộc tính 
available, last_used, và workspace được cập nhật nếu cần thiếu . 
Nếu workspace thực sự đầy, trả về -1. 
*/ 
{ 
 index new_index; 
 if (available != -1) { // ngăn xếp chưa rỗng. 
 new_index = available; // pop từ ngăn xếp. 
 available = workspace[available].next; // cập nhật cho ngăn xếp. 
 } else if (last_used<max_list - 1){// ngăn xếp rỗng và workspace chưa đầy. 
 new_index = ++last_used; 
 } else return -1; 
Chương 4 – Danh sách 
Giáo trình Cấu trúc dữ liệu và Giải thuật 73
 workspace[new_index].next = -1; 
 return new_index; 
} 
template 
void List::delete_node(index old_index) 
/* 
pre: Danh sách có một phần tử lưu tại chỉ số old_index. 
post: Vùng nhớ có chỉ số old_index được đẩy vào ngăn xếp các chỗ trống có thể sử dụng lại; 
các thuộc tính available, last_used, và workspace được cập nhật nếu cần thiết. 
*/ 
{ 
 index previous; 
 if (old_index == head) head = workspace[old_index].next; 
 else { 
 previous = set_position(current_position(old_index) - 1); 
 workspace[previous].next = workspace[old_index].next; 
 } 
 workspace[old_index].next = available; // đẩy vào ngăn xếp. 
 available = old_index; 
} 
Cả hai hàm này thực ra là thực hiện việc push và pop ngăn xếp. Nếu muốn 
chúng ta có thể viết các hàm xử lý ngăn xếp riêng rồi mới viết hàm sử dụng 
chúng. 
Các hàm phụ trợ protected khác là set_position và current_position. 
Cũng giống như các hiện thực trước, set_position nhận vị trí (thứ tự) của phần 
tử trong danh sách và trả về chỉ số phần tử đó trong workspace. Hàm 
current_position nhận chỉ số phần tử trong workspace và trả về vị trí (thứ 
tự) của phần tử trong danh sách. Hiện thực của chúng được xem như bài tập. 
index List::set_position(int position) const; 
pre: position là vị trí hợp lý trong danh sách; 0 ≤ position < count. 
post: trả về chỉ số trong workspace của node tại vị trí position trong danh sách.. 
int List::current_position(index n) const; 
post: trả về vị trí trong danh sách của node tại chỉ số n trong workspace, hoặc –1 nếu không có 
node này. 
4.5.3. Các tác vụ khác 
Chúng ta hiện thực các phương thức xử lý cho DSLK trong mảng liên tục bằng 
cách thay đổi các phương thức đã có của DSLK trong phần 4.3.2. Phần lớn việc 
hiện thực này được dành lại xem như bài tập, ở đây chúng ta sẽ viết hàm duyệt 
danh sách và thêm phần tử mới vào danh sách. 
template 
void List::traverse(void (*visit)(Entry &)) 
Chương 4 – Danh sách 
Giáo trình Cấu trúc dữ liệu và Giải thuật 74
/* 
post: Công việc cần làm bởi hàm *visit được thực hiện trên từng phần tử của danh sách, bắt 
đầu tử phần tử thứ 0. 
*/ 
{ 
 for (index n = head; n != -1; n = workspace[n].next) 
 (*visit)(workspace[n].entry); 
} 
So sánh phương thức này với phương thức tương ứng đối với DSLK dùng con 
trỏ và bộ nhớ động trong phần 4.3.2, chúng ta dễ dàng nhận thấy mỗi dòng lệnh 
là một sự chuyển đổi đơn giản một dòng lệnh của hiện thực trước. Bằng cách 
chuyển đổi tương tự chúng ta cũng có được phương thức thêm một phần tử mới 
vào DSLK trong mảng liên tục. 
template 
Error_code List::insert(int position, const Entry &x) 
/* 
post: Nếu danh sách chưa đầy và 0 <= position <= n, với n là số phần tử hiện có trong 
danh sách, phương thức sẽ thực hiện thành công việc chèn x vào tại position và các 
phần tử phía sau bị đẩy lùi thứ tự bởi 1 đơn vị. Ngược lại, phương thức trả về mã lỗi thích 
hợp. 
*/ 
{ 
 index new_index, previous, following; 
 if (position count) return range_error; 
 if (position > 0) { Tìm phần tử trước và sau vị trí 
 previous = set_position(position - 1); cần thêm phần tử mới. 
 following = workspace[previous].next; 
 } 
 else following = head; 
 if ((new_index = new_node()) == -1) return overflow; // Tìm vùng trống. 
 workspace[new_index].entry = x; // Cập nhật dữ liệu vào vùng trống. 
 workspace[new_index].next = following; 
 if (position == 0) 
 head = new_index; // Trường hợp đặc biệt: thêm 
vào đầu DSLK. Thêm phần tử mới 
 else vào DSLK. 
 workspace[previous].next = new_index; 
 count++; 
 return success; 
} 
4.5.4. Các biến thể của danh sách liên kết trong mảng liên tục 
Mảng liên tục cùng các chỉ số không những được dùng cho DSLK, chúng còn có 
hiệu quả tương tự đối với DSLK kép hoặc với vài biến thể khác. Đối với DSLK 
kép, khả năng áp dụng phép tính số học cho các chỉ số cho phép một hiện thực 
mà trong đó các tham chiếu tới và lui chỉ cần chứa trong một vùng chỉ số đơn (sử 
dụng cả trị âm lẫn trị dương cho các chỉ số).