Bài giảng Ngôn ngữ lập trình C - Chương 7: Mảng hai chiều - Ngô Hữu Dũng

Ngôn ngữ lập trình C
Mảng hai chiều
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH
Nội dung
Ngôn ngữ lập trình C - Mảng hai chiều2
 Mảng hai chiều
 Vòng lặp lồng nhau
Ma Trận
Ngôn ngữ lập trình C - Mảng hai chiều
0
m-1
0 1  n-1
Am,n
0
n-1
An
0  n-1
3
Ma Trận
Ngôn ngữ lập trình C - Mảng hai chiều
0
n-1
An
0  n-1
0
n-1
0  n-1
0
n-1
0  n-1
dòng = cột dòng > cột dòng < cột
0
n-1
An
0  n-1
0
n-1
0  n-1
0
n-1
0  n-1
dòng + cột = n-1 dòng + cột > n-1 dòng + cột < n-1
4
Khai báo kiểu mảng 2 chiều
 Cú pháp
 N1, N2: số lượng phần tử mỗi chiều
 Ví dụ
Ngôn ngữ lập trình C - Mảng hai chiều
typedef [][];
typedef int MaTran[3][4];
0
1
2
0 1 2 3
Kiểu MaTran
5
Khai báo biến mảng 2 chiều
 Cú pháp
 Tường minh
 Không tường minh (thông qua kiểu)
Ngôn ngữ lập trình C - Mảng hai chiều
 [][];
typedef [][];
 ;
 , ;
6
Khai báo biến mảng 2 chiều
 Ví dụ
 Tường minh
 Không tường minh (thông qua kiểu)
Ngôn ngữ lập trình C - Mảng hai chiều
int a[10][20], b[10][20];
int c[5][10];
int d[10][20];
typedef int MaTran10x20[10][20];
typedef int MaTran5x10[5][10];
MaTran10x20 a, b;
MaTran11x11 c;
MaTran10x20 d;
7
Truy xuất đến một phần tử
 Thông qua chỉ số
 Ví dụ
 Cho mảng 2 chiều như sau
 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]
Ngôn ngữ lập trình C - Mảng hai chiều
[][]
int a[3][4]; 0
1
2
0 1 2 3
8
Gán dữ liệu kiểu mảng
 Khô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ử
 Ví dụ
Ngôn ngữ lập trình C - Mảng hai chiều
 = ; //sai
[][giá trị cs2] =
;
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];
9
Truyền mảng cho hàm
 Truyề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
 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.
Ngôn ngữ lập trình C - Mảng hai chiều
void NhapMaTran(int a[50][100]);
void NhapMaTran(int a[][100]);
void NhapMaTran(int (*a)[100]);
10
Truyền mảng cho hàm
 Truyền mảng cho hàm
 Số lượng phần tử thực sự truyền qua biến khác
 Lời gọi hàm
Ngôn ngữ lập trình C - Mảng hai chiều
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);
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);
}
11
Một số bài toán cơ bản
 Viế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
 
Ngôn ngữ lập trình C - Mảng hai chiều12
Một số quy ước
 Kiểu dữ liệu
 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ể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.
Ngôn ngữ lập trình C - Mảng hai chiều
#define MAXD 50
#define MAXC 100
13
Thủ tục HoanVi & Hàm LaSNT
Ngôn ngữ lập trình C - Mảng hai chiều
void HoanVi(int &x, int &y){
int tam = x; x = y; y = tam;
}
bool LaSNT(int n){
int i=2; 
while(i<n){
if(n%i==0)
break;
else
i++;
}
if(i==n)
return true;
return false;
}
14
Nhập Ma Trận
 Yêu cầu
 Cho phép nhập mảng a, m dòng, n cột
 Ý 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].
Ngôn ngữ lập trình C - Mảng hai chiều15
Hàm Nhập Ma Trận
Ngôn ngữ lập trình C - Mảng hai chiều
1. void NhapMaTran(int a[][MAXC], int &m, int &n)
2. {
3. printf(“Nhap so dong, so cot cua ma tran: ”);
4. scanf(“%d%d”, &m, &n);
5. int i, j;
6. for (i=0; i<m; i++)
7. for (j=0; j<n; j++)
8. {
9. printf(“Nhap a[%d][%d]: ”, i, j);
10. scanf(“%d”, &a[i][j]);
11. }
12.}
16
Xuất Ma Trận
 Yêu cầu
 Cho phép nhập mảng a, m dòng, n cột
 Ý 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 đó.
Ngôn ngữ lập trình C - Mảng hai chiều17
Hàm Xuất Ma Trận
Ngôn ngữ lập trình C - Mảng hai chiều
1. void XuatMaTran(int a[][MAXC], int m, int n)
2. {
3. int i, j;
4. for (i=0; i<m; i++)
5. {
6. for (j=0; j<n; j++)
7. printf(“%d ”, a[i][j]);
8. printf(“\n”);
9. }
10.}
18
Tìm kiếm một phần tử trong Ma Trận
 Yê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?
 Ý 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).
