Bài giảng Ngôn ngữ lập trình - Bài 10: Các kiểu dữ liệu trừu tượng: Danh sách liên kết, ngăn xếp, hàng đợi - Lê Nguyễn Tuấn Thành

NGÔN NGỮ LẬP TRÌNH 
Bài 10: 
Các Kiểu Dữ Liệu Trừu Tượng: 
Danh sách liên kết, 
Ngăn xếp, Hàng đợi 
Giảng viên: Lê Nguyễn Tuấn Thành 
Email: thanhlnt@tlu.edu.vn 
Bộ Môn Công Nghệ Phần Mềm – Khoa CNTT 
Trường Đại Học Thủy Lợi 
NỘI DUNG 
1. Các nút (Nodes) và Danh sách liên kết 
1. Tạo, tìm kiếm 
2. Ứng dụng danh sách liên kết 
1. Ngăn xếp (Stacks), 
2. Hàng đợi (Queue) 
3. Lớp bạn 
3. Iterators 
1. Con trỏ như iterators 
4. Cây (Trees) 
2 
Bài giảng có sử dụng hình vẽ trong cuốn sách “Practical Debugging in C++, 
A. Ford and T. Teorey, Prentice Hall, 2002” 
GIỚI THIỆU 
 Danh sách liên kết 
 Được xây dựng sử dụng con trỏ 
 Tăng giảm kích thước trong thời gian chạy 
 Cây cũng sử dụng con trỏ 
 Con trỏ là xương sống của những cấu trúc này 
 Sử dụng biến động 
 Thư viện mẫu chuẩn (STL) 
 Có những phiên bản định nghĩa sẵn của một vài cấu 
trúc 
3 
CÁCH TIẾP CẬN 
 Có 3 cách để xử lý những cấu trúc dữ liệu này 
1. Cách tiếp cận C-style: sử dụng hàm và cấu trúc toàn 
cục với mọi thứ đều public 
2. Sử dụng lớp với các biến thành viên private và các 
hàm accessor – mutator 
3. Sử dụng lớp bạn 
 Danh sách liên kết sử dụng phương thức 1 
 Ngăn xếp, hàng đợi sử dụng phương thức 2 
 Cây sử dụng phương thức 3 
4 
NÚT VÀ DANH SÁCH LIÊN KẾT 
 Danh sách liên kết 
 Một ví dụ đơn giản của “cấu trúc dữ liệu động” 
 Bao gồm nhiều nút 
 Mỗi nút là một biến kiểu cấu trúc hoặc đối tượng 
của lớp (có thể tạo tự động với lệnh new) 
 Nút cũng bao gồm con trỏ trỏ tới những nút khác 
 Cung cấp “sự liên kết” 
5 
NÚT VÀ CON TRỎ 
6 
ĐỊNH NGHĨA NÚT 
 struct ListNode 
{ 
 string item; 
 int count; 
 ListNode *link; 
}; 
typedef ListNode* ListNodePtr; 
 Chú ý sự tuần hoàn (circularity) 
7 
CON TRỎ HEAD 
 Đối tượng với nhãn “head” không phải là một nút: 
ListNodePtr head; 
 Là một con trỏ đơn giản tới một nút 
 Chỉ tới nút đầu tiên trong danh sách 
 Head được sử dụng để lưu trữ vị trí đầu tiên trong 
danh sách 
 Cũng được sử dụng như đối số truyền vào hàm 
8 
VÍ DỤ VỀ TRUY CẬP NÚT 
 (*head).count = 12; 
 Đặt biến thành viên count của nút trỏ bởi con trỏ head 
bằng 12 
 Toán tử alternate -> 
 Được gọi là toán tử mũi tên (arrow operator) 
 Kí hiệu viết tắt là sự kết hợp của hai toán tử * và . 
 Viết lại câu lệnh trên bằng: head->count=12; 
 cin>>head->item: 
 Gắn chuỗi nhập vào cho biến thành viên item 
9 
DẤU HIỆU KẾT THÚC (END MARKERS) 
 Sử dụng NULL cho con trỏ nút 
 Được xem như “lính canh” (sentinel) cho các nút 
 Chỉ định rằng không còn liên kết sau nút này 
 Cung cấp dấu hiệu kết thúc tương tự như cách 
