Chương 3 Cấu trúc dữ liệu động
*
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++
*
Cho một mảng có N=8 phần tử
1 2 3 4 5 6 7 8
*
Làm sao để chèn thêm số 6 vào mảng tại vị trí 5
1 2 3 4 5 6 7 8 9
Bổ sung thêm
Giả sử cần thêm tiếp 1 phần tử
?
*
Làm sao để chèn thêm số 6 vào mảng tại vị trí 5
*
Hãy cài đặt hàm (bằng ngôn ngữ C/C++) chèn
một phần tử có giá trị x vào một mảng số
nguyên a, kích thước n (có thứ tự tăng dần) sao
cho mảng a vẫn có thứ tự tăng dần, theo mẫu
hàm như sau:
void ChenX(int a[], int n, int x, int vt);
*
Làm sao để xóa phần tử 9 ?


Được cấp phát vùng nhớ trong vùng dữ liệu

Kích thước cố định
*
Biến động
<kiểu dữ liệu> *tên biến;
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
*
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
*
Giới thiệu cấu trúc “Danh sách liên kết”
1

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ớ)
*
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
Node
pHead pTail
List
*
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
*
Ta cũng có thể quản lý danh sách bằng cách sử
dụng thêm con trỏ cuối (pTail)
*
pTail không phải là 1 nút, nó chỉ là “con trỏ
chỉ đến nút” mà thôi
*
Tạo lập bằng cách cấp phát bộ nhớ động

(địa chỉ tăng dần) trong bộ
nhớ
Các phần tử liên kết với
nhau bằng con trỏ
Phải dịch chuyển các phần
tử khi Thêm/Xóa
Chỉ cần thay đổi con trỏ liên
kết khi Thêm/Xóa
Truy xuất ngẫu nhiên Truy xuất tuần tự