Bài giảng Nhập môn lập trình - Chương 7: Mảng hai chiều

Nội dung text: Bài giảng Nhập môn lập trình - Chương 7: Mảng hai chiều

1. & VC BB Nội dung 1 Khái niệm 2 Khai báo 3 Truy xuất dữ liệu kiểu mảng 4 Một số bài toán trên mảng 2 chiều 1 NMLT - Mảng hai chiều
2. & VC BB Ma Trận 0 1 n-1 0 n-1 0 0 Am,n An m-1 n-1 2 NMLT - Mảng hai chiều
3. & VC BB Ma Trận 0 n-1 0 n-1 0 n-1 0 0 0 An n-1 n-1 n-1 dòng = cột dòng > cột dòng n-1 dòng + cột < n-1 3 NMLT - Mảng hai chiều
4. & VC BB Khai báo kiểu mảng 2 chiều vCú pháp typedef [ ][ ]; § N1, N2: số lượng phần tử mỗi chiều vVí dụ typedef int MaTran[3][4]; 0 1 2 3 0 Kiểu MaTran 1 2 4 NMLT - Mảng hai chiều
5. & VC BB Khai báo biến mảng 2 chiều vCú pháp § Tường minh [ ][ ]; § Không tường minh (thông qua kiểu) typedef [ ][ ]; ; , ; 5 NMLT - Mảng hai chiều
6. & VC BB Khai báo biến mảng 2 chiều vVí dụ § Tường minh int a[10][20], b[10][20]; int c[5][10]; int d[10][20]; § Không tường minh (thông qua kiểu) typedef int MaTran10x20[10][20]; typedef int MaTran5x10[5][10]; MaTran10x20 a, b; MaTran11x11 c; MaTran10x20 d; 6 NMLT - Mảng hai chiều
7. & VC BB Truy xuất đến một phần tử vThông qua chỉ số [ ][ ] vVí dụ 0 1 2 3 § Cho mảng 2 chiều như sau 0 1 int a[3][4]; 2 § Các truy xuất • Hợp lệ: a[0][0], a[0][1], , a[2][2], a[2][3] • Không hợp lệ: a[-1][0], a[2][4], a[3][3] 7 NMLT - Mảng hai chiều
8. & VC BB Gán dữ liệu kiểu mảng vKhông được sử dụng phép gán thông thường mà phải gán trực tiếp giữa các phần tử = ; //sai [ ][giá trị cs2] = ; vVí dụ int a[5][10], b[5][10]; b = a;// Sai int i, j; for (i = 0; i < 5; i++) for (j = 0; j < 10; j++) b[i][j] = a[i][j]; 8 NMLT - Mảng hai chiều
9. & VC BB Truyền mảng cho hàm vTruyền mảng cho hàm § Tham số kiểu mảng trong khai báo hàm giống như khai báo biến mảng void NhapMaTran(int a[50][100]); § Tham số kiểu mảng truyền cho hàm chính là địa chỉ của phần tử đầu tiên của mảng • Có thể bỏ số lượng phần tử chiều thứ 2 hoặc con trỏ. • Mảng có thể thay đổi nội dung sau khi thực hiện hàm. void NhapMaTran(int a[][100]); void NhapMaTran(int (*a)[100]); 9 NMLT - Mảng hai chiều
10. & VC BB Truyền mảng cho hàm vTruyền mảng cho hàm § Số lượng phần tử thực sự truyền qua biến khác void XuatMaTran(int a[50][100], int m, int n); void XuatMaTran(int a[][100], int m, int n); void XuatMaTran(int (*a)[100], int m, int n); vLời gọi hàm void NhapMaTran(int a[][100], int &m, int &n); void XuatMaTran(int a[][100], int m, int n); void main() { int a[50][100], m, n; NhapMaTran(a, m, n); XuatMaTran(a, m, n); 10 } NMLT - Mảng hai chiều
11. & VC BB Một số bài toán cơ bản vViết chương trình con thực hiện các yêu cầu sau § Nhập mảng § Xuất mảng § Tìm kiếm một phần tử trong mảng § Kiểm tra tính chất của mảng § Tính tổng các phần tử trên dòng/cột/toàn ma trận/đường chéo chính/nửa trên/nửa dưới § Tìm giá trị nhỏ nhất/lớn nhất của mảng § 11 NMLT - Mảng hai chiều
12. & VC BB Một số quy ước vKiểu dữ liệu #define MAXD 50 #define MAXC 100 vCác chương trình con § Hàm void HoanVi(int x, int y): hoán vị giá trị của hai số nguyên. § Hàm int LaSNT(int n): kiểm tra một số có phải là số nguyên tố. Trả về 1 nếu n là số nguyên tố, ngược lại trả về 0. 12 NMLT - Mảng hai chiều
13. & VC BB Thủ tục HoanVi & Hàm LaSNT void HoanVi(int &x, int &y) { int tam = x; x = y; y = tam; } int LaSNT(int n) { int i, dem = 0; for (i = 1; i <= n; i++) if (n%i == 0) dem++; if (dem == 2) return 1; else return 0; } 13 NMLT - Mảng hai chiều
14. & VC BB Nhập Ma Trận vYêu cầu § Cho phép nhập mảng a, m dòng, n cột vÝ tưởng § Cho trước một mảng 2 chiều có dòng tối đa là MAXD, số cột tối đa là MAXC. § Nhập số lượng phần tử thực sự m, n của mỗi chiều. § Nhập từng phần tử từ [0][0] đến [m-1][n-1]. 14 NMLT - Mảng hai chiều
15. & VC BB Hàm Nhập Ma Trận void NhapMaTran(int a[][MAXC], int &m, int &n) { cout >m>>n; int i, j; for (i=0; i >a[i][j]; } } 15 NMLT - Mảng hai chiều
16. & VC BB Xuất Ma Trận vYêu cầu § Cho phép nhập mảng a, m dòng, n cột vÝ tưởng § Xuất giá trị từng phần tử của mảng 2 chiều từ dòng có 0 đến dòng m-1, mỗi dòng xuất giá giá trị của cột 0 đến cột n-1 trên dòng đó. 16 NMLT - Mảng hai chiều
17. & VC BB Hàm Xuất Ma Trận void XuatMaTran(int a[][MAXC], int m, int n) { int i, j; for (i=0; i<m; i++) { for (j=0; j<n; j++) cout<< a[i][j]<<setw(4); cout<<“\n”; } } 17 NMLT - Mảng hai chiều
18. & VC BB Tìm kiếm một phần tử trong Ma Trận vYêu cầu § Tìm xem phần tử x có nằm trong ma trận a kích thước mxn hay không? vÝ tưởng § Duyệt từng phần của ma trận a. Nếu phần tử đang xét bằng x thì trả về có (1), ngược lại trả về không có (0). 18 NMLT - Mảng hai chiều
19. & VC BB Hàm Tìm Kiếm int TimKiem(int a[][MAXC], int m, int n, int x) { int i, j; for (i=0; i<m; i++) for (j=0; j<n; j++) if (a[i][j] == x) return 1; return 0; } 19 NMLT - Mảng hai chiều
20. & VC BB Kiểm tra tính chất của mảng vYêu cầu § Cho trước ma trận a kích thước mxn. Ma trận a có phải là ma trậntoàn các số nguyên tố hay không? vÝ tưởng § Cách 1: Đếm số lượng số ngtố của ma trận. Nếu số lượng này bằng đúng mxn thì ma trận toàn ngtố. § Cách 2: Đếm số lượng số không phải ngtố của ma trận. Nếu số lượng này bằng 0 thì ma trận toàn ngtố. § Cách 3: Tìm xem có phần tử nào không phải số ngtố không. Nếu có thì ma trận không toàn số ngtố. 20 NMLT - Mảng hai chiều
21. & VC BB Hàm Kiểm Tra (Cách 1) int KiemTra_C1(int a[][MAXC], int m, int n) { int i, j, dem = 0; for (i=0; i<m; i++) for (j=0; j<n; j++) if (LaSNT(a[i][j]==1) dem++; if (dem == m*n) return 1; return 0; } 21 NMLT - Mảng hai chiều
22. & VC BB Hàm Kiểm Tra (Cách 2) int KiemTra_C2(int a[][MAXC], int m, int n) { int i, j, dem = 0; for (i=0; i<m; i++) for (j=0; j<n; j++) if (LaSNT(a[i][j]==0) dem++; if (dem == 0) return 1; return 0; } 22 NMLT - Mảng hai chiều
23. & VC BB Hàm Kiểm Tra (Cách 2) int KiemTra_C3(int a[][MAXC], int m, int n) { int i, j, dem = 0; for (i=0; i<m; i++) for (j=0; j<n; j++) if (LaSNT(a[i][j]==0) return 0; return 1; } 23 NMLT - Mảng hai chiều
24. & VC BB Tính tổng các phần tử vYêu cầu § Cho trước ma trận a, kích thước mxn. Tính tổng các phần tử trên: • Dòng d, cột c • Đường chéo chính, đường chéo phụ (ma trận vuông) • Nửa trên/dưới đường chéo chính (ma trận vuông) • Nửa trên/dưới đường chéo phụ (ma trận vuông) vÝ tưởng § Duyệt ma trận và cộng dồn các phần tử có tọa độ (dòng, cột) thỏa yêu cầu. 24 NMLT - Mảng hai chiều
25. & VC BB Hàm tính tổng trên dòng int TongDong(int a[][MAXC], int m, int n, int d) { int j, tong; tong = 0; for (j=0; j<n; j++) // Duyệt các cột tong = tong + a[d][j]; return tong; } 25 NMLT - Mảng hai chiều
26. & VC BB Hàm tính tổng trên cột int TongCot(int a[][MAXC], int m, int c) { int i, tong; tong = 0; for (i=0; i<m; i++) // Duyệt các dòng tong = tong + a[i][c]; return tong; } 26 NMLT - Mảng hai chiều
27. & VC BB Hàm tính tổng đường chéo chính int TongDCChinh(int a[][MAXC], int n) { int i, tong; tong = 0; for (i=0; i<n; i++) tong = tong + a[i][i]; return tong; } 27 NMLT - Mảng hai chiều
28. & VC BB Hàm tính tổng trên đường chéo chính int TongTrenDCChinh(int a[][MAXC], int n) { int i, j, tong; tong = 0; for (i=0; i<n; i++) for (j=0; j<n; j++) if (i < j) tong = tong + a[i][j]; return tong; } 28 NMLT - Mảng hai chiều
29. & VC BB Hàm tính tổng dưới đường chéo chính int TongTrenDCChinh(int a[][MAXC], int n) { int i, j, tong; tong = 0; for (i=0; i j) tong = tong + a[i][j]; return tong; } 29 NMLT - Mảng hai chiều
30. & VC BB Hàm tính tổng trên đường chéo phụ int TongDCPhu(int a[][MAXC], int n) { int i, tong; tong = 0; for (i=0; i<n; i++) tong = tong + a[i][n-i-1]; return tong; } 30 NMLT - Mảng hai chiều
31. & VC BB Tìm giá trị lớn nhất của Ma Trận vYêu cầu § Cho trước ma trận a, kích thước mxn. Tìm giá trị lớn nhất trong ma trận a (gọi là max) vÝ tưởng § Giả sử giá trị max hiện tại là giá trị phần tử đầu tiên a[0][0] § Lần lượt kiểm tra các phần tử còn lại để cập nhật max. 31 NMLT - Mảng hai chiều
32. & VC BB Hàm tìm Max int TimMax(int a[][MAXC], int m, int n) { int i, j, max; max = a[0][0]; for (i=0; i max) max = a[i][j]; return max; } 32 NMLT - Mảng hai chiều
33. & VC BB Câu hỏi và bài tập v Nêu lợi ích của việc dùng mảng. v Nêu cách khai báo và khởi tạo giá trị cho biến mảng một chiều, biến mảng hai chiều. v Nêu cách truyền tham số mảng cho hàm, cách gọi hàm có tham số mảng. v Trình bày các thao tác cơ bản trên kiểu mảng (1 chiều và 2 chiều): − Nhập/Xuất giá trị cho các phần tử mảng − Thêm phần tử mới vào mảng − Xóa một phần tử trong mảng thỏa tiêu chuẩn P nào đó. − Tìm kiếm trên mảng − Sắp xếp mảng. 33