›
›

Bài giảng Nhập môn lập trình - Chủ đề 5: Kiểu dữ liệu mảng, chuỗi - Phần 1: Mảng một chiều

pdf 47 trang phuongnguyen 7520
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn lập trình - Chủ đề 5: Kiểu dữ liệu mảng, chuỗi - Phần 1: Mảng một chiều", để 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:

  • pdfbai_giang_nhap_mon_lap_trinh_chu_de_5_kieu_du_lieu_mang_chuo.pdf

Nội dung text: Bài giảng Nhập môn lập trình - Chủ đề 5: Kiểu dữ liệu mảng, chuỗi - Phần 1: Mảng một chiều

  1. NHẬP MÔN LẬP TRÌNH MẢNG MỘT CHIỀU 1
  2. Nội dung 1 Khái niệm 2 Khai báo 3 Truy xuấtdữ liệukiểumảng 4 Mộtsố bàitoántrênmảng 1 chiều Mảng mộtchiều 2
  3. Đặtvấn đề ™Ví dụ ƒ Chương trình cầnlưu trữ 3 số nguyên? => Khai báo 3 biến int a1, a2, a3; ƒ Chương trình cầnlưu trữ 100 số nguyên? => Khai báo 100 biếnkiểusố nguyên! ƒ Người dùng muốnnhập n số nguyên? => Không thựchiện được! ™Giải pháp ƒ Kiểudữ liệumới cho phép lưu trữ một dãy các số nguyên và dễ dàng truy xuất. Mảng mộtchiều 3
  4. Dữ liệukiểumảng ™Khái niệm ƒ Là một kiểudữ liệucócấutrúcdo ngườilập trình định nghĩa. ƒ Biểudiễnmộ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ự ƒ Kích thước được xác định ngay khi khai báo và không bao giờ thay đổi. ƒ NNLT C luôn chỉđịnh mộtkhốinhớ liên tục cho mộtbiếnkiểumảng. Mảng mộtchiều 4
  5. Khai báo biếnmảng (tường minh) ™Tường minh [ ]; [ ][ ] [ ]; ƒ , , : số lượng phầntử củamỗichiều. ™Lưu ý ƒ Phải xác định cụ thể (hằng) khi khai báo. ƒ Mảng nhiềuchiều: = N1*N2* *Nn ƒ Bộ nhớ sử dụng = *sizeof( ) ƒ Bộ nhớ sử dụng phải ít hơn 64KB (65536 Bytes) ƒ Mộtdãyliêntụccóchỉ số từ 0 đến -1 Mảng mộtchiều 5
  6. Khai báo biếnmảng (tường minh) ™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 Mảng mộtchiều 6
  7. Khai báo biếnmảng (kô tường minh) ™Cú pháp ƒ Không tường minh (thông qua khai báo kiểu) typedef [ ]; typedef [ ] [ ]; ; ™Ví dụ typedef int Mang1Chieu[10]; typedef int Mang2Chieu[3][4]; Mang1Chieu m1, m2, m3; Mang2Chieu m4, m5; Mảng mộtchiều 7
  8. Số phầntử củamảng ™Phảixácđịnh cụ thể số phầntử ngay lúc khai báo, không được sử dụng biếnhoặchằng thường int n1 = 10; int a[n1]; const int n2 = 20; int b[n2]; ™Nên sử dụng chỉ thị tiềnxử lý #define để định nghĩasố phầntử mảng #define n1 10 #define n2 20 int a[n1]; // Ù int a[10]; int b[n1][n2]; // Ù int b[10][20]; Mảng mộtchiều 8
  9. Khởitạogiátrị cho mảng lúc khai báo ™Gồm các cách sau ƒ Khởitạogiátrị cho mọiphầntử củamảng int a[4] = {2912, 1706, 1506, 1904}; 0 1 2 3 a 2912 1706 1506 1904 ƒ Khởitạogiátrị cho mộtsố phầntửđầu mảng int a[4] = {2912, 1706}; 0 1 2 3 a 2912 1706 0 0 Mảng mộtchiều 9
  10. Khởitạogiátrị cho mảng lúc khai báo ™Gồm các cách sau ƒ Khởitạogiátrị 0 cho mọiphầntử củamảng int a[4] = {0}; 0 1 2 3 a 0 0 0 0 ƒ Tựđộng xác định số lượng phầntử int a[] = {2912, 1706, 1506, 1904}; 0 1 2 3 a 2912 1706 1506 1904 Mảng mộtchiều 10
  11. Truy xuất đến mộtphầntử ™Thông qua chỉ số [ ][ ] [ ] ™Ví dụ ƒ Cho mảng như sau 0 1 2 3 int a[4]; ƒ Các truy xuất • Hợplệ: a[0], a[1], a[2], a[3] • Không hợplệ: a[-1], a[4], a[5], => Cho kếtthường không như mong muốn! Mảng mộtchiều 11
  12. Gán dữ liệukiểumảng ™Không được sử dụng phép gán thông thường mà phải gán trựctiếpgiữacácphầntử tương ứng ™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]; Mảng mộtchiều 12
  13. Mộtsố lỗithường gặp ™ Khai báo không chỉ rõ số lượng phầntử ƒ int a[]; => int a[100]; ™ Số lượng phầntử liên quan đến biếnhoặchằng ƒ intn1 = 10; inta[n1]; => int a[10]; ƒ const int n2 = 10; int a[n2]; => int a[10]; ™ Khởitạocáchbiệtvới khai báo ƒ int a[4]; a = {2912, 1706, 1506, 1904}; => int a[4] = {2912, 1706, 1506, 1904}; ™ Chỉ số mảng không hợplệ ƒ int a[4]; ƒ a[-1] = 1; a[10] = 0; Mảng mộtchiều 13
  14. Truyềnmảng cho hàm ™Truyềnmảng cho hàm ƒ Tham số kiểumảng trong khai báo hàm giống như khai báo biến mảng void SapXepTang(int a[100]); ƒ Tham số kiểumảng truyền cho hàm chính là địa chỉ củaphầntửđầu tiên củamảng •Cóthể bỏ số lượng phầntử hoặc sử dụng con trỏ. •Mảng có thể thay đổi nội dung sau khi thựchiệnhàm. void SapXepTang(int a[]); void SapXepTang(int *a); Mảng mộtchiều 14
  15. Truyềnmảng cho hàm ™Truyềnmảng cho hàm ƒ Số lượng phầntử thựcsự 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); ™Lờigọihàm void NhapMang(int a[], int &n); void XuatMang(int a[], int n); void main() { int a[100], n; NhapMang(a, n); XuatMang(a, n); } Mảng mộtchiều 15
  16. Mộtsố bài toán cơ bản ™Viết hàm thựchiệntừng yêu cầusau ƒ Nhậpmảng ƒ Xuấtmảng ƒ Tìm kiếmmộtphầntử trong mảng ƒ Kiểmtratínhchấtcủamảng ƒ Tách mảng / Gộpmảng ƒ Tìm giá trị nhỏ nhất/lớnnhấtcủamảng ƒ Sắpxếpmảng giảmdần/tăng dần ƒ Thêm/Xóa/Sửamộtphầntử vào mảng Mảng mộtchiều 16
  17. Mộtsố quy ước ™Số lượng phầntử #define MAX 100 ™Các hàm ƒ 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ểmtramộtsố có phải là số nguyên tố. Trả về 1 nếun làsố nguyên tố, ngược lạitrả về 0. Mảng mộtchiều 17
  18. Thủ tụcHoanVi& HàmLaSNT Mảng mộtchiều 18
  19. Nhậpmảng ™Yêu cầu ƒ Cho phép nhậpmảng a, số lượng phầntử n ™Ý tưởng ƒ Cho trước mộtmảng có số lượng phầntử là MAX. ƒ Nhập số lượng phầntử thựcsự n củamảng. ƒ Nhậptừng phầntử cho mảng từ chỉ số 0 đến n – 1. 0 1 2 3 n 4- 1 MAX - 1 Mảng mộtchiều 19
  20. Hàm NhậpMả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]); } } Mảng mộtchiều 20
  21. Xuấtmảng ™Yêu cầu ƒ Cho trước mảng a, số lượng phầntử n. Hãy xuấtnội dung mảng a ra màn hình. ™Ý tưởng ƒ Xuấtgiátrị từng phầntử củamảng từ chỉ số 0 đến n- 1. 012 n - 1 MAX - 1 Mảng mộtchiều 21
  22. Hàm XuấtMả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”); } Mảng mộtchiều 22
  23. Tìm kiếmmộtphầntử trong mảng ™Yêu cầu ƒ Tìm xem phầntử x có nằmtrongmảng a kích thước n hay không? Nếucóthìnónằm ở vị trí đầu tiên nào. ™Ý tưởng ƒ Xét từng phầncủamảng a. Nếuphầntửđang xét bằng x thì trả về vị trí đó. Nếukôtìmđược thì trả về -1. x vị trí = 1 012 n - 1 MAX - 1 a x b x Mảng mộtchiều 23
  24. Hàm Tìm Kiếm (dùng while) Mảng mộtchiều 24
  25. Hàm Tìm Kiếm (dùng for) int TimKiem(int a[], int n, int x) { for (int vt = 0; vt < n; vt++) if (a[vt] == x) return vt; return -1; } Mảng mộtchiều 25
  26. Kiểm tra tính chấtcủamảng ™Yêu cầu ƒ Cho trước mảng a, số lượng phầntử n. Mảng a có phảilàmảng toàn các số nguyên tố hay không? ™Ý tưởng ƒ Cách 1: Đếmsố lượng số ngtố củamảng. Nếusố lượng này bằng đúng n thì mảng toàn ngtố. ƒ Cách 2: Đếmsố lượng số không phảingtố củamảng. Nếusố lượng này bằng 0 thì mảng toàn ngtố. ƒ Cách 3: Tìm xem có phầntử nào không phảisố ngtố không. Nếucóthìmảng không toàn số ngtố. Mảng mộtchiều 26
  27. Hàm KiểmTra(Cách1) int KiemTra_C1(int a[], int n) { int dem = 0; for (int i = 0; i < n; i++) if (LaSNT(a[i]) == 1) // có thể bỏ == 1 dem++; if (dem == n) return 1; return 0; } Mảng mộtchiều 27
  28. Hàm KiểmTra(Cách2) int KiemTra_C2(int a[], int n) { int dem = 0; for (int i = 0; i < n; i++) if (LaSNT(a[i]) == 0) // Có thể sử dụng ! dem++; if (dem == 0) return 1; return 0; } Mảng mộtchiều 28
  29. Hàm KiểmTra(Cách3) int KiemTra_C3(int a[], int n) { for (int i = 0; i < n ; i++) if (LaSNT(a[i]) == 0) return 0; return 1; } Mảng mộtchiều 29
  30. Tách các phầntử thỏa điềukiện ™Yêu cầu ƒ Cho trước mảng a, số lượng phầntử na. Tách các số nguyên tố có trong mảng a vào mảng b. ™Ý tưởng ƒ Duyệttừ phầntử củamảng a, nếu đólàsố nguyên tố thì đưa vào mảng b. Mảng mộtchiều 30
  31. Hàm Tách Số Nguyên Tố void TachSNT(int a[], int na, int b[], int &nb) { nb = 0; for (int i = 0; i < na; i++) if (LaSNT(a[i]) == 1) { b[nb] = a[i]; nb++; } } Mảng mộtchiều 31
  32. Tách mảng thành 2 mảng con ™Yêu cầu ƒ Cho trước mảng a, số lượng phầntử na. Tách mảng a thành 2 mảng b (chứasố nguyên tố) và mảng c (các số còn lại). ™Ý tưởng ƒ Cách 1: viết 1 hàm tách các số nguyên tố từ mảng a sang mảng b và 1 hàm tách các số không phải nguyên tố từ mảng a sang mảng c. ƒ Cách 2: Duyệttừ phầntử củamảng a, nếu đólàsố nguyên tố thì đưa vào mảng b, ngược lại đưa vào mảng c. Mảng mộtchiều 32
  33. Hàm Tách 2 Mảng void TachSNT2(int a[], int na, int b[], int &nb, int c[], int &nc) { nb = 0; nc = 0; for (int i = 0; i < na; i++) if (LaSNT(a[i]) == 1) { b[nb] = a[i]; nb++; } else { c[nc] = a[i]; nc++; } } Mảng mộtchiều 33
  34. Gộp2 mảng thành mộtmảng ™Yêu cầu ƒ Cho trước mảng a, số lượng phầntử na và mảng b số lượng phầntử nb. Gộp2 mảng trên theo tứ tựđó thành mảng c, số lượng phầntử nc. ™Ý tưởng ƒ Chuyểncácphầntử củamảng a sang mảng c => nc = na ƒ Tiếptục đưa các phầntử củamảng b sang mảng c => nc = nc + nb Mảng mộtchiều 34
  35. Hàm GộpMảng void GopMang(int a[], int na, int b[], int nb, int c[], int &nc) { nc = 0; for (int i = 0; i < na; i++) { c[nc] = a[i]; nc++; // c[nc++] = a[i]; } for (int i = 0; i < nb; i++) { c[nc] = b[i]; nc++; // c[nc++] = b[i]; } } Mảng mộtchiều 35
  36. Tìm giá trị lớnnhấtcủamảng ™Yêu cầu ƒ Cho trước mảng a có n phầntử. Tìm giá trị lớnnhất trong a (gọilàmax) ™Ý tưởng ƒ Giả sử giá trị max hiệntại là giá trị phầntửđầu tiên a[0] ƒ Lầnlượt kiểm tra các phầntử còn lại để cậpnhật max. max 78? 012 n – 1 MAX - 1 7 2 8 8 Mảng mộtchiều 36
  37. Hàm tìm Max int TimMax(int a[], int n) { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } Mảng mộtchiều 37
  38. Sắpxếpmảng thành tăng dần ™Yêu cầu ƒ Cho trước mảng a kích thước n. Hãy sắpxếpmảng a đó sao cho các phầntử có giá trị tăng dần. ™Ý tưởng ƒ Sử dụng 2 biến i và j để so sánh tấtcả cặpphầntử với nhau và hoán vị các cặp nghịch thế (sai thứ tự). tạm 58 012 n – 1 MAX - 1 51 15 86 68 38 i j j j j Mảng mộtchiều
  39. Hàm SắpXếpTăng void SapXepTang(int a[], int n) { int i, j; for (i = 0; i a[j]) HoanVi(a[i], a[j]); } } } Mảng mộtchiều 39
  40. Thêm mộtphầntử vào mảng ™Yêu cầu ƒ Thêm phầntử x vào mảng a kích thước n tạivị trí vt. ™Ý tưởng ƒ “Đẩy” các phầntử bắt đầu tạivị trí vt sang phải 1 vị trí. ƒ Đưa x vào vị trí vt trong mảng. ƒ Tăng n lên 1 đơn vị. x chèn? 0123 n – 1 n MAX - 1 a b c z Mảng mộtchiều 40 vt
  41. Hàm Thêm 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++; } } Mảng mộtchiều 41
  42. Xóa mộtphầntử trong mảng ™Yêu cầu ƒ Xóa mộtphầntử trong mảng a kích thước n tạivị trí vt ™Ý tưởng ƒ “Kéo” các phầntử bên phảivị trí vt sang trái 1 vị trí. ƒ Giảm n xuống 1 đơn vị. xóa? 012n - 1 n – 1 MAX - 1 a x b z 42 vt Mảng mộtchiều
  43. Hàm Xóa 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 ; } } Mảng mộtchiều 43
  44. Bài tập 1. Các thao tác nhậpxuất a. Nhậpmảng b. Xuấtmảng 2. Các thao tác kiểmtra a. Mảng có phảilàmảng toàn chẵn b. Mảng có phảilàmảng toàn số nguyên tố c. Mảng có phảilàmảng tăng dần Mảng mộtchiều 44
  45. Bài tập 3. Các thao tác tính toán a. Có bao nhiêu số chia hết cho 4 nhưng không chia hếtcho5 b. Tổng các số nguyên tố có trong mảng 4. Các thao tác tìm kiếm a. Vị trí cuốicùngcủaphầntử x trong mảng b. Vị trí số nguyên tốđầu tiên trong mảng nếucó c. Tìm số nhỏ nhấttrongmảng d. Tìm số dương nhỏ nhất trong mảng Mảng mộtchiều 45
  46. Bài tập 5. Các thao tác xử lý a. Tách các số nguyên tố có trong mảng a đưa vào mảng b. b. Tách mảng a thành 2 mảng b (chứacácsố nguyên dương) và c (chứacácsố còn lại) c. Sắpxếpmảng giảmdần d. Sắpxếpmảng sao cho các số dương đứng đầu mảng giảmdần, kếđến là các số âm tăng dần, cuối cùng là các số 0. Mảng mộtchiều 46
  47. Bài tập 6. Các thao tác thêm/xóa/sửa a. Sửacácsố nguyên tố có trong mảng thành số 0 b. Chèn số 0 đằng sau các số nguyên tố trong mảng c. Xóa tấtcả số nguyên tố có trong mảng Mảng mộtchiều 47