Bài giảng Kĩ thuật lập trình cơ bản - Chương 4: Mảng một chiều - Trần Nguyễn Anh Chi

Nội dung text: Bài giảng Kĩ thuật lập trình cơ bản - Chương 4: Mảng một chiều - Trần Nguyễn Anh Chi

1. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Trường Cao đẳng Công nghệ Thông Tin Khoa Công nghệ Thông Tin CHƯƠNG 4 MẢNG MỘT CHIỀU GV: ThS. TRẦN NGUYỄN ANH CHI TpHCM, 02/2011 Đặt vấn đề Ví dụ . Chương trình cần lưu trữ 3 số nguyên? => Khai báo 3 biến int a1, a2, a3; . Chương trình cần lưu trữ 100 số nguyên? => Khai báo 100 biến kiểu số nguyên! . Người dùng muốn nhập n số nguyên? => Không thực hiện được! Giải pháp . Kiểu dữ liệu mới cho phép lưu trữ một dãy các số nguyên. 2 GV: ThS. Trần Nguyễn Anh Chi 1
2. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Dữ liệu kiểu mảng Khái niệm . Là một kiểu dữ liệu có cấu trúc do người lập trình định nghĩa. . 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ự . Kích thước được xác định ngay khi khai báo. . NNLT C luôn chỉ định một khối nhớ liên tục cho một biến kiểu mảng. 3 Dữ liệu kiểu mảng (tt) Khai báo [ ]; Ví dụ 1 int Mang1Chieu[10]; 0 1 2 3 4 5 6 7 8 9 Chỉ số Mang1Chieu 1 3 -1 7 -2 9 0 4 5 -1 Giá trị Ví dụ 2 float a[7]; 0 1 2 3 4 5 6 Chỉ số a 1.2 -1 2.5 3.7 8.1 -9 5.2 Giá trị 4 GV: ThS. Trần Nguyễn Anh Chi 2
3. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Số phần tử mảng 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 chưa có giá trị int n1; int a[n1]; //sai int n2 = 10; int a[n2]; Nên sử dụng chỉ thị tiền xử lý #define để định nghĩa số phần tử mảng #define n3 10 int a[n3]; //  int a[10]; 5 Khởi tạo giá trị cho mảng . Khởi tạo giá trị cho mọi phần tử của mảng int a[4] = {123, 456, -789, 100}; 0 1 2 3 a 123 456 -789 100 . Khởi tạo giá trị cho một số phần tử đầu mảng int a[4] = {123, -456}; 0 1 2 3 a 123 -456 0 0 6 GV: ThS. Trần Nguyễn Anh Chi 3
4. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Khởi tạo giá trị cho mảng(tt) . 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 . Tự động xác định số lượng phần tử của mảng int a[] = {123, -456, 789, 100}; 0 1 2 3 a 123 -456 789 100 7 Truy xuất đến một phần tử trong mảng Truy xuất thông qua chỉ số Ví dụ: cho mảng như sau: 0 1 2 3 int a[4]; 11 22 33 44 Các truy xuất: . Hợp lệ: a[0], a[1], a[2], a[3] . Không Hợp lệ: a[-2], a[-1], a[4], a[5] Chỉ số không hợp lệ thường cho kết quả không mong muốn 8 GV: ThS. Trần Nguyễn Anh Chi 4
5. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Truy xuất đến một phần tử (tt) i= 0 i= 1 i= 2 i= 3 i= 4 9 Một số thao tác trên mảng Nhập mảng Xuất mảng Đếm, tính tổng, tính trung bình Tìm kiếm Kiểm tra mảng thỏa điều kiện cho trước Sắp xếp Tách / ghép mảng Chèn / xóa 10 GV: ThS. Trần Nguyễn Anh Chi 5
6. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Nhập mảng Yêu cầu . Cho phép nhập mảng a, số lượng phần tử n Ý tưởng . Cho trước một mảng có số lượng phần tử là MAX. . Nhập số lượng phần tử thực sự n của mảng. . Nhập từng phần tử cho mảng từ chỉ số 0 đến n – 1. 0 1 2 3 n 4- 1 MAX - 1 11 Nhập mảng (tt) #define MAX 100 void NhapMang(int a[], int n) { int i; for (i=0; i >a[i]; } } 12 GV: ThS. Trần Nguyễn Anh Chi 6
7. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Xuất mảng Yêu cầu . Cho trước mảng a, số lượng phần tử n. Hãy xuất nội dung mảng a ra màn hình. Ý tưởng . Xuất giá trị từng phần tử của mảng từ chỉ số 0 đến n-1. 0 1 2 n - 1 MAX - 1 13 Xuất mảng (tt) void XuatMang(int a[], int n) { int i; for (i = 0; i >n; NhapMang(a,n); XuatMang(a,n); } 14 GV: ThS. Trần Nguyễn Anh Chi 7
8. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Liệt kê các phần tử thỏa điều kiện Yêu cầu . Cho trước mảng a, số lượng phần tử n. Hãy xuất các phần tử thỏa điều kiện nào đó. Ý tưởng . Duyệt từ đầu đến cuối mảng (từ chỉ số 0 đến n-1) . Tại vị trí thứ i, nếu a[i] thỏa điều kiện → xuất giá trị a[i] . Nếu không có giá trị nào thỏa điều kiện → xuất thông báo 15 Liệt kê các phần tử thỏa điều kiện (tt) Ví dụ 1: Liệt kê các số chẵn trong mảng void XuatChan(int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i]%2==0) cout<<a[i]<<“\t”; } Main: XuatChan(a,n); 16 GV: ThS. Trần Nguyễn Anh Chi 8
9. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Liệt kê các phần tử thỏa điều kiện (tt) void XuatChan(int a[], int n) //co thong bao { int i, flag=0; for (i = 0; i < n; i++) if(a[i]%2==0) { flag = 1; cout<<a[i]<<“\t”; } if(flag==0) cout<<“Khong co so chan trong mang”; } 17 Liệt kê các phần tử thỏa điều kiện (tt) Ví dụ 2: Liệt kê các số nguyên tố bool LaSNT(int x) { if(x<2) return false; int i, demus=0; for (i = 1; i <= x; i++) if(x%i==0) demus++; if(demus==2) return true; void XuatSNT(int a[], int n) return false; { } int i; for (i = 0; i < n; i++) if(LaSNT(a[i])==true) cout<<a[i]<<“\t”; } 18 GV: ThS. Trần Nguyễn Anh Chi 9
10. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Liệt kê các phần tử thỏa điều kiện (tt) void XuatSNT(int a[], int n) //co thong bao { int i, flag=0; for (i = 0; i < n; i++) if(LaSNT(a[i])==true) { flag = 1; cout<<a[i]<<“\t”; } if(flag==0) cout<<“Khong co SNTtrong mang”; } Main: 19 Đếm số lượng các phần tử thỏa đk Yêu cầu . Cho trước mảng a, số lượng phần tử n. Hãy đếm các phần tử thỏa điều kiện nào đó. Ý tưởng . Duyệt từ đầu đến cuối mảng . Tại vị trí thứ i, nếu a[i] thỏa điều kiện → tăng giá trị biến đếm . Trả về giá trị đếm được 20 GV: ThS. Trần Nguyễn Anh Chi 10
11. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Đếm số lượng (tt) Ví dụ 1: Đếm số lượng các số chẵn int DemChan(int a[], int n) { int i, dem=0; for (i = 0; i < n; i++) if(a[i]%2==0) dem++; return dem; } Main: int kq = DemChan(a,n); if(kq==0) cout<<“Khong co so chan”; else cout<<“SL so chan: “<<kq; 21 Đếm số lượng (tt) Ví dụ 2: Đếm số lượng các số nguyên tố int DemSNT(int a[], int n) { int i, dem=0; for (i = 0; i < n; i++) if(LaSNT(a[i])==true) dem++; return dem; } Main: 22 GV: ThS. Trần Nguyễn Anh Chi 11
12. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Tính tổng/tích các phần tử thỏa đk Yêu cầu . Cho trước mảng a, số lượng phần tử n. Hãy tính tổng/tích các phần tử thỏa điều kiện nào đó. Ý tưởng . Duyệt từ đầu đến cuối mảng . Tại vị trí thứ i, nếu a[i] thỏa điều kiện → cộng dồn/nhân dồn giá trị biến tổng/tích . Trả về giá trị tính được 23 Tính tổng/tích (tt) Ví dụ 1: Tính tổng các số chẵn int TongChan(int a[], int n) { int i, tong=0, flag=0; for (i = 0; i < n; i++) if(a[i]%2==0) { flag = 1; tong+=a[i]; } Main: if(flag==1) return tong; return -1; } 24 GV: ThS. Trần Nguyễn Anh Chi 12
13. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Tính tổng/tích (tt) Ví dụ 2: Tính tích các số nguyên tố long TichSNT(int a[], int n) { int i; long tich=1; for (i = 0; i < n; i++) if(LaSNT(a[i])==true) tich*=a[i]; return tich; } Main: 25 Tính trung bình các phần tử thỏa đk Yêu cầu . Cho trước mảng a, số lượng phần tử n. Hãy tính trung bình cộng các phần tử thỏa điều kiện nào đó. Ý tưởng . Duyệt từ đầu đến cuối mảng . Tại vị trí thứ i, nếu a[i] thỏa điều kiện → tăng giá trị biến đếm và cộng dồn . Tính trung bình = tổng/đếm . Trả về giá trị trung bình tính được 26 GV: ThS. Trần Nguyễn Anh Chi 13
14. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Tính trung bình (tt) Ví dụ 1: Tính trung bình cộng các số chẵn float TrungBinhChan(int a[], int n) { int i, dem=0, tong=0; for (i = 0; i < n; i++) if(a[i]%2==0) { tong+=a[i]; dem++; } return (float)tong/dem; } 27 Tính trung bình (tt) Ví dụ 2: Tính trung bình cộng các số nguyên tố float TrungBinhSNT(int a[], int n) { int i, dem=0, tong=0; for (i = 0; i < n; i++) if(LaSNT(a[i])==true) { tong+=a[i]; dem++; } if(dem!=0) return (float)tong/dem; return 0; } 28 GV: ThS. Trần Nguyễn Anh Chi 14
15. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Tìm kiếm giá trị thỏa đk Yêu cầu . Cho trước mảng a, số lượng phần tử n. Hãy tìm 1 phần tử thỏa điều kiện nào đó. Ý tưởng . Duyệt từ đầu đến cuối mảng . Tại vị trí thứ i, nếu a[i] thỏa điều kiện → trả về giá trị a[i], hoặc trả về vị trí thứ i 29 Tìm kiếm giá trị thỏa đk (tt) Ví dụ 1: Tìm giá trị lớn nhất mảng int TimMax(int a[], int n) { int i, max = a[0]; for (i = 1; i max) max = a[i]; return max; } 30 GV: ThS. Trần Nguyễn Anh Chi 15
16. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Tìm kiếm giá trị thỏa đk (tt) Ví dụ 2: Tìm vị trí của giá trị lớn nhất mảng int TimViTriMax(int a[], int n) { int i, max = a[0], vtmax = 0; for (i = 1; i max) { max = a[i]; vtmax = i; } return vtmax; } 31 Tìm kiếm giá trị thỏa đk (tt) Ví dụ 3: Tìm vị trí giá trị chẵn đầu tiên int TimChanDau(int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i]%2==0) return i; return -1; } 32 GV: ThS. Trần Nguyễn Anh Chi 16
17. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Kiểm tra tính chất mảng TH1: kiểm tra xem trong mảng có tồn tại 1 phần tử thỏa điều kiện nào đó hay không → tìm phần tử thỏa điều kiện rồi kết luận Ý tưởng: . Duyệt từ đầu đến cuối mảng . Tại vị trí thứ i, nếu a[i] thỏa điều kiện → trả về true . Trả về false 33 Kiểm tra tính chất mảng (tt) TH2: kiểm tra xem tất cả các phần tử trong mảng có thỏa điều kiện nào đó hay không → tìm phần tử không thỏa điều kiện rồi kết luận Ý tưởng: . Duyệt từ đầu đến cuối mảng . Tại vị trí thứ i, nếu a[i] không thỏa điều kiện → trả về false . Trả về true 34 GV: ThS. Trần Nguyễn Anh Chi 17
18. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Kiểm tra tính chất mảng (tt) Ví dụ 1: Kiểm tra xem trong mảng có tồn tại giá trị lẻ hay không? bool KiemTraTonTaiLe(int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i]%2!=0) return true; return false; } 35 Kiểm tra tính chất mảng (tt) Ví dụ 2: Kiểm tra xem mảng có chứa toàn giá trị lẻ hay không? bool KiemTraToanLe(int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i]%2==0) return false; return true; } 36 GV: ThS. Trần Nguyễn Anh Chi 18
19. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Sắp xếp Có nhiều tiêu chí sắp xếp mảng: sắp tăng dần, sắp giảm dần, sắp chẵn tăng lẻ giảm Có nhiều thuật toán sắp xếp mảng: chọn trực tiếp, chèn trực tiếp, đổi chỗ trực tiếp Ý tưởng: . Sử dụng 2 biến i và j để so sánh tất cả cặp phần tử với nhau và hoán vị các cặp nghịch thế (sai thứ tự). tạm 58 0 1 2 n – 1 MAX - 1 51 15 86 68 i j j j j 37 Sắp xếp (tt) Ví dụ: Sắp xếp mảng tăng dần void HoanVi(int &x, int &y) { int tam=x; x = y; y = tam; } void SapTang(int a[], int n) { int i, j; for (i=0; i a[j]) HoanVi(a[i],a[j]); } 38 GV: ThS. Trần Nguyễn Anh Chi 19