Chương 6: Kiểu array (tiếp theo)

CÂU HỎI: Cho biết kết quả thực thi chương trình sau: int f(int); void main() { int n=3; cout0) return a*a + f(a-1); else return 0; } CHƯƠNG 6 KIỂU ARRAY (Tiếp theo) Khai báo biến kiểu array Truy xuất biến array Truyền thông số kiểu array Sử dụng hàm tạo số ngẫu nhiên Một số thuật tóan trên array A. ARRAY 1 CHIỀU: Thông số hình thức không cần chỉ định số phần tử. Thông số thực có thể có số lượng phần tử bất kỳ. Ví dụ 1: Hàm xuất giá trị mảng void xuat(int a[], int n) { for(int i=0; i>n; for (int i=0; i>a[i]; } } void main() { int a[50],n; nhap(a,n); xuat(a,n); getch(); } III. Hàm có thông số kiểu array Hàm random(n) cho kết quả là một số ngẫu nhiên có trị 0  n -1. Các số ngẫu nhiên sinh ra thay đổi sau mỗi lần gọi hàm khởi động trình ngẫu nhiên randomize(); Hai hàm này được cung cấp bởi thư viện stdlib.h IV. Sử dụng hàm tạo số ngẫu nhiên Ví dụ 1: Nhập các phần tử mảng bằng số ngẫu nhiên 0-99: void nhap(int a[], int& n) { cout>n; randomize(); for (int i=0; i=0) i--; return i; } V. Một số thuật tóan thường gặp trên dữ liệu kiểu array 3. Đếm số phần tử theo điều kiện cho trước: Duyệt tòan bộ mảng, tăng trị biến đếm khi phần tử đang duyệt thỏa điều kiện. Ví dụ: Đếm số phần tử lẽ. Đếm số phần tử chẵn. Đếm số phần tử là số chính phương. V. Một số thuật tóan thường gặp trên dữ liệu kiểu array Ví dụ: Đếm số phần tử là số chính phương. int ChinhPhuong(int n) { int i=1; while (i*ia[j]) { tam=a[i]; a[i]=a[j]; a[j]=tam; } } V. Một số thuật tóan thường gặp trên dữ liệu kiểu array Định nghĩa: Là kiểu mảng một chiều trong đó mỗi phần tử có kiểu là kiểu mảng một chiều. Nội dung: Khai báo và truy xuất phần tử. Truyền thông số kiểu array 2 chiều. Một số thuật tóan trên array 2 chiều. B. ARRAY 2 CHIỀU: 1. Cú pháp khai báo biến: Ý nghĩa: Khai báo biến TênBiến là dãy có N1 phần tử, mỗi phần tử là dãy N2 phần tử kiểu TênKiểu Trong đó: TênKiểu: các kiểu cơ sở, là kiểu đơn N1, N2 là các hằng số N1 là số phần tử của chiều thứ 1 N2 là số phần tử của chiều thứ 2 I. Khai báo và truy xuất phần tử TênKiểu TênBiến[N1][N2] Ví dụ 1: Để lưu điểm của 5 môn, mỗi môn có 3 cột điểm. float diem[5][3]; Ví dụ 2: Lưu họ tên cho 10 sinh viên, mỗi họ tên là một dãy 30 ký tự. char HoTen[10][30]; I. Khai báo và truy xuất phần tử Lưu ý 1: Người ta thường trình bày mỗi phần tử của chiều thứ 1 trên một dòng. Nên N1 còn gọi là số dòng, N2 là số cột. Ví dụ 3: Biến diem là một bảng 5 dòng, 3 cột Biến HoTen một bảng 10 dòng, 30 cột Ví dụ 4: Để lưu ma trận số nguyên dạng sau: 4 5 7 1 2 1 8 4 4 6 1 4 Ta khai báo biến: int MaTran[3][4]; I. Khai báo và truy xuất phần tử Lưu ý 2: Các phần tử của biến mảng 2 chiều được cấp phát không gian nhớ liên tục theo thứ tự hàng. Ví dụ 5: Các phần tử của biến MaTran trong bộ nhớ như sau: 4 5 7 1 2 1 8 4 4 6 1 4 I. Khai báo và truy xuất phần tử 2. Truy xuất biến mảng 2 chiều: Phải truy xuất từng phần tử. Ý nghĩa: Truy xuất phần tử ở dòng i cột j của biến mảng 2 chiều TênBiến Trong đó: i, j là biểu thức nguyên. i là chỉ số chiều thứ nhất, hay chỉ số dòng. j là chỉ số chiều thứ hai, hay chỉ số cột. I. Khai báo và truy xuất phần tử cú pháp: TênBiến[i][j] Ví dụ 1: int T[2][3]; Biến T gồm các phần tử T[0][0], T[0][1], T[0][2] T[1][0], T[1][1], T[1][2] T[2][0], T[2][1], T[2][2] T[0][0] là một biến nguyên int. T[0] là một mảng nguyên 3 phần tử. I. Khai báo và truy xuất phần tử Ví dụ 2: Nhập dữ liệu cho biến mảng 2c int T[10][20]; for(int i=0; i>a[i][j]; } I. Khai báo và truy xuất phần tử Lưu ý: Quản lý số dòng cột thực tế nhập bằng 2 biến nguyên m, n. Ví dụ 2: const SIZE1=50; const SIZE2=50; int T[SIZE1][SIZE2]; int m, n; cout> m; cout>n; for(int i=0; i>a[i][j]; } I. Khai báo và truy xuất phần tử 3. Khai báo có khởi động trị: Ví dụ : int T[3][2]={ {1,2}, {3,4}, {5,6} }; Kết quả mảng T được mang giá trị 1 2 3 4 5 6 I. Khai báo và truy xuất phần tử 1. Cách viết thông số hình thức: Thông số hình thức kiểu mảng 2 chiều không cần chỉ ra số dòng, nhưng phải chỉ định số cột. Khi gọi hàm, thông số thực phải là mảng 2 chiều có số cột khai báo giống như thông số hình thức. Ví dụ: hàm xuất mảng 2 chiều. II. Thông số kiểu mảng 2 chiều: const N=50; void xuatM2C(int T[][N],int m, int n) { for(int i=0; i> m; cout>n; for(int i=0; i>a[i][j]; } } Là các thuật tóan trên mảng 1 chiều được áp dụng trên một số phần tử giới hạn hoặc trên tòan mảng 2C. Ví dụ: - Tổng cột thứ 5 của mảng. - Sắp xếp tăng các phần tử trên đường chéo chính. - ... Vì vậy ta xét thao tác cơ bản trên M2C là các cách duyệt M2C: 1. Duyệt dòng 2. Duyệt cột 3. Duyệt đường chéo chính 4. Duyệt đường chéo phụ 5. Duyệt nửa tam giác trên đường chéo phụ. III. Một số thuật tóan trên M2C: III. Một số thuật tóan trên M2C: Dòng L=1 Xét mảng T[5][5] 1. Duyệt dòng: Các phần tử trên dòng thứ L là các phần tử có chỉ số thứ nhất là L Ví dụ: int T[4][5]={{1,2,3,4,5},{6,7,8,9,10}}; int L; cout>L; for(int i=0; i>K; for(int i=0; i=n-1 i=j Tóm lại Ví dụ áp dụng các cách duyệt: Sắp xếp các phần tử trên đường chéo phụ. void swap(int&a, int&b) { int t=a; a=b; b=t; } void sapxep(int m[N][N], int n) { //i, j la chỉ số thứ 1 của phần tử for(int i=0; im[j][n-j-1]) swap(m[i][n-i-1], m[j][n-j-1]); }