Bài giảng Cấu trúc dữ liệu và giải thuật - Con trỏ và mảng cấp phát động trong C++ - Hoàng Thị Điệp

Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Con trỏ và mảng cấp phát động trong C++ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014 Dịch từ slides Chapter 12: Pointers and Dynamic Arrays của tác giả David Mann (North Idaho College). 1. Con trỏ 2. Mảng cấp phát động 3. class và mảng cấp phát động diepht@vnu 2 Nội dung chính Con trỏ  Con trỏ là địa chỉ nhớ của một biến.  Địa chỉ nhớ có thể được dùng như tên biến  Nếu một biến được lưu trong 3 ô nhớ thì địa chỉ của ô đầu tiên có thể được dùng như tên biến.  Khi một biến được dùng như đối số tham chiếu của một hàm, địa chỉ của nó được truyền vào cho hàm. diepht@vnu 3 Con trỏ cho biết phải tìm một biến ở đâu diepht@vnu 4  Một địa chỉ cho biết một biến được lưu ở đâu trong bộ nhớ được gọi là một con trỏ.  Con trỏ “trỏ” tới một biến bằng cách cho biết phải tìm biến đó ở đâu. Khai báo con trỏ  Biến con trỏ phải được khai báo là có kiểu con trỏ.  Ví dụ: khai báo một biến con trỏ p trỏ tới một biến kiểu double double *p;  Dấu * chỉ định p là một biến con trỏ. diepht@vnu 5 Khai báo nhiều biến con trỏ diepht@vnu 6  Để khai báo nhiều biến con trỏ trong một câu lệnh, thêm dấu * trước mỗi biến con trỏ  Ví dụ int *p1, *p2, v1, v2;  p1 và p2 trỏ tới các biến kiểu int  v1 và v2 là các biến kiểu int Phép toán lấy địa chỉ diepht@vnu 7  Phép toán & có thể được dùng để lấy địa chỉ của một biến. Có thể gán địa chỉ này cho một biến con trỏ.  Ví dụ: p1 = &v1;  p1 là một con trỏ trỏ tới v1  v1 được gọi là biến trỏ bởi p1 Phép toán khử tham chiếu  Dấu * trong C++ còn được dùng theo cách khác  Cụm “biến trỏ bởi p” trong C++ được hiểu là *p  Ở đây, * là phép toán khử tham chiếu diepht@vnu 8 Ví dụ  v1 = 0; p1 = &v1; *p1 = 42; cout << v1 << endl; cout << *p1 << endl; output: 42 42 v1 and *p1 ám chỉ cùng một biến diepht@vnu 9 Gán con trỏ  Phép gán = được dùng để gán một giá trị con trỏ cho một biến con trỏ.  Ví dụ  Nếu p1 trỏ tới v1 thì câu lệnh p2 = p1; sẽ dẫn tới *p1, *p2 và v1 ám chỉ cùng một biến diepht@vnu 10 diepht@vnu 11 Phép toán new  Dùng con trỏ, bạn có thể thao tác trên các biến mà không cần đặt tên cho chúng  Tạo một con trỏ trỏ tới một biến “vô danh” mới kiểu int int *p1; p1 = new int;  Biến mới này chính là *p1  *p1 có thể dùng y như một biến int cin >> *p1; *p1 = *p1 + 7; diepht@vnu 12 Biến cấp phát động  Biến sinh ra bởi phép toán new được gọi là biến cấp phát động  Biến cấp phát động được tạo và hủy trong khi chương trình đang chạy diepht@vnu 13 diepht@vnu 14 Phép toán new và kiểu định nghĩa bằng class  Khi dùng phép toán new với kiểu định nghĩa bằng class sẽ diễn ra 2 việc  gọi hàm kiến tạo (constructor) của kiểu định nghĩa bằng class  cấp phát bộ nhớ  Ví dụ  Nếu ComplexType là một kiểu định nghĩa bằng class thì  ComplexType *myPtr; tạo một con trỏ trỏ tới một biến kiểu ComplexType  myPtr = new ComplexType ; gọi hàm kiến tạo mặc định ComplexType(); và cấp phát bộ nhớ  myPtr = new ComplexType(20.5, 10.7); gọi hàm kiến tạo ComplexType(double, double); và cấp phát bộ nhớ diepht@vnu 15 Quản lý bộ nhớ  Một vùng nhớ gọi là free store được chỉ định lưu trữ các biến cấp phát động  Biến cấp phát động mới dùng các ô nhớ trong free store  Khi tất cả các ô nhớ trong free store đều đã bị chiếm dụng thì lời gọi tới phép toán new sẽ thất bại  Những vùng nhớ không còn cần tới có thể được tái chế  Có thể xóa những biến không còn cần tới và trả vùng nhớ chúng chiếm dụng lại cho free store. diepht@vnu 16 Phép toán delete  Hãy delete những biến không còn cần tới và trả vùng nhớ chúng chiếm dụng lại cho free store.  Ví dụ delete p;  giá trị của p hiện giờ là không xác định và  vùng nhớ mà p trỏ tới được trả về cho free store. diepht@vnu 17 Con trỏ lạc  Dùng delete với một biến con trỏ sẽ hủy vùng nhớ trỏ bởi con trỏ đó  Nếu có một con trỏ khác đang trỏ tới biến cấp phát động này thì sau phép delete, nó cũng không xác định  Các biến con trỏ không xác định được gọi là con trỏ lạc  Khử tham chiếu con trỏ lạc là việc làm cực kì nguy hiểm diepht@vnu 18 Biến tự động diepht@vnu 19  Biến khai báo bên trong một hàm sẽ được tạo bởi C++ và hủy khi hàm này kết thúc  Chúng được gọi là biến tự động vì việc tạo và hủy chúng diễn ra tự động  Lập trình viên cần kiểm soát thủ công việc tạo và hủy các biến con trỏ với phép toán new và delete Biến toàn cục  Biến được khai báo bên ngoài tất cả các hàm được gọi là biến toàn cục  Có thể truy cập biến toàn cục ở mọi nơi trong chương trình  Biến toàn cục không được sử dụng phổ biến diepht@vnu 20 Định nghĩa kiểu dữ liệu  Có thể gán tên cho một định nghĩa kiểu rồi dùng nó để khai báo biến  Từ khóa typedef dùng để định nghĩa tên mới cho một kiểu  Cú pháp typedef định_nghĩa_kiểu_đã_biết tên_mới; diepht@vnu 21 Định nghĩa kiểu dữ liệu con trỏ  Để tránh nhầm lẫn khi sử dụng con trỏ, ta nên định nghĩa một tên cho kiểu con trỏ  Ví dụ  typedef int* IntPtr;  định nghĩa một kiểu mới IntPtr cho những biến con trỏ trỏ tới biến kiểu int  IntPtr p;  tương đương với  int *p; diepht@vnu 22 Khai báo nhiều biến  Để khai báo nhiều biến con trỏ, ta có thể dùng kiểu con trỏ mới định nghĩa  typedef int* IntPtr;  int *p1, p2; // chỉ p1 là biến con trỏ  IntPtr p1, p2; // cả p1 và p2 đều là biến con trỏ diepht@vnu 23 Tham số tham chiếu là con trỏ  Một lợi thế khác khi dùng typedef để định nghĩa kiểu con trỏ là khi đọc hiểu danh sách tham số của hàm  Ví dụ  void sample_function(IntPtr& pointer_var);  thì rõ ràng hơn  void sample_function(int*& pointer_var); diepht@vnu 24 Ôn tập  Hãy 1. Khai báo một biến con trỏ 2. Gán giá trị cho một biến con trỏ 3. Dùng phép toán new để tạo một biến mới trong free store 4. Định nghĩa kiểu NumberPtr là một kiểu con trỏ trỏ tới các biến cấp phát động kiểu int 5. Khai báo biến myPoint là một biến con trỏ kiểu NumberPtr diepht@vnu 25 1. Con trỏ 2. Mảng cấp phát động 3. class và mảng cấp phát động diepht@vnu 26 Nội dung chính Mảng cấp phát động  Mảng (cấp phát) động là mảng có kích thước thiết lập khi chương trình đang chạy chứ không phải khi bạn viết chương trình diepht@vnu 27 Biến con trỏ và biến mảng  Biến mảng thực ra là biến con trỏ trỏ tới phần tử đầu tiên được đánh chỉ số  Ví dụ int a[10]; typedef int* IntPtr; IntPtr p;  Biến a và p thuộc cùng một kiểu.  Do a là biến con trỏ trỏ tới a[0], câu lệnh p = a; dẫn tới p trỏ tới a[0] diepht@vnu 28 Biến con trỏ dùng như biến mảng diepht@vnu 29 int a[10]; typedef int* IntPtr; IntPtr p; p = a;  Ta có thể dùng biến con trỏ p như một biến mảng  Ví dụ p[0], p[1], ., p[9]  Có thể dùng a như một biến con trỏ nhưng bạn không thể thay đổi địa chỉ lưu trong a  Làm như dưới đây là không hợp lệ IntPtr p2; // gán giá trị cho p2 a = p2; Tạo mảng động  Mảng thông thường cần bạn chỉ định kích thước lúc viết chương trình  Nếu bạn chỉ định một kích thước quá lớn?  Lãng phí bộ nhớ  Nếu bạn chỉ định một kích thước quá nhỏ?  Chương trình có thể không đúng đắn trong một số trường hợp  Trong lúc chương trình chạy, bạn có thể tạo mảng động với kích thước vừa phải diepht@vnu 30 Tạo mảng động  Bạn tạo mảng động bằng phép toán new  Ví dụ: tạo một mảng động gồm 10 phần tử kiểu double typedef double* DoublePtr; DoublePtr d; d = new double[10];  Giờ thì ta có thể dùng d như mảng thông thường diepht@vnu 31 Mảng động typedef double* DoublePtr; DoublePtr d; d = new double[10];  Biến con trỏ d trỏ tới d[0]  Khi bạn làm việc xong với mảng này, hãy delete nó để trả bộ nhớ lại cho free store  Ví dụ delete [] d;  Cặp ngoặc vuông cho C++ biết cần hủy một mảng động. Vì thế C++ sẽ kiểm tra kích thước để biết cần hủy bao nhiêu phần tử.  Nếu bạn quên cặp ngoặc vuông, C++ chỉ hủy phần tử đầu tiên d[0] diepht@vnu 32 Số học con trỏ  Có thể thực hiện các phép tính số học trên các giá trị của biến con trỏ  Ví dụ typedef double* DoublePtr; DoublePtr d; d = new double[10];  Biểu thức d+1 trả về địa chỉ của phần tử d[1]  Biểu thức d+2 trả về địa chỉ của phần tử d[2] diepht@vnu 33 Các phép toán số học trên con trỏ  Bạn có thể cộng và trừ với các con trỏ  Có thể sử dụng các phép tự tăng ++ và tự giảm --  Khi trừ 2 con trỏ cùng kiểu, bạn thu được số lượng phần tử nằm giữa  2 con trỏ này nên trỏ tới các phần của cùng một mảng  Dưới đây cũng là một cách dùng số học con trỏ for (int i = 0; i < arraySize; i++) cout << *(d + i) << " " ; // giống với cout << d[i] << " " ; diepht@vnu 34 Mảng động nhiều chiều  Để tạo một mảng động kích thước 3x4  Ta xem mảng động nhiều chiều là mảng của các mảng  Trước tiên tạo một mảng động một chiều  Bắt đầu với một định nghĩa mới typedef int* IntPtr;  Sau đó tạo một mảng động tên m là mảng các con trỏ IntPtr *m = new IntPtr[3];  Với mỗi con trỏ trong m, tạo một mảng động các biến int for(int i = 0; i < 3; i++) m[i] = new int[4]; diepht@vnu 35 Mảng động nhiều chiều  Minh họa mảng động 3x4 m IntPtr's int's IntPtr * diepht@vnu 36 Hủy mảng động nhiều chiều  Để hủy mảng động nhiều chiều  Mỗi lời gọi tới phép new để tạo một mảng cần một lời gọi tương ứng tới phép delete  Ví dụ: hủy mảng động 3x4 tạo trong slide trước for(int i = 0; i < 3; i++) delete [] m[i]; delete [] m; diepht@vnu 37 Ôn tập  Hãy 1. Định nghĩa kiểu CharArray cho các biến con trỏ trỏ tới mảng cấp phát động chứa các phần tử kiểu char. 2. Viết mã để thiết lập giá trị cho các phần tử trong mảng “entry” với 10 số nhập từ bàn phím int *entry; entry = new int[10]; diepht@vnu 38 1. Con trỏ 2. Mảng cấp phát động 3. class và mảng cấp phát động diepht@vnu 39 Nội dung chính Các lớp và mảng động  Một mảng động có thể chứa các phần tử thuộc kiểu dữ liệu do người dùng định nghĩa bằng class (một lớp)  Một lớp có thể có biến thành viên là mảng động diepht@vnu 40 Chương trình ví dụ: Lớp xâu ký tự  Ta sẽ định nghĩa lớp StringVar  Đối tượng StringVar là biến xâu ký tự  Đối tượng StringVar dùng mảng động (có kích thước được chỉ định khi chương trình đang chạy) diepht@vnu 41 Các hàm kiến tạo StringVar  Hàm kiến tạo mặc định StringVar tạo một đối tượng chiều dài xâu tối đa là 100 ký tự  Một hàm kiến tạo StringVar khác nhận một đối số kiểu int chỉ định chiều dài xâu tối đa của đối tượng  Hàm kiến tạo StringVar thứ ba nhận đối số là xâu kiểu C và  đặt chiều dài xâu tối đa là chiều dài của xâu đối số  chép xâu kiểu C vào xâu của đối tượng diepht@vnu 42 Các phép toán trên StringVar  Ngoài các hàm kiến tạo, giao diện của StringVar còn có  Các hàm thành viên  int getLength( );  void inputLine(istream& ins);  friend ostream& operator<<(ostream& outs, const StringVar& aString);  Hàm kiến tạo sao chép (copy constructor)  Hàm hủy diepht@vnu 43 Cài đặt StringVar  StringVar dùng một mảng động để lưu trữ xâu  Các hàm kiến tạo StringVar gọi phép toán new để tạo mảng động cho biến thành viên value  Dùng ‘\0’ để kết thúc xâu  Trước khi khai báo mảng, kích thước của nó không được thiết lập  Các đối số của hàm kiến tạo chỉ định kích thước diepht@vnu 44 Biến cấp phát động  Biến cấp phát động không tự biến mất nếu ta không gọi phép delete  Kể cả khi một biến con trỏ địa phương bị thu hồi ở cuối một hàm thì biến cấp phát động mà nó trỏ tới vẫn tồn tại (nếu delete không được gọi tường minh)  Một người sử dụng lớp StringVar không thể biết được một thành viên của lớp là mảng động nên cũng không thể mong chờ người ấy sẽ gọi delete khi làm việc xong với đối tượng StringVar diepht@vnu 45 Hàm hủy  Hàm hủy là một hàm thành viên được gọi tự động khi một đối tượng của lớp ra ngoài phạm vi hoạt động  Hàm hủy chứa mã nguồn thực hiện delete tất cả các biến cấp phát động tạo ra bởi đối tượng  Một lớp chỉ có một hàm hủy. Hàm này không có đối số.  Tên hàm hủy phân biệt với hàm kiến tạo mặc định bởi dấu ngã ~  Ví dụ: ~StringVar(); diepht@vnu 46 ~StringVar()  Hàm hủy của lớp StringVar phải gọi tới delete [] để trả lại free store những vùng nhớ các biến cấp phát động chiếm giữ  Ví dụ StringVar::~StringVar( ) { delete [ ] value; } diepht@vnu 47 Truyền con trỏ vào trong hàm bằng kiểu truyền giá trị (call-by-value) diepht@vnu 48  Truyền con trỏ vào trong hàm kiểu truyền giá trị có thể dẫn tới kết quả không như mong đợi  Hãy nhớ các tham số là các biến địa phương  Biến đổi tham số không thực sự biến đổi đối số  Giá trị của tham số được đặt bằng giá trị của đối số  Trong trường hợp này là một địa chỉ lưu trong một biến con trỏ  Đối số và tham số cùng lưu một địa chỉ  Nếu bên trong hàm, bạn thay đổi giá trị của biến trỏ bởi tham số thì biến trỏ bởi đối số cũng bị thay đổi Hàm kiến tạo sao chép  Vấn đề do dùng tham số truyền bằng giá trị với các biến con trỏ có thể được giải quyết bằng hàm kiến tạo sao chép  Hàm kiến tạo sao chép là một hàm kiến tạo với một tham số cùng kiểu với lớp  Tham số này được truyền bằng tham chiếu (call-by- reference)  Nó thường là hằng tham số  Hàm kiến tạo tạo ra một bản sao hoàn thiện và độc lập của đối số diepht@vnu 49 Hàm kiến tạo sao chép của StringVar  Đoạn mã sau đây của hàm kiến tạo sao chép StringVar  Tạo một mảng động mới cho bản sao của đối số  Tạo một bản sao mới, giữ bản gốc không bị biến đổi StringVar::StringVar(const StringVar& aStringVarObj) : maxLength(aStringVarObj.getLength()) { value = new char[maxLength + 1]; strcpy(value, aStringVarObj.value); } diepht@vnu 50 Gọi hàm kiến tạo sao chép  Có thể gọi hàm kiến tạo sao chép giống với cách gọi các hàm kiến tạo khác – khi khai báo đối tượng  Hàm kiến tạo sao chép được gọi tự động  Khi một đối tượng được định nghĩa và khởi tạo bởi một đối tượng cùng lớp  Khi một hàm trả về một giá trị có kiểu là lớp đó  Khi một đối số có kiểu là lớp đó được truyền bằng giá trị vào trong hàm diepht@vnu 51 Tính cần thiết của hàm kiến tạo sao chép  Đoạn mã sau (giả sử không có hàm kiến tạo sao chép) cho thấy tính cần thiết của hàm kiến tạo sao chép  void showString(StringVar aStringVarObj) { } StringVar greeting("Hello"); showString(greeting); cout << greeting << endl;  Khi hàm showString được gọi, greeting được sao vào aStringVarObj  aStringVarObj.value được thiết lập bằng greeting.value  Vì aStringVarObj.value và greeting.value là các con trỏ, chúng trỏ tới cùng một mảng động diepht@vnu 52 greeting.value aStringVarObj.value "Hello" greeting.value aStringVarObj.value Undefined Tính cần thiết của hàm kiến tạo sao chép  Khi showString kết thúc, hàm hủy cho aStringVarObj được gọi, trả mảng động trỏ bởi aStringVarObj.value về free store  greeting.value trỏ tới một vùng nhớ đã được giải phóng! diepht@vnu 53 Tính cần thiết của hàm kiến tạo sao chép diepht@vnu 54  Đối tượng greeting giờ đây gặp 2 vấn đề  Việc in ra màn hình greeting.value có thể sinh lỗi  Tuy trong một vài trường hợp chương trình vẫn hoạt động  Khi không còn cần greeting, hàm hủy sẽ được gọi  Gọi hàm hủy dẫn tới giải phóng một vùng nhớ 2 lần có thể sinh lỗi hệ thống greeting.value aStringVarObj.value "Hello" greeting.value aStringVarObj.value Undefined Hàm kiến tạo sao chép  Cùng một ví dụ nhưng khi có hàm kiến tạo sao chép sẽ không có 2 vấn đề ở slide trước "Hello" "Hello" diepht@vnu 55 Khi nào thì cần hàm kiến tạo sao chép  Khi trong định nghĩa lớp có chứa con trỏ và vùng nhớ cấp phát động bằng phép new thì cần hàm kiến tạo sao chép  Các lớp không liên quan tới con trỏ hay vùng nhớ cấp phát động thì không cần hàm kiến tạo sao chép diepht@vnu 56 Bộ ba quan trọng  Bộ ba quan trọng bao gồm  Hàm kiến tạo sao chép  Phép toán gán  Hàm hủy  Nếu bạn cần định nghĩa 1 trong chúng, bạn cần định nghĩa cả 3. diepht@vnu 57 Phép toán gán  Nếu được cho các khai báo sau StringVar str1(10), str2(20); thì câu lệnh str1 = str2; là hợp lệ.  Nhưng vì thành phần value của StringVar là một con trỏ nên str1.value và str2.value trỏ tới cùng một vùng nhớ. diepht@vnu 58 Nạp chồng phép gán  Giải pháp là nạp chồng phép toán gán của StringVar  operator= được nạp chồng như một hàm thành viên  Ví dụ: khai báo operator= void operator=(const StringVar& rightSide);  rightSide là đối số từ vế phải của phép gán diepht@vnu 59 Định nghĩa phép gán (1)  void StringVar::operator= (const StringVar& rightSide) { int newLength = strlen(rightSide.value); if (newLength > maxLength) newLength = maxLength; for(int i = 0; i < newLength; i++) value[i] = rightSide.value[i]; value[newLength] = '\0'; } Không sao hết nội dung của xâu bên vế phải diepht@vnu 60 Định nghĩa phép gán (2)  void StringVar::operator= (const StringVar& rightSide) { delete [ ] value; int newLength = strlen(rightSide.value); maxLength = newLength; value = new char[maxLength + 1]; for(int i = 0; i < newLength; i++) value[i] = rightSide.value[i]; value[newLength] = '\0'; } Lỗi nếu gán một đối tượng StringVar cho chính nó diepht@vnu 61 Định nghĩa phép gán (3)  void StringVar::operator = (const StringVar& rightSide) { int newLength = strlen(rightSide.value); if (newLength > maxLength){ //delete value chỉ khi // cần thêm không gian nhớ delete [ ] value; maxLength = newLength; value = new char[maxLength + 1]; } for (int i = 0; i< newLength; i++) value[i] = rightSide.value[i]; value[newLength] = '\0'; } diepht@vnu 62 Ôn tập  Hãy 1. Giải thích vì sao không cần nạp chồng phép gán nếu một lớp chỉ chứa các kiểu cơ bản 2. Giải thích nhiệm vụ của hàm hủy 3. Khi nào hàm kiến tạo sao chép được gọi diepht@vnu 63