Bài giảng Lập trình C - Bài 5: Mảng một chiều - Võ Đức Hoàng

Lập trình C Bài 5. Mảng một chiều Võ Đức Hoàng Email: hoangvd.it@dut.udn.vn Website: Cập nhật: 8/2018 1 2Mục tiêu 1. Kiểu dữ liệu mảng một chiều 2. Các thao tác nhập/ xuất mảng 3. Kỹ thuật tìm kiếm, liệt kê giá trị trong mảng 3KHÁI NIỆM •Mảng đượ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 KDL và cùng tên 0 1 2 3 4 5 6 7 8 9 Giá trị Vị trí Vị trí được tính từ 0 4KHAI BÁO • int a[100]; //Khai bao mang so nguyen a gom 100 phan tu • float b[50]; //Khai bao mang so thuc b gom 50 phan tu • char str[30]; //Khai bao mang ky tu str gom 30 ky tu [ ] ; Nên định nghĩa hằng số MAX ở đầu chương trình –kích thước tối đa của mảng - như sau: #define MAX 100 int main() { int a[MAX], b[MAX]; //Các lệnh return 0; } 5KHAI BÁO VÀ GÁN GIÁ TRỊ BAN ĐẦU CHO MẢNG Gán từng phần tử int a[5] = {3, 6, 8, 1, 12}; Gán toàn bộ phần tử có cùng giá trị int a[8] = {3}; Giá trị 3 6 8 1 12 Vị trí 0 1 2 3 4 Giá trị 3 3 3 3 3 3 3 3 Vị trí 0 1 2 3 4 5 6 7 6TRUY XUẤT GIÁ TRỊ TênMảng [vị trí cần truy xuất] int main() { int a[5] = {3, 6, 8, 11, 12}; printf(“Gia tri mang tai vi tri 3 = “, a[3]); getch(); return 0; } Kết quả: Gia tri mang tai vi tri 3 = 11 Vị trí 3 7CÁC THAO TÁC TRÊN MẢNG •Nhập •Xuất (liệt kê) •Tìm kiếm •Đếm •Sắp xếp •Kiểm tra mảng thỏa điều kiện cho trước •Tách/ ghép mảng •Chèn / xóa 8NHẬP XUẤT MẢNG a[0] a[1] a[2] a[3] a[4] a[5] a[n-1] Nhập a[0] Nhập a[1] Nhập a[2] Nhập a[n-1]  Nhập a[i], 0<=i<n 9NHẬP/ XUẤT MẢNG #define MAX 100 void NhapKichThuoc(int &n) { printf("Nhap vao kich thuoc mang: "); scanf("%d", &n); } void NhapMang(int a[], int n) { for (int i = 0; i < n; i++) { printf("* Nhap vao phan tu tai vi tri %d: ", i); scanf("%d", &a[i]); } } 10 void XuatMang(int a[], int n) { for(int i=0; i<n;i++) { printf("%d\t", a[i]); } } int main() { int a[MAX], n; NhapKichThuoc(n); NhapMang(a, n); printf("Cac gia tri trong mang a:\n"); XuatMang(a, n); getch(); return 0; } 11 PHÁT SINH CÁC GIÁ TRỊ CHO MẢNG • Sử dụng thư viện hàm và •Dùng hàm srand() trong hàm main() trước khi gọi hàm phát sinh: để khởi tạo bộ giá trị ngẫu nhiên •Dùng hàm rand()%k để phát sinh số ngẫu nhiên: có giá trị từ 0 đến k-1 12 Ví dụ: Chương trình tạo mảng số nguyên có giá trị ngẫu nhiên từ 1 đến MAX #include #include #include #include #define MAX 100 void NhapKichThuoc(int &n); void PhatSinh(int a[], int n); void XuatMang(int a[], int n); 13 void NhapKichThuoc(int &n) { printf("Nhap vao kich thuoc mang: "); scanf("%d", &n); } void PhatSinh(int a[], int n) { for (int i = 0; i < n; i++) { a[i] = rand() % MAX + 1; } } void XuatMang(int a[], int n) { for(int i=0; i<n;i++) { printf("%d\t", a[i]); } } 14 int main() { int a[MAX], n; NhapKichThuoc(n); srand((unsigned int)time(NULL)); PhatSinh(a, n); printf("Cac gia tri trong mang a:\n"); XuatMang(a, n); getch(); return 0; } 15 Bài tập •Cho mảng một chiều số nguyên a, kích thước n. Hãy viết các hàm: 1. Phát sinh giá trị các phần tử ngẫu nhiên theo thứ tự tăng dần cho a. 2. Phát sinh giá trị các phần tử ngẫu nhiên có giá âm và dương. 16 LIỆT KÊ CÁC PHẦN TỬ THỎA ĐK CHO TRƯỚC Mẫu 1: void LietKeXXX(int a[], int n) { for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện) Xuất a[i]; } 17 LIỆT KÊ CÁC PHẦN TỬ THỎA ĐK CHO TRƯỚC Mẫu 2: void LietKeXXX(int a[], int n, int x) { for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện so với x) Xuất a[i]; } 18 Ví dụ 1: Liệt kê các phần tử có giá trị chẵn trong mảng void LietKeChan(int a[], int n) { for (int i = 0; i<n; i++) if (a[i] %2 ==0) printf(“%d\t”, a[i]); } Ví dụ 2: Liệt kê các phần tử có giá trị lớn hơn x trong mảng void LietKeLonHonX(int a[], int n, int x) { for (int i = 0; i<n; i++) if (a[i] > x) printf(“%d\t”, a[i]); } 19 Ví dụ 3: Chương trình nhập vào mảng một chiều số nguyên a, kích thước n. In ra các phần tử có giá trị lớn hơn x có trong mảng #define MAX 100 void NhapKichThuoc(int &n); void NhapMang(int a[], int n); void XuatMang(int a[], int n); void LietKeLonHonX(int a[], int n, int x); void NhapKichThuoc(int &n) { prinft(“Nhap vao kich thuoc mang: “); scanf(“%d”, &n); } void NhapMang (int a[], int n) { for (int i = 0; i < n; i ++) { printf(“Nhap phan tu tai vi tri %d: “, i); scanf(“%d”, &a[i]); } } 20 void XuatMang (int a[], int n) { for (int i = 0; i < n; i ++) printf(“%d\t”, a[i]); } void LietKeLonHonX(int a[], int n, int x) { for (int i = 0; i<n; i++) if (a[i] > x) printf(“%d\t”, a[i]); } 21 int main() { int a[MAX], n, x; NhapKichThuoc(n); NhapMang(a, n); printf("Cac phan tu cua mang:\n"); XuatMang(a, n); printf("Nhap gia tri x: “); scanf(“%d”, &x); printf("Cac phan tu co gia tri lon hon %d:\n", x); LietKeLonHonX(a, n, x); getch(); return 0; } 22 Bài tập tại lớp Cho mảng số nguyên a, gồm n phần tử, viết chương trình gồm các hàm thực hiện các yêu cầu sau: 1. Nhập vào kích thước mảng (0<n<=100), nếu nhập không thỏa miền giá trị thì cho phép người dùng nhập lại 2. Nhập các giá trị vào mảng một chiều a 3. Xuất các phần tử là bội số của 5 trong mảng a 4. Xuất các phần tử là số nguyên tố trong mảng a 5. Hàm main() để gọi thực hiện các yêu cầu từ 1 đến 4 23 ĐẾM SỐ LƯỢNG PHẦN TỬ Mẫu 1: int DemXXX(int a[], int n) { int d = 0; for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện) d++; return d; } 24 Mẫu 2: int DemXXX(int a[], int n, int x) { int d = 0; for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện so với x) d++; return d; } 25 Ví dụ 1: Đếm các phần tử có giá trị là số nguyên tố int DemSNT(int a[], int n) { int d = 0; for (int i = 0; i<n; i++) { if (LaSNT(a[i]) ==1) { d++; } } return d; } int LaSNT(int k) { int d = 0; for (int i = 1; i <= k; i++) { if (k % i == 0) { d++; } } if(d == 2) return 1; return 0; } 26 int DemNhoHonX(int a[], int n, int x) { int d = 0; for (int i = 0; i<n; i++) if (a[i] < x) d++; return d; } Ví dụ 2: Đếm các phần tử có giá trị nhỏ hơn x trong mảng 27 Ví dụ 3: Chương trình nhập vào mảng một chiều số nguyên a, kích thước n. Đếm số lượng các phần tử là số nguyên tố có trong mảng #define MAX 100 void NhapKichThuoc(int &n); void NhapMang(int a[], int n); void XuatMang(int a[], int n); int LaSNT(int k); int DemSNT(int a[], int n); void NhapKichThuoc(int &n){ prinft(“Nhap vao kich thuoc mang: “); scanf(“%d”, &n); } void NhapMang (int a[], int n){ for (int i = 0; i < n; i ++) { printf(“Nhap phan tu tai vi tri %d: “, i); scanf(“%d”, &a[i]); } } 28 int DemSNT(int a[], int n) { int d = 0; for (int i = 0; i<n; i++) if (LaSNT(a[i]) ==1) d++; return d; } void XuatMang (int a[], int n) { for (int i = 0; i < n; i ++) printf(“%d\t”, a[i]); } int LaSNT(int k) { int d = 0; for (int i = 1; i <= k; i++) if (k % i == 0) d++; if (d == 2) return 1; return 0; } 29 int main() { int a[MAX], n, kq; NhapKichThuoc(n); NhapMang(a, n); printf("Cac phan tu cua mang:\n"); XuatMang(a, n); kq = DemSNT(a, n); if(kq==0) printf("Khong co so nguyen to trong mang“); else printf("So luong so nguyen to la: %d“, kq); getch(); return 0; } 30 Bài tập Cho mảng một chiều số nguyên a, kích thước n. Hãy viết các hàm: 1. Đếm số lượng các phần tử có giá trị lẻ. 2. Đếm những phần tử có giá trị là bội số của 3. 31 TÌM PHẦN TỬ X • Ý tưởng Lần lượt so sánh x với phần tử thứ nhất, thứ hai, ... của mảng a cho đến khi gặp được phần tử cần tìm, hoặc đã tìm hết mảng mà không thấy x • Minh họa tìm x =10 • Minh họa tìm x =25 Chưa hết mảng 7 5 12 41 10 32 13 9 15 3 0 1 2 3 4 5 6 7 8 9 7 5 12 41 10 32 13 9 15 3 0 1 2 3 4 5 6 7 8 9 10 25 Chưa hết mảng Đã tìm thấy ại vị trí 4 Đã hết mảng 32 (nếu x không xuất hiện trong mảng trả về -1) int TimVTX(int a[], int n, int x) { for (int i = 0; i < n; i++) { if (a[i] == x) return i; } return -1; } CODE MINH HỌA 33 Bài tập •Cho mảng một chiều số nguyên a, kích thước n. Viết các hàm sau: 1. Tìm vị trí xuất hiện cuối cùng của phần tử có giá trị x nếu có. 2. Tìm vị trí phần tử có giá trị âm xuất hiện đầu tiên trong mảng. 34 0 1 2 3 4 5 6 7 TÌM VỊ TRÍ PHẦN TỬ NHỎ NHẤT? 10 5 7 3 9 2 15 1 Giả sử cần tìm vị trí phần tử nhỏ nhất trong dãy số sau ? 35 0 1 2 3 4 5 6 7 10 5 7 3 9 2 15 1 Bước 1: Giả sử vị trí phần tử nhỏ nhất là 0 (vtmin), phần tử này có giá trị 10 vtmin 36 0 1 2 3 4 5 6 7 5 7 3 9 2 15 1 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 1 đến 7), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 5 nhỏ hơn 10 nên cập nhật vị trí min 10 37 0 1 2 3 4 5 6 7 3 9 2 15 1 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 1 đến 7), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 7 lớn hơn 5 nên không cập nhật vị trí min 10 5 7 38 0 1 2 3 4 5 6 7 3 9 2 15 1 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 1 đến 7), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 3 nhỏ hơn 5 nên cập nhật vị trí min 10 5 7 39 0 1 2 3 4 5 6 7 3 9 2 15 1 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 1 đến 7), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 9 lớn hơn 3 nên không cập nhật vị trí min 10 5 7 40 0 1 2 3 4 5 6 7 9 2 15 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 1 đến 7), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 1 nhỏ hơn 3 nên cập nhật vị trí min 10 5 7 3 1 41 0 1 2 3 4 5 6 7 9 2 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 1 đến 7), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 15 lớn hơn 1 nên không cập nhật vị trí min 10 5 7 3 15 1 42 0 1 2 3 4 5 6 7 9 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 1 đến 7), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 10 5 7 3 15 2 lớn hơn 1 nên không cập nhật vị trí min 21 43 CODE MINH HỌA int TimVTMin(int a[], int n) { int vtmin = 0; for (int i = 1; i < n; i++) { if (a[i] < a[vtmin]) vtmin = i; } return vtmin; } 44 Bài tập Cho mảng một chiều số nguyên a, kích thước n. Hãy viết hàm tìm phần tử có giá trị lớn nhất 45 TÍNH TỔNG, GIÁ TRỊ TRUNG BÌNH CÓ ĐIỀU KIỆN Mẫu tính tổng: int TongXXX(int a[], int n) { int s = 0; for (int i = 0; i<n; i++) { if (a[i] thỏa điều kiện) s += a[i]; } return s; } 46 Mẫu tính trung bình: float TrungBinhXXX(int a[], int n) { int s = 0; int d = 0; for (int i = 0; i<n; i++) { if (a[i] thỏa điều kiện) { s += giatri; d ++; } } if (d==0) return 0; return (float) s / d; } 47 Ví dụ 1: Tính tổng các phần tử có giá trị lẻ trong mảng int TongLe(int a[], int n) { int s = 0; for (int i = 0; i<n; i++) { if (a[i] %2!=0) s += a[i]; } return s; } 48 Ví dụ 2: Tính giá trị trung bình các phần tử có giá trị âm trong mảng float TrungBinhAm(int a[], int n) { long s = 0; int d = 0; for (int i = 0; i<n; i++) { if (a[i] < 0) { s += a[i]; d++; } } if (d == 0) return 0; return (float)s / d; } 49 Mẫu phương thức sắp thứ tự tăng: void SapTang(int a[], int n) { for (int i = 0; i < n-1; i ++) { for(int j = i+1; j < n; j ++) if (a[i] > a[j]) HoanVi(a[i], a[j]); } } void HoanVi(int &a, int &b) { int tam = a; a = b; b = tam; } 50 Q&A