Xem mẫu
- Chương 3 (1) : Con Trỏ & Cấu Trúc
Dữ Liệu Động
Giảng viên : Nguyễn Minh Thành
Email : thanhnm.itc@itc.edu.vn
- Nội Dung
I. So sánh dữ liệu tĩnh và dữ liệu động
II. Con trỏ
1. Con trỏ với dữ liệu cấu trúc
2. Cấp phát bộ nhớ
III. Tổng quan về danh sách liên kết
IV. Các loại DSLK
V. So sánh mảng và DSLK
2
- I. So Sánh Dữ Liệu Tĩnh và Động
Xét kiểu dữ liệu tĩnh
Cho một mảng có N=8 phần tử
6
15
10 9
5 7
3 2 1
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
3
- I. So Sánh Dữ Liệu Tĩnh và Động
Xét kiểu dữ liệu tĩnh
6
? Giả sử cần thêm tiếp 1 phần tử
15
10 9
5 7
3 2 1
1 2 3 4 5 6 7 8 9
4 Bổ sung thêm
- I. So Sánh Dữ Liệu Tĩnh và Động
Xét kiểu dữ liệu tĩnh
Bài tập : 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);
5
- I. So Sánh Dữ Liệu Tĩnh và Động
Xét kiểu dữ liệu tĩnh
Xoá phần tử 9 ra khỏi mảng ?
15
10 9
5 7
3 2 1
1 2 3 4 5 6 7 8
6
- I. So Sánh Dữ Liệu Tĩnh và Động
Xét kiểu dữ liệu tĩnh
Xoá phần tử 9 ra khỏi mảng ?
15
10 9
5 7
3 2 1
1 2 3 4 5 6 7 8
7
- I. So Sánh Dữ Liệu Tĩnh và Động
Xét kiểu dữ liệu tĩnh
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
- I. So Sánh Dữ Liệu Tĩnh và Động
Xét kiểu dữ liệu tĩnh
Ta thấy, các thao tác chèn và xoá dữ liệu trên mảng 1 chiều đều
phải duyệt qua tất cả các phần tử => Độ phức tạp O(n)
Các vấn đề :
Giải quyết vấn đề phức tạp khi chèn/ xóa?
Giải quyết vấn đề giới hạn kích thước vùng nhớ tối đa?
Giải quyết vấn đề vùng nhớ không liên tục?
Giải quyết vấn đề giải phóng vùng nhớ khi không cần dùng
đến?
Kiểu dữ liệu động
9
- II. Con Trỏ
Bộ nhớ gồm 1 tập hợp các ô nhớ được đánh địa
chỉ. Bộ nhớ được chia làm 2 phần : stack và heap
Stack : để cấp phát bộ nhớ cho các biến tĩnh &
động
Heap : để cấp phát bộ nhớ cho các động
Con trỏ là một biến dùng để lưu địa chỉ của một
vùng nhớ được cập phát trên vùng heap.
Con trỏ có thể được cấp phát vùng nhớ và thu hồi
vùng nhớ.
Con trỏ là nền tảng cho cấu trúc dữ liệu động
10
- II. Con Trỏ
Khai báo dữ liệu tĩnh
tên biến;
Vd: int a; float y;
Tồn tại trong phạm vi khai báo
Được cấp phát vùng nhớ trong vùng dữ liệu
Kích thước cố định
11
- II. Con Trỏ
Khai báo dữ liệu động (con trỏ)
*tên_biến_động;
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
- II. Con Trỏ
Khai báo dữ liệu động (con trỏ)
Cấp phát bộ nhớ: new int [kích thước]
Giải phóng bộ nhớ: delete biến_động
Ví dụ:
int *a;
a=new int; // Cấp phát 1 phan tử
a=new int [10]; // Cấp phát 1 mảng
//Các thao tác trên a
………………........
delete a; // Giải phóng
13
- II. Con Trỏ
Xét ví dụ sau :
int foo;
int *x;
foo = 123;
x = &foo;
14
- II. Con Trỏ
Xét câu lệnh sau : int *x;
x là một con trỏ trỏ đến một số nguyên
Ta có thể sử dụng số nguyên của x trỏ đến bằng 1 trong 2 cách
sau :
Y = *x + 17;
*x = *x + 1;
15
- II. Con Trỏ
Lưu ý :
Toán tử ‘*’ có hai chức năng :
Khai báo con trỏ
Truy xuất dữ liệu tại địa chỉ lưu dữ con trỏ
16
- II. Con Trỏ
Toán tử ‘&’ : dùng để lấy địa chỉ của một biến.
17
- II. Con Trỏ
Một con trỏ phải có giá trị trước khi tham chiếu ngược để truy xuất
dữ liệu
18
- II. Con Trỏ
Con trỏ NULL :
Không trỏ đến một vị trí nào
Tham chiếu ngược con trỏ NULL sẽ gây ra lỗi thực thi chương
trình (run-time error)
Kiểm tra con trỏ NULL trước khi tham chiếu.
19
- II.1 Con Trỏ Với Dữ Liệu Cấu Trúc
20
nguon tai.lieu . vn