chúng ta sử dụng mảng được lấp đầy một phần 
(partially-filled) 
10 
TRUY CẬP DỮ LIỆU TRONG NÚT 
11 
DANH SÁCH LIÊN KẾT 
 Nút đầu tiên gọi là head 
 Được trỏ tới bởi con trỏ tên là head 
 Nút cuối cùng cũng đặc biệt 
 Biến con trỏ thành viên của nó là NULL 
 Dễ dàng kiểm tra kết thúc của danh sách liên kết 
12 
ĐỊNH NGHĨA LỚP DANH SÁCH LIÊN KẾT 
 class IntNode 
{ 
public: 
 IntNode() { } 
 IntNode(int theData, IntNOde* theLink) 
 : data(theData), link(theLink) { } 
 IntNode* getLink() const {return link;} 
 int getData() const {return data;} 
 void setData(int theData) {data = theData;} 
 void setLink(IntNode* pointer) {link=pointer;} 
private: 
 int data; 
 IntNode *link; 
}; 
typedef IntNode* IntNodePtr; 13 
LỚP DANH SÁCH LIÊN KẾT 
 Chú ý tất cả định nghĩa hàm thành viên đều 
inline 
 Đủ nhỏ và đơn giản 
 Chú ý hàm khởi tạo 2 tham số 
 Cho phép tạo các nút với dữ liệu riêng biệt và thành 
viên liên kết được chỉ định 
 Ví dụ: IntNodePtr p2 = new IntNode(42, p1); 
14 
TẠO NÚT ĐẦU TIÊN 
 IntNodePtr head; 
 Khai báo biến con trỏ head 
 head = new IntNode; 
 Cấp phát động cho nút mới 
 Nút đầu tiên đã trong danh sách và được gán cho 
head 
 head->setData(3); 
head->setLink(NULL); 
 Đặt dữ liệu cho nút head 
 Đặt liên kết của nút đầu là NULL, bởi chúng ta mới 
chỉ có 1 nút! 
15 
MINH HỌA THÊM MỘT NÚT CHO HEAD 
CỦA DANH SÁCH LIÊN KẾT 
16 
TRƯỜNG HỢP BỊ MẤT NÚT 
17 
CHÈN MỘT NÚT VÀO GIỮA 
DANH SÁCH LIÊN KẾT (1/2) 
18 
CHÈN MỘT NÚT VÀO GIỮA 
DANH SÁCH LIÊN KẾT (2/2) 
19 
XÓA MỘT NÚT 
20 
TÌM KIẾM TRONG DANH SÁCH LIÊN KẾT 
 Hàm với hai đối số 
 IntNodePtr search(IntNodePtr head, int target); 
 // Điều kiện trước: con trỏ head trỏ tới đầu danh 
 // sách liên kết. Con trỏ của nút cuối cùng là NULL. 
 // Nếu danh sách rỗng, head là NULL 
 // Trả về con trỏ tới nút đầu tiên chứa giá trị target 
 // Nếu không tìm thấy, trả về NULL 
 Đơn giản là duyệt qua (traversal) danh sách 
 Giống như duyệt mảng 
21 
MÃ GIẢ (PSEUDOCODE) 
CHO HÀM TÌM KIẾM 
 while (con trỏ here chưa trỏ tới nút đích hoặc nút 
cuối) 
{ 
 dịch chuyển con trỏ here tới nút tiếp theo 
trong danh sách 
} 
if (nút được trỏ bởi here chứa giá trị đích) 
 return con_trỏ; 
else 
 return NULL; 
22 
THUẬT TOÁN CHO HÀM TÌM KIẾM 
 while (here->getData() != target && 
 here->getLink() != NULL) 
 here = here->getLink(); 
if (here->getData() == target) 
 return here; 
else 
 return NULL; 
23 
NGĂN XẾP (STACKS) 
 Cấu trúc dữ liệu ngăn xếp 
 Lấy ra dữ liệu theo thứ tự ngược với khi được lưu trữ 
 LIFO – Last-in/First-out (vào sau, ra trước) 
 Hình dung giống như một cái “hố trên mặt đất” 
 Ngăn xếp được sử dụng cho nhiều tác vụ 
 Truy vết những lời gọi hàm 
 Quản lý bộ nhớ 
 Sử dụng danh sách liên kết để cài đặt ngăn xếp 
