Bài giảng Cấu trúc dữ liệu - Chương 4: Kiểu danh sách liên kết - Thiều Quang Trung

CHƯƠNG 4 
KIỂU DANH SÁCH LIÊN KẾT 
GV Th.S. Thiều Quang Trung 
Bộ môn Khoa học cơ bản 
Trường Cao đẳng Kinh tế Đối ngoại 
• Khái niệm danh sách liên kết 1 
• Các phép tính trên danh sách liên kết đơn 2 
• Các phép tính trên danh sách liên kết kép 3 
• Ứng dụng của danh sách liên kết 4 
Nội dung 
2 GV. Thiều Quang Trung 
Danh sách liên kết 
• Định nghĩa: Danh sách liên kết (DSLK) là một danh 
sách mà các phần tử được kết nối với nhau nhờ vào 
vùng liên kết của chúng. 
• Một phần tử của DSLK bao gồm 2 vùng chính: 
– Vùng chứa thông tin 
– Vùng chứa địa chỉ, còn gọi là vùng liên kết 
• DSLK là cấu trúc dữ liệu động nên có thể thực hiện 
các phép thêm vào, loại bỏ phần tử trong khi chạy 
chương trình. 
• Việc lưu trữ DSLK tốn bộ nhớ hơn danh sách đặc vì 
phải chứa thêm vùng liên kết. 
3 GV. Thiều Quang Trung 
Danh sách liên kết 
• Các kiểu tổ chức DSLK: 
– Danh sách liên kết đơn: mỗi phần tử liên kết với 
phần tử đứng sau nó trong danh sách: 
– Danh sách liên kết kép: mỗi phần tử liên kết với 
các phần tử đứng trước và sau nó trong danh 
sách: 
– Danh sách liên kết vòng: phần tử cuối danh sách 
liên kết với phần tử đầu danh sách: 
 4 GV. Thiều Quang Trung 
A B X Z Y 
A B C D 
Danh sách liên kết 
– Danh sách liên kết đơn vòng 
– Danh sách liến kết kép vòng 
5 GV. Thiều Quang Trung 
A B X Z Y 
A B C D 
Danh sách liên kết 
• Các phép toán cơ bản trên danh sách liên kết: 
1. Khởi tạo danh sách 
2. Kiểm tra danh sách rỗng 
3. Tìm kiếm 1 phần tử trong danh sách 
4. Thêm 1 phần tử vào danh sách 
5. Hủy 1 phần tử khỏi danh sách 
6. Duyệt danh sách 
7. Hủy toàn bộ danh sách 
6 GV. Thiều Quang Trung 
Danh sách liên kết đơn 
• Định nghĩa: DSLK đơn là loại DSLK mà vùng địa chỉ 
của mỗi phần tử chỉ chứa duy nhất một địa chỉ của 
phần tử tiếp theo. 
• Phần tử cuối cùng của DSLK đơn sẽ trỏ đến NULL 
GV. Thiều Quang Trung 7 
A B X Z Y 
head 
NULL 
Danh sách liên kết đơn 
• Ví dụ: Ta có danh sách theo dạng bảng sau 
 Ta có danh sách liên kết là : 
Joe – Marta – Bill – Koch - Sahra 
GV. Thiều Quang Trung 8 
Address Name Age Link 
100 Joe 20 140 
110 Bill 42 500 
140 Marta 27 110 
230 Sahra 25 NULL 
500 Koch 31 230 
Cài đặt danh sách liên kết đơn 
• Khai báo kiểu của 1 phần tử và kiểu danh sách liên kết đơn. 
• Để đơn giản ta xét mỗi node gồm vùng chứa dữ liệu là kiểu 
số nguyên: 
typedef struct NODE // kiểu của một phần tử trong danh sách 
{ 
 int info; 
 NODE *pNext; 
}; 
typedef struct LIST // kiểu danh sách liên kết 
{ 
 NODE *phead; 
}; 
• Trong thực tế biến info là một kiểu struct 
GV. Thiều Quang Trung 9 
Ví dụ danh sách liên kết đơn 
GV. Thiều Quang Trung 10 
Các phép toán trên DSLK đơn 
1. Khởi tạo danh sách: Khi khởi tạo, DSLK rỗng, ta 
đặt pHead = NULL 
GV. Thiều Quang Trung 11 
2. Kiểm tra danh sách rỗng: Kiểm tra pHead có 
bằng NULL hay không 
GV. Thiều Quang Trung 12 
Các phép toán trên DSLK đơn 
3. Tìm kiếm 1 phần tử trong danh sách: 
NODE* Search(LIST &list , int x) 
{ 
 NODE* p=list.pHead; 
 while( p!=NULL && p->info!=x) 
 p=p->pNext; 
 return p; 
} 
GV. Thiều Quang Trung 13 
Các phép toán trên DSLK đơn 
4. Thêm 1 phần tử vào DSLK: 
• Tạo node: 
GV. Thiều Quang Trung 14 
// Gán thông tin cho phần tử p 
Các phép toán trên DSLK đơn 
4.1. Thêm vào đầu DSLK: 
GV. Thiều Quang Trung 15 
Các phép toán trên DSLK đơn 
4.2. Thêm vào ngay sau phần tử q: 
GV. Thiều Quang Trung 16 
Các phép toán trên DSLK đơn 
5. Hủy 1 phần tử khỏi DSLK: 
5.1. Hủy 1 phần tử ở đầu danh sách: 
GV. Thiều Quang Trung 17 
Các phép toán trên DSLK đơn 
5.2. Hủy 1 phần tử đứng sau q: 
GV. Thiều Quang Trung 18 
Các phép toán trên DSLK đơn 
5.3. Hủy 1 phần tử có giá trị x: 
GV. Thiều Quang Trung 19 
Các phép toán trên DSLK đơn 
6. Duyệt DSLK: 
GV. Thiều Quang Trung 20 
Các phép toán trên DSLK đơn 
In các phần tử trong DSLK: 
void Output(LIST &list) 
{ 
 NODE* p=list.pHead; 
 while(p!=NULL) 
 { 
 printf(“%d\t”,p->info); 
 p=p ->pNext; 
 } 
 printf(“\n”); 
} 
GV. Thiều Quang Trung 21 
Các phép toán trên DSLK đơn 
7. Hủy toàn bộ DSLK: 
GV. Thiều Quang Trung 22 
Các phép toán trên DSLK đơn 
Nhận xét danh sách liên kết đơn 
• Ưu và nhược điểm của DSLK đơn: 
1. Ưu điểm: 
 - Dễ thực hiện các thao tác thêm, hủy một phần tử. 
 - Tận dụng được các vùng nhớ rời rạc 
