›
›

Bài giảng Cơ sở lập trình 1 - Chương 5: Kiểu dữ liệu mảng

pptx 56 trang phuongnguyen 2900
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cơ sở lập trình 1 - Chương 5: Kiểu dữ liệu mảng", để 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:

  • pptxbai_giang_co_so_lap_trinh_1_chuong_5_kieu_du_lieu_mang.pptx

Nội dung text: Bài giảng Cơ sở lập trình 1 - Chương 5: Kiểu dữ liệu mảng

  1. Chương 5 KIỂU DỮ LIỆU MẢNG Khoa Hệ thống thông tin quản lý Hà Nội – 2013
  2. Nội dung 1 Mảng 1 chiều 2 Mảng nhiều chiều 23/05/2021 Chương 5- Kiểu dữ liệu mảng 2/56
  3. 5.1 Mảng một chiều 1 Khái niệm 2 Khai báo 3 Truy xuất dữ liệu kiểu mảng 4 Một số bài toán trên mảng 1 chiều 23/05/2021 Chương 5- Kiểu dữ liệu mảng 3/56
  4. Đặt vấn đề o Ví dụ n Chương trình cần lưu trữ 3 số nguyên? => Khai báo 3 biến int a1, a2, a3; n Chương trình cần lưu trữ 100 số nguyên? => Khai báo 100 biến kiểu số nguyên! n Người dùng muốn nhập n số nguyên? => Không thực hiện được! o Giải pháp n Kiểu dữ liệu mới cho phép lưu trữ một dãy các số nguyên và dễ dàng truy xuất. 23/05/2021 Chương 5- Kiểu dữ liệu mảng 4/56
  5. 5.1.1 Khái niệm o Khái niệm n Là một kiểu dữ liệu có cấu trúc do người lập trình định nghĩa. n Biểu diễn một dãy các biến có cùng kiểu. Ví dụ: dãy các số nguyên, dãy các ký tự n Kích thước được xác định ngay khi khai báo và không bao giờ thay đổi. n C luôn chỉ định một khối nhớ liên tục cho một biến kiểu mảng. 23/05/2021 Chương 5- Kiểu dữ liệu mảng 5/56
  6. 5.1.2 Khai báo o Khai báo tường minh [ ]; [ ][ ] [ ]; n , , : số lượng phần tử của mỗi chiều. o Lưu ý n Phải xác định cụ thể (hằng) khi khai báo. n Mảng nhiều chiều: = N1*N2* *Nn n Bộ nhớ sử dụng = *sizeof( ) n Một dãy liên tục có chỉ số từ 0 đến -1 23/05/2021 Chương 5- Kiểu dữ liệu mảng 6/56
  7. Khai báo tường minh (tt) o Ví dụ int Mang1Chieu[10]; 0 1 2 3 4 5 6 7 8 9 Mang1Chieu int Mang2Chieu[3][4]; 0 1 2 3 4 5 6 7 8 9 10 11 Mang2Chieu 0 1 2 23/05/2021 Chương 5- Kiểu dữ liệu mảng 7/56
  8. Khai báo không tường minh o Cú pháp n Không tường minh (thông qua khai báo kiểu) typedef [ ]; typedef [ ] [ ]; ; o Ví dụ typedef int Mang1Chieu[10]; typedef int Mang2Chieu[3][4]; Mang1Chieu m1, m2, m3; Mang2Chieu m4, m5; 23/05/2021 Chương 5- Kiểu dữ liệu mảng 8/56
  9. Số phần tử của mảng o Phải xác định cụ thể số phần tử ngay lúc khai báo, không được sử dụng biến hoặc hằng thường int n1 = 10; int a[n1]; const int n2 = 20; int b[n2]; o Nên sử dụng chỉ thị tiền xử lý #define để định nghĩa số phần tử mảng #define n1 10 #define n2 20 int a[n1]; //  int a[10]; int b[n1][n2]; //  int b[10][20]; 23/05/2021 Chương 5- Kiểu dữ liệu mảng 9/56
  10. Khởi tạo giá trị cho mảng lúc khai báo o Gồm các cách sau n Khởi tạo giá trị cho mọi phần tử của mảng int a[4] = {2912, 1706, 1506, 1904}; 0 1 2 3 a 2912 1706 1506 1904 n Khởi tạo giá trị cho một số phần tử đầu mảng int a[4] = {2912, 1706}; 0 1 2 3 a 2912 1706 23/05/2021 Chương 5- Kiểu dữ liệu mảng 10/56
  11. Khởi tạo giá trị cho mảng lúc khai báo o Gồm các cách sau n Khởi tạo giá trị 0 cho mọi phần tử của mảng int a[4] = {0}; 0 1 2 3 a 0 0 0 0 n Tự động xác định số lượng phần tử int a[] = {2912, 1706, 1506, 1904}; 0 1 2 3 a 2912 1706 1506 1904 23/05/2021 Chương 5- Kiểu dữ liệu mảng 11/56
  12. 5.1.3 Truy xuất đến một phần tử o Thông qua chỉ số [ ] o Ví dụ 0 1 2 3 n Cho mảng như sau int a[4]; n Các truy xuất o Hợp lệ: a[0], a[1], a[2], a[3] o Không hợp lệ: a[-1], a[4], a[5], => Cho kết thường không như mong muốn! 23/05/2021 Chương 5- Kiểu dữ liệu mảng 12/56
  13. Gán dữ liệu kiểu mảng o 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ử tương ứng = ; //sai [ ] = ; o Ví dụ #define MAX 3 typedef int MangSo[MAX]; MangSo a = {1, 2, 3}, b; b = a;// Sai for (int i = 0; i < 3; i++) b[i] = a[i]; 23/05/2021 Chương 5- Kiểu dữ liệu mảng 13/56
  14. Một số lỗi thường gặp o Khai báo không chỉ rõ số lượng phần tử n int a[]; int a[100]; o Số lượng phần tử liên quan đến biến hoặc hằng n int n1 = 10; int a[n1]; o Khởi tạo cách biệt với khai báo n int a[4]; a = {2912, 1706, 1506, 1904}; int a[4] = {2912, 1706, 1506, 1904}; o Chỉ số mảng không hợp lệ n int a[4]; n a[-1] = 1; a[10] = 0; 23/05/2021 Chương 5- Kiểu dữ liệu mảng 14/56
  15. 5.1.4 Một số bài toán trên mảng 1 chiều o Nhập mảng o Xuất mảng o Tìm kiếm một phần tử trong mảng o Tìm giá trị nhỏ nhất/lớn nhất của mảng o Sắp xếp mảng giảm dần/tăng dần o Thêm/Xóa/Sửa một phần tử vào mảng 23/05/2021 Chương 5- Kiểu dữ liệu mảng 15/56
  16. Nhập mảng o Đoạn chương trình nhập vào từ bàn phím một mảng 1 chiều a gồm n phần tử #define MAXN 100 int a[MAXN]; printf(“Nhap so luong phan tu n: ”); scanf(“%d”, &n); for (int i = 0; i < n; i++) { printf(“Nhap phan tu thu %d: ”, i); scanf(“%d”, &a[i]); } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 16/56
  17. Xuất mảng o Đoạn chương trình in ra màn hình một mảng 1 chiều a gồm n phần tử printf(“Noi dung cua mang la: ”); for (int i = 0; i < n; i++) printf(“%d ”, a[i]); printf(“\n”); /*Đưa con trỏ màn hình xuống dòng tiếp theo */ 23/05/2021 Chương 5- Kiểu dữ liệu mảng 17/56
  18. Hàm có mảng là tham số o Khai báo n Tham số kiểu mảng trong khai báo hàm giống như khai báo biến mảng void SapXepTang(int a[100]); n 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 o Có thể bỏ số lượng phần tử hoặc sử dụng con trỏ. o Mảng có thể thay đổi nội dung sau khi thực hiện hàm. void SapXepTang(int a[]); void SapXepTang(int *a); n Số lượng phần tử thực sự truyền qua biến khác void SapXepTang(int a[100], int n); void SapXepTang(int a[], int n); void SapXepTang(int *a, int n); 23/05/2021 Chương 5- Kiểu dữ liệu mảng 18/56
  19. Hàm nhập mảng void NhapMang(int a[], int &n) { printf(“Nhap so luong phan tu n: ”); scanf(“%d”, &n); for (int i = 0; i < n; i++) { printf(“Nhap phan tu thu %d: ”, i); scanf(“%d”, &a[i]); } } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 19/56
  20. Hàm xuất mảng void XuatMang(int a[], int n) { printf(“Noi dung cua mang la: ”); for (int i = 0; i < n; i++) printf(“%d ”, a[i]); printf(“\n”); } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 20/56
  21. Truyền tham số mảng cho hàm (sử dụng) o Lời gọi hàm void NhapMang(int a[], int &n); void XuatMang(int a[], int n); int main() { int a[100], n; NhapMang(a, n); XuatMang(a, n); } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 21/56
  22. Tìm kiếm một phần tử trong mảng o Yêu cầu n Tìm xem phần tử x có nằm trong mảng a kích thước n hay không? Nếu có thì nó nằm ở vị trí đầu tiên nào. o Ý tưởng (tìm kiếm tuần tự) n Xét từng phần của mảng a. Nếu phần tử đang xét bằng x thì trả về vị trí đó. Nếu không tìm được thì trả về -1. x vị trí = 1 0 1 2 n - 1 MAX - 1 a x b x 23/05/2021 Chương 5- Kiểu dữ liệu mảng 22/56
  23. Hàm tìm kiếm int TimKiem(int a[], int n, int x) { for (int vt = 0; vt < n; vt++) if (a[vt] == x) return vt; return -1; } o Bài tập: n Viết lại hàm tìm kiếm sử dụng câu lệnh while n Cài đặt thuật toán tìm kiếm nhị phân 23/05/2021 Chương 5- Kiểu dữ liệu mảng 23/56
  24. Tìm giá trị lớn nhất của mảng o Yêu cầu n Cho trước mảng a có n phần tử. Tìm giá trị lớn nhất trong a o Ý tưởng n Giả sử giá trị max hiện tại là giá trị phần tử đầu tiên a[0] n Với mọi i từ 1 đến n-1, nếu a[i] > max thì max = a[i] max 78? 0 1 2 n – 1 MAX - 1 7 2 8 8 23/05/2021 Chương 5- Kiểu dữ liệu mảng 24/56
  25. Hàm tìm giá trị lớn nhất của mảng int TimMax(int a[], int n) { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 25/56
  26. Sắp xếp mảng theo thứ tự tăng dần o Yêu cầu n Cho mảng a kích thước n. Sắp xếp mảng a theo thứ tự tăng dần. o Ý tưởng n Với mỗi phần từ a[i], (i=0 n-1), tìm xem có phần tử a[j], (j=i+1 n) nào đó mà a[i]>a[j] hay không? Nếu có thì đổi chỗ a[i] và a[j]. 23/05/2021 Chương 5- Kiểu dữ liệu mảng 26/56
  27. Hàm sắp xếp mảng theo thứ tự tăng dần void SapXepTang(int a[], int n) { int i, j; int tmp; for (i=0;i a[j]) { tmp=a[i]; a[i]=a[j]; a[j]=tmp; } } } } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 27/56
  28. Thêm một phần tử vào mảng o Yêu cầu n Thêm phần tử x vào mảng a kích thước n tại vị trí vt. o Ý tưởng n “Đẩy” các phần tử bắt đầu tại vị trí vt sang phải 1 vị trí. n Đưa x vào vị trí vt trong mảng. n Tăng n lên 1 đơn vị. 23/05/2021 Chương 5- Kiểu dữ liệu mảng 28/56
  29. Hàm thêm một phần tử vào mảng void Them(int a[], int &n, int vt, int x) { if (vt >= 0 && vt vt; i ) a[i] = a[i - 1]; a[vt] = x; n++; } } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 29/56
  30. Xóa một phần tử trong mảng o Yêu cầu n Xóa một phần tử trong mảng a kích thước n tại vị trí vt o Ý tưởng n “Kéo” các phần tử bên phải vị trí vt sang trái 1 vị trí. n Giảm n xuống 1 đơn vị. 23/05/2021 Chương 5- Kiểu dữ liệu mảng 30/56
  31. Hàm xóa một phần tử trong mảng void Xoa(int a[], int &n, int vt) { if (vt >= 0 && vt < n) { for (int i = vt; i < n – 1; i++) a[i] = a[i + 1]; n ; } } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 31/56
  32. Bài tập thực hành 1. Các thao tác nhập xuất a. Nhập mảng gồm n số nguyên từ bàn phím b. Xuất mảng vừa nhập ra màn hình 2. Các thao tác kiểm tra Nhập vào một mảng gồm n số nguyên a. Mảng vừa nhập có phải là mảng toàn số chẵn (số lẻ) hay không? b. Mảng có phải là mảng toàn số nguyên tố? Số chính phương? c. Mảng có phải là mảng tăng dần hay giảm dần hay không? 23/05/2021 Chương 5- Kiểu dữ liệu mảng 32/56
  33. Bài tập thực hành 3. Các thao tác tính toán Nhập vào mảng gồm n số nguyên, và 2 số m và k a. Mảng có bao nhiêu số chia hết cho m nhưng không chia hết cho k? b. Tổng các số nguyên tố, chính phương có trong mảng? 4. Các thao tác tìm kiếm Nhập vào mảng gồm n số nguyên và số nguyên x a. Tìm vị trí cuối cùng của phần tử x trong mảng b. Tìm vị trí số nguyên tố đầu tiên trong mảng nếu có c. Tìm số nhỏ nhất trong mảng d. Tìm số dương nhỏ nhất, số âm lớn nhất 23/05/2021 Chương 5- Kiểu dữ liệu mảng 33/56
  34. Bài tập thực hành 5. Các thao tác xử lý Nhập mảng a gồm n số nguyên a. Xây dựng mảng b gồm các số nguyên tố có trong mảng a b. Xây dựng mảng b (chứa các số nguyên dương) và mảng c (chứa các số còn lại) c. Sắp xếp mảng theo chiều giảm dần d. Sắp xếp mảng sao cho các số dương đứng đầu mảng giảm dần, kế đến là các số âm tăng dần, cuối cùng là các số 0. 23/05/2021 Chương 5- Kiểu dữ liệu mảng 34/56
  35. Bài tập thực hành 6. Các thao tác thêm/xóa/sửa a. Sửa các số nguyên tố có trong mảng thành số 0, tất cả các số chính phương thành số -1 b. Chèn số 0 đằng sau mỗi số nguyên tố trong mảng, chèn số -1 phía trước mỗi số chính phương trong mảng. c. Xóa tất cả số nguyên tố trong mảng 23/05/2021 Chương 5- Kiểu dữ liệu mảng 35/56
  36. 5.2 Mảng nhiều chiều 1 Khái niệm 2 Khai báo 3 Truy xuất dữ liệu kiểu mảng 4 Một số bài toán trên mảng nhiều chiều 23/05/2021 Chương 5- Kiểu dữ liệu mảng 36/56
  37. 5.2.1 Khái niệm o Ma trận 0 1 n-1 0 n-1 0 0 Am,n An m-1 n-1 23/05/2021 Chương 5- Kiểu dữ liệu mảng 37/56
  38. Ma trận vuông 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 23/05/2021 Chương 5- Kiểu dữ liệu mảng 38/56
  39. 5.2.2 Khai báo Khai báo mảng 2 chiều o Tường minh [ ][ ]; o Không tường minh (thông qua kiểu) typedef [ ][ ]; ; , ; n N1, N2: số lượng phần tử mỗi chiều Chú ý: Ví dụ khai báo mảng 3 chiều: int m[3][5][8] 23/05/2021 Chương 5- Kiểu dữ liệu mảng 39/56
  40. Khai báo mảng 2 chiều (tt) o Ví dụ n Tường minh int a[10][20], b[10][20]; int c[5][10]; int d[10][20]; n 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; 23/05/2021 Chương 5- Kiểu dữ liệu mảng 40/56
  41. Khởi tạo giá trị cho mảng nhiều chiều o Tương tự như khởi tạo giá trị ban đầu cho mảng 1 chiều o Ví dụ: n int x[3][2]={{1,2},{3,4},{5,6}}; n int y[3][2]={1,2,3,4,5,6}; n int z[5][4]={0} 23/05/2021 Chương 5- Kiểu dữ liệu mảng 41/56
  42. 5.2.3 Truy xuất đến một phần tử o Thông qua chỉ số [ ][ ] o Ví dụ 0 1 2 3 n Cho mảng 2 chiều như sau: 0 1 int a[3][4]; 2 n Các truy xuất o Hợp lệ: a[0][0], a[0][1], , a[2][2], a[2][3] o Không hợp lệ: a[-1][0], a[2][4], a[3][3] 23/05/2021 Chương 5- Kiểu dữ liệu mảng 42/56
  43. Gán giá trị cho mảng o 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ử = ; //sai [ ][chỉ số 2]= ; o 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]; 23/05/2021 Chương 5- Kiểu dữ liệu mảng 43/56
  44. 5.2.4 Một số bài toán cơ bản o Nhập mảng o Xuất mảng o Tìm kiếm một phần tử trong mảng o Kiểm tra tính chất của mảng o Tìm giá trị nhỏ nhất/lớn nhất của mảng o 23/05/2021 Chương 5- Kiểu dữ liệu mảng 44/56
  45. Nhập mảng 2 chiều o Yêu cầu n Nhập vào từ bàn phím một mảng a gồm m dòng, n cột o Ý tưởng n Khai báo một mảng 2 chiều có dòng tối đa là MAXD, số cột tối đa là MAXC. (dùng #define để định nghĩa) n Nhập số dòng m và số cột n thực sự của mảng n Nhập từng phần tử từ [0][0] đến [m-1][n-1]. 23/05/2021 Chương 5- Kiểu dữ liệu mảng 45/56
  46. Nhập mảng 2 chiều o Đoạn chương trình nhập vào từ bàn phím một mảng 2 chiều a gồm m dòng, n cột #define MAXD 100 #define MAXC 100 int a[MAXD][MAXC]; int main() { 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]); } } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 46/56
  47. Xuất mảng 2 chiều o Yêu cầu n In ra màn hình mảng a gồm m dòng, n cột o Ý tưởng n In giá trị từng phần tử của mảng 2 chiều từ dòng có 0 đến dòng m-1; n Mỗi dòng giá trị của cột 0 đến cột n-1 trên dòng đó; n Kết thúc mỗi dòng chèn thêm dấu xuống dòng “\n” 23/05/2021 Chương 5- Kiểu dữ liệu mảng 47/56
  48. Xuất mảng 2 chiều (tt) o Đoạn chương trình in ra màn hình một mảng 2 chiều a gồm m dòng, n cột int main() { /*Các thao tác nhập, xử lý mảng */ /*in mảng ra màn hình */ int i, j; for (i=0; i<m; i++) { for (j=0; j<n; j++) printf(“%d ”, a[i][j]); printf(“\n”); } } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 48/56
  49. Hàm có mảng là tham số n Tham số kiểu mảng trong khai báo hàm giống như khai báo biến mảng void NhapMaTran(int a[50][100]); n 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 o Có thể bỏ số lượng phần tử chiều thứ 2 hoặc con trỏ. o Mảng có thể thay đổi nội dung sau khi thực hiện hàm. void NhapMaTran(int a[][100]); void NhapMaTran(int (*a)[100]); n Số lượng phần tử thực sự 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); 23/05/2021 Chương 5- Kiểu dữ liệu mảng 49/56
  50. Hàm nhập mảng 2 chiều 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]); } } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 50/56
  51. Hàm xuất mảng 2 chiều 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”); } } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 51/56
  52. Truyền mảng cho hàm (sử dụng hàm) o Lời gọi hà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); } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 52/56
  53. Ví dụ o Viết chương trình nhập 2 ma trận a và b gồm m dòng và n cột, tính ma trận c=a+b theo công thức c[i][j]=a[i][j]+b[i][j]. In c ra màn hình. o Ý tưởng n Viết các hàm: nhập, cộng, in ma trận n Nhập số dòng/số cột cho ma trận n Nhập giá trị cho a và b n Thực hiện cộng n In kết quả ra màn hình 23/05/2021 Chương 5- Kiểu dữ liệu mảng 53/56
  54. Ví dụ (tt) o Hàm cộng ma trận /* Cong 2 ma tran A & B ket qua la ma tran C*/ void CongMaTran(int a[][MAXC],int b[][MAXC],int M,int N,int c[][MAXC]) { int i,j; for(i=0;i<M;i++) for(j=0; j<N; j++) c[i][j]=a[i][j]+b[i][j]; } int main() //Chương trình chính { /*Nhập m,n */ NhapMaTran(a, m, n); NhapMaTran(b, m, n); CongMaTran(a,b,m,n,c); XuatMaTran(c,m,n); } 23/05/2021 Chương 5- Kiểu dữ liệu mảng 54/56
  55. Bài tập thực hành 23/05/2021 Chương 5- Kiểu dữ liệu mảng 55/56
  56. Bài tập thực hành 3. Nhập ma trận vuông a cấp n a. Tính tổng các phần tử dương trên đường chéo chính. b. Tính tổng các phần tử là số nguyên tố trong ma trận tam giác trên. c. Đếm số phần tử là số chính phương trong ma trận tam giác dưới. 4. Nhập vào ma trận a (m dòng, n cột), đưa ra các phần tử yên ngựa trong a. Phần tử yên ngựa là phần tử nhỏ nhất trên dòng nhưng lớn nhất trên cột hoặc nhỏ nhất trên cột nhưng lớn nhất trên dòng. 23/05/2021 Chương 5- Kiểu dữ liệu mảng 56/56