24 
MINH HỌA NGĂN XẾP 
25 
FILE GIAO DIỆN CỦA MỘT 
LỚP KHUÔN MẪU NGĂN XẾP (1/2) 
26 
FILE GIAO DIỆN CỦA MỘT 
LỚP KHUÔN MẪU NGĂN XẾP (2/2) 
27 
DRIVER LỚP KHUÔN MẪU NGĂN XẾP 
CHƯƠNG TRÌNH MẪU (1/3) 
28 
DRIVER LỚP KHUÔN MẪU NGĂN XẾP 
CHƯƠNG TRÌNH MẪU (2/3) 
29 
DRIVER LỚP KHUÔN MẪU NGĂN XẾP 
CHƯƠNG TRÌNH MẪU (3/3) 
30 
THAO TÁC PUSH VÀ POP CỦA NGĂN XẾP 
 Push: thêm dữ liệu vào ngăn xếp 
 Đẩy vào từ vị trí đầu tiên của ngăn xếp 
 Pop: lấy dữ liệu ra khỏi ngăn xếp 
 Lấy ra từ vị trí đầu tiên của ngăn xếp 
31 
HÀNG ĐỢI (QUEUE) 
 Một cấu trúc dữ liệu phổ biến khác 
 Xử lý dữ liệu theo cách first-in/first-out (vào trước/ra 
trước - FIFO) 
 Dữ liệu được chèn vào cuối danh sách 
 Dữ liệu được lấy ra từ đầu danh sách 
 Đại diện của hình thức “đường” (line) điển hình 
 Giống như bank teller lines, movie theatre lines  
32 
FILE GIAO DIỆN CỦA 
MỘT LỚP KHUÔN MẪU HÀNG ĐỢI (1/3) 
33 
FILE GIAO DIỆN CỦA 
MỘT LỚP KHUÔN MẪU HÀNG ĐỢI (2/3) 
34 
FILE GIAO DIỆN CỦA 
MỘT LỚP KHUÔN MẪU HÀNG ĐỢI (3/3) 
35 
DRIVER LỚP KHUÔN MẪU GIAO DIỆN: 
CHƯƠNG TRÌNH MẪU 
36 
LỚP BẠN 
 Nhớ lại cách sử dụng của hai hàm getLink và 
setLink (accessor và mutator) 
 Có một chút phiền toái 
 Giống như làm dữ liệu public (khả dụng cho tất cả)?! 
 Sử dụng hàm bạn 
 Sử dụng lớp “bạn” khuôn mẫu hàng đợi của lớp khuôn 
mẫu node 
 Tất cả thành viên liên kết riêng chỉ trực tiếp khả dụng 
(available) trong hàm thành viên của lớp hàng đợi 
37 
KHAI BÁO TIẾN (FORWARD DECLARATION) 
 Mối quan hệ bạn bè giữa các lớp thường yêu cầu 
các lớp tham chiếu lẫn nhau 
 Bằng cách nào cả hai lớp được khai báo cùng một thời 
điểm? 
 Yêu cầu khai báo tiến (forward declaration) 
 Một tiêu đề lớp đơn giản được đặt bên trong lớp kia 
 class Queue; //Forward Dec. 
 Ám chỉ rằng lớp Queue sẽ tồn tại 
38 
ITERATORS 
 Xây dựng để duyệt dữ liệu 
 Cho phép bất kỳ hành động nào được yêu cầu trên dữ 
liệu 
 Con trỏ thường được sử dụng như iterator 
 Nhớ lại: danh sách liên kết – một cấu trúc dữ liệu 
nguyên mẫu/điển hình (prototypical) 
 Con trỏ: ví dụ điển hình của iterator, duyệt qua 
danh sách từ vị trí đầu tiên 
 Node_Type *iterator; 
for (iterator = Head; iterator != NULL; iterator=iterator-
>Link) 
 Do_Action 39 
LỚP ITERATOR 
 Linh hoạt hơn so với con trỏ 
 Các toán tử được nạp chồng điển hình như 
 ++ dịch chuyển tiến iterator sang vị trí tiếp theo 
 -- dịch lùi iterator về vị trí trước 
 == so sánh bằng với iterator 
 != so sánh khác với iterator 
 * truy cập một vị trí/mục 
 Lớp cấu trúc dữ liệu sẽ có 2 hàm thành viên 
 begin(): trả iterator về vị trí đầu tiên trong cấu trúc 
 end(): kiểm tra iterator có ở vị trí cuối không 
40 
VÍ DỤ LỚP ITERATOR 
 Duyệt qua cấu trúc dữ liệu có tên ds: 
 for (i=ds.begin();i!=ds.end();i++) 
 process *i //*i is current data item 
 i là một iterator 