2. Nhược điểm: 
 - Không thuận tiện cho thao tác truy xuất phần tử vì 
phải duyệt từ đầu danh sách. 
GV. Thiều Quang Trung 23 
Danh sách liên kết kép 
• Định nghĩa: DSLK kép (double linked list) là DSLK 
mà mỗi phần tử có 2 vùng liên kết: một vùng liên 
kết đến phần tử đứng trước nó và một vùng liên 
kết đến phần tử đứng sau nó 
GV. Thiều Quang Trung 24 
Cài đặt danh sách liên kết kép 
GV. Thiều Quang Trung 25 
Danh sách liên kết kép 
• Các phép toán trên DSLK kép: 
1. Khởi tạo danh sách (tương tự DSLK đơn) 
2. Thêm 1 phần tử vào danh sách 
3. Tìm kiếm 1 phần tử trong danh sach (tương tự DSLK 
đơn) 
4. Hủy một phần tử khỏi danh sách 
5. Duyệt danh sách (tương tự DSLK đơn) 
6. Hủy toàn bộ danh sách (tương tự DSLK đơn) 
GV. Thiều Quang Trung 26 
Các phép toán trên DSLK kép 
• Hàm bổ trợ tạo một Node mới 
– 
GV. Thiều Quang Trung 27 
• Thêm 1 phần tử vào đầu danh sách 
GV. Thiều Quang Trung 28 
Các phép toán trên DSLK kép 
• Thêm 1 phần tử vào đầu danh sách 
– 
GV. Thiều Quang Trung 29 
Các phép toán trên DSLK kép 
• Thêm 1 phần tử vào sau phần tử q: 
– 
GV. Thiều Quang Trung 30 
Các phép toán trên DSLK kép 
GV. Thiều Quang Trung 31 
Các phép toán trên DSLK kép 
• Thêm 1 phần tử vào trước phần tử q: 
– 
GV. Thiều Quang Trung 32 
Các phép toán trên DSLK kép 
• Hủy 1 phần tử khỏi danh sách: 
– Hủy phần tử ở đầu danh sách: 
GV. Thiều Quang Trung 33 
Các phép toán trên DSLK kép 
• Hủy phần tử đứng sau phần tử q: 
GV. Thiều Quang Trung 34 
Các phép toán trên DSLK kép 
• Hủy phần tử đứng trước phần tử q: 
GV. Thiều Quang Trung 35 
Các phép toán trên DSLK kép 
• Hủy phần tử có giá trị x: 
GV. Thiều Quang Trung 36 
Các phép toán trên DSLK kép 
1. Máy tính bỏ túi: 
 - Mô tả: xây dựng chương trình minh họa 1 máy tính 
bỏ túi dạng đơn giản 
 - Cách biểu diển: Phép toán được nhập vào dưới dạng 
hậu tố 
 + VD: tính a*(b+c) 
 + biểu thức hậu tố: abc+* 
 - Ứng dụng stack để tính kết quả biểu thức 
GV. Thiều Quang Trung 37 
Ứng dụng của danh sách 
2. Bài toán đa thức: 
 - Cộng, trừ, nhân, chia 2 đa thức. 
GV. Thiều Quang Trung 38 
Ứng dụng của danh sách 
3. Bài toán tính giá trị biểu thức: 
 - Biểu thức dạng trung tố: là cách viết tự nhiên của 
biểu thức. 
 VD: 8+2*(5-3) 
 - Biểu thức dạng hậu tố(postfix): còn được gọi là dạng 
ký pháp nghịch đảo Ba Lan (reverse Polish). Trong biểu 
thức dạng này, toán tử luôn đứng sau toán hạng của 
nó. 
 VD: 8+2*(5-3) 8253-*+ 
GV. Thiều Quang Trung 39 
Ứng dụng của danh sách 
GV: Thiều Quang Trung 40