Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Mảng một chiều

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Mảng một chiều

1. CHƯƠNG 5 MẢNG MỘT CHIỀU 1
2. KHÁI NIỆM  Mảng thực chất 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. Do đó để truy xuất các biến thành phần, ta dùng cơ chế chỉ mục. Giá trị 0 1 2 3 4 5 6 7 8 9 Vị trí Vị trí được tính từ 0 4/3/2015 2
3. KHAI 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 Nhằm thuận tiện cho việc viết chương trình, ta nên định nghĩa hằng số MAX ở đầu chương trình – là kích thước tối đa của mảng - như sau: #define MAX 100 void main() { int a[MAX], b[MAX]; //Các lệnh } 4/3/2015 3
4. KHAI 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}; Giá trị 3 6 8 1 12 Vị trí 0 1 2 3 4 Gán toàn bộ phần tử có cùng giá trị int a[8] = {3}; Giá trị 3 3 3 3 3 3 3 3 Vị trí 0 1 2 3 4 5 6 7 4/3/2015 4
5. TRUY XUẤT GIÁ TRỊ TênMảng [vị trí cần truy xuất] void main() { Vị trí 3 int a[5] = {3, 6, 8, 11, 12}; cout<<“Giá trị mảng tại vị trí 3 = “<<a[3]; } Kết quả: Giá trị mảng tại vị trí 3 = 11 4/3/2015 5
6. CÁ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 4/3/2015 6
7. NHẬP XUẤT MẢNG #define MAX 100 void NhapMang (int a[], int n) { for (int i = 0; i >a[i]; } } 4/3/2015 7
8. void XuatMang (int a[], int n) { for (int i = 0; i >n; NhapMang (a,n); cout<<“Cac gia tri cua mang vua nhap: ”<<endl; XuatMang (a,n); } 4/3/2015 8
9. LIỆT KÊ CÁC PHẦN TỬ THỎA ĐK CHO TRƯỚC Mẫu 1: void LietKe???(int a[], int n) { for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện) Xuất a[i]; } Mẫu 2: void LietKe???(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]; } 4/3/2015 9
10. 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 x) cout<<a[i]<<“\t”; } 4/3/2015 10
11.  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 NhapMang(int a[], int n); void XuatMang(int a[], int n); void LietKeLonHonX(int a[], int n, int x); void NhapMang(int a[], int n) { for(int i=0; i >a[i]; } } void XuatMang(int a[], int n) { for(int i=0; i<n; i++) cout<<a[i]<<"\t"; } 4/3/201511
12. void LietKeLonHonX(int a[], int n, int x) { for (int i = 0; i x) cout >n; NhapMang(a, n); cout >x; cout<<"Cac phan tu co gia tri lon hon "<<x<<endl; LietKeLonHonX(a, n, x); } 4/3/201512
13. ĐẾM Mẫu 1: int Dem???(int a[], int n) { int dem = 0; for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện) dem++; return dem; } 4/3/2015 13
14. Mẫu 2: int Dem???(int a[], int n, int x) { int dem = 0; for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện so với x) dem++; return dem; } 4/3/2015 14
15. Ví dụ 1: Đếm các phần tử có giá trị là số nguyên tố bool LaSNT(int k) { for (int i = 2; i <= k/2; i++) if (k % i == 0) return false; return true; int DemSNT(int a[], int n) } { int dem = 0; for (int i = 0; i<n; i++) if (LaSNT(a[i])) dem++; return dem; } 4/3/2015 15
16. Ví dụ 2: Đếm các phần tử có giá trị nhỏ hơn x có trong mảng int DemNhoHonX(int a[], int n, int x) { int dem = 0; for (int i = 0; i<n; i++) if (a[i] < x) dem++; return dem; } 4/3/2015 16
17.  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 NhapMang(int a[], int n); void XuatMang(int a[], int n); int DemSNT(int a[], int n); bool LaSNT(int k); void NhapMang(int a[], int n) { for(int i=0; i >a[i]; } } void XuatMang(int a[], int n) { for(int i=0; i<n; i++) cout<<a[i]<<"\t"; } 4/3/201517
18. bool LaSNT(int k) { for (int i = 2; i <= k/2; i++) if (k % i == 0) return false; return true; int DemSNT(int a[], int n) } { int dem = 0; for (int i = 0; i<n; i++) if (LaSNT(a[i]) ==true) dem++; return dem; } 4/3/2015 18
19. void main() { int a[MAX], n, kq; cout >n; NhapMang(a, n); cout<<"Cac phan tu cua mang:"<<endl; XuatMang(a, n); kq = DemSNT(a, n); if(kq==0) cout<<"Khong co so nguyen to trong mang"; else cout<<"So luong so nguyen to la: "<<kq; } 4/3/201519
20. TÌM KIẾM Mẫu 1: Tìm và trả về vị trí phần tử có giá trị lớn nhất int TimVTMax(int a[], int n) { int vtmax = 0; for (int i = 0; i a[vtmax]) vtmax = i; return vtmax; } 4/3/2015 20
21. Mẫu 2: Tìm vị trí phần tử có giá trị x (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; } 4/3/2015 21
22. KIỂM TRA XEM MẢNG CÓ THỎA ĐIỀU KIỆN CHO TRƯỚC  TH1: kiểm tra tồn tại một phần tử trong mảng thỏa điều kiện nào đó cho trước tìm phần tử thỏa điều kiện để kết luận.  TH2: kiểm tra tất cả các phần tử thỏa điều kiện nào đó cho trước tìm phần tử không thỏa điều kiện để kết luận mảng không thỏa điều kiện. 4/3/2015 22
23. Mẫu TH1: bool KiemTraTonTai???(int a[], int n) { for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện) return true; return false; } Mẫu TH2: bool KiemTra???(int a[], int n) { for (int i = 0; i<n; i++) if (a[i] không thỏa điều kiện) return false; return true; } 4/3/2015 23
24. Ví dụ 1: Kiểm tra xem mảng có tồn tại số lẻ không? bool KiemTraTonTaiLe(int a[], int n) { for (int i = 0; i < n; i++) if (a[i] % 2 != 0) return true; return false; } 4/3/2015 24
25. Ví dụ 2: Kiểm tra xem mảng có toàn giá trị âm không? (true: có/ false: không) bool KiemTraToanAm(int a[], int n) { for (int i = 0; i = 0) return false; return true; } 4/3/2015 25
26. TÍNH TỔNG, GIÁ TRỊ TRUNG BÌNH CÓ ĐIỀU KIỆN Mẫu tính tổng: int Tong???(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; } 4/3/2015 26
27. Mẫu tính trung bình: float TrungBinh???(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; } 4/3/2015 27
28. 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; } 4/3/2015 28
29. 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; } 4/3/2015 29
30. SẮP XẾP Mẫu phương thức sắp thứ tự tăng: void SapTang(int a[], int n) { for (int i = 0; i a[j]) HoanVi(a[i], a[j]); } void HoanVi(int &a, int &b) { int tam = a; a = b; b = tam; } 4/3/2015 30