Bài giảng Lập trình cơ bản - Chương 6: Sử dụng mảng - Lê Đức Long

Nội dung text: Bài giảng Lập trình cơ bản - Chương 6: Sử dụng mảng - Lê Đức Long

1. SỬ DỤNG MẢNG LÊ ĐỨC LONG-NGÔ QUỐC VIỆT 2011
2. 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
3. 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
4. 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
5. 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[2] iArr[3] iArr[4] Chỉ số phần tử mảng 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
6. 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 > iMyArr[i]; cout = 0; i ) { cout << iMyArr[i] << “’ ”; } } Ngô Quốc Việt-Lập trình cơ bản 6
7. 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]; 0 1 2 3 4 iArr[0] iArr[1] iArr[2]  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ước mảng Ngô Quốc Việt-Lập trình cơ bản 7
8. Sử dụng mảng một chiều Ngô Quốc Việt-Lập trình cơ bản 8
9. Sử dụng mảng một chiều Khai báo tường minh và gán giá trị Khai báo không tường minh Ngô Quốc Việt-Lập trình cơ bản 9
10. Trường hợp với chuỗi - string Ngô Quốc Việt-Lập trình cơ bản 10
11. Processing an array – NNLT C 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])); } Ngô Quốc Việt-Lập trình cơ bản 11
12. Sử dụng mảng một chiều Ngô Quốc Việt-Lập trình cơ bản 12
13. 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
14. 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 > 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
15. “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
16. “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
17. “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
18. 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
19. 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
20. 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 trong mảng //n: số phần tử trong mả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
21. Sử dụng tham số mảng một chiều int main() { int iArr[10]; cout > 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
22. Sử dụng tham số mảng một chiều 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 Ngô Quốc Việt-Lập trình cơ bản 22
23. Sử dụng tham số mảng một chiều Kết luận: Mảng được truyền vào trong hàm theo dạng tham biến Ngô Quốc Việt-Lập trình cơ bản 23
24. Sử dụng tham số mảng một chiều Lưu ý: cách sử dụng biến toàn cục vàbi ến địa phương Ngô Quốc Việt-Lập trình cơ bản 24
25. Bài toán tìm phần tử 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 // 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 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); Ngô Quốc Việt-Lập trình cơ bản 25
26. Bài toán tìm phần tử 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 Ngô Quốc Việt-Lập trình cơ bản 26
27. Bài toán tìm phần tử lớn/nhỏ nhất 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 // Tìm phần tử nhỏ nhất + Chọn phần tử x0 S, gán max = x0 + 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 + 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 Với mỗi phần tử kế tiếp x S, nếu max x thì gán min = x Cuối lặp. 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); Ngô Quốc Việt-Lập trình cơ bản 27
28. Bài toán sắp xếp 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 // Có nhiều thuật toán sắp xếp như: Selection, Insertion, Buble, Quick, Merge, 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); Ngô Quốc Việt-Lập trình cơ bản 28
29. Bài toán sắp xếp 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 Ngô Quốc Việt-Lập trình cơ bản 29
30. Bài toán tìm cặp quan hệ 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 //Chương trình con-xét quan hệ Lặp tuần tự j = i+1, i+2, i+3, n-1 làm qh = FALSE; // qh được gọi là cờ hiệu Nếu (Quan_he(A[i], A[j])) thì Nếu (A[i], A[j] cóquan hệ nhau) thì In cặp (A[i], A[j]); qh = TRUE; Cuối nếu Cuối nếu Cuối lặp j return qh; Cuối lặp i // nếu qh = FALSE thì không có cặp quan hệ nào, ngược lại thì in ra 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ó. Ngô Quốc Việt-Lập trình cơ bản 30
31. 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
32. Ví dụ về mảng 2 chiều Ví dụ: float x[20][50]; x là mảng 2 chiều, cóm dòng và n cột char page[24][80]; int A[20][20]; Ngô Quốc Việt-Lập trình cơ bản 32
33. Ví dụ về mảng 2 chiều Ngô Quốc Việt-Lập trình cơ bản 33
34. 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
35. 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
36. 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 = 0 ; i ++ , j ) printf (“%4d”,A[i]][j]); Ngô Quốc Việt-Lập trình cơ bản 36
37. 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
38. 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
39. 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 100 ) { flag = 1; break; } return flag; } Ngô Quốc Việt-Lập trình cơ bản 39
40. 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
41. 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 #define M 50 #defene N 40 typedef int [K][M] MATRANA; typedef int [M][N] MATRANB; typedef int [K][N] MATRANC; void MultipleMatrix(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
42. 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
43. CÁM ƠN ĐÃ THEO DÕI TP.HCM - 2011