›

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++

pdf 63 trang huongle 7170
Download
Bạn đang xem 20 trang mẫu của tài liệu "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++", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_con_tro_va_mang_cap.pdf

Nội dung text: 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++

  1. Con trỏ và mảng cấp phát động trong C++ Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Dịch từ slides Chapter 12: Pointers and Dynamic Arrays của tác giả David Mann (North Idaho College). Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
  2. Nội dung chính 1. Con trỏ 2. Mảng cấp phát động 3. class và mảng cấp phát động 2 diepht@vnu
  3. 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. 3 diepht@vnu
  4. Con trỏ cho biết phải tìm một biến ở đâu  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. 4 diepht@vnu
  5. 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ỏ. 5 diepht@vnu
  6. Khai báo nhiều biến con trỏ  Để 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 6 diepht@vnu
  7. Phép toán lấy địa chỉ  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 7 diepht@vnu
  8. 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 8 diepht@vnu
  9. Ví dụ  v1 = 0; p1 = &v1; v1 and *p1 ám chỉ cùng một biến *p1 = 42; cout << v1 << endl; cout << *p1 << endl; output: 42 42 9 diepht@vnu
  10. 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 10 diepht@vnu
  11. 11 diepht@vnu
  12. 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; 12 diepht@vnu
  13. 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 13 diepht@vnu
  14. 14 diepht@vnu
  15. 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ớ 15 diepht@vnu
  16. 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. 16 diepht@vnu
  17. 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. 17 diepht@vnu
  18. 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 18 diepht@vnu
  19. Biến tự động  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 19 diepht@vnu
  20. 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 20 diepht@vnu
  21. Đị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; 21 diepht@vnu
  22. Đị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; 22 diepht@vnu
  23. 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ỏ 23 diepht@vnu
  24. 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); 24 diepht@vnu
  25. Ô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 25 diepht@vnu
  26. Nội dung chính 1. Con trỏ 2. Mảng cấp phát động 3. class và mảng cấp phát động 26 diepht@vnu
  27. 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 27 diepht@vnu
  28. 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] 28 diepht@vnu
  29. Biến con trỏ dùng như biến mảng 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; 29 diepht@vnu
  30. 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 30 diepht@vnu
  31. 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 31 diepht@vnu
  32. 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] 32 diepht@vnu
  33. 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] 33 diepht@vnu
  34. 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] << " " ; 34 diepht@vnu
  35. 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]; 35 diepht@vnu
  36. Mảng động nhiều chiều  Minh họa mảng động 3x4 m IntPtr's IntPtr * int's 36 diepht@vnu
  37. 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; 37 diepht@vnu
  38. Ô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]; 38 diepht@vnu
  39. Nội dung chính 1. Con trỏ 2. Mảng cấp phát động 3. class và mảng cấp phát động 39 diepht@vnu
  40. 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 40 diepht@vnu
  41. 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) 41 diepht@vnu
  42. 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 42 diepht@vnu
  43. 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 43 diepht@vnu
  44. 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 44 diepht@vnu
  45. 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 45 diepht@vnu
  46. 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(); 46 diepht@vnu
  47. ~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; } 47 diepht@vnu
  48. Truyền con trỏ vào trong hàm bằng kiểu truyền giá trị (call-by-value)  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 48 diepht@vnu
  49. 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ố 49 diepht@vnu
  50. 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); } 50 diepht@vnu
  51. 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 51 diepht@vnu
  52. 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 52 diepht@vnu
  53. Tính cần thiết của hàm kiến tạo sao chép "Hello" Undefined greeting.value aStringVarObj.value aStringVarObj.value greeting.value  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! 53 diepht@vnu
  54. Tính cần thiết của hàm kiến tạo sao chép  Đố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 54 diepht@vnu
  55. Hàm kiến tạo sao chép "Hello" "Hello" Undefined "Hello" greeting.value aStringVarObj.value aStringVarObj.value greeting.value  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 55 diepht@vnu
  56. 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 56 diepht@vnu
  57. 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. 57 diepht@vnu
  58. 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ớ. 58 diepht@vnu
  59. 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 59 diepht@vnu
  60. Định nghĩa phép gán (1)  void StringVar::operator= (const StringVar& rightSide) { int newLength = strlen(rightSide.value); if (newLength > maxLength) newLength = maxLength; Không sao hết nội for(int i = 0; i < newLength; i++) dung của xâu bên value[i] = rightSide.value[i]; vế phải value[newLength] = '\0'; } 60 diepht@vnu
  61. Đị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]; Lỗi nếu gán một đối tượng StringVar cho for(int i = 0; i < newLength; i++) chính nó value[i] = rightSide.value[i]; value[newLength] = '\0'; } 61 diepht@vnu
  62. Đị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'; } 62 diepht@vnu
  63. Ô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 63 diepht@vnu