Xem mẫu
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
Nội dung
1
• Khái niệm danh sách liên kết
2
• Các phép tính trên danh sách liên kết đơn
3
• Các phép tính trên danh sách liên kết kép
4
• Ứng dụng của danh sách liên kết
GV. Thiều Quang Trung
2
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.
GV. Thiều Quang Trung
3
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:
A
B
X
Z
Y
– 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:
A
B
C
D
– 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:
GV. Thiều Quang Trung
4
Danh sách liên kết
– Danh sách liên kết đơn vòng
A
B
A
X
B
Z
C
Y
D
– Danh sách liến kết kép vòng
GV. Thiều Quang Trung
5
nguon tai.lieu . vn
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
Nội dung
1
• Khái niệm danh sách liên kết
2
• Các phép tính trên danh sách liên kết đơn
3
• Các phép tính trên danh sách liên kết kép
4
• Ứng dụng của danh sách liên kết
GV. Thiều Quang Trung
2
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.
GV. Thiều Quang Trung
3
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:
A
B
X
Z
Y
– 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:
A
B
C
D
– 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:
GV. Thiều Quang Trung
4
Danh sách liên kết
– Danh sách liên kết đơn vòng
A
B
A
X
B
Z
C
Y
D
– Danh sách liến kết kép vòng
GV. Thiều Quang Trung
5