Bài giảng Cấu trúc dữ liệu 1 - Chương 4: Danh sách liên kết

26
4. Danh sách liên kết
• Có nhiều loại danh sách liên kiết như: 
– Danh sách liên kết đơn
– Danh sách liên kết kép
– Danh sách liên kết vòng
– ….
• Trong môn này ta tìm hiểu kỹ về danh 
sách liên kết đơn
27
4. Danh sách liên kết
28
4. Danh sách liên kết
29
4. Danh sách liên kết
30
4. Danh sách liên kết
31
4. Danh sách liên kết
32
5. Danh sách liên kết đơn
Mô tả:
 Danh sách liên kết đơn là danh sách gồm nhiều
nút mỗi nút có thông tin cần thiết và một liên
kết đến nút khác.
 Danh sách liên kết đơn cần có 1 head trỏ vào
nút đầu tiên và con trỏ tail trỏ vào nút cuối
cùng.
A B C D
head
tail
33
5. Danh sách liên kết đơn
• Tạo danh sách
– Khai báo danh sách liên kết
– Khởi tạo danh sách liên kết
– Tạo mới một phần tử để thêm vào danh sách liên kết
– Thêm vào đầu danh sách
– Thêm vào cuối danh sách
– Xuất dữ liệu của toàn bộ danh sách liên kết
– Thêm vào sau một phần tử cho trước
• Tìm kiếm
– Tìm một phần tử có khóa cho trước
– Tìm một phần tử đứng trước một phần tử cho trước
• Hủy danh sách
– Hủy một phần tử đầu danh sách
– Hủy một phần tử cuối danh sách
– Hủy một phần tử sau một phần tử cho trước
– Hủy một phần tử có khóa cho trước
– Hủy toàn bộ danh sách 34
5. Danh sách liên kết đơn
struct NODE
{
int data; // 2 byte (dos)
NODE* next; // 2 byte (dos)
};
struct LIST
{
NODE* pHead;
NODE* pTail;
};
35
5. Danh sách liên kết đơn
void KhoiTao(LIST &l)
{
l.pHead =NULL;
l.pTail =NULL;
}
Việc khởi tạo danh sách liên kết nhằm xác định 
danh sách ban đầu mới tạo ra là rỗng
36
5. Danh sách liên kết đơn
NODE* GetNode(int x)
{
NODE* p;
p=new NODE;
p->next=NULL;
p->data=x;
return p;
}
Tạo mới một phần tử để thêm vào danh sách
37
5. Danh sách liên kết đơn
Thêm một phần tử vào đầu danh sách liên kết
1. Danh sách rỗng
2. Danh sách đã có phần tử
38
5. Danh sách liên kết đơn
void AddHead(LIST &l, NODE* add)
{
if(l.pHead==NULL)
{
l.pHead=l.pTail=add;
}
else
{
add->next=l.pHead;
l.pHead=add;
}
}
Thêm một phần tử vào đầu danh sách liên kết
39
5. Danh sách liên kết đơn
Thêm một phần tử vào cuối danh sách liên kết
1. Danh sách rỗng
2. Danh sách đã có phần tử
40
5. Danh sách liên kết đơn
void AddTail(LIST &l, NODE* add)
{
if(l.pHead==NULL)
{
l.pHead=l.pTail=add;
}
else
{
l.pTail->next=add;
l.pTail=add;
}
}
Thêm một phần tử vào cuối danh sách liên kết
41
5. Danh sách liên kết đơn
void PrintfList(LIST l)
{
NODE* p;
p=l.pHead;
while(p!=NULL)
{
cout”data;
p = p->next;
}
}
Xuất dữ liệu của danh sách liên kết
42
5. Danh sách liên kết đơn
Tìm một phần tử trong danh sách liên kết khi biết khóa (data)
Sử dụng 1 con trỏ phụ p để duyệt tất cả
các phần tử trong danh sách liên kết
43
5. Danh sách liên kết đơn
NODE* Search(LIST l, int data)
{
NODE* p=l.pHead;
while((p!=NULL) && 
(p->data !=data))
p=p->next;
return p;
}
Tìm một phần tử trong danh sách liên kết khi biết khóa (data)
Kết quả trả về là NULL tức là không tìm thấy phần tử có khóa data
Ngược lại nếu tìm thấy thì nó sẽ trả về địa chỉ của phần tử đầu tiên 
có khóa data trong danh sách liên kết. 
44
5. Danh sách liên kết đơn
Thêm một phần tử vào sau một phần tử cho trước
1. Danh sách rỗng
2. Danh sách đã có phần tử
q
45
5. Danh sách liên kết đơn
void AddAfter(LIST &l, NODE* q, NODE* add)
{
if(q!=NULL)
{
add->next=q->next;
q->next=add;
if(q==l.pTail)
l.pTail=add;
}
else
{
AddHead(l,add);
}
}
Thêm một phần tử vào sau một phần tử cho trước 46
5. Danh sách liên kết đơn
NODE* SearchPre(LIST l, NODE* s)
{
NODE* p=l.pHead;
if(p==s)
return NULL;
while((p!=NULL) && (p->next!=s))
p=p->next;
return p;
}
Tìm một phần tử đứng trước một phần tử cho trước
47
5. Danh sách liên kết đơn
Hủy phần tử đầu trong danh sách liên kết
1. Tách phần tử đầu ra khỏi danh sách
2. Xóa phần tử này
48
5. Danh sách liên kết đơn
void RemoveHead(LIST &l)
{
if(l.pHead!=NULL)
{
p=l.pHead;
l.pHead=l.pHead->next;
delete p;
if(l.pHead==NULL)
l.pTail=NULL;
}
} 
Hủy phần tử đầu trong danh sách liên kết
49
5. Danh sách liên kết đơn
Hủy phần tử cuối trong danh sách liên kết
1. Tách phần tử cuối ra khỏi danh sách
2. Gán pTail = địa chỉ của phần tử kế cuối
3. Xóa phần tử này
50
5. Danh sách liên kết đơn
void RemoveTail(LIST &l)
{
if(l.pHead==NULL)
return;
NODE *p=l.pTail;
l.pTail=SearchPre(l,l.pTail);
delete p;
if(l.pTail!=NULL)
l.pTail->next=NULL;
else
l.pHead=NULL;
} 
Hủy phần tử cuối trong danh sách liên kết
51
5. Danh sách liên kết đơn
Hủy phần tử sau phần tử q trong danh sách liên kết
1. Tách phần tử p ra khỏi danh sách liên kết
2. Xóa phần tử này
q
52
5. Danh sách liên kết đơn
void RemoveAfter(LIST &l, NODE* q)
{
NODE* p;
if(q!=NULL)
{
p=q->next;
if(p!=NULL)
{
if(p==l.pTail)
l.pTail=q;
q->next=p->next;
delete p;
}
}
else
RemoveHead(l);
} 
Hủy phần tử sau phần tử q trong danh sách liên kết
Lưu ý: q là phần tử
trong danh sách liên kết
53
5. Danh sách liên kết đơn
Hủy phần tử có khóa k cho trước
1. Tìm phần tử p có khóa k và phần tử q trước nó
2. Tách phần tử p ra khỏi danh sách liên kết
3. Xóa nó
q
K=39
54
5. Danh sách liên kết đơn
void Remove (LIST &l, int k)
{
NODE* p=l.pHead,*q=NULL;
while((p!=NULL)&&(p->data!=k))
{
q=p; p=p->next;
}
if(p==NULL) return;
if(q!=NULL)
{
if(p==l.pTail)
{
l.pTail=q;
l.pTail->next=NULL;
}
q->next=p->next;
delete p;
}
else // p là phần tử đầu tiên (pHead)
RemoveHead(l);
}
Hủy phần tử có khóa k cho trước
55
5. Danh sách liên kết đơn
Cách 1: 
void RemoveList (LIST &l, int k)
{
while(l.pHead!=NULL)
RemoveHead(l);
}
Cách 2: 
void RemoveList (LIST &l)
{
while(l.pHead!=NULL)
{
p=l.pHead;
l.pHead=l.pHead->next;
delete p;
}
l.pTail=NULL;
}
Hủy toàn bộ danh sách liên kết 56
6. Sắp xếp trên danh sách liên kết
void ListSelectionSort (LIST &l)
{ 
NODE* min; //trỏ đến pt có data min
NODE* i,*j; 
for(i = l.pHead;i->next!=NULL;i=i->next)
{
min=i;
for(j=i->next;j!=NULL;j=j->next)
if(j->datadata)
min=j;
HoanVi(min->data,i->data);
}
}
Selection Sort – Hoán vị nội dung phần dữ liệu (data)
57
6. Sắp xếp trên danh sách liên kết
void ListSelectionSort (LIST &l)
{ 
NODE *i,*j,*min, *minpre=NULL;
LIST lresult;KhoiTao(lresult);
while(l.pHead!=NULL) //danh dách chưa hết
{
min=l.pHead;minpre=NULL;
for(j=min,i=min->next;i!=NULL;j=i,i=i->next)
if(i->datadata)
{
min=i;
minpre=j;
}
if(minpre==NULL)
{
l.pHead=l.pHead->next;if(min==l.pTail) l.pTail=NULL;
}
else
{
if(min==l.pTail) l.pTail=minpre;minpre->next=min->next;
}
min->next=NULL;
AddTail(lresult,min);
}
l=lresult;
}
Selection Sort – Thay đổi mối liên kết
1. Tìm pt min có data nhỏ nhất
2. Tách min ra khỏi danh sách
3. Thêm min vào đầu ds mới
58
7. Các cấu trúc đặc biệt của dslk đơn
• Stack
– Là vật chứa (container) các đối tượng làm việc 
theo cơ chế LIFO (last in first out)
– Các thao tác trên stack: 
• Push(o): thêm đối tượng vào đâu stack
• Pop(): lấy đối tượng ở đầu stack ra khỏi stack và trả về 
đối tượng đó, nếu stack rỗng thì trả về NULL
• isEmpty(): Kiểm tra stack có rỗng hay không
• Top(): trả về phần tử nằm ở đầu stack mà không lấy phần 
tử này ra khỏi stack
– Stack được sử dụng để: khử đệ quy, tổ chức lưu 
vết của quá trình tìm kiếm theo chiều sâu và quay 
lui, vét cạn, định trị biểu thức, …
SV tự cài đặt stack.
59
7. Các cấu trúc đặc biệt của dslk đơn
• Hàng đợi
– Là một vật chứa (container) các đối tượng 
làm việc theo cơ chế FIFO (first in first out)
– Các thao tác trên hàng đợi
• EnQueue(o): thêm đối tượng vào hàng đợi
• DeQueue(): Lấy đối tượng ra khỏi hàng đợi và trả
về đối tượng đó.
• IsEmpty(): Kiểm tra hàng đợi có rỗng không
• Front(): Trả về đối tượng nằm ở đầu hàng đợi mà
không hủy nó.
SV tự cài đặt hàng đợi
60
7. Các cấu trúc đặc biệt của dslk đơn
• Hàng đợi
61
8. Chuyển từ trung tố sang hậu tố
• Biểu thức trung tố: 
– Có phép toán ở giữa
– Ví dụ: a+b
• Biểu thức hậu tố:
– Có phép toán để ở đằng sau
– Ví dụ: a b +
• Biểu thức tiền tố: 
– Có phép toán ở đằng trước
– Ví dụ: + a b
62
8. Chuyển từ trung tố sang hậu tố
• Duyệt từ trái sang phải
– Gặp (: đưa vào stack
– Gặp số: ghi ra
– Gặp phép toán: 
• Lấy và ghi ra tất cả các phép toán tại đỉnh của stack mà
có độ ưu tiên >= phép toán hiện tại. 
• Đưa phép toán hiện tại vào stack. 
– Gặp ): 
• Lấy và ghi ra tất cả các phép toán tại đỉnh cho đến khi 
gặp (. 
• Lấy ( ra khỏi stack
– Sau khi duyệt hết dãy thì lấy và ghi ra những gì
còn trong stack
Độ ưu tiên
Bậc 2: *,/
Bậc 1: +, -
Bậc 0: (,)
63
8. Chuyển từ trung tố sang hậu tố
A + B * C - D / E
Infix Stack(bot->top)Postfix
a) A + B * C - D / E
b) + B * C - D / E A
c) B * C - D / E + A
d) * C - D / E + A B
e) C - D / E + * A B
f) - D / E + * A B C
g) D / E - A B C *+
h) / E - A B C *+D
i) E - / A B C *+D
j) - / A B C *+D E
k) A B C *+D E / -
64
8. Chuyển từ trung tố sang hậu tố
A * B - ( C + D ) + E
Infix Stack(bot->top) Postfix
a) A * B - ( C - D ) + E empty empty
b) * B - ( C + D ) + E empty A
c) B - ( C + D ) + E * A
d) - ( C + D ) + E * A B
e) - ( C + D ) + E empty A B *
f) ( C + D ) + E - A B *
g) C + D ) + E - ( A B *
h) + D ) + E - ( A B * C
i) D ) + E - ( + A B * C
j) ) + E - ( + A B * C D
k) + E - A B * C D +
l) + E empty A B * C D + -
m) E + A B * C D + -
n) + A B * C D + - E
o) empty A B * C D + - E +
65
9. Định trị biểu thức hậu tố
• Duyệt từ trái sang phải
– Gặp số: đưa vào stack
– Gặp phép toán: 
• Lấy ra 1 số và gán vào a
• Lấy ra 1 số và gán vào b
• Thực hiện c=b a;
• Đưa c vào stack.
– Sau khi duyệt hết thì lấy kết quả ra từ
stack
Lưu ý thứ tự của a, 
b, phép toán
66
9. Định trị biểu thức hậu tố
1*(2+3)
1 2 3 + *
Postfix Stack( bot -> top )
a) 1 2 3 + *
b) 2 3 + * 1
c) 3 + * 1 2
d) + * 1 2 3
e) * 1 5 // 5 from 2 + 3
f) 5 // 5 from 1 * 5
67
67
Câu hỏi và thảo luận