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
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:
- bai_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
- NHẬP MÔN LẬP TRÌNH MẢNG MỘT CHIỀU 1
- 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
- Đặ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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Thủ tụcHoanVi& HàmLaSNT Mảng mộtchiều 18
- 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
- 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
- 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
- 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
- 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
- Hàm Tìm Kiếm (dùng while) Mảng mộtchiều 24
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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