Chương 3.1. Danh sách
liên kết đơn
Trần Minh Thái
Email:
Website: www.minhthai.edu.vn
Cập nhật: ngày 20 tháng 10 năm 2012
Mục tiêu

Nắm vững khái niệm về kiểu dữ liệu tĩnh và
động

Nắm vững cách tổ chức dữ liệu động bằng danh
sách liên kết và minh họa được các thao tác xử
lý trên danh sách liên kết đơn

Cài đặt minh họa được các thao tác của danh
sách đơn bằng ngôn ngữ C/ C++
2
Vấn đề kiểu dữ liệu tĩnh
3
1 2 3 4 5 6 7 8
10
5
7
3
9
2
15
1
? Làm sao để chèn thêm số 6 vào vị trí 5 của mảng
6

9
2
15
1
Vấn đề kiểu dữ liệu tĩnh
7
1 2 3 4 5 6 7 8
10
5
7
3
9
2
15
1
Bài tập

Hãy cài đặt hàm (bằng ngôn ngữ C/C++) xóa
phần tử có giá trị x (nếu có) trong mảng số
nguyên a, kích thước n (giả sử giá trị các
phần tử trong mảng không trùng nhau), theo
mẫu hàm như sau:
void XoaX (int a[], int &n, int x);
8
Vấn đề kiểu dữ liệu tĩnh
9
Độ phức tạp của chèn/ xóa
trên mảng 1 chiều là O(n)
i
Vấn đề kiểu dữ liệu tĩnh



Vd: int *a; float *y;

Chứa địa chỉ của một đối tượng dữ liệu

Được cấp phát hoặc giải phóng bộ nhớ tùy thuộc vào
người lập trình

Kích thước có thể thay đổi
12
Biến tĩnh và biến động trong C++

Biến động

Cấp phát bộ nhớ: new int [kích thước]

Giải phóng bộ nhớ: delete vùng nhớ

Ví dụ:
int *a;
a=new int [10]; // Cấp phát
//Các thao tác trên a
delete a; // Giải phóng
13
Danh sách liên kết (DSLK)
14
1
7
2

Các nút không cần phải lưu trữ liên tiếp nhau
trong bộ nhớ

Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung
lượng bộ nhớ)
16
Đặc điểm DSLK

Thao tác Chèn/Xóa không cần phải dịch
chuyển phần tử mà chỉ cần thay đổi mối liên
kết

Quản lý phần tử đầu tiên bằng con trỏ pHead

Có thể truy xuất đến các phần tử khác thông
qua con trỏ liên kết
17
Node
Cấu tạo của DSLK
18
pHead pTail
List
Cấu tạo của DSLK

Quản lý toàn bộ danh sách liên kết thông qua
con trỏ đầu pHead

pHead không phải là 1 nút, nó chỉ là “con trỏ
chỉ đến nút” mà thôi


List
Các loại hình DSLK
DSLK đơn: Các phần tử kết nối với nhau theo
hướng “chiều đi tới”
23
Các loại hình DSLK
DSLK đôi: Các phần tử kết nối với nhau theo
hướng “chiều đi tới và và đi lui”
24
Các loại hình DSLK
Danh sách liên kết vòng: Các phần tử kết nối
với nhau theo hướng “chiều đi tới” và phần tử
cuối cùng có “đường đi vòng trở lại tới” phần
tử đầu danh sách
25