Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 9 đến 11 - Khương Đại Thế

Nội dung text: Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 9 đến 11 - Khương Đại Thế

1. Chương 9: CON TRỎ (POINTER) Gv.Khương Đại Thể 1
2. CON TRỎ (Pointer) Khai báo biến và khởi tạo int x = 8, y = 10; 0xFA30 0xFA32 Khai báo biến pointer x -1684 y -105 int *p; Gán địa chỉ P = &x; // p = x; Error p 0xAA00???? Truy xuất nội dung biến 0xAA000xFA300xFA32???????? NULL6? *p = *p – 12; // x = *p = – 4 , y = 10 p = &y; // y = *p = 10 , x = – 4 y – = 15; // y = *p = – 5 , x = – 4 x += 20; // x = 16 , y = *p = – 5 P = (int*)malloc(sizeof(int)); *P = x – 10; // *p = 6, x = 16, y = – 5 Free(p); // p = NULL Gv.Khương Đại Thể 2
3. Chương 10: HÀM (FUNCTION) Gv.Khương Đại Thể 3
4. Function Khái niệm ❖ Hàm là một đoạn chương trình độc lập thực hiện trọn vẹn một công việc nhất định, sau đó trả về giá trị cho chương trình gọi nó. ❖ Hay nói cách khác hàm là sự chia nhỏ của chương trình. Gv.Khương Đại Thể 4
5. Function #include Ví dụ: #include // Prototype void HoanDoi (int& a, int& b); // void main() { int a,b; clrscr(); printf("Nhap vao 2 so nguyen A,B: "); scanf("%d %d",&a,&b); printf("Truoc khi hoan doi: A=%d va B=%d\n",a,b); HoanDoi(a,b); printf("Sau khi hoan doi: A=%d va B=%d\n",a,b); getch(); } // void HoanDoi (int& a, int& b) { int temp = a; a = b; b = temp; } Gv.Khương Đại Thể 5
6. Function Khai báo Tên hàm([ danh sách các tham số]); Với: Kiểu dữ liệu : int, float, char, struct (void: không kiểu) Tên hàm : người lập trình tự đặt tên theo qui tắc như tên Biến. Ví dụ: void HoanDoi (int& a, int& b); Gv.Khương Đại Thể 6
7. Function Cách Khai báo biến trong hàm: Tên_hàm (danh sách các tham số) { Khai báo các biến cục bộ Các câu lệnh / khối lệnh hay lời gọi đến hàm khác. } #include #include // // Prototype void HoanDoi (int& a, int& b) void HoanDoi (int& a, int& b); { // int temp = a; void main() a = b; { b = temp; int a,b; } clrscr(); printf("Nhap vao 2 so nguyen A,B: "); scanf("%d %d",&a,&b); printf("Truoc khi hoan doi: A=%d va B=%d\n",a,b); HoanDoi(a,b); printf("Sau khi hoan doi: A=%d va B=%d\n",a,b); getch(); } Gv.Khương Đại Thể 7
8. Function Truyền tham số hàm: 1.Truyền Tham Trị: Bên trong giá trị các tham số thay đổi, nhưng ra khỏi hàm vẫn không đổi. Truyền Tham TRỊ Ví dụ: int Tinh (int a) { int temp; a = a+3; temp = 2*(a+4); return temp; } Gv.Khương Đại Thể 8
9. Function Truyền tham số hàm: 2.Truyền Tham Chiếu (&): Bên trong giá trị các tham số thay đổi, ra khỏi hàm bị thay đổi theo. Ví dụ: Truyền Tham CHIẾU void HoanDoi (int& a, int& b) { int temp = a; a = b; b = temp; } Gv.Khương Đại Thể 9
10. Function Truyền tham số hàm: 3.Truyền Tham Biến (*): Bên trong giá trị các tham số thay đổi, ra khỏi hàm bị thay đổi theo. Ví dụ: Truyền Tham BiẾN void HoanDoi (int* a, int* b) { Cơ chế giống Tham int temp = *a; Chiếu, nhưng cách *a = *b; viết theo con trỏ *b = temp; } Gv.Khương Đại Thể 10
11. Function Hàm Đệ quy: ❑ Ngôn ngữ C cho phép từ trong thân của một hàm có lời gọi hàm chính hàm đó. Hàm như vậy gọi là hàm đệ qui. ❑ Khi hàm gọi đệ qui đến chính nó, thì mỗi lần gọi, máy sẽ tạo ra một tập các biến cục bộ mới hoàn toàn độc lập với tập các biến cục bộ đã được tạo ra trong các lần gọi trước. Ví dụ: #include #include // // Prototype unsigned long GiaiThua(int n) // Tính n! với n>=0 { unsigned long GiaiThua(int n); unsigned long gt=1; unsigned long GiaiThuaDQ(int n); for (int i=2; i<=n; i++) // gt *=i; void main() return gt; { } int n; // unsigned long GiaiThuaDQ(int n) printf(“Nhap n = ”); { scanf(“%d”,&n); if (n==0 || n==1) printf(" %d!=%lu", n, GiaiThua(n) ); return 1; printf(" %d!=%lu", n, GiaiThuaDQ(n) ); else getch( ); return (n*GiaiThuaDQ(n-1)); } } Gv.Khương Đại Thể 11
12. Chương 11: MẢNG (ARRAY) Gv.Khương Đại Thể 12
13. MẢNG MỘT CHIỀU (One-dimensional array) Nội dung ➢Khái niệm ➢Khai báo ➢Khởi tạo mảng ➢Chỉ số– giá trị – địa chỉ của phần tử mảng ➢Truyền mảng qua tham số của hàm ➢Các thao tác trên mảng Gv.Khương Đại Thể 13
14. MẢNG MỘT CHIỀU (One-dimensional array) Nội dung ➢ Khái niệm ➢ Khai báo ➢ Khởi tạo mảng ➢ Chỉ số(index)–Giá trị(value)–Địa chỉ(address) của phần tử mảng ➢ Truyền mảng qua tham số của hàm ➢ Các thao tác trên mảng Gv.Khương Đại Thể 14
15. Khái niệm CHỖ ĐẬU XE 0 1 2 3 4 3 Tất cả xe này của tôi Gv.Khương Đại Thể 15
16. One-dimensional array Khái niệm ❖ Mảng là nhóm các phần tử cùng kiểu dữ liệu và cóchung tên. ❖ Mỗi phần tử là một biến thành phần của mảng được quản lý bằng chỉ số(index) bắt đầu từ 0 (liên tiếp, tăng một đơn vị). Như vậy để truy xuất một phần tử của mảng, chúng ta phải biết được chỉ số của nó. ❖ Trong bộ nhớ, các phần tử của mảng được cấp phát các ônhớ có địa chỉ liên tiếp khác nhau. Gv.Khương Đại Thể 16
17. MẢNG MỘT CHIỀU (One-dimensional array) Nội dung ➢ Khái niệm ➢ Khai báo ➢ Khởi tạo mảng ➢ Chỉ số(index)–Giá trị(value)–Địa chỉ(address) của phần tử mảng ➢ Truyền mảng qua tham số của hàm ➢ Các thao tác trên mảng Gv.Khương Đại Thể 17
18. One-dimensional array Khai báo dạng con trỏ hằng (constant pointer) [ ] ; Với: Kiểu dữ liệu : int, float, char, struct, pointer Tên mảng : người lập trình tự đặt tên theo qui tắc như tên Biến. Tên mảng thực chất là một hằng địa chỉ của phần tử đầu tiên. Số phần tử tối đa của mảng : là hằng số nguyên cụ thể. Ví dụ: int a[100]; // Khai báo mảng số nguyên a gồm 100 phần tử #define MAX 50 float b[MAX]; // Khai báo mảng số thực b gồm 50 phần tử const int n = 10; // n là biến hằng char str[n]; // Error, n không phải là hằng số nguyên cụ thể long c[]; // Error, phải khai báo số phần tử tối đa của mảng Gv.Khương Đại Thể 18
19. One-dimensional array Khai báo dạng Con trỏ động (Pointer) (1) * ; Lưu ý: Tên mảng tại thời điểm khai báo này thực chất là biến (pointer) đang chỉ đến vùng nhớ (kể cả giá trị tại vùng nhớ đó) không tường minh. Để chính thức là mảng cần thao tác thêm: Cách 1: cùng quản lý chung với mảng đã tồn tại Ví dụ : p ?? int *p; // khai báo con trỏ p ?? ??? int b[100]; p = b; // p trỏ vào phần tử tại vị trí0 của mảng b Với cách viết này có thể hiểu các cách viết sau là tương đương: p[i]  *(p + i)  b[i]  *(b+i) Gv.Khương Đại Thể 19
20. One-dimensional array Khai báo dạng Con trỏ động (dynamic array) (2) Cách 2: Xin cấp phát một vùng nhớ động để contr ỏ thành mảng động. - Dùng hàm malloc trong thư viện Ví dụ: px ???? int *px; ???? ? // Khai báo con trỏ px px = (int*) malloc(10*sizeof(int)); // Cấp phát10 ô nhớ kiểu int Chú ý: Sau khi sử dụng xong thì nên giải phóng vùng nhớ bằng hàm free Ví dụ : free (px) ; // giải phóng vùng nhớ cho con trỏ px px 0xFA30 Gv.Khương Đại Thể 20
21. MẢNG MỘT CHIỀU (One-dimensional array) Nội dung ➢ Khái niệm ➢ Khai báo ➢Khởi tạo mảng ➢ Chỉ số(index)–Giá trị(value)–Địa chỉ(address) của phần tử mảng ➢ Truyền mảng qua tham số của hàm ➢ Các thao tác trên mảng Gv.Khương Đại Thể 21
22. One-dimensional array Khởi tạo mảng Số lượng các giá trị được khởi tạo bằng đúng với số phần tử khai báo trong mảng. Ví dụ: int a[5] = { 1, 2, 3, 4, 5 }; Số lượng các giá trị được khai báo nếu ít hơn số phần tử của mảng, thì các phần tử còn lại của mảng sẽ được khởi tạo bằng 0. Ví dụ: int a[5] = { 1, 2 }; // int a[5] = { 1, 2, 0, 0, 0 }; Số phần tử của mảng không được chỉ định, thì số phần tử khởi tạo sẽ xác định kích thước của mảng. Ví dụ: int a[ ] = { 1, 2, 3, 4, 5 }; // số phần tử của mảng a bằng 5 Khởi tạo giá trị của tất cả các phần tử trong mảng bằng một giá trị hằng. Ví dụ: int a[10] = {0};//giá trị tất cả các phần tử của mảng a bằng 0 Gv.Khương Đại Thể 22
23. MẢNG MỘT CHIỀU (One-dimensional array) Nội dung ➢Khái niệm ➢Khai báo ➢Khởi tạo mảng ➢Chỉ số– giá trị – địa chỉ của phần tử mảng ➢Truyền mảng qua tham số của hàm ➢Các thao tác trên mảng Gv.Khương Đại Thể 23
24. One-dimensional array Chỉ số (index)–giá trị (value)–địa chỉ(address) của phần tử mảng Ví dụ: #define MAX 10 int a[MAX] = {5, 3, -2, 6, 3, -3, 9, 8, 44, 6}; int *pa; pa = a; // tương đương pa = &a[0]; a 0xFA30 pa 0xFA30 Gv.Khương Đại Thể 24
25. One-dimensional array Index – Value – Address của phần tử mảng (tiếp theo) Cách truy xuất giá trị và địa chỉ của các phần tử của mảng a hay con trỏ pa là tương đương Gv.Khương Đại Thể 25
26. One-dimensional array Nhận xét: Giá trị các phần tử có thểgiống nhau, nhưng chỉ số (hay còn gọi là vị trí) của các phần tử trong mảngluôn phân biệt. Theo qui định của ngôn ngữ C, mảng được quản lý bằng chỉ số nguyên, bắt đầu từ 0, liên tiếp, tăng một đơn vị. Do đó chỉ số trong mảng đóng vai trò rất quan trọng trong việc truy xuất các phần tử của mảng. Ngôn ngữ C không kiểm tra việc truy xuất ngoài phạm vi của mảng. Sự khác biệt rất quan trọng giữa tên mảng và con trỏ : Tên mảng thực chất là một hằng địa chỉ (cố định) của phần tử đầu tiên, nên không thể thay đổi trị của nó được. Còn con trỏ hoàn toàn có thể thay đổi trị bên trong để nó chỉ đến một đối tượng khác. Ví dụ : #define MAX 10 int a[MAX] = {5, 3, -2, 6, 3, -3, 9, 8, 44, 6}; int *pa; pa = a; // tương đương pa = &a[0]; a = a + 1; // Error pa = pa + 1; //tương đương pa = &a[1]; hợp lệ Gv.Khương Đại Thể 26
27. One-dimensional array a 0xFA30 pa pb 00xFAxFA 3032 0xFA3C Lưu ý: Con trỏ trên mảng có thể truy xuất các phần tử theo chiều tăng hay theo chiều giảm. pa = pa + 1; int *pb; pb = a + 6; Hai con trỏ trên cùng một mảng có thể trừ nhau, cho ra số nguyên, chính là khoảng cách giữa hai phần tử của mảng mà hai con trỏ trên đang trỏ đến. printf(“%d”, pb – pa); // 5 Gv.Khương Đại Thể 27
28. MẢNG MỘT CHIỀU (One-dimensional array) Nội dung ➢ Khái niệm ➢ Khai báo ➢ Khởi tạo mảng ➢ Chỉ số(index)–Giá trị(value)–Địa chỉ(address) của phần tử mảng ➢Truyền mảng qua tham số của hàm ➢ Các thao tác trên mảng Gv.Khương Đại Thể 28
29. One-dimensional array Truyền mảng qua tham số của hàm Khi một mảng được truyền qua tham số của hàm thì tên mảng (con trỏ chỉ đến phần tử đầu tiên của mảng) được gởi đi. Các thao tác bên trong hàm có thể truy xuất làm thay đổi trị của bất kỳ phần tử nào. Có hai dạng khai báo mảng là tham số của hàm: Gv.Khương Đại Thể 29
30. MẢNG MỘT CHIỀU (One-dimensional array) Nội dung ➢ Khái niệm ➢ Khai báo ➢ Khởi tạo mảng ➢ Chỉ số(index)–Giá trị(value)–địa chỉ(address) của phần tử mảng ➢ Truyền mảng qua tham số của hàm ➢Các thao tác trên mảng Gv.Khương Đại Thể 30
31. One-dimensional array Các thao tác trên mảng ✓ Nhập và xuất mảng ✓ Kỹ thuật đặt cờ hiệu ✓ Kỹ thuật đặt lính canh ✓ Tìm kiếm trên mảng ✓ Đếm – Tần suất ✓ Tính tổng – Trung bình có điều kiện ✓ Sắp xếp mảng ✓ Xóa phần tử của mảng ✓ Chèn thêm phần tử vào mảng ✓ Tách / chia mảng ✓ Ghép / nối mảng Gv.Khương Đại Thể 31
32. One-dimensional array Nhập và xuất mảng Viết chương trình nhập xuất mảng một chiều các số nguyên. #include void NhapMang (int a[], int &n) #include { #define MAX 100 printf (“Nhap so phan tu: “); // Prototype scanf (“ %d ”, &n); void NhapMang (int a[], int &n); for (int i = 0; i < n; i ++) { void XuatMang (int a[], int n); printf (“ a [%d] = “, i); // scanf (“ %d “, &a[i]); void main ( ) } { } clrscr ( ); // int a[MAX] , n; void XuatMang (int a[], int n) NhapMang (a,n); { printf (“\nNoi dung mang: “); for (int i = 0; i < n; i ++) XuatMang (a,n); printf (“ %d \t “, a[i]); getch ( ); } } Gv.Khương Đại Thể 32
33. One-dimensional array Kỹ thuật đặt cờ hiệu Viết hàm kiểm tra xem mảng các số nguyên có thứ tự tăng dần không? Index 0 1 2 3 4 5 6 7 8 9 a -3 -1 51 82 23 34 15 85 58 48 // Trả về 1: Nếu mảng tăng dần, ngược lại trả về 0 int KiemTraTang (int a[ ], int n) { int flag = 1; for (int i = 0; i a[i+1] ) // Vi phạm điều kiện tăng dần { flag = 0; break; } return flag; } Gv.Khương Đại Thể 33
34. One-dimensional array Kỹ thuật đặt lính canh Viết hàm tìm giá trị lớn nhất trong mảng một chiều các số nguyên. i Index 0 1 2 3 4 5 6 7 8 9 a -3 -1 5 7 2 3 1 8 5 4 int TimMax (int a[], int n) { int max, i; max = a[0]; i = 1; max while ( i max ) max = a[i] ; i++; } return max; } Gv.Khương Đại Thể 34
35. One-dimensional array Tìm kiếm trên mảng Viết hàm tìm vị trí phần tử có giá trị x xuất hiện đầu tiên trong mảng một chiều các số nguyên. // Nếu tìm thấy trả về vị trí xuất hiện x, ngược lại trả về -1 int TimX (int a[], int n, int x) { for (int i = 0; i < n ; i ++) if ( x == a[i] ) return i; return -1; } Gv.Khương Đại Thể 35
36. One-dimensional array Đếm – Tần suất Viết hàm đếm các phần tử dương và bội của 5 trong mảng các số nguyên. int Dem (int a[], int n ) { int dem = 0; for (int i = 0; i 0 )&& ( a[i] % 5 == 0 )) dem++; return dem; } Gv.Khương Đại Thể 36
37. One-dimensional array Tính tổng-Trung bình có điều kiện Viết hàm tính trung bình cộng các phần tử dương trong mảng các số nguyên. float TinhTBC (int a[], int n ) { float tong = 0; int dem = 0; for (int i = 0; i 0) { tong = tong + a[i] ; dem++; } return (tong / dem); } Gv.Khương Đại Thể 37
38. One-dimensional array Sắp xếp mảng Viết hàm sắp xếp mảng theo thứ tự tăng dần. Gợi ý: Trong khi duyệt mảng từ trái sang phải, thì tại vị trí đang xét chúng ta lại duyệt qua tất cả các phần tử đứng sau nó, so sánh trị (nếu cần thì hoán đổi). nhằm đưa trị thích hợp về vị trí đang xét. void HoanDoi (int &a, int &b) { int temp = a; a = b; b = temp; } void SapTang (int a[], int n) { for (int i = 0; i a [j]) HoanDoi (a[i], a[j]); } Gv.Khương Đại Thể 38
39. One-dimensional array Xóa phần tử của mảng Viết hàm xoá phần tử tại vị trí (k) cho trước trong mảng. Gợi ý: + Trước khi xóa ta phải xác định vị trí cần xóa theo điều kiện phù hợp của bài toán. + Duyệt mảng từ trái sang phải. Xuất phát từ vị trí cần xoá tiến hành dời lần lượt các phần tử về phía trước cho đến khi kết thúc mảng, sau đó giảm kích thước mảng. void XoaViTri (int a[], int &n, int k) { if (k =n) return; for (int i =k; i < n-1 ; i++) a[i] = a[i+1]; n ; } Gv.Khương Đại Thể 39
40. One-dimensional array Chèn thêm phần tử vào mảng Viết hàm chèn phần tử có giá trị nguyên X vào mảng số nguyên (a) tại vị trí (k) cho trước. Gợi ý: + Trước khi chèn ta phải xác định vị trí cần chèn theo điều kiện phù hợp của bài toán. + Duyệt mảng từ phải sang trái. Xuất phát từ cuối mảng tiến hành đẩy lần lượt các phần tử về phía sau cho đến vị trí cần chèn, chèn phần tử cần chèn vào vị trí chèn và tăng kích thước mảng. void ChenX (int a[], int &n, int X, int k) { if (k n) return; for (int i = n; i >k ; i ) a[i] = a[i-1] ; a[k] = X; n++; } Gv.Khương Đại Thể 40
41. One-dimensional array Tách / chia mảng Cho mảng số nguyên a( na phần tử), tách mảng a thành 2 mảng b(nb phần tử) và mảng c (nc phần tử) sao cho mảng b chỉ chứa cácph ần tử số nguyên âm và cácph ần tử còn lại đưa vào mảng c. void TachMang(int a[], int na, int b[], int &nb, int c[], int &nc) { nb = nc = 0; for(int i=0; i<na; i++) { if (a[i] < 0) b[nb++] = a[i]; else c[nc++] = a[i]; } } Gv.Khương Đại Thể 41
42. One-dimensional array Ghép / nối mảng Cho 2 mảng số nguyên a (na phần tử) và b (nb phần tử), nối mảng b vào cuối mảng a. void NoiMang(int a[], int &na, int b[], int nb) { for(int i=0; i<nb; i++) a[na+i]=b[i]; na=na+nb; } Gv.Khương Đại Thể 42
43. One-dimensional array Tóm lại ❑ Dữ liệu kiểu mảng dùng cho việc biểu diễn những thông tin có cùng kiểu dữ liệu liên tiếp nhau. ❑ Khi cài đặt bài tập mảng một chiều nên xây dựng thành những hàm chuẩn để dùng lại cho các bài tập khác. ❑ Các thao tác trên mảng đều theo quy tắc nhất định, chúng ta có thể ứng dụng mảng trong việc biểu diễn số lớn, dùng bảng tra Gv.Khương Đại Thể 43
44. One-dimensional array Câu hỏi 1 int a[5] = {1,2,3,4,5}; int *pa = a; *(pa+2)++; Sau khi thực thi đoạn code trên, tập trị của mảng a là gì? a) { 1,2,3,4,5} b) { 6,7,8,9,10} c) { 1,2,3,9,5} { 1,2,4,4,5} d) Tập trị khác ĐÚNG Gv.Khương Đại Thể 44
45. One-dimensional array Câu hỏi2 int a[5] = {2,3,4,5,5}; int *p1 = &a[0], *p2 = &a[4]; (*p1)++; *(p2 -1)- - ; Sau khi thực thi đoạn code trên, tập trị của mảng a là gì? a) { 2,3,4,5,5} b) { 3,3,4,5,5} c) { 3,3,4,4,5} ĐÚNG d) { 3,3,4,6,6} Gv.Khương Đại Thể 45
46. One-dimensional array Câu hỏi3 int a[6] = {1,2,3,4,5,6}; int *p1 = &a[0], *p2 = &a[5]; printf(“%d”,++(*p1) – (*p2)); Sau khi thực thi đoạn code trên, kết quả xuất ra là gì? a) - 4 ĐÚNG b) 2 c) 5 d) Tất cả đều sai Gv.Khương Đại Thể 46
47. MẢNG HAI CHIỀU (Two-dimensional array) Nội dung ➢Khái niệm ➢Khai báo ➢Khởi tạo mảng 2 chiều ➢Truyền mảng 2 chiều qua tham số của hàm ➢Các thao tác trên mảng 2 chiều Gv.Khương Đại Thể 47
48. MẢNG HAI CHIỀU (Two-dimensional array) Nội dung ➢ Khái niệm ➢ Khai báo ➢ Khởi tạo mảng 2 chiều ➢ Truyền mảng 2 chiều qua tham số của hàm ➢ Các thao tác trên mảng 2 chiều Gv.Khương Đại Thể 48
49. Khái niệm Two-dimensional arrays ❖Mảng hai chiều thực chất là mảng một chiều trong đó mỗi phần tử của mảng là một mảng một chiều, và được truy xuất bởi hai chỉ số dòng và cột. Multidimensional arrays ❖Từ khái niệm trên ta có thể đưa ra một khái niệm về mảng nhiều chiều như sau: mảng có từ hai chiều trở lên gọi là mảng nhiều chiều. Gv.Khương Đại Thể 49
50. Two-dimensional array Hình ảnh minh họa: int a[RM][CM]; Dòng Cột Cột ( j ) 0 1 2 3 o o o CM-1 Dòng 0 2 3 9 4 14 ( ( o o o o o i i 1 5 6 7 6 -6 ) 2 2 9 4 7 0 o o o o o o o o o o o o o RM-1 1 3 6 -7 o o o 5 Gv.Khương Đại Thể 50
51. Two-dimensional array Hình ảnh minh họa: int a[3][4] = { {2,3,9,4} , {5,6,7,6} , {2,9,4,7} }; ROWMAX COLMAX Cột ( j ) 0 1 2 3 k = i *COLMAX ? + j Dòng 0 2 3 9 4 1 5 6 7 6 i = k / COLMAX ? ( i ) 2 2 9 4 7 j = k % ?COLMAX k Index 0 1 2 3 4 5 6 7 8 9 10 11 a Dòng 0 Dòng 1 Dòng 2 Gv.Khương Đại Thể 51
52. MẢNG HAI CHIỀU (Two-dimensional array) Nội dung ➢ Khái niệm ➢ Khai báo ➢ Khởi tạo mảng 2 chiều ➢ Truyền mảng 2 chiều qua tham số của hàm ➢ Các thao tác trên mảng 2 chiều Gv.Khương Đại Thể 52
53. Two-dimensional array Khai báo Kiểu dữ liệu [Số dòng tối đa][Số cột tối đa]; Với: Kiểu dữ liệu : int, float, char, struct Tên mảng 2 chiều : người lập trình tự đặt tên theo qui tắc như tên Biến. Tên mảng 2chiều thực chất là một hằng địa chỉ của phần tử đầu tiên (dòng 0, cột 0). Số dòng, số cột tối đa của mảng : là hằng số nguyên cụ thể. Ví dụ: int a[10][10]; // Khai báo mảng 2 chiều kiểu int gồm 10 dòng, 10 cột float b[10][10]; // Khai báo mảng 2 chiều kiểu float gồm 10 dòng, 10 cột int c[10][]; // Error, phải khai báo số phần tử tối đa của cột long d[][10]; // Error, phải khai báo số phần tử tối đa của dòng Gv.Khương Đại Thể 53
54. MẢNG HAI CHIỀU (Two-dimensional array) Nội dung ➢ Khái niệm ➢ Khai báo ➢Khởi tạo mảng 2 chiều ➢ Truyền mảng 2 chiều qua tham số của hàm ➢ Các thao tác trên mảng 2 chiều Gv.Khương Đại Thể 54
55. Two-dimensional array Ví dụ: int a[3][4] = { {2,3,9,4} , {5,6,7,6} , {2,9,4,7} }; 0 1 2 3 0 2 3 9 4 1 5 6 7 6 2 2 9 4 7 Với cách khai báo như trên ta có : a[0][0] = 2; a[0][1] = 3; a[1][1] = 6; a[2][3] = 7; Gv.Khương Đại Thể 55
56. MẢNG HAI CHIỀU (Two-dimensional array) Nội dung ➢ Khái niệm ➢ Khai báo ➢ Khởi tạo mảng 2 chiều ➢ Truyền mảng 2 chiều qua tham số của hàm ➢ Các thao tác trên mảng 2 chiều Gv.Khương Đại Thể 56
57. Two-dimensional array Truyền mảng 2 chiều qua tham số của hàm Khi một mảng 2 chiều được truyền qua tham số của hàm thì tên mảng (con trỏ chỉ đến phần tử đầu tiên của mảng) được gởi đi. Các thao tác bên trong hàm có thể truy xuất làm thay đổi trị của bất kỳ phần tử nào. Dạng khai báo mảng 2 chiều là tham số của hàm: void NhapMang ( int a[][MAX] , int &dong , int &cot ) { } Gv.Khương Đại Thể 57
58. MẢNG HAI CHIỀU (Two-dimensional array) Nội dung ➢ Khái niệm ➢ Khai báo ➢ Khởi tạo mảng 2 chiều ➢ Truyền mảng 2 chiều qua tham số của hàm ➢Các thao tác trên mảng 2 chiều Gv.Khương Đại Thể 58
59. Two-dimensional array Các thao tác trên mảng Gần như tương tự như trên mảng một chiều Gv.Khương Đại Thể 59
60. Nhập và xuất Two-dimensional array Viết chương trình nhập xuất mảng hai chiều các số nguyên. #include void NhapMatran (int a[][MAX], int &r, int &c) #include { #define MAX 10 printf (“Nhap so dong: “); // Prototype scanf (“ %d ”, &r); void NhapMatran (int a[][MAX], int& r, int& c); printf (“Nhap so cot: “); scanf (“ %d ”, &c); void XuatMatran (int a[][MAX], int r, int c); for (int i = 0; i < r; i ++) // for (int j = 0; j < c; j ++) void main ( ) { { printf (“ a [%d][%d] = “, I,j); clrscr ( ); scanf (“ %d “, &a[i][j]); int a[MAX][MAX]; } int r,c; } NhapMatran (a,r,c); // printf (“\nNoi dung ma tran: \n“); void XuatMatran (int a[][MAX], int r, int c) XuatMatran (a,r,c); { getch ( ); for (int i = 0; i < r; i ++) { for (int j = 0; j < c; j ++) } printf (“ %d \t “, a[i][j]); printf (“\n“); } } Gv.Khương Đại Thể 60
61. Two-dimensional array Sắp xếp ma trận Viết hàm sắp xếp ma trận có giá trị tăng dần từ trái sang phải và từ trên xuống dưới. Gợi ý: Tư tưởng sắp xếp giống như trên mảng 1 chiều. void HoanDoi (int &a, int &b) { int temp = a; a = b; b = temp; } void SapTang (int a[][MAX], int r, int c) { for (int i = 0; i a [j/c][j%c]) HoanDoi (a[i/c][i%c], a[j/c][j%c]); } Gv.Khương Đại Thể 61
62. XIN CÁM ƠN Gv.Khương Đại Thể 62