Kỹ thuật lập trình cơ bản - Chương 4: Mảng một chiều

Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 1 Chương 4: Mảng một chiều GV: ThS. TRẦN NGUYỄN ANH CHI Trường Cao đẳng Công nghệ Thông Tin Khoa Công nghệ Thông Tin TpHCM, 02/2011 CHƯƠNG 4 MẢNG MỘT CHIỀU Đặ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 Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 2 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 4 []; 1 3 -1 7 -2 4 5 -19 0 0 1 2 3 4 7 85 6 9 Mang1Chieu Ví dụ 1 int Mang1Chieu[10]; 1.2 -1 2.5 3.7 8.1 -9 5.2 0 1 2 3 4 5 6 a Ví dụ 2 float a[7]; Chỉ số Giá trị Chỉ số Giá trị Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 3 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ị 5 Nên sử dụng chỉ thị tiền xử lý #define để định nghĩa số phần tử mảng int n1; int a[n1]; //sai int n2 = 10; int a[n2]; #define n3 10 int a[n3]; //  int a[10]; 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 6  Khởi tạo giá trị cho một số phần tử đầu mảng int a[4] = {123, 456, -789, 100}; 123 456 -789 100 0 1 2 3 a int a[4] = {123, -456}; 123 -456 0 0 0 1 2 3 a Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 4 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 7 int a[4] = {0}; 0 0 0 0 0 1 2 3 a  Tự động xác định số lượng phần tử của mảng int a[] = {123, -456, 789, 100}; 123 -456 789 100 0 1 2 3 a Truy xuất đến một phần tử trong mảng  Truy xuất thông qua chỉ số 8 Ví dụ: cho mảng như sau: 11 22 33 44 0 1 2 3 int a[4]; 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 Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 5 Chương 4: Mảng một chiều Truy xuất đến một phần tử (tt) 9 i= 0 i= 1 i= 2 i= 3 i= 4 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 Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 6 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. 11 40 1 2 3 MAX - 1n - 1 Nhập mảng (tt) 12 #define MAX 100 void NhapMang(int a[], int n) { int i; for (i=0; i<n; i++) //for(i=0; i<=n-1;i++) { cout<<“Phan tu thu: ”<<i; cin>>a[i]; } } Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 7 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. 13 0 1 2 MAX - 1n - 1 Xuất mảng (tt) 14 void XuatMang(int a[], int n) { int i; for (i = 0; i < n; i++) cout<<a[i]<<“\t”; } void main() { int n, a[MAX]; cout<<“Nhap so luong phan tu thuc su: “; cin>>n; NhapMang(a,n); XuatMang(a,n); } Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 8 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 16 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); Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 9 Chương 4: Mảng một chiều Liệt kê các phần tử thỏa điều kiện (tt) 17 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”; } 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ố 18 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; return false; } void XuatSNT(int a[], int n) { int i; for (i = 0; i < n; i++) if(LaSNT(a[i])==true) cout<<a[i]<<“\t”; } Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 10 Chương 4: Mảng một chiều Liệt kê các phần tử thỏa điều kiện (tt) 19 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: Đế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 Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 11 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 21 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; Đếm số lượng (tt) 22 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: Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 12 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 24 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]; } if(flag==1) return tong; return -1; } Main: Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 13 Chương 4: Mảng một chiều Tính tổng/tích (tt) 25 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: 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 Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 14 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 27 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; } Tính trung bình (tt) Ví dụ 2: Tính trung bình cộng các số nguyên tố 28 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; } Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 15 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 30 int TimMax(int a[], int n) { int i, max = a[0]; for (i = 1; i < n; i++) if(a[i]>max) max = a[i]; return max; } Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 16 Chương 4: Mảng một chiều Tìm kiếm giá trị thỏa đk (tt) 31 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 < n; i++) if(a[i] > max) { max = a[i]; vtmax = i; } return vtmax; } Tìm kiếm giá trị thỏa đk (tt) 32 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; } Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 17 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 Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 18 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? 35 bool KiemTraTonTaiLe(int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i]%2!=0) return true; return false; } 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? 36 bool KiemTraToanLe(int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i]%2==0) return false; return true; } Kỹ thuật lập trình cơ bản GV: ThS. Trần Nguyễn Anh Chi 19 Chương 4: Mảng một chiều Sắp xếp 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 37 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 Ý 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ự). 0 1 2 MAX - 1n – 1 5 1 8 6 tạm 5 i j 8 1 5 j j 6 8 j Sắp xếp (tt) Ví dụ: Sắp xếp mảng tăng dần 38 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<n-1; i++) for(j=i+1; j<n; j++) if(a[i]>a[j]) HoanVi(a[i],a[j]); }