Lập trình cơ bản - Sử dụng mảng

SỬ DỤNG MẢNG LÊ ĐỨC LONG-NGÔ QUỐC VIỆT 2011 NỘI DUNG 1. Khai báo và sử dụng mảng một hay hai chiều  Khai báo mảng một chiều  Thao tác trên dữ liệu mảng một chiều  Khai báo mảng hai chiều  Thao tác trên dữ liệu mảng hai chiều  Dùng mảng làm tham số cho hàm 2. Khai báo và sử dụng chuỗi.  Khai báo chuỗi ký tự  Nhập xuất chuỗi trên bàn phím và màn hình  Một số hàm dùng với chuỗi 3. Bài tập Ngô Quốc Việt-Lập trình cơ bản 2 MẢNG  100 quả trứng, mỗi quả trứng có vai trò, tính chất “gần như nhau” lưu trữ 100 biến ?  1000 số nguyên trong dãy số nguyên  lưu 1000 biến nguyên?  Tính trung bình cộng của một dãy n số (không phải tăng từ 1 đến n) cần lưu n giá trị dùng n biến?  Ví dụ: tính trung bình 10 giá trị  Nhập 10 giá trị từ bàn phím, lưu vô n1, n2, n3, n4, n5, n6, n7, n8, n9, n10.  Tính ntb = (n1, n2, n3, n4, n5, n6, n7, n8, n9, n10) /10.0;  Khi n lớn thì sao? Không thể làm như vậy. Ngô Quốc Việt-Lập trình cơ bản 3 MẢNG Mảng được dùng để lưu trữ nhiều giá trị cùng kiểu và tham gia vào một vấn đề cụ thể. Mảng là một biến được cấp phát bộ nhớ liên tục và bao gồm nhiều biến thành phần.  Các thành phần của mảng là tập hợp các biến có cùng kiểu dữ liệu và cùng tên.  Để truy xuất thành phần, dùng chỉ số mảng. Ngô Quốc Việt-Lập trình cơ bản 4 Khai báo mảng một chiều [ ] ;  Ví dụ khai báo mảng integer 50 phần tử int iArr[5]; //kiểu integer, tên iArr, số phần tử: 5 Các phần tử của mảng iArr là iArr[0], iArr[1], ..iArr[4]: là các tên biến sử dụng được.  Ví dụ khai báo mảng float 50 phần tử float fArr[20]; //kiểu float, tên fArr, số lượng: 20 Ngô Quốc Việt-Lập trình cơ bản 5 iArr[0] iArr[1] iArr[2] iArr[3] iArr[4] Chỉ số phần tử mảng Sử dụng mảng một chiều  Chương trình khai báo, nhập và in ra mảng 10 phần tử integer #include int main() { int iMyArr[10]; cout << “Hay nhap 10 phan tu ” << endl; for (int i = 0; i < 10; i ++) { cout << “Nhap phan tu thu: “ << i; cin >> iMyArr[i]; cout << endl; } cout << “Cac phan tu moi nhap tinh tu cuoi la:” << endl; for (int i = 9; i >= 0; i --) { cout << iMyArr[i] << “’ ”; } } Ngô Quốc Việt-Lập trình cơ bản 6 Sử dụng mảng một chiều  Truy xuất các phần tử mảng thông qua chỉ số mảng. int iArr[5];  Chỉ số mảng bắt đầu từ zero.  Phần tử cuối cùng có chỉ số n-1, với n là kích thướcmảng Ngô Quốc Việt-Lập trình cơ bản 7 0 1 2 3 4 iArr[1]iArr[0] iArr[2] Sử dụng mảng một chiều Ngô Quốc Việt-Lập trình cơ bản 8 Sử dụng mảng một chiều Ngô Quốc Việt-Lập trình cơ bản 9  Khai báo tường minh và gán giá trị  Khai báo không tường minh Trường hợp với chuỗi - string Ngô Quốc Việt-Lập trình cơ bản 10 Processing an array – NNLT C Ngô Quốc Việt-Lập trình cơ bản 11 Lowercase to Uppercase Text Conversion /* read in a line of lowercase text to uppercase */ #include #include #define SIZE 80 void main ( ) { char letter[SIZE]; int count ; /* read in the line */ for (count = 0; count < SIZE; ++count) letter[count] = getchar(); /* display the line in uppercase */ for (count = 0; count < SIZE; ++count) putchar(toupper(letter[count])); } Sử dụng mảng một chiều Ngô Quốc Việt-Lập trình cơ bản 12 Khởi tạo mảng lúc khai báo  Mục đích: gán giá trị cho phần tử mảng lúc khai báo.  Khởi tạo khi biết rõ mảng cần giá trị nào.  Ví dụ, khai báo mảng chứa các loại tiền có mệnh giá 500, 1000, 2000, 5000, 10000. int iMoneyArr[5] = {500, 1000, 2000, 5000, 10000}’;  Ví dụ, khai báo mảng chứa các giá vé, không cần kích thước. Kích thước mảng xác định bởi số phần tử khởi tạo int iMoneyArr[] = {40000, 50000, 60000, 240000}’; Ngô Quốc Việt-Lập trình cơ bản 13 Ví dụ về mảng  Trả về giá trị lớn nhất trong mảng các số thực #include int main() { const int MAXPHANTU = 20; float fMyArr[MAXPHANTU]; cout << “Hay nhap “ << MAXPHANTU << “ phan tu ” << endl; for (int i = 0; i < MAXPHANTU; i ++) { cout << “Nhap phan tu thu: “ << i; cin >> fMyArr[i]; cout << endl; } float fMax = iMyArr[0]; for (int i = 1; i < MAXPHANTU; i ++) { if(fMax < fMyArr [i]) fMax = fMyArr [i]; } cout << “Gia tri lon nhat la: “ << fMax << endl; } Ngô Quốc Việt-Lập trình cơ bản 14 “Xoá” một phần tử ra khỏi mảng  “Xoá”: thật ra là “dồn” các phần tử phía sau phần tử cần xóa lên trên một vị trí.  “Xoá” một phần tử mảng không làm thay đổi kích thước mảng  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 các phần tử về phía trước cho đến khi kết thúc mảng Ngô Quốc Việt-Lập trình cơ bản 15 “Xoá” một phần tử ra khỏi mảng  Ví dụ “xoá” một phần tử tại vị trí cho trước trong mảng void XoaPhanTuMatTai(int iArr[], int &n, int vitri) { if(vitri >= n || vitri < 0) return; for(int i = vitri; i < n-1; i ++) iArr[i] = iArr[i+1]; n = n-1; } Ngô Quốc Việt-Lập trình cơ bản 16 “Thêm” một phần tử vào mảng  “Thêm” một giá trị vào mảng: dời các phần tử về bên phải mảng, chừa ra một chỗ trống để đặt giá trị mới vào  “Thêm” một phần tử mảng không làm thay đổi kích thước mảng void ChenX (int a[], int &n, int X, int vitri) { for (int i = n; i >vitri ; i--) a[i] = a[i-1] ; a[vitri] = X; n++; } Ngô Quốc Việt-Lập trình cơ bản 17 Bài tập luyện tập 1. Viết chương trình nhập vào N ( <= 50)số nguyên, tính trung bình cộng N số nguyên đó 2. Nhập vào nhập vào N ( <= 50) số nguyên chứa trong mảng. Nhập vào phần tử x. Tìm vị trí xuất hiện của x trong mảng đã nhập. Nếu x không tồn tại trong mảng, xuất ra -1. 3. Sửa lại bài 2 với yêu cầu, viết hàm tìm vị trí phần tử có giá trị x xuất hiện cuối cùng trong mảng. 4. Viết hàm in vị trí các phần tử nguyên tố trong mảng các số nguyên. Ngô Quốc Việt-Lập trình cơ bản 18 Bài tập luyện tập 5. Viết hàm tính tổng các phần tử nằm ở vị trí lẻ trong mảng các số nguyên. 6. Viết hàm tính tổng các phần tử nằm ở vị trí nguyên tố trong mảng 7. Viết chương trình nhập M giá trị nguyên vào mảng. Thực hiện xoá ra khỏi mảng các giá trị âm. 8. Viết chương trình xóa phần tử nhỏ nhất ra khỏi mảng. 9. Viết hàm chèn phần tử có giá trị X vào phía sau phần tử có giá trị lớn nhất trong mảng Ngô Quốc Việt-Lập trình cơ bản 19 Sử dụng tham số mảng một chiều  Cho phép chuyển mảng một chiều giữa các hàm  Ví dụ về hàm có tham số dạng mảng //Trả về giá rịmax trongmảng //n: số phần tử trongmảng //iArr:mảng input int KiemtraMax(int iArr[], int n) { int iMax = iArr[0]; for(int i = 1; i < n; i ++) if(iMax < iArr[i]) iMax = iArr[i]; return iMax; } Ngô Quốc Việt-Lập trình cơ bản 20 Sử dụng tham số mảng một chiều int main() { int iArr[10]; cout << “Nhap 10 gia tri chomang” << endl for(int i = 0; i < 10; i ++) { cout < “Nhap gia tri cho phan tu thu: “ << i; cin >> iArr[i]; //nhap gia tri cho phan tu mang thu i coutn << endl; } int iMax = KiemtraMax(iArr, 10); cout << “Gia tri lon nhat la: “ << iMax; return 0; } Ngô Quốc Việt-Lập trình cơ bản 21 Sử dụng tham số mảng một chiều Ngô Quốc Việt-Lập trình cơ bản 22 An entire array can be passed to a function as an argument. To pass an array to a function, the array name must appear by itself, without brackets or subscripts, as an actual argument within the function call.  Lời gọi hàm – sử dụng tên của mảng Sử dụng tham số mảng một chiều Ngô Quốc Việt-Lập trình cơ bản 23 Kết luận: Mảng được truyền vào trong hàm theo dạng tham biến Sử dụng tham số mảng một chiều Ngô Quốc Việt-Lập trình cơ bản 24 Lưu ý: cách sử dụng biến toàn cục và biến địa phương Bài toán tìm phần tử Ngô Quốc Việt-Lập trình cơ bản 25 YÊU CẦU: Tìm phần tử đầu tiên trong (A,n) thoả mãn một điều kiện nào đó DẠNG BÀI TOÁN: flag = -1; i = 0; // flag được gọi là phần tử lính canh Lặp trong khi (i < n) và (flag = -1) làm Nếu (A[i] thoả điều kiện) thì flag = i; Cuối nếu i ++; Cuối lặp Ví dụ: Nhập vào số nguyên dương n ( 1  n  20) và một mảng số nguyên A gồm n phần tử. Tìm và in ra phần tử âm đầu tiên trong mảng tận cùng bằng 6 Gợi ý: int Am_6(int A[ ], int n); // kết thúc vòng lặp nếu j = -1 thì tìm không có – ngược lại thì a[j] chính là phần tử cần tìm ở vị trí j Bài toán tìm phần tử Ngô Quốc Việt-Lập trình cơ bản 26 YÊU CẦU: Tìm tất cả các phần tử trong (A,n) thoả mãn một điều kiện nào đó DẠNG BÀI TOÁN: //Sử dụng một mảng phụ (B,m) để lưu phần tử tìm được //Duyệt mảng (B,m) để xuất tất cả các phần tử tìm được m = 0; Lặp tuần tự i = 0, 1, 2, n-1 làm Nếu (A[i] thoả điều kiện) thì B[m] = A[i]; m = m + 1; Cuối nếu Cuối lặp Hoặc, trường hợp xuất thẳng ra màn hình: Lặp tuần tự i = 0, 1, 2, n-1 làm Nếu (A[i] thoả điều kiện) thì In A[i] ra màn hình Cuối nếu Cuối lặp Bài toán tìm phần tử lớn/nho ̉ nhất Ngô Quốc Việt-Lập trình cơ bản 27 YÊU CẦU: Tìm phần tử lớn nhất (max) hoặc nhỏ nhất (min) trong (A,n) Điều kiện cần: S là tập hợp có thứ tự toàn phần – nghĩa là, mọi cặp phần tử của S đều có thể so sánh được với nhau DẠNG BÀI TOÁN: // Tìm phần tử lớn nhất + Chọn phần tử x0  S, gán max = x0 + Lặp cho đến khi chọn hết các phần tử của S Với mỗi phần tử kế tiếp x  S, nếu max < x thì gán max = x Cuối lặp. Ví dụ: Nhập vào số nguyên dương n ( 1  n  20) và một mảng số thực A gồm n phần tử. Tìm phần tử nhỏ nhất trong mảng. Gợi ý: float Tim_min(float A[ ], int n); // Tìm phần tử nhỏ nhất + Chọn phần tử x0  S, gán min = x0 + Lặp cho đến khi chọn hết các phần tử của S Với mỗi phần tử kế tiếp x  S, nếu min > x thì gán min = x Cuối lặp. Bài toán sắp xếp Ngô Quốc Việt-Lập trình cơ bản 28 YÊU CẦU: Sắp xếp các phần tử trong (A,n) thoả mãn một điều kiện nào đó DẠNG BÀI TOÁN: // Sắp xếp phần tử tăng dần Lặp tuần tự i = 0, 1, 2, n-2 làm Lặp tuần tự j = 1, 2, 3, n-1 làm Nếu A[i] > A[j] thì Tmp = A[i]; // hoán vị 2 phần tử thứ i và j A[i] = A[j]; A[j] = Tmp; Cuối nếu Cuối lặp j Cuối lặp i Ví dụ: Nhập vào số nguyên dương n ( 1  n  20) và một mảng số nguyên A gồm n phần tử. Sắp xếp các phần tử trong mảng A theo thứ tự tăng dần Gợi ý: void Sapxep(int A[ ], int n); // Có nhiều thuật toán sắp xếp như: Selection, Insertion, Buble, Quick, Merge, ... Bài toán sắp xếp Ngô Quốc Việt-Lập trình cơ bản 29 YÊU CẦU: Sắp xếp các phần tử trong (A,n) thoả mãn một điều kiện nào đó DẠNG BÀI TOÁN: // Sắp xếp các phần tử thoả điều kiện. // Giữ nguyên vị trí các phần tử khác Lặp tuần tự i = 0, 1, 2, n-2 làm Lặp tuần tự j = i+1, i+2, i+3, n-1 làm Nếu (A[i], A[j] thoả điều kiện) thì Nếu A[i] > A[j] thì Hoán vị A[i], A[j]; Cuối nếu Cuối nếu Cuối lặp j Cuối lặp i Ví dụ: Nhập vào số nguyên dương n ( 1  n  20) và một mảng số nguyên A gồm n phần tử. Sắp xếp các phần tử không âm trong mảng A theo thứ tự tăng dần Bài toán tìm cặp quan hệ Ngô Quốc Việt-Lập trình cơ bản 30 YÊU CẦU: Tìm cặp phần tử trong (A,n) có quan hệ với nhau theo đkiện nào đó DẠNG BÀI TOÁN: //Chương trình chính Lặp tuần tự i = 0, 1, 2, n-2 làm Lặp tuần tự j = i+1, i+2, i+3, n-1 làm Nếu (Quan_he(A[i], A[j])) thì In cặp (A[i], A[j]); Cuối nếu Cuối lặp j Cuối lặp i Ví dụ: a) Nhập vào 10 số nguyên, xác định xem có cặp số nào trong các số đó có quan hệ chia hết hay không? In ra nếu có. b) Nhập vào 10 số nguyên, xác định xem có cặp số nào trong các số đó có hiệu của chúng bằng 5 hay không? In ra nếu có. // nếu qh = FALSE thì không có cặp quan hệ nào, ngược lại thì in ra //Chương trình con-xét quan hệ qh = FALSE; // qh được gọi là cờ hiệu Nếu (A[i], A[j] có quan hệ nhau) thì qh = TRUE; Cuối nếu return qh; Mảng hai chiều  Phát triển tự nhiên từ mảng một chiều.  Là mảng một chiều: trong đó mỗi phần tử lại là mảng một chiều. Ma trận MxN (M hàng N cột): sử dụng mảng hai chiều để quản lý.  Các phần tử trong mảng hai chiều được truy xuất bằng hai chỉ số Ngô Quốc Việt-Lập trình cơ bản 31 Ví dụ về mảng 2 chiều Ngô Quốc Việt-Lập trình cơ bản 32 x là mảng 2 chiều, có m dòng và n cột Ví dụ: float x[20][50]; char page[24][80]; int A[20][20]; Ví dụ về mảng 2 chiều Ngô Quốc Việt-Lập trình cơ bản 33 Khai báo mảng hai chiều [ ][ ];  Ví dụ khai báo mảng: int iArr[5][6]; //ma trận 5 hàng 6 cột. float fArr[10][7]//ma trận thực 10 hàng, mỗi hàng 7 cột  Khai báo mảng 2 chiều và khởi tạo giá trị int iArr[3][4] = { {1,3,5,4} , {5,1,3,2} , {2,3,4,5} }; float fArr[2][3] = {{3, 4, 7}, {4, 1, 8}}; Ngô Quốc Việt-Lập trình cơ bản 34 Sử dụng mảng hai chiều  Sử dụng hai chỉ số để truy xuất một phần tử mảng void Nhap (int a[][], int &d, int &c ) { printf (“\nNhap so dong: ”); scanf (“ %d”, &d ); printf (“\nNhap so cot: ”); scanf (“%d”, &c ); for ( int i = 0; i < d; i ++ ) for (int j = 0; j < c; j ++) { printf (“ a[%d][%d] = ”, i, j ); scanf (“%d”,&a[i][j]); } } Ngô Quốc Việt-Lập trình cơ bản 35 Truy xuất phần tử mảng  Đường chéo loại 1 (đường chéo chính và những đường song song với nó ) ma trận vuông  Đường chéo chính có tính chất: chỉ số cột = chỉ số dòng. Ví dụ: for ( i = i0, j = i0 ; i < n ; i ++, j ++ ) printf (“%4d”,A[i][j]);  Đường chéo loại 2 ma trận vuông (gồm đường chéo phụ và những đường song song với nó)  Đường chéo phụ có tính chất: chỉ số cột + chỉ số dòng = số dòng (hoặc số cột).  Ví dụ for ( i = io , j = jo ; i = 0 ; i ++ , j --) printf (“%4d”,A[i]][j]); Ngô Quốc Việt-Lập trình cơ bản 36 Minh hoạ nhập giá trị mảng 2 chiều #define MAX 100 typedef int [MAX][MAX] MATRAN; MATRAN a; void Nhap (MATRAN a, int &d, int &c ) { printf (“\nNhap so dong: ”); scanf (“ %d”, &d ); printf (“\nNhap so cot: ”); scanf (“%d”, &c ); for ( int i = 0; i < d; i ++ ) for (int j = 0; j < c; j ++) { printf (“ a[%d][%d] = ”, i, j ); scanf (“%d”, &a[i][j]); } } Ngô Quốc Việt-Lập trình cơ bản 37 Minh hoạ xuất giá trị mảng 2 chiều void Xuat (MATRAN a, int d, int c) { printf (“\nNoi dung ma tran:\n”); for (int i = 0; i < d; i++) { for (int j = 0; j < c; j++) printf (“ \t %d ”, a[i][j] ); printf (“\n”); } } Ngô Quốc Việt-Lập trình cơ bản 38 Minh hoạ kiểm tra tồn tại giá trị lẻ trong mảng 2 chiều int KiemTraLe (MATRAN a, int d, int c) { int flag = 0; //tra ve 1 neu co nguoc lai tra ve 0 for (int i = 0; i < d; i ++ ) for (int j = 0; j < c; j++) if ( a[i][j] % 2 != 0 && a[i][j] > 100 ) { flag = 1; break; } return flag; } Ngô Quốc Việt-Lập trình cơ bản 39 Tổng hai ma trận  Cho hai ma trận A(MxN) và B(MxN). Tính tổng của hai ma trận A, B và lưu vào ma trận C. #define M 100 #define N 50 typedef int [M][N] MATRAN; void SumMatrix(MATRAN a, MATRAN b, MATRAN c) { for (int i = 0; i < M; i ++ ) for (int j = 0; j < N; j++) C[i][ j] = A[i][j] + B[i][j]; return; } Ngô Quốc Việt-Lập trình cơ bản 40 Nhân hai ma trận  Cho hai ma trận A(KxM) và B(MxN). Tính tích của hai ma trận A, B và lưu vào ma trận C(KxN). #define K 100 #defineM 50 #defene N 40 typedef int [K][M] MATRANA; typedef int [M][N] MATRANB; typedef int [K][N] MATRANC; voidMultipleMatrix(MATRANA a, MATRANB b, MATRANC c) { for (int i = 0; i < K; i ++ ) for (int j = 0; j < N; j++) { c[i][j] = 0; for(k = 0; k < M; k ++) c[i][j] += a[i][k]*b[k][j]; } } Ngô Quốc Việt-Lập trình cơ bản 41 Bài tập luyện tập 1. Khai báo ma trận MxN (M, N là hằng số). Viết chương trình in ra những phần tử của mảng có số tận cùng là 7. 2. Viết chương trình in ra các phần tử nằm trên 2 đường chéo. 3. Viết chương trình tạo ma trận a các số nguyên gồm 9 dòng 14 cột. Trong đó a[i][j] = i*j; 4. Viết chương trình tính tổng các giá trị lớn nhất trên mỗi dòng (mỗi dòng chọn giá trị lớn nhất, sau đó cộng các giá trị này lại). Ngô Quốc Việt-Lập trình cơ bản 42 CÁM ƠN ĐÃ THEO DÕI TP.HCM - 2011