›
›

Bài giảng Nhập môn lập trình - Chủ đề 5: Kiểu dữ liệu mảng, chuỗi - Phần 2: Mảng hai chiều

pdf 33 trang phuongnguyen 2970
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn lập trình - Chủ đề 5: Kiểu dữ liệu mảng, chuỗi - Phần 2: Mảng hai chiều", để 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_nhap_mon_lap_trinh_chu_de_5_kieu_du_lieu_mang_chuo.pdf

Nội dung text: Bài giảng Nhập môn lập trình - Chủ đề 5: Kiểu dữ liệu mảng, chuỗi - Phần 2: Mảng hai chiều

  1. NHẬP MÔN LẬP TRÌNH MẢNG HAI CHIỀU 1
  2. Nội dung 1 Khái niệm 2 Khai báo 3 Truy xuấtdữ liệukiểumảng 4 Mộtsố bàitoántrênmảng 2 chiều Mảng hai chiều 2
  3. Ma Trận 0 1 n-1 0 n-1 0 0 Am,n An m-1 n-1 Mảng hai chiều 3
  4. 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 Mảng hai chiều 4
  5. Khai báo kiểumảng 2 chiều ™Cú pháp typedef [ ][ ]; ƒ N1, N2: số lượng phầntử mỗichiều ™Ví dụ typedef int MaTran[3][4]; 0 1 2 3 0 KiểuMaTran 1 2 Mảng hai chiều 5
  6. Khai báo biếnmảng 2 chiều ™Cú pháp ƒ Tường minh [ ][ ]; ƒ Không tường minh (thông qua kiểu) typedef [ ][ ]; ; , ; Mảng hai chiều 6
  7. Khai báo biếnmảng 2 chiều ™Ví 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; Mảng hai chiều 7
  8. Truy xuất đến mộtphầntử ™Thông qua chỉ số [ ][ ] ™Ví dụ 0 1 2 3 ƒ Cho mảng 2 chiềunhư sau 0 1 int a[3][4]; 2 ƒ Các truy xuất • Hợplệ: a[0][0], a[0][1], , a[2][2], a[2][3] • Không hợplệ: a[-1][0], a[2][4], a[3][3] Mảng hai chiều 8
  9. Gán dữ liệukiểumảng ™Không được sử dụng phép gán thông thường mà phải gán trựctiếpgiữacácphầntử ™Ví 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]; Mảng hai chiều 9
  10. Truyềnmảng cho hàm ™Truyềnmảng cho hàm ƒ Tham số kiểumả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ểumảng truyền cho hàm chính là địa chỉ củaphầntửđầu tiên củamảng •Cóthể bỏ số lượng phầntử chiềuthứ 2 hoặc con trỏ. •Mảng có thể thay đổi nội dung sau khi thựchiệnhàm. void NhapMaTran(int a[][100]); void NhapMaTran(int (*a)[100]); Mảng hai chiều 10
  11. Truyềnmảng cho hàm ™Truyềnmảng cho hàm ƒ Số lượng phầntử thựcsự 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); ™Lờigọihà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); } Mảng hai chiều 11
  12. Mộtsố bài toán cơ bản ™Viếtchương trình con thựchiệncácyêucầusau ƒ Nhậpmảng ƒ Xuấtmảng ƒ Tìm kiếmmộtphầntử trong mảng ƒ Kiểmtratínhchấtcủamảng ƒ Tính tổng các phầntử trên dòng/cột/toàn ma trận/đường chéo chính/nửatrên/nửadưới ƒ Tìm giá trị nhỏ nhất/lớnnhấtcủamảng ƒ Mảng hai chiều 12
  13. Mộtsố quy ước ™Kiểudữ liệu #define MAXD 50 #define MAXC 100 ™Cá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ểmtramộtsố có phải là số nguyên tố. Trả về 1 nếun làsố nguyên tố, ngược lạitrả về 0. Mảng hai chiều 13
  14. Thủ tụcHoanVi& HàmLaSNT Mảng hai chiều 14
  15. NhậpMa Trận ™Yêu cầu ƒ Cho phép nhậpmảng a, m dòng, n cột ™Ý tưởng ƒ Cho trước mộtmảng 2 chiều có dòng tối đa là MAXD, số cộttối đa là MAXC. ƒ Nhập số lượng phầntử thựcsự m, n củamỗichiều. ƒ Nhậptừng phầntử từ [0][0] đến [m-1][n-1]. Mảng hai chiều 15
  16. Hàm NhậpMa Trận void NhapMaTran(int a[][MAXC], int &m, int &n) { printf(“Nhap so dong, so cot cua ma tran: ”); scanf(“%d%d”, &m, &n); int i, j; for (i=0; i<m; i++) for (j=0; j<n; j++) { printf(“Nhap a[%d][%d]: ”, i, j); scanf(“%d”, &a[i][j]); } } Mảng hai chiều 16
  17. XuấtMa Trận ™Yêu cầu ƒ Cho phép nhậpmảng a, m dòng, n cột ™Ý tưởng ƒ Xuấtgiátrị từng phầntử củamảng 2 chiềutừ dòng có 0 đến dòng m-1, mỗi dòng xuấtgiágiátrị củacột 0 đến cột n-1 trên dòng đó. Mảng hai chiều 17
  18. Hàm XuấtMa 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++) printf(“%d ”, a[i][j]); printf(“\n”); } } Mảng hai chiều 18
  19. Tìm kiếmmộtphầntử trong Ma Trận ™Yêu cầu ƒ Tìm xem phầntử x có nằm trong ma trận a kích thước mxn hay không? ™Ý tưởng ƒ Duyệttừng phầncủama trận a. Nếuphầntửđang xét bằng x thì trả về có (1), ngược lạitrả về không có (0). Mảng hai chiều 19
  20. 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; } Mảng hai chiều 20
  21. Kiểm tra tính chấtcủamảng ™Yêu cầu ƒ Cho trước ma trận a kích thước mxn. Ma trậna có phảilàma trậntoàn các số nguyên tố hay không? ™Ý tưởng ƒ Cách 1: Đếmsố lượng số ngtố củama trận. Nếusố lượng này bằng đúng mxn thì ma trận toàn ngtố. ƒ Cách 2: Đếmsố lượng số không phảingtố củama trận. Nếusố lượng này bằng 0 thì ma trận toàn ngtố. ƒ Cách 3: Tìm xem có phầntử nào không phảisố ngtố không. Nếucóthìma trận không toàn số ngtố. Mảng hai chiều 21
  22. Hàm KiểmTra(Cách1) 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; } Mảng hai chiều 22
  23. Hàm KiểmTra(Cách2) 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; } Mảng hai chiều 23
  24. Hàm KiểmTra(Cách2) 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; } Mảng hai chiều 24
  25. Tính tổng các phầntử ™Yêu cầu ƒ Cho trước ma trận a, kích thước mxn. Tính tổng các phầntử trên: •Dòngd, cộtc • Đườ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) ™Ý tưởng ƒ Duyệtma trậnvàcộng dồncácphầntử có tọa độ (dòng, cột) thỏayêucầu. Mảng hai chiều 25
  26. 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; } Mảng hai chiều 26
  27. 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; } Mảng hai chiều 27
  28. 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; } Mảng hai chiều 28
  29. 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; } Mảng hai chiều 29
  30. 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; } Mảng hai chiều 30
  31. 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; } Mảng hai chiều 31
  32. Tìm giá trị lớnnhấtcủaMa Trận ™Yê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ọilàmax) ™Ý tưởng ƒ Giả sử giá trị max hiệntại là giá trị phầntửđầu tiên a[0][0] ƒ Lầnlượt kiểm tra các phầntử còn lại để cậpnhật max. Mảng hai chiều 32
  33. 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; } Mảng hai chiều 33