CON TRỎ VÀ CẤP PHÁT ĐỘNG CĐR buổi học • Sau khi học xong buổi học, sinh viên có khả năng: • Hiểu được về con trỏ và cấp phát động. • Áp dụng con trỏ trong cấp phát mảng. • Áp dụng con trỏ và tham số của hàm. • Áp dụng con trỏ và cấu trúc.
Cấp phát động 2. Cấp phát động mảng 1 chiều 3. Cấp phát động mảng 2 chiều 4. Con trỏ và hàm số 5.
Con trỏ và cấu trúc 6. Một số vấn đề mở rộng NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 3 1. Cấp phát động • Cấp phát bộ nhớ tĩnh (static memory allocation) • Khai báo biến, cấu trúc, mảng, … • Bắt buộc phải biết trước cần bao nhiều bộ nhớ lưu trữ è tốn bộ nhớ, không thay đổi được kích thước, … • Cấp phát động (dynamic memory allocation) • Cần bao nhiêu cấp phát bấy nhiêu. • Có thể giải phóng nếu không cần sử dụng.
• Sử dụng vùng nhớ ngoài chương trình (cả bộ nhớ ảo virtual memory). NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 4 Cấu trúc một CT C++ trong bộ nhớ • Toàn bộ tập tin chương trình sẽ được nạp vào bộ nhớ tại vùng nhớ còn trống, gồm 4 phần: STACK Lưu đối tượng cục bộ Last-In First-Out khi thực hiện hàm Vùng nhớ trống Vùng cấp phát động HEAP (RAM trống và bộ nhớ ảo) Đối tượng toàn cục Vùng cấp phát tĩnh & tĩnh (kích thước cố định) Gồm các lệnh và hằng Mã chương trình (kích thước cố định) NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 5 Cấp phát bộ nhớ • Cấp phát bộ nhớ • Trong C: Hàm malloc, calloc, realloc (<stdlib.h>) • Trong C++: Toán tử new • Giải phóng bộ nhớ • Trong C: Hàm free • Trong C++: Toán tử delete NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 6 Biến cấp phát động và Biến tự động • Biến cục bộ • Khai báo bên trong định nghĩa hàm • Sinh ra khi hàm được gọi • Hủy đi khi hàm kết thúc • Thường gọi là biến tự động nghĩa là được trình biên dịch quản lý một cách tự động • Biến cấp phát động • Sinh ra bởi cấp phát động • Sinh ra và hủy đi khi chương trình đang chạy • Biến cấp phát động hay Biến động là biến con trỏ trước khi sử dụng được cấp phát bộ nhớ. NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 7 Toán tử new • Vì con trỏ có thể tham chiếu tới biến nhưng không thực sự cần phải có định danh cho biến đó. • Có thể cấp phát động cho biến con trỏ bằng toán tử new.
Toán tử new sẽ tạo ra biến “không tên” cho con trỏ trỏ tới. • Cú pháp: <type> *<pointerName> = new <type> Ví dụ: int *ptr = new int; o Tạo ra một biến “không tên” và gán ptr trỏ tới nó o Có thể làm việc với biến “không tên” thông qua *ptr NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 8 Kiểm tra việc cấp phát có thành công không #include <iostream> using namespace std; 0x34 3199 int main() { int *p = new int; 0x90 if (p == NULL) { ptr 0x34 cout << "Error: Khong du bo nho.\n"; exit(1); } *p = 3199; } NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 9 Khởi tạo giá trị trong cấp phát động • Cú pháp: <type> pointer = new <type> (value) • Ví dụ: #include <iostream> using namespace std; int main() { int *p; p = new int(99); // initialize with 99 cout << *p; // displays 99 return 0; } NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 10 Ví dụ 1. int *p1 = new int; p1 6. p2 = p1; p2 40 p1 p2 30 NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 11 Toán tử delete • Toán tử delete dùng để giải phóng vùng nhớ trong HEAP do con trỏ trỏ tới (con trỏ được cấp pháp bằng toán tử new).
Cú pháp: delete <pointerName>; • Ghi chú: Sau khi gọi toán tử delete thì con trỏ vẫn trỏ tới vùng nhớ trước khi gọi hàm delete. Ta gọi là “con trỏ lạc”. Ta vẫn có thể gọi tham chiếu trên con trỏ, tuy nhiên: • Kết quả không lường trước được • Thường là nguy hiểm Þ Hãy tránh con trỏ lạc bằng cách gán con trỏ bằng NULL sau khi delete. • Ví dụ: delete pointer; pointer = NULL; NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 12 Từ khóa typedef • Từ khóa typedef dùng để định nghĩa 1 tên mới hay gọi là một biệt danh (alias) cho tên kiểu dữ liệu có sẵn.
Ví dụ: typedef int SONGUYEN; Các khai báo sau tương đương: int a; SONGUYEN a; NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 13 Định nghĩa kiểu dữ liệu con trỏ • Có thể đặt tên cho kiểu dữ liệu con trỏ • Để có thể khai báo biến con trỏ như các biến khác • Loại bỏ * trong khai báo con trỏ Ví dụ: typedef int* IntPtr; - Định nghĩa một tên khác cho kiểu dữ liệu con trỏ - Các khai báo sau tương đương: IntPtr p; int *p; NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 14 Con trỏ và hàm • Con trỏ là kiểu dữ liệu hoàn chỉnh có thể dùng nó như các kiểu khác • Con trỏ có thể là tham số của hàm • Có thể là kiểu trả về của hàm Ví dụ: int* findOtherPointer(int* p); Hàm này khai báo: - Có tham số kiểu con trỏ trỏ tới int - Trả về biến con trỏ trỏ tới int NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 15 Ví dụ typedef int *IntPointer; void Input(IntPointer temp) { *temp = 20; cout << "Trong ham goi *temp = " << *temp << endl; } Truoc khi goi ham, *p = 10 int main() { Trong ham goi *temp = 20 IntPointer p = new int; Sau khi ket thuc ham, *p = 20 *p = 10; cout << "Truoc khi goi ham, *p = " << *p << endl; Input(p); cout << "Sau khi ket thuc ham, *p = " << *p << endl; } NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 16 Ví dụ 1. Trước khi gọi hàm Input 3. Thay đổi giá trị *temp p 10 p 20 temp 2. Giá trị của p sẽ được truyền 4.
Sau khi kết thúc gọi hàm Input vào temp p 10 p 20 temp NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 17 Bài tập • Viết hàm cấp phát và nhập giá trị cho 1 con trỏ theo 2 cách. NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 18 Bài giải // Cách 1 // Cách 2 #include <iostream> #include <iostream> using namespace std; using namespace std; typedef int *IntPointer; typedef int *IntPointer; IntPointer Input() { IntPointer Input(IntPointer &temp) { IntPointer temp = new int; temp = new int; *temp = 20; *temp = 20; return temp; return temp; } } int main() { int main() { IntPointer p; IntPointer p; p = Input(); Input(p); cout << "Sau khi ket thuc cout << "Sau khi ket thuc ham, ham, *p = " << *p << endl; *p = " << *p << endl; } } NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 19 2. Cấp phát động và mảng 1 chiều NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 20 Nhắc lại • Mảng lưu trong các ô nhớ liên tiếp trong bộ nhớ máy tính • Biến mảng tham chiếu tới phần tử đầu tiên • Biến mảng là một biến hằng con trỏ NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 21 Nhắc lại • Ví dụ: int a[10]; typedef int* IntPtr; IntPtr p; Þ a và p là các biến con trỏ. • Phép gán hợp lệ p = a; • p bây giờ sẽ trỏ tới nơi a trỏ, tức là tới phần tử đầu tiên của mảng a • Phép gán không hợp lệ a = p; • Bởi con trỏ mảng là con trỏ hằng.
NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 22 Hạn chế của mảng chuẩn • Hạn chế của mảng chuẩn • Bắt buộc phải biết trước cần bao nhiều bộ nhớ lưu trữ => tốn bộ nhớ, không thay đổi được kích thước, … Þ Dùng Mảng động • Mảng động • Kích thước không xác định ở thời điểm lập trình • Mà xác định khi chạy chương trình NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 23 Tạo mảng động bằng toán tử new • Cấp phát động cho biến con trỏ • Sau đó dùng con trỏ như mảng chuẩn • Cú pháp: <type> <pointer> = new <type> [<number_of_elements>] Ví dụ: typedef double * doublePtr; doublePtr d; d = new double[10]; Þ Tạo biến mảng cấp phát động d có 10 phần tử, kiểu cơ sở là double. NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 24 Xóa mảng động • Dùng toán tử delete[] để xóa mảng động. Ví dụ: double *d = new double[10]; //. Processing delete[] d; Þ Giải phóng tất cả vùng nhớ của mảng động này Þ Cặp ngoặc vuông báo hiệu có mảng Þ Nhắc lại: d vẫn trỏ tới vùng nhớ đó.
Vì vậy sau khi delete, cần gán d = NULL; NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 25 Bài tập Hãy viết chương trình tạo mảng 1 chiều có n phần tử bằng 2 cách: • Cách 1: Bằng mảng chuẩn • Cách 2: Bằng cấp phát động NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 26 Lời giải #include <iostream> #include <iostream> using namespace std; using namespace std; int main() { int main() { int arr[10]; int *arr; return 0; arr = new int[10]; } return 0; } NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 27 Hàm trả về kiểu mảng • Ta không được phép trả về kiểu mảng trong hàm. Ví dụ: int[] someFunction(); // Không hợp lệ! • Có thể thay bằng trả về con trỏ tới mảng có cùng kiểu cơ sở: int* someFunction(); // Hợp lệ! NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 28 Bài tập • Hãy viết HÀM tạo mảng 1 chiều có n phần tử bằng cấp phát động. • Viết hàm xuất mảng 1 chiều đã tạo. • Viết hàm đếm số phần tử âm trong mảng 1 chiều.
NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 29 Lời giải #include <iostream> #include <iostream> using namespace std; using namespace std; int* Input(int n){ void Input(int *&p, int n){ int *p; p = new int[n]; p = new int[n]; for (int i = 0; i < n; i++){ for (int i = 0; i < n; i++){ cin >> p[i]; cin >> p[i]; } } } return p; } int main() { int *arr, n; int main() { cout << "Nhap n: "; int *arr, n; cin >> n; cout << "Nhap n: "; Input(arr, n); cin >> n; } arr = Input(n); } NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 30 Lời giải // Hàm xuất mảng void Output(int *p, int n) { cout << "\n Xuat mang 1 chieu: "; for (int i = 0; i < n; i++) { cout << p[i] << " " ; } } NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 31 3.