Ngôn ngữ lập trình C - Mảng hai chiều19
Hàm Tìm Kiếm
Ngôn ngữ lập trình C - Mảng hai chiều
1. int TimKiem(int a[][MAXC], int m, int n, int x)
2. {
3. int i, j;
4. for (i=0; i<m; i++)
5. for (j=0; j<n; j++)
6. if (a[i][j] == x)
7. return 1;
8. return 0;
9. }
20
Kiểm tra tính chất của mảng
 Yê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?
 Ý 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ố.
Ngôn ngữ lập trình C - Mảng hai chiều21
Hàm Kiểm Tra (Cách 1)
Ngôn ngữ lập trình C - Mảng hai chiều
1. int KiemTra_C1(int a[][MAXC], int m, int n)
2. {
3. int i, j, dem = 0;
4. for (i=0; i<m; i++)
5. for (j=0; j<n; j++)
6. if (LaSNT(a[i][j]==1)
7. dem++;
8. if (dem == m*n)
9. return 1;
10. return 0;
11.}
22
Hàm Kiểm Tra (Cách 2)
Ngôn ngữ lập trình C - Mảng hai chiều
1. int KiemTra_C2(int a[][MAXC], int m, int n)
2. {
3. int i, j, dem = 0;
4. for (i=0; i<m; i++)
5. for (j=0; j<n; j++)
6. if (LaSNT(a[i][j]==0)
7. dem++;
8. if (dem == 0)
9. return 1;
10. return 0;
11.}
23
Hàm Kiểm Tra (Cách 2)
Ngôn ngữ lập trình C - Mảng hai chiều
1. int KiemTra_C3(int a[][MAXC], int m, int n)
2. {
3. int i, j, dem = 0;
4. for (i=0; i<m; i++)
5. for (j=0; j<n; j++)
6. if (LaSNT(a[i][j]==0)
7. return 0;
8. return 1;
9. }
24
Tính tổng các phần tử
 Yê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)
 Ý 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.
Ngôn ngữ lập trình C - Mảng hai chiều25
Hàm tính tổng trên dòng
Ngôn ngữ lập trình C - Mảng hai chiều
1. int TongDong(int a[][MAXC], int m, int n, int d)
2. {
3. int j, tong;
4. tong = 0;
5. for (j=0; j<n; j++) // Duyệt các cột
6. tong = tong + a[d][j];
7. return tong;
8. }
26
Hàm tính tổng trên cột
Ngôn ngữ lập trình C - Mảng hai chiều
1. int TongCot(int a[][MAXC], int m, int c)
2. {
3. int i, tong;
4. tong = 0;
5. for (i=0; i<m; i++) // Duyệt các dòng
6. tong = tong + a[i][c];
7. return tong;
8. }
27
Hàm tính tổng đường chéo chính
Ngôn ngữ lập trình C - Mảng hai chiều
1. int TongDCChinh(int a[][MAXC], int n)
2. {
3. int i, tong;
4. tong = 0;
5. for (i=0; i<n; i++)
6. tong = tong + a[i][i];
7. return tong;
8. }
28
Hàm tính tổng trên đường chéo chính
Ngôn ngữ lập trình C - Mảng hai chiều
1. int TongTrenDCChinh(int a[][MAXC], int n)
2. {
3. int i, j, tong;
4. tong = 0;
5. for (i=0; i<n; i++)
6. for (j=0; j<n; j++)
7. if (i < j)
8. tong = tong + a[i][j];
9. return tong;
10.}
29
Hàm tính tổng dưới đường chéo chính
Ngôn ngữ lập trình C - Mảng hai chiều
1. int TongTrenDCChinh(int a[][MAXC], int n)
2. {
3. int i, j, tong;
4. tong = 0;
5. for (i=0; i<n; i++)
6. for (j=0; j<n; j++)
7. if (i > j)
8. tong = tong + a[i][j];
9. return tong;
10.}
30
Hàm tính tổng trên đường chéo phụ
Ngôn ngữ lập trình C - Mảng hai chiều
1. int TongDCPhu(int a[][MAXC], int n)
2. {
3. int i, tong;
4. tong = 0;
5. for (i=0; i<n; i++)
6. tong = tong + a[i][n-i-1];
7. return tong;
8. }
31
Tìm giá trị lớn nhất của Ma 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ọi là max)
 Ý 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.
Ngôn ngữ lập trình C - Mảng hai chiều32
Hàm tìm Max
Ngôn ngữ lập trình C - Mảng hai chiều
1. int TimMax(int a[][MAXC], int m, int n)
2. {
3. int i, j, max;
4. max = a[0][0];
5. for (i=0; i<m; i++)
6. for (j=0; j<n; j++)
7. if (a[i][j] > max)
8. max = a[i][j];
9. return max;
10.}
33