›
›

Cấu trúc dữ liệu và thuật toán

pdf 97 trang vanle 3670
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và thuật toán", để 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:

  • pdfcau_truc_du_lieu_va_thuat_toan.pdf

Nội dung text: Cấu trúc dữ liệu và thuật toán

  1. 1 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN DATA STRUCTURE AND ALGORITHMS
  2. Tài liệu học tập 2  Giáo trình:  C & Data Structures, P. S. Deshpande, O. G. Kakde - CHARLES RIVER MEDIA, INC. Hingham, Massachusetts.  Tham khảo:  Giáo trình Cấu trúc dữ liệu 1, Trần Hạnh Nhi – Dương Anh Đức, Trường ĐHKHTN – ĐHQG TP.HCM.  Phần mềm lập trình:  C-Free  Borland C++ Chương 1: Ôn tập C/C++
  3. Đánh giá kết quả 3 1. Kiểm tra giữa kỳ: thực hành  Điểm Kiểm tra giữa kỳ < 5 không được thi kết thúc môn học lại 2. Kiểm tra cuối kỳ: thực hành  Điểm Kiểm tra cuối kỳ < 5 không được thi kết thúc môn học lại 3. Bài tập lớn: làm bài tập trong module: bốc thăm  Điểm Đề tài < 5 không được thi kết thúc môn học lại 4. Thi kết thúc môn: trắc nghiệm 5. Kiểm tra thường kỳ Chương 1: Ôn tập C/C++
  4. Nội dung môn học 4  Chương 0: Giới thiệu chung  Chương 1: Ôn tập C/C++  Chương 2: Đệ quy (Recursion)  Chương 3: Tìm kiếm (Searching)  Chương 4: Sắp xếp (Sorting)  Chương 5: Ngăn xếp - Hàng đợi (Stacks - Queues)  Chương 6: Danh sách liên kết (Linked List)  Chương 7: Cây (Tree)  ÔN TẬP - KIỂM TRA (REVIEW – TEST) Chương 1: Ôn tập C/C++
  5. 5 Chương 0: Giới thiệu chung
  6. Nội dung 6  Cấu trúc dữ liệu  Thuật toán  Độ phức tạp của thuật toán Chương 1: Ôn tập C/C++
  7. Cấu trúc dữ liệu 7  (1) Sự tổ chức hợp lý của các thành phần dữ liệu,  (2) Tập các thao tác để truy cập các thành phần dữ liệu.  (1) the logical arrangement of data elements, combined with  (2) the set of operations we need to access the elements. Chương 1: Ôn tập C/C++
  8. Ví dụ các cấu trúc dữ liệu 8  Mảng (array)  Danh sách liên kết (linked list)  Ngăn xếp (stack)  Hàng đợi (queue)  Cây (tree)  Chương 1: Ôn tập C/C++
  9. Nội dung 9  Cấu trúc dữ liệu  Thuật toán  Độ phức tạp của thuật toán Chương 1: Ôn tập C/C++
  10. Thuật toán 10  Tập các bước có thể tính toán được để đạt được kết quả mong muốn  A computable set of steps to achieve a desired result Chương 1: Ôn tập C/C++
  11. Ví dụ 11  Tính tổng các số nguyên lẻ từ 1 n  B1: S=0  B2: i=1  B3: Nếu i=n+1 thì sang B7, ngược lại sang B4  B4: S=S+i  B5: i=i+2  B6: Quay lại B3  B7: Tổng cần tìm là S Chương 1: Ôn tập C/C++
  12. Mối quan hệ của CTDL và thuật toán 12 CTDL + Thuật toán = Chương trình Chương 1: Ôn tập C/C++
  13. Ví dụ 13  Một chương trình quản lý điểm thi của sinh viên cần lưu trữ các điểm số của 3 sinh viên. Giả sử mỗi sinh viên có 4 điểm số ứng với 4 môn học khác nhau, dữ liệu có dạng bảng như sau: Chương 1: Ôn tập C/C++
  14. Ví dụ 14  Chỉ xét thao tác xử lý là xuất điểm số các môn của từng sinh viên.  Phương án 1 : Sử dụng mảng một chiều: int result [12] = {7, 9, 5, 2, 5, 0, 9, 4, 6, 3, 7, 4};  các phần tử sẽ được lưu trữ như sau:  Truy xuất điểm số môn j của sinh viên i phải sử dụng một công thức xác định chỉ số tương ứng trong mảng result: result[(i*số cột) + j] Chương 1: Ôn tập C/C++
  15. Ví dụ 15 void XuatDiem() //Xuất điểm số của tất cả sinh viên { const int so_mon = 4; int sv,mon; for (int i=0; i<12; i++) { sv = i/so_mon; mon = i % so_mon; cout<<"Điểm môn "<<mon<<" của sv "<<sv<<"là:" <<result[i]; } } Chương 1: Ôn tập C/C++
  16. Ví dụ 16  Chỉ xét thao tác xử lý là xuất điểm số các môn của từng sinh viên.  Phương án 2 : Sử dụng mảng hai chiều: int result[3][4] ={{ 7, 9, 5, 2}, { 5, 0, 9, 4}, { 6, 3, 7, 4 }};  các phần tử sẽ được lưu trữ như sau:  Truy xuất điểm số môn j của sinh viên i cũng chính là phần tử nằm ở vị trí (dòng i, cột j) trong mảng: result[i][j] Chương 1: Ôn tập C/C++
  17. Ví dụ 17 void XuatDiem() //Xuất điểm số của tất cả sinh viên { const int so_mon = 4, so_sv = 3; for ( int i=0; i<so_sv; i++) for ( int j=0; j<so_mon; j++) cout<<"Điểm môn "<< j <<" của sv "<< i <<"là:" result[i][j]; } Chương 1: Ôn tập C/C++
  18. Nội dung 18  Cấu trúc dữ liệu  Thuật toán  Độ phức tạp của thuật toán (algorithm complexity) Chương 1: Ôn tập C/C++
  19. Độ phức tạp của thuật toán 19  Phân tích thuật toán  Tính đúng  Tính đơn giản  Không gian  Thời gian chạy của thuật toán Chương 1: Ôn tập C/C++
  20. Độ phức tạp của thuật toán 20  Thời gian chạy của thuật toán  Đánh giá như thế nào  Thực nghiệm  Xấp xỉ Chương 1: Ôn tập C/C++
  21. Độ phức tạp của thuật toán 21  Thực nghiệm  Chịu sự hạn chế của ngôn ngữ lập trình  Ảnh hưởng bởi trình độ của người cài đặt  Chọn được các bộ dữ liệu thử đặc trưng cho tất cả tập các dữ liệu vào của thuật toán: khó khăn và tốn nhiều chi phí  Phụ thuộc nhiều vào phần cứng Chương 1: Ôn tập C/C++
  22. Độ phức tạp của thuật toán 22  Xấp xỉ tiệm cận  Cách thông dụng nhất để đánh giá một thuật toán là ký hiệu tiệm cận gọi là Big-O  Định nghĩa toán học của Big-O: Cho f và g là hai hàm từ tập các số nguyên hoặc số thực đến số thực. Ta nói f(x) là O(g(x)) nếu tồn tại hằng số C và k sao cho: |f(x)| ≤ C |g(x)| với mọi x > k  Ví dụ, hàm f(x) = x2+ 3x + 2 là O(x2) Thật vậy, khi x > 2 thì x < x2 và 2 < 2x2 Do đó x2 + 3x + 2 < 6x2 Nghĩa là ta chọn được C = 6 và k = 2 Chương 1: Ôn tập C/C++
  23. Độ phức tạp của thuật toán 23  Một số kết quả Big-O quan trọng:  Hàm đa thức: n n-1  f(x) = anx + an-1x + + a1x + a0  Khi đó f(x) là O(xn)  Hàm giai thừa:  f(n) = n! là O(nn)  Logarit của hàm giai thừa:  f(n) = logn! là O(nlogn)  Hàm điều hòa  H(n) = 1 + 1/2 + 1/3 + + 1/n là O(logn) Chương 1: Ôn tập C/C++
  24. Độ phức tạp của thuật toán 24  Một số lớp thuật toán Chương 1: Ôn tập C/C++
  25. Độ phức tạp của thuật toán 25  Một số lớp thuật toán O(log n)  2 O(n) O(nlog2 n) ®é phøc t¹p ®a thøc chÊp nhËn ®­îc 2 O(n ) k O() n  O(2n )  ®é phøc t¹p cao khã chÊp nhËn n!  Chương 1: Ôn tập C/C++
  26. Độ phức tạp của thuật toán 26  Một số lớp thuật toán Chương 1: Ôn tập C/C++
  27. Độ phức tạp của thuật toán 27  Ví dụ, xét hàm sau:  Hai lệnh cout ngoài vòng lặp có độ phức tạp hằng O(1) – vì không phụ thuộc vào N  Số lệnh cout trong vòng lặp bằng với kích thước mảng, do đó vòng lặp có độ phức tạp O(N)  Tổng cộng: Hàm f có độ phức tạp: 2 * O(1) + O(N) Độ phức tạp: O(N) void f (int a[], int n) { cout<< "N = "<< n; for (int i = 0; i < n; i++ ) cout<<a[i]; cout<< "\n"; } Chương 1: Ôn tập C/C++
  28. 28 Chương 1: Ôn tập C/C++ (Tham khảo tài liệu môn Phương Pháp Lập Trình)
  29. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 29
  30. 1. Cấu trúc chương trình C/C++ 30 Cấu trúc chương trình C #include “stdio.h” #include “conio.h” void main() /*ham chinh*/ { int a=7; printf( “%d”, a ); getch(); } Chương 1: Ôn tập C/C++
  31. 1. Cấu trúc chương trình C/C++ 31 Cấu trúc chương trình C++ #include “iostream.h” #include “conio.h” void main() /*ham chinh*/ { int a=7; cout<< a ; getch(); } Chương 1:1: Ôn tập C/C++
  32. 1. Cấu trúc chương trình C/C++ 32  Qui cách viết chương trình  Các dòng trong cùng một khối thẳng cột  Khối con của một khối lùi vào ít nhất một TAB  Sử dụng thống nhất các qui tắc giãn cách  Ghi chú thích ở những chỗ cần thiết Chương 1: Ôn tập C/C++
  33. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 33
  34. 2. Các cú pháp cơ bản 34  Khai báo biến: Kiểu_dữ_liệu tên_biến;  Khai báo và khởi tạo biến: Kiểu_dữ_liệu tên_biến = giá trị;  Khai báo hằng số: const Kiểu_dữ_liệu tên_biến = giá trị; Chương 1:1: Ôn tập C/C++
  35. 2. Các cú pháp cơ bản 35 Các kiểu dữ liệu cơ sở Kiểu Phạm vi biểu diễn Kích thước (byte) char -27 27-1 1 int -215 215-1 2 long -231 231-1 4 float 3.4E-38 3.4E+38 4 double 1.7E-308 1.7E+308 6 35 Chương 1: Ôn tập C/C++
  36. 2. Các cú pháp cơ bản 36 Các phép toán số học Phép toán Tên + cộng - trừ * nhân / chia % chia lấy phần dư ++, Phép tăng, giảm 1 36 Chương 1: Ôn tập C/C++
  37. 2. Các cú pháp cơ bản 37 Các phép toán so sánh Phép toán Tên > lớn hơn >= lớn hơn hoặc bằng < nhỏ hơn <= nhỏ hơn hoặc bằng == bằng != khác 37 Chương 1:1: Ôn tập C/C++
  38. 2. Các cú pháp cơ bản 38 Các phép toán logic Phép toán Tên gọi && AND || OR ! NOT 38 Chương 1:1: Ôn tập C/C++
  39. 2. Các cú pháp cơ bản 39  Chuyển đổi kiểu:  Trong biểu thức: kiểu thấp hơn sẽ được nâng thành kiểu cao hơn trước khi thực hiện phép toán  Ví dụ:  7 + 3.5 Chương 1:1: Ôn tập C/C++
  40. 2. Các cú pháp cơ bản 40  Chuyển đổi kiểu:  Trong phép gán: Giá trị của biểu thức vế phải được chuyển sang kiểu của biến vế trái Ví dụ: int a=5/2; //a=? float b=5/2; //b=? Chương 1:1: Ôn tập C/C++
  41. 2. Các cú pháp cơ bản 41  Ép kiểu:  Cú pháp: (Kiểu) biểu_thức  Ví dụ: (float) 23 (int) x float(23) x*1.0 Chương 1:1: Ôn tập C/C++
  42. 2. Các cú pháp cơ bản 42 Các toán tử điều khiển:  if  if else  switch case  for  while  do while Chương 1:1: Ôn tập C/C++
  43. 2. Các cú pháp cơ bản 43 Toán tử điều kiện if ( bt_điều_kiện ) if ( bt_điều_kiện_1 ) khối_lệnh; khối_lệnh_1 else if ( bt_điều_kiện_2 ) if ( bt_điều_kiện ) khối_lệnh_2 khối_lệnh_1 else else khối_lệnh_2 khối_lệnh_n Chương 1:1: Ôn tập C/C++
  44. 2. Các cú pháp cơ bản 44 Câu lệnh switch switch (biểu_thức_nguyên) { case hằng_1: các_câu_lệnh_1 [break;] case hằng_2: các_câu_lệnh_2 [break;] [default: các_câu_lệnh] } Chương 1:1: Ôn tập C/C++
  45. 2. Các cú pháp cơ bản 45 Các toán tử điều khiển lặp for (bt_khởi_tạo; bt_kiểm_tra; bt_tăng) khối_lệnh while ( bt_điều_khiển ) do { { câu_lệnh_1; câu_lệnh_2; khối_lệnh }while (bt_điều_khiển); } Chương 1:1: Ôn tập C/C++
  46. 2. Các cú pháp cơ bản 46  Cấp phát bộ nhớ tĩnh:  Ví dụ: int a,b;  Cấp phát bộ nhớ động:  Bộ nhớ cũng có thể được cấp phát tại thời gian chạy, gọi là Cấp phát động (dynamic allocation)  Dùng toán tử new để cấp phát bộ nhớ động  Ví dụ: int *P; P = new int; Chương 1:1: Ôn tập C/C++
  47. 2. Các cú pháp cơ bản 47 Chương 1:1: Ôn tập C/C++
  48. 2. Các cú pháp cơ bản 48  Cấp phát bộ nhớ động:  heap: vùng bộ nhớ đặc biệt dành riêng cho các biến động. Để tạo một biến động mới, hệ thống cấp phát không gian từ heap. Nếu không còn bộ nhớ, new không thể cấp phát bộ nhớ thì nó trả về giá trị NULL  Trong lập trình, ta nên luôn kiểm tra lỗi này: int *p; p = new int; if (p == NULL) { cout << “Loi cap phat bo nho\n“; exit; } Chương 1:1: Ôn tập C/C++
  49. 2. Các cú pháp cơ bản 49  Hủy bộ nhớ động:  Trả lại vùng bộ nhớ trỏ bởi P, nhưng không sửa giá trị của P  Dùng toán tử delete để hủy bộ nhớ động  Sau khi thực thi delete, giá trị của con trỏ không xác định  Ví dụ: delete P; Chương 1:1: Ôn tập C/C++
  50. Bài tập 50  Viết chương trình tính diện tích, chu vi hình chữ nhật  Viết chương trình tính diện tích, chu vi hình tròn Chương 1:1: Ôn tập C/C++
  51. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 51
  52. 3. Địa chỉ (Address) 52  Mỗi biến đều có 2 thuộc tính: địa chỉ (address) và giá trị (value) Trong bộ nhớ: + Tại địa chỉ 3: giá trị là 45 + Tại địa chỉ 2: giá trị là “Dave”  Lấy địa chỉ của biến: dùng & int y=90; cout << "Value of 'y' is: " << y << "\n"; cout << "Address of 'y' is: " << &y << "\n\n“; Chương 1: Ôn tập C/C++
  53. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 53
  54. 4. Con trỏ (Pointer) 54  Là một biến mà giá trị của nó chứa một địa chỉ  Định nghĩa một con trỏ: thêm dấu * vào trước tên biến  Ví dụ: int *ia; int x, *p, *q;  Toán tử * : trả về nội dung của địa chỉ được chứa trong một biến con trỏ Chương 1:1: Ôn tập C/C++
  55. 4. Con trỏ (Pointer) 55  Các phép toán số học trên con trỏ:  Phép gán  Phép cộng, trừ một con trỏ với một số nguyên  Tăng, giảm  Ví dụ: int x, *p, *q; p = &x; p = p+2; // tăng 2 kích thước bộ nhớ int q = p; Chương 1:1: Ôn tập C/C++
  56. 4. Con trỏ (Pointer) 56 #include #include void main () { int i; int *ia; i = 10; ia = &i; cout<<" The address of i is "<< ia <<"\n"; cout<<" The value at that location is "<< i <<"\n"; cout<<" The value at that location is "<< *ia <<"\n"; *ia = 50; cout<<" The value of i is "<<i; } Chương 1: Ôn tập C/C++
  57. 4. Con trỏ (Pointer) 57 int i; int *ia; cout<<"Dia chi cua i "<< &i << " co gia tri ="<<i <<endl; cout<<" Dia chi cua ia " << &ia << " co gia tri = " << ia<<endl; i = 10; ia = &i; cout<<"sau khi gan gia tri:"<<endl; cout<<" Dia chi cua i "<< &i << " co gia tri ="<<i <<endl; cout<<" Dia chi cua ia " << &ia << " co gia tri= " << ia<< " tro đen: "<< *ia; Chương 1:1: Ôn tập C/C++
  58. Chương 1: Ôn tập C/C++
  59. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 59
  60. 5. Mảng (Array) 60  Mảng:  Là một cấu trúc dữ liệu  Là danh sách các phần tử có cùng kiểu  Cho phép truy xuất ngẫu nhiên đến các phần tử của nó thông qua chỉ số mảng [0] [1] [2] [3] [4] A 12 2 8 5 1  Khai báo: Kiểu_dữ_liệu tên_mảng[số_phần_tử]; Ví dụ: int a[100]; Chương 1: Ôn tập C/C++
  61. 5. Mảng (Array) 61  Địa chỉ của mỗi phần tử trong mảng:  Mỗi phần tử trong mảng có một địa chỉ trong bộ nhớ (Each element of the array has a memory address)  Ví dụ: void printdetail (int a[]) { for(int i = 0; i<5; i++) { cout<< "value in array "<< a[i] <<" at address: " << &a[i]; } } Chương 1:1: Ôn tập C/C++
  62. 5. Mảng (Array) 62  Truy cập mảng sử dụng con trỏ:  Có thể truy cập từng phần tử của mảng bằng cách sử dụng con trỏ void print_usingptr(int a[], int n) void print_usingptr(int *a, int n) { { int *b; cout<<"value in array\n"; b=a; cout<<"value in array\n"; for (int i=0; i<n; i++) for (int i=0; i<n; i++) { { cout<<*(a+i)<<" "; cout<<*b<<" "; } b++; } } } Chương 1:1: Ôn tập C/C++
  63. 5. Mảng (Array) 63  Cấp phát động cho mảng và hủy mảng:  Kích thước của mảng động không cần là hằng số mà có thể có giá trị được quyết định tại thời gian chạy  new T[n] : cấp phát một mảng gồm n đối tượng kiểu T và trả về một con trỏ tới đầu mảng  delete [] p : hủy mảng mà p trỏ tới P phải trỏ tới đầu mảng động, nếu không, kết quả của delete sẽ phụ thuộc vào trình biên dịch và loại dữ liệu đang sử dụng. Ta có thể nhận được lỗi runtime error hoặc kết quả sai Chương 1:1: Ôn tập C/C++
  64. 5. Mảng (Array) 64 Chương 1:1: Ôn tập C/C++
  65. 5. Mảng (Array) 65 Chương 1:1: Ôn tập C/C++
  66. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 66
  67. 6. Mảng con trỏ (Pointer array) 67  Có thể khai báo mảng con trỏ (tương tự như mảng số)  Trong mảng con trỏ, các phần tử mảng lưu con trỏ void main() { void printarr(int *a[]) int *a[5]; { int i1=4, i2=3, i3=2, i4=1, i5=0; for(int j=0; j<5; j++) a[0] = &i1; { a[1] = &i2; cout<<a[j] <<" "; a[2] = &i3; } a[3] = &i4; } a[4] = &i5; printarr(a); } Chương 1: Ôn tập C/C++
  68. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 68
  69. 7. Mảng hai chiều (Two-dimensional array) 69  Khai báo: Kiểu_dữ_liệu tên_mảng[số_dòng] [số_cột];  Ví dụ: int a[2][3]; float mang[10][5];  Không lấy địa chỉ của phần tử mảng hai chiều bằng toán tử & Chương 1:1: Ôn tập C/C++
  70. 7. Mảng hai chiều (Two-dimensional array) 70  Duyệt mảng hai chiều sử dụng con trỏ:  Ví dụ: float *pa, a[2][3]; pa = (float*)a; // neu khong ep kieu thi C se canh bao // nhung chuong trinh van chay tot Khi đó pa trỏ tới a[0][0] pa+1 trỏ tới a[0][1] pa+2 trỏ tới a[0][2] pa+3 trỏ tới a[1][0] pa+4 trỏ tới a[1][1] pa+5 trỏ tới a[1][2] Chương 1:1: Ôn tập C/C++
  71. Bài tập 71  Viết chương trình cho nhập 1 mảng hình chữ nhật và tính diện tích, chu vi của chúng  Viết chương trình cho nhập 1 mảng hình tròn và tính diện tích, chu vi của chúng Chương 1:1: Ôn tập C/C++
  72. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 72
  73. 8. Cấu trúc (Structure) 73  Được sử dụng khi cần thao tác trên dữ liệu có nhiều thuộc tính  Cú pháp: struct Tên_kiểu_cấu_trúc { các_thành_phần; };  Ví dụ: struct Ngay { int thang; int ngay; int nam; }; Chương 1:1: Ôn tập C/C++
  74. 8. Cấu trúc (Structure) 74  Khai báo biến kiểu cấu trúc (2 cách): Tên_cấu_trúc tên_biến; struct Tên_cấu_trúc tên_biến;  Ví dụ: Ngay n; hoặc: struct Ngay ng;  Khởi tạo cho một cấu trúc: Ví dụ: struct Ngay d={10,15,2004}; struct Ngay a[]={ {10,15,2004}, {10,16,2004}, {10,17,2004}, {10,18,2004}}; Chương 1:1: Ôn tập C/C++
  75. 8. Cấu trúc (Structure) 75  Truy cập thành phần của cấu trúc:  Dùng toán tử “.”: Tên_biến_cấu_trúc.Tên_thành _phần  Ví dụ: Ngay d; d.ngay = 10; d.thang = 10; d.nam = 1910; Chương 1:1: Ôn tập C/C++
  76. 8. Cấu trúc (Structure) 76  Ví dụ Chương 1:1: Ôn tập C/C++
  77. Bài tập 77  Viết chương trình tính diện tích, chu vi hình chữ nhật (yêu cầu khai báo cấu trúc hình chữ nhật)  Viết chương trình tính diện tích, chu vi hình tròn (yêu cầu khai báo cấu trúc hình tròn) Chương 1:1: Ôn tập C/C++
  78. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 78
  79. 9. Con trỏ cấu trúc (Structure pointer) 79  Giống như các kiểu dữ liệu khác, ta có thể khai báo con trỏ cấu trúc  Ví dụ struct Ngay *p, a[10], *p1, b; p = a; p1 = &b;  Truy nhập thành phần của cấu trúc: tên_con_trỏ->tên_thành_phần hoặc : (*tên_con_trỏ).tên_thành_phần Chương 1:1: Ôn tập C/C++
  80. 9. Con trỏ cấu trúc (Structure pointer) 80 #include struct student { char name[30]; float marks; }; void main ( ) { student *sv; char s[30]; float f; cin>>s; cin>>f; sv->name = s; sv->marks = f; cout name marks<<"\n"; } Chương 1: Ôn tập C/C++
  81. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 81
  82. 10. Chuỗi (String) 82  Là mảng các ký tự (array of char)  Kết thúc bởi ký tự null “\0” (ending with null char \0)  Chuỗi hằng được tự động thêm “\0”  Ví dụ: char str[]=“Hello”;
  83. 10. Chuỗi (String) 83  Khai báo chuỗi:  char str[] = {‘H’,’e’,’l’,’l’,’o’,’\0’};  char str[] = “Hello”;  char *str = “Hello”;
  84. 10. Chuỗi (String) 84  Hàm nhập chuỗi:  char *gets(char *s);  Nhận ký tự cho đến khi nhận dấu Enter  Tự động thêm ký tự ‘\0’  So sánh với cin>>s; //????  Hàm xuất chuỗi:  int puts(const char *s);  cout<<s;
  85. 10. Chuỗi (String) 85  Keyboard buffer char szKey[] = "aaa"; char s[10]; do { cout<<"doan lai di?"; gets(s); } while (strcmp (szKey,s) != 0); puts ("OK. corect"); If user input: aaaaaaaaaaaaa???
  86. 10. Chuỗi (String) 86  Một số hàm về chuỗi: (cần #include )  strcpy(s1, s2)  strcat(s1, s2)  strlen(s1)  strcmp(s1, s2) -> (-1,0,1)  strchr(s1, ch)  strstr(s1, s2) 
  87. 10. Chuỗi (String) 87  Ví dụ: char s1[80], s2[80]; cout << "Input the first string: :"; gets(s1); cout << "Input the second string: "; gets(s2); cout << "Length of s1= " << strlen(s1); cout << "Length of s2= " << strlen(s2); if (!strcmp(s1, s2)) cout << "These strings are equal\n"; strcat(s1, s2); cout << "s1 + s2: " << s1 << endl;; strcpy(s1, "This is a test.\n"); cout << s1; if (strchr(s1, 'e')) cout << "e is in " << s1; if (strstr(s2, "hi")) cout << "found hi in " <<s2;
  88. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 88
  89. 11. Tập tin (File) 89  Cần #include  Tạo file mới:  FILE *fp;  fp=fopen(“d:\\test.txt", "wb"))  Ghi nội dung vào file:  fwrite(&Address, sizeof(TYPE), count, fp);  Đóng file (Lưu file):  fclose(fp); Chương 1:1: Ôn tập C/C++
  90. 11. Tập tin (File) 90  FILE *f;  File text, File binary  fopen, fclose, fread, fwrite, fscanf, fprintf, feof . Chương 1:1: Ôn tập C/C++
  91. 11. Tập tin (File) 91  Đọc file: FILE *fp; fp = fopen(“d:\\test.txt", “rb")) while (fwrite(&Address, sizeof(TYPE), count, fp)) { // xử lý nội dung đọc được } fclose(fp); Chương 1:1: Ôn tập C/C++
  92. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 92
  93. 12. Hàm (Function) 93  Các cú pháp định nghĩa hàm: void Tên_Hàm (kiểu_dữ_liệu tên_biến, ) { // các khai báo biến, // các lệnh } Kiểu_dữ_liệu Tên_Hàm (kiểu_dữ_liệu tên_biến, ) { // các khai báo biến, // các lệnh return value; } Chương 1:1: Ôn tập C/C++
  94. 12. Hàm (Function) 94  Cách gọi hàm: 1. Chuẩn bị các tham số để gởi cho hàm nếu có:  Khai báo biến tương ứng và cho nhập dữ liệu cho biến (nếu cần) 2. Hàm không trả về giá trị (void):  Tên_Hàm (tham_số_1, tham_số_2, ); 2. Hàm có trả về giá trị:  Khai báo một biến có kiểu trùng với kiểu trả về của hàm  Viết lệnh gán: biến = Tên_Hàm (tham_số_1, tham_số_2, );  Sử dụng biến để xuất, tính toán, gọi hàm khác Chương 1:1: Ôn tập C/C++
  95. 12. Hàm (Function) 95  Nguyên mẫu hàm (Prototype)  Nguyên mẫu hàm được sử dụng để khai báo một hàm nhờ đó nó có thể được sử dụng trong chương trình trước khi hàm đó được định nghĩa thực sự  Công dụng:  Giúp chương trình mạch lạc  Giúp tổ chức chương trình  Cho phép sử dụng hàm trước khi định nghĩa Chương 1:1: Ôn tập C/C++
  96. #include int compute_sum (int n); /* Function Prototype*/ void main() { int lim = 8, sum; cout 0;n ) sum +=n; return sum; } 96
  97. #include int compute_sum(int n) { int sum=0; for(;n>0;n ) sum +=n; return sum; } void main() { int lim = 8, sum; cout<<"Main lim (before call) is “<<lim<<“\n"; sum = compute_sum(lim); cout<<"Main lim (after call) is “<<lim<<“\n"; cout<<"The sum of integers from 1 to “<< lim<< “ is “<<sum; } 97