41 
GIỚI THIỆU VỀ CÂY 
 Cây là một cấu trúc dữ liệu phức tạp 
 Giới thiệu những điều cơ bản trong bài học này 
 Xây dựng, thao tác với cây 
 Sử dụng nút và con trỏ 
 Nhớ lại danh sách liên kết: các nút chỉ có một con 
trỏ tới vị trí nút tiếp theo 
 Cây có 2 con trỏ, hoặc thậm chí nhiều hơn, tới 
những nút khác 
42 
CÂY NHỊ PHÂN (1/2) 
43 
CÂY NHỊ PHÂN (2/2) 
44 
THUỘC TÍNH CỦA CÂY 
 Đường đi 
 Từ đỉnh tới một nút bất kỳ 
 Không quay vòng, đi theo con trỏ sẽ đến vị trí cuối 
cùng 
 Chú ý ở đây mỗi nút có 2 liên kết 
 Được gọi là cây nhị phân (binary tree) 
 Kiểu phổ biến nhất của cây 
 Nút gốc (root node) 
 Tương tự như head của danh sách liên kết 
 Nút lá (leaf nodes) 
 Cả hai biến liên kết đều là NULL (không có cây con) 
45 
CÂY VÀ ĐỆ QUY 
 Thấy rằng: cây có cấu trúc đệ quy 
 Mỗi cây có 2 cây con 
 Mỗi cây con lại có hai cây con của nó  
 Có thể sử dụng các thuật toán đệ quy để tìm kiếm! 
46 
XỬ LÝ CÂY – 3 PHƯƠNG PHÁP 
(TREE PROCESSING) 
1. Xử lý preorder (preorder processing) 
 Xử lý dữ liệu ở nút gốc 
 Xử lý cây con bên trái 
 Xử lý cây con bên phải 
2. Xử lý in-order 
 Xử lý cây con bên trái 
 Xử lý dữ liệu ở nút gốc 
 Xử lý cây con bên phải 
3. Xử lý postorder 
 Xử lý cây con bên trái 
 Xử lý cây con bên phải 
 Xử lý dữ liệu ở nút gốc 
47 
LƯU TRỮ CÂY 
 Ví dụ của chúng ta lưu giá trị theo một cách đặc 
biệt 
 Quy luật lưu trữ dữ liệu trong cây nhị phân 
 Dữ liệu ở cây con bên trái nhỏ hơn dữ liệu gốc 
 Dữ liệu ở cây con bên phải lớn hơn dữ liệu gốc 
 2 quy tắc trên được áp dụng đệ quy với từng cây con 
 Cây sử dụng cơ chế lưu trữ: 
 Được gọi là cây nhị phân tìm kiếm (Called binary 
search tree - BST) 
 Duyệt cây: 
Inorder values "in order" 
Preorder  "prefix" notation 
Postorder  "postfix" notation 
48 
TÓM TẮT 
 Nút là cấu trúc hoặc đối tượng của lớp 
 Một hoặc nhiều thành viên là con trỏ 
 Các nút được kết nối bởi con trỏ thành viên 
 Tạo nên cấu trúc mà kích thước có thể thay đổi trong lúc 
chạy chương trình 
 Danh sách liên kết 
 Danh sách các nút mà mỗi nút trỏ tới phần tử tiếp theo 
 Kết thúc của danh sách liên kết với con trỏ NULL 
 Ngăn xếp có cấu trúc LIFO 
 Hàng đợi có cấu trúc FIFO 
 Xây dựng iterator cho phép duyệt qua phần tử dữ liệu 
trong cấu trúc dữ liệu 
 Cấu trúc dữ liệu cây 
 Mỗi nút có nhiều hơn 2 con trỏ thành viên 
 Mỗi con trỏ trỏ tới nút khác hoặc cây con khác 
 Cây nhị phân tìm kiếm 
 Một vài quy luật lưu trữ đặc biệt giúp cho việc tìm kiếm 
nhanh hơn 
49 
GIÁO TRÌNH THAM KHẢO 
 Giáo trình chính: W. Savitch, Absolute C++, 
Addison Wesley, 2002 
 Tham khảo: 
 A. Ford and T. Teorey, Practical Debugging in C++, 
Prentice Hall, 2002 
 Nguyễn Thanh Thủy, Kĩ thuật lập trình C++, NXB 
Khoa học và Kĩ Thuật, 2006 
50