Bài giảng Công nghệ phần mềm - Chương 3: Danh sách liên kết - Ngô Công Thắng

CHƯƠNG 3
DANH SÁCH LIÊN KẾT
GV. Ngô Công Thắng
Bộ môn Công nghệ phần mềm
Khoa Công nghệ thông tin
Website: dse.vnua.edu.vn/ncthang
Email: ncthang@vnua.edu.vn
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
CHƯƠNG 3
DANH SÁCH LIÊN KẾT
1. Giới thiệu về danh sách liên kết
2. Danh sách liên kết đơn
3. Danh sách liên kết vòng
4. Danh sách liên kết kép
5. Cài đặt ngăn xếp và hàng đợi bằng danh
sách liên kết đơn
3.2
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
1. Giới thiệu về danh sách liên kết
l Sử dụng con trỏ để tổ chức lưu trữ danh 
sách tuyến tính sẽ tạo ra cấu trúc dữ liệu 
danh sách liên kết.
l Mỗi phần tử của danh sách được lưu trữ 
trong một phần tử nhớ mà ta gọi là nút 
(node). Mỗi nút bao gồm một số ô nhớ liền 
kề nhau và có thể nằm ở bất kỳ chỗ nào 
trong bộ nhớ. Trong mỗi nút ngoài thông 
tin ứng với phần tử, còn có địa chỉ của nút 
liền kề nó.
3.3
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
1. Giới thiệu về danh sách liên kết 
(tiếp)
l Danh sách liên kết được chia thành danh 
sách liên kết đơn, danh sách liên kết vòng 
và danh sách liên kết kép.
l Danh sách liên kết đơn có thể dùng làm 
cấu trúc lưu trữ cho cấu trúc ngăn xếp và 
hàng đợi.
3.4
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2. Danh sách liên kết đơn
2.1. Quy tắc tổ chức danh sách liên kết đơn
l Mỗi nút trong danh sách có hai trường, 
trường INFOR chứa thông tin của phần tử 
và trường LINK chứa địa chỉ của nút đứng 
sau (đây chính là địa chỉ liên kết).
INFOR LINK
3.5
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2.1. Quy tắc tổ chức danh sách
liên kết đơn (tiếp)
l Nút cuối cùng trong danh sách không có 
nút đứng sau nên trường địa chỉ là rỗng, 
không chứa địa chỉ, ta ký hiệu là Æ.
l Để truy nhập vào tất cả nút trong danh 
sách thì phải có địa chỉ nút đầu tiên, do đó 
cần phải có con trỏ F trỏ tới nút đầu tiên.
l Nếu danh sách rỗng thì qui ước F = Æ
A1 A2 A3 A4 ÆF
3.6
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2.1. Quy tắc tổ chức danh sách
liên kết đơn (tiếp)
l Để tổ chức lưu trữ một danh sách liên kết thì phải 
có:
l Phải có phương tiện chia bộ nhớ ra thành các nút và ở 
mỗi nút có thể truy nhập vào từng trường.
l Phải có cơ chế để xác định một nút đang được sử 
dụng hoặc chưa được sử dụng (nút trống).
l Phải có cơ chế cung cấp các nút trống khi có yêu cầu 
sử dụng và thu hồi lại các nút khi không cần dùng nữa.
l Ta ký hiệu:
l P Ü AVAIL là phép lấy ra một nút trống có địa chỉ là P 
(cấp phát một nút)
l P Þ AVAIL là phép thu hồi một nút có địa chỉ là P
3.7
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2.2. Một số phép toán trên
danh sách liên kết đơn
l Ký hiệu: Một nút có địa chỉ là p (được trỏ
bởi p) thì INFOR(p) và LINK(p) tương ứng
chỉ trường INFOR và LINK của nút đó.
a) Bổ sung một nút mới vào danh sách
Cho danh sách liên kết đơn F, M là con trỏ
trỏ tới một nút trong danh sách. Viết thủ
tục bổ sung phần tử dữ liệu X vào sau nút
M.
3.8
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2.2. Một số phép toán trên
danh sách liên kết đơn (tiếp)
a) Bổ sung một nút mới vào danh sách:
- Vào: F, M, X
- Ra: Không có
{Thủ tục này bổ sung phần tử X vào sau nút 
trỏ bởi M trong danh sách liên kết đơn F}
Procedure INSERT(F,M,X)
1. {Tạo nút mới}
new Ü AVAIL
INFOR(new):=X; LINK(new):= Æ;
3.9
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2.2. Một số phép toán trên
danh sách liên kết đơn (tiếp)
2. {Thực hiện bổ sung: Nếu danh sách rỗng thì bổ 
sung nút mới vào thành nút đầu tiên. Nếu danh 
sách không rỗng thì bổ sung nút mới vào sau 
nút M}
If F=Æ then F:=new 
Else begin
LINK(new):=LINK(M);
LINK(M):=new;
end;
Return
3.10
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2.2. Một số phép toán trên
danh sách liên kết đơn (tiếp)
b) Loại bỏ một nút khỏi danh sách
- Vào: F, M
- Ra: Không
{Cho danh sách liên kết đơn F, loại bỏ nút trỏ bởi 
M khỏi danh sách.}
Procedure DELETE(F,M)
1. { Trường hợp danh sách rỗng}
If F=Æ then begin 
Write(‘danh sách rỗng’)
Return
end
3.11
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2.2. Một số phép toán trên
danh sách liên kết đơn (tiếp)
b) Loại bỏ một nút khỏi danh sách
2. {Nút trỏ bởi M là nút đầu tiên của danh 
sách }
If M=F then begin
F:=LINK(F)
M Þ AVAIL
Return
end
3.12
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2.2. Một số phép toán trên
danh sách liên kết đơn (tiếp)
3. {Tìm đến nút đứng trước nút M }
P:=F;
While LINK(P) # M do P:=LINK(P)
4. {Loại bỏ nút trỏ bởi M}
LINK(P):=LINK(M)
5. {Hủy nút M}
M Þ AVAIL
Return
3.13
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2.2. Một số phép toán trên
danh sách liên kết đơn (tiếp)
c) Ghép hai danh sách liên kết đơn
Cho 2 danh sách liên kết đơn lần lượt trỏ bởi p 
và q, ghép 2 danh sách trở thành một danh sách 
và cho p trỏ tới. Thuật toán có các bước sau:
Procedure Ghep(p,q)
1. {Danh sách trỏ bởi q rỗng}
If q = Æ then Return
2. {Trường hợp danh sách trỏ bởi p rỗng}
If p = Æ then begin
p:=q
return
end
3.14
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
2.2. Một số phép toán trên
danh sách liên kết đơn (tiếp)
c) Ghép hai danh sách liên kết đơn
3. {Tìm đến nút cuối danh sách p}
p1:= p
While link(p1) # Æ do p1:=link(p1);
4. {Ghép}
Link(p1):=q;
Return
3.15
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 03
Ưu nhược điểm của danh sách liên kết đơn
l Với danh sách tuyến tính động, trong quá
trình xử lý luôn có bổ sung, loại bỏ thì tổ
chức danh sách liên kết là hợp lý, tận
dụng được các vùng nhớ nằm rải rác
trong bộ nhớ.
l Chỉ có phần tử đầu tiên là truy nhập trực
tiếp, các phần tử khác phải truy nhập qua 
phần tử đứng trước nó.
l Tốn bộ nhớ do phải lưu cả 2 trườ