›
›

Bài giảng Giới thiệu lập trình - Chương 6: Cấu trúc mảng - Lê Nguyên Khôi

pdf 29 trang hoanguyen 3130
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Giới thiệu lập trình - Chương 6: Cấu trúc mảng - Lê Nguyên Khôi", để 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:

  • pdfbai_giang_gioi_thieu_lap_trinh_chuong_6_cau_truc_mang_le_ngu.pdf

Nội dung text: Bài giảng Giới thiệu lập trình - Chương 6: Cấu trúc mảng - Lê Nguyên Khôi

  1. Gi ới Thi ệu Lập Trình Cấu Trúc M ảng TS. Lê Nguyên Khôi Tr ườ ng Đại học Công ngh ệ, ĐHQGHN
  2. Nội Dung  Khái ni m chung  Truy n m ng vào hàm  Lp trình v i m ng Gi i Thi u L p Trình 1
  3. Đặt V ấn Đ ề  Ki n th c v ki u và bi n không bi u di n, x lý nh ng ki u d li u ph c t p, ví d :  Danh sách im thi c a m t sinh viên  Danh sách sinh viên c a l p h c  Cn l ưu tr và x lý m t chu i d li u cùng ki u  Sp x p, tìm ki m, tính toán trên chu i d li u  Ngôn ng l p trình (C++) cung c p các ki u d li u có c u trúc x lý các v n trên  Trong ó m ng là c u trúc d li u thông d ng nh t  Mng dùng l ưu tr d li u cùng ki ểu Gi i Thi u L p Trình 2
  4. Khái Ni ệm Chung  Mng m t chi u là chu i d li u có cùng ki u  t t i các ô nh liên ti p trong b nh  Mi ph n t m ng có m t ch s riêng bi t  S d ng ch s nh v & truy c p ph n t  Ví d : im thi 5 môn c a sinh viên l ưu tr trong m ng có 5 ph n t (m ng diemSo ) Ch ỉ số 0 1 2 3 4 Dữ li ệu 45 60 77 72 83  Mng trên có 5 ph n t , l ưu d li u ki u int , ch s b t u t 0 n 4 Gi i Thi u L p Trình 3
  5. Khái Ni ệm Chung Ch ỉ số 0 1 2 3 4 Dữ li ệu 45 60 77 72 83  Các ph n t c a m ng có th coi là bi n s tên diemSo[0] , diemSo[1] , diemSo[2] , diemSo[3] , diemSo[4] , có ki u d li u int  Ch s ph n t t trong ngo c vuông ( [] )  Truy c p ph n t m ng, s d ng :  Tên m ng ( diemSo )  Và ch s ph n t là m t giá tr nguyên hay bi u th c giá tr nguyên Gi i Thi u L p Trình 4
  6. Truy C ập M ảng Ch ỉ số 0 1 2 3 4 Dữ li ệu 45 60 77 72 83  S d ng tên m ng và ch s ph n t diemSo[2] = 74; // 77 -> 74 // v i i=1, câu l nh sau -> diemSo[3] = 75 diemSo[i+2] = 75; // 72 -> 75 // th c hi n tính toán tb = (diemSo[2] + diemSo[3]) / 2; //in ra 45 và 83 cout << diemSo[0] << " " << diemSo[4]; Gi i Thi u L p Trình 5
  7. Khai Báo  Mng ph i ư c khai báo tr ư c khi s d ng  Khi khai báo ph i quy nh s ph n t m ng  Cú pháp : Ki ểuDL TênM ảng [SốPh ầnT ử];  Ví d : int diemSo[5];  Khai báo m t m ng có tên diemSo , có 5 ph n t , lưu tr giá tr ki u int  Lưu ý :  S ph n t c a m ng không ư c thay i Gi i Thi u L p Trình 6
  8. Nh ập D ữ Li ệu  Mng sau khi khai báo, có th ư c nh p d li u, và th c ti n tính toán trên d li u m ng const int SO_MON_HOC = 5; int main() { int diemSo[SO_MON_HOC]; double tongDiem = 0.0; for (int i = 0; i > diemSo[i]; tongDiem += diemSo[i]; } cout << "diem trung binh: " << tongDiem / SO_MON_HOC; } Gi i Thi u L p Trình 7
  9. Kh ởi T ạo  Mng có th ư c kh i t o nh ư sau: int diemSo[5] = {45, 60, 77, 72, 83};  Lưu ý : s giá tr trong danh sách kh i t o (trong {} ) không ư c v ư t quá kích th ư c m ng (trong [] )  Mng c ng có th ư c kh i t o nh ư sau: int diemSo[] = {45, 60, 77, 72, 83};  C++ s t xác nh dài c a m ng d a trên dài ca danh sách kh i t o  Mng không ư c kh i t o, ph n t m ng có giá tr không xác nh (gi ng bi n) Gi i Thi u L p Trình 8
  10. Ứng D ụng  Th ng kê s l n ra m t giá tr t 1 n 6, sau 6000 l n tung xúc x c int main(){ const int SO_MAT = 6; int dem[SO_MAT + 1] = { 0 }; for (int t = 0; t < 6000; t++) { int mat = 1 + rand() % SO_MAT; dem[mat]++; } for (int m = 1; m <= SO_MAT; m++) { cout << m << "\t" << dem[m] << "\n"; } return 0; } Gi i Thi u L p Trình 9
  11. Qu ản Lý Ch ỉ Số Ph ần T ử  Khai báo m ng có kích th ư c SốPh ầnT ử, ch s các ph n t t 0 n SốPh ầnT ử - 1  Tt c các ch s khác không h p l  Truy c p vào các ch s không h p l , ví d diemSo[-1] , diemSo[SO_MON_HOC]:  Truy c p ra vùng b nh ngoài m ng  Không gây l i cú pháp (l i d ch)  Có th gây l i khi ch y ch ươ ng trình  Ch ươ ng trình ch y sai  Dng t ng t  Lp trình viên có trách nhi m ki m soát giá tr ch s Gi i Thi u L p Trình 10
  12. Truy ền M ảng Cho Hàm  Dùng tên m ng làm tham s truy n cho hàm void nhapMang(int diemSo [] ) { for (int i = 0; i > diemSo[i]; } int main() { int diemSo[SO_MON_HOC]; nhapMang(diemSo); return 0; }  Mng ư c truy n theo ki u tham chi u, nh ưng không s d ng toán t &  Hàm thay i giá tr trong m ng, k t thúc hàm, m ng thay i Gi i Thi u L p Trình 11
  13. Truy ền M ảng Cho Hàm  Nu không mu n hàm thay i giá tr trong m ng, s dng khai báo h ng s trong ch ký hàm i v i m ng  Thay i giá tr ph n t m ng (gán, nh p) gây l i d ch double dtb( const int diemSo[], int soPT) { double tong = 0.0; for (int i = 0; i < soPT; i++) tong += diemSo[i]; return (tong / soPT); } int main() { int diemSo[SO_MON_HOC]; nhapMang(diemSo); cout << "dtb: << dtb(diemSo, SO_MON_HOC); return 0; } Gi i Thi u L p Trình 12
  14. Xâu Ký T ự  Ki u d li u xâu ký (th ư vi n string ca C++)  Xâu ký t là m t chu i các ký t , k t thúc '\0' int main() { char ten1[20] = {'L','e',' ','B','e','\0'}; char ten2[20] = "Le Be"; cout > ten1; cin.getline(ten2, 15, '\n'); return 0; } Gi i Thi u L p Trình 13
  15. Lập Trình V ới M ảng  Nh p & in d li u  Tìm ki m d li u  Sp x p d li u  Thêm & lo i d li u Gi i Thi u L p Trình 14
  16. Nh ập & In void nhapMang(int a[], int soPhanTu){ for (int i = 0; i > a[i]; } void inMang(const int a[], int soPhanTu){ for (int i = 0; i < soPhanTu; i++) cout << a[i] << endl; } int main() { const int SO_MON_HOC = 10; int diemSo[SO_MON_HOC]; nhapMang(diemSo, SO_MON_HOC); inMang(diemSo, 5); return 0; } Gi i Thi u L p Trình 15
  17. Tìm Ki ếm  Tìm ki m giá tr có khóa k trong m ng  Bt u t u (ho c cu i), duy t t ng ph n t  Có ph n t giá tr b ng khóa tr v úng (tìm th y)  Ht m ng, không có, tr v sai (không tìm th y) bool timKiemBF{const int a[], int soPT, int k) { for (int i = 0; i = 0 && a[i] != k) i ; return (i >= 0); } Gi i Thi u L p Trình 16
  18. Tìm Ki ếm  Tìm ki m giá tr có khóa k trong m ng  Bt u t u (ho c cu i), duy t t ng ph n t  Có ph n t giá tr b ng khóa tr v ch s ph n t  Ht m ng, không có, tr v -1 (ngoài kho ng m ng) int timKiemIF{const int a[], int soPT, int k) { for (int i = 0; i = 0 && a[i] != k) i ; return i; } Gi i Thi u L p Trình 17
  19. Sắp X ếp L ựa Ch ọn  Ln l p 1:  Tìm ph n t nh nh t c a m ng  i ch v i ph n t u tiên  Ln l p 2:  Tìm ph n t nh th 2 ca m ng  i ch v i ph n t th 2  Ln l p 3:  Tìm ph n t nh th 3 ca m ng  i ch v i ph n t th 3 Gi i Thi u L p Trình 18
  20. Sắp X ếp L ựa Ch ọn  Coi m ng là 2 ph n:  Ph n u: các ph n t ã ư c s p x p úng ch  Ph n sau: các ph n t còn l i c n ư c s p x p  Mt giá tr ch s xác nh im phân cách 2 m ng  Lp  Tìm ph n t nh nh t trong m ng ch ưa s p x p  i ch lên u m ng ch ưa s p x p  Tng giá tr ch s lên 1 Gi i Thi u L p Trình 19
  21. Sắp X ếp L ựa Ch ọn void sapXepLuaChon(int a[], int soPT) { for (int i = 0; i < soPT – 1; i++) { // tìm ch s ph n t có giá tr nh nh t int minI = i; for (int j = i + 1; j < soPT; j++) if (a[j] < a[minI]) minI = j; // i ch lên u m ng ch ưa s p x p int tmp = a[i]; a[i] = a[minI]; a[minI] = tmp; } } Gi i Thi u L p Trình 20
  22. Thêm & Lo ại D ữ Li ệu  t v n :  Sinh viên ng ký l p môn h c  Sinh viên l n l ư t ng ký (thêm vào danh sách)  Sinh viên rút kh i l p môn h c (lo i kh i danh sách)  Kích th ư c c a danh sách l p môn h c ban u  S l ư ng sinh viên th c s c a l p môn h c Gi i Thi u L p Trình 21
  23. Thêm & Lo ại D ữ Li ệu  Thêm hay lo i d li u trong m ng làm thay i s ph n t m ng, không thay i kích th ư c  Bi n s qu n lý s ph n t th c s c a m ng  Bi n s này trong kho ng ch s h p l c a m ng  Ch ươ ng trình ph i qu n lý bi n s này  Thêm d li u  Tng s ph n t m ng  Ph i ki m tra m ng có y hay không  Lo i d li u  Gi m s ph n t m ng  Ph i ki m tra ph n t có trong m ng hay không Gi i Thi u L p Trình 22
  24. Thêm Dữ Li ệu  Mng ch ưa s p x p  Thêm vào cu i cùng, sau ph n t cu i cùng  S d ng bi n s qu n lý s ph n t th c s  Nu m ng ch ưa y, thêm ư c, tr v úng bool them(int a[], int & soPT, int k) { if (soPT < SO_SINH_VIEN) { a[soPT] = k; soPT++; return true; } else { return false; } } Gi i Thi u L p Trình 23
  25. Lo ại D ữ Li ệu  Mng ch ưa s p x p  Ph n t b lo i có ch s là i (c n ph i tìm tr ư c)  i ch ph n t này v i ph n t cu i cùng  S d ng bi n s qu n lý s ph n t th c s bool loai(int a[], int & soPT, int i) { if (soPT = soPT) { return false; } else { // o ch a[i] và a[soPT-1] soPT ; return false; } } Gi i Thi u L p Trình 24
  26. Thêm Dữ Li ệu  Mng ã s p x p  Sau khi thêm m ng v n ph i ư c s p x p  Tìm v trí thêm khóa k  Bt u t v trí ó lùi các ph n t ra sau m t ch s bool them(int a[], int & soPT, int k) { if (soPT < SO_SINH_VIEN) { // tìm v trí thêm k (index) // lùi các ph n t ra sau, sau ó dsmssv[index] = k; soPT++; return true; } return false; } Gi i Thi u L p Trình 25
  27. Lo ại D ữ Li ệu  Mng ã s p x p  Sau khi lo i m ng vn ph i ư c s p x p  Tìm v trí lo i khóa k  Bt u v trí ó ti n các ph n t lên tr ư c mt ch s bool loai(int a[], int & soPT, int k) { if (soPT < 0) return false; // tìm v trí thêm k (index) // ti n các ph n t ra tr ư c soPT ; return true; } Gi i Thi u L p Trình 26
  28. Mảng Nhi ều Chi ều  Trò ch ơi c ca rô  Xem mã ngu n Gi i Thi u L p Trình 27
  29. Tham Kh ảo  c sách:  Ch ươ ng 5, Lp Trình Cơ Bn C++ Gi i Thi u L p Trình 28