Cấu Trúc Dữ Liệu Và Giải Thuật Chapter 3.1 List
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (477.31 KB, 10 trang )
Chương 3:
Cấu trúc danh sách
1
Nội dung
1) Khái niệm
2) Danh sách kề.
3) Danh sách liên kết đơn.
4) Danh sách liên kết đôi.
2
Khái niệm
Danh sách là một tập sắp thứ tự các phần
tử cùng kiểu.
Các phần tử có thứ tự “trước- sau”
Hai phương pháp cài đặt danh liên kết:
Cài đặt theo kiểu kế tiếp: Danh sách kề, danh
sách đặc.
Cài đặt theo kiểu liên kết: Danh sách liên kết.
3
Phần 1: Danh sách kề
4
Nội dung
Biểu diễn, quản lý danh sách kề.
Các thao tác trên danh sách kề.
Đánh giá ưu, nhược điểm.
Khắc phục nhược điểm của DS kề.
5
1. Biểu diễn danh sách kề
Sử dụng mảng để biểu diễn.
Các phần tử của danh sách được lưu trữ
ở các vị trí kế tiếp nhau trong bộ nhớ.
Các thao tác trên danh sách.
Ví dụ, DS = ( A, B, C, D, E, F, G, H, I, J, K)
Mảng M gồm 11 phần tử:
A B
C D E
F
6
G H I
J
K
2. Thao tác thêm phần tử
Chèn phần tử:
A B
C D E
P
F
G H I
J
K
Dồn tất cả các phần tử từ vị trí P đến cuối
sang phải một vị trí:
A B C D E
F
G H
I
J
K
F P G H
I
J
K
Đặt P vào vị trí trống:
A B C D E
7
3. Thao tác xóa phần tử
Xóa phần tử
A B
C
D
E
F
G
H
I
J
K
Chuyển tất cả các phần tử từ vị trí cần
xóa đến cuối sang trái 1 vị trí:
A
B
C
D
E
F
H
I
J
K
Giảm n đi 1.
Nếu không cần bảo lưu thứ tự các phần tử sau khi
xóa thì chỉ cần tráo đổi giá trị phần tử cần xóa cho
phần tử cuối cùng và giảm n đi 1.
8
4. Đánh giá ưu, nhược điểm
Kích thước cố định (fixed size)
Chèn 1 phần tử vào mảng rất khó
Các phần tử tuần tự theo chỉ số 0 n-1
Truy cập ngẫu nhiên (random access)
chèn
0
1
2
3
4
9
n-2
n-1
5. Khắc phụ nhược điểm
Cần xây dựng cấu trúc dữ liệu đáp ứng được
các yêu cầu:
Linh động hơn.
Có thể thay đổi kích thước, cấu trúc trong suốt
thời gian sống.
Cấu trúc danh sách liên kết.
10
