Bài giảng Kỹ thuật lập trình nâng cao - Chương 2: Kiểu dữ liệu có cấu trúc - Dương Thành Phết

Nội dung text: Bài giảng Kỹ thuật lập trình nâng cao - Chương 2: Kiểu dữ liệu có cấu trúc - Dương Thành Phết

1. TRƯỜNG CAO ĐẲNG CNTT TP.HCM KHOA CÔNG NGHỆ THÔNG TIN KỸ THUẬT LẬP TRÌNH NÂNG CAO Chương 2 KIỂU DỮ LIỆU CÓ CẤU TRÚC Giảng Viên: ThS. Dương Thành Phết Email: phetcm@gmail.com Website: 1 Tel: 0918158670 – facebook.com/DuongThanhPhet
2. NỘI DUNG 1. Kiểu dữ liệu mảng 1 chiều 2. Các thao tác trên mảng 1 chiều 3. Mảng 2 chiều 4. Kiểu chuổi ký tự 5. Kiểu cấu trúc – Mảng cấu trúc 6. Kiểu tập tin - File 2 2
3. 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU 1.1 Khái niệm Mảng thực chất là một biến bao gồm nhiều biến thành phần được cấp phát bộ nhớ liên tục. 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 (Vị trí). Giá trị 0 1 2 3 4 5 6 7 8 9 3 Vị trí 3
4. 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU 1.2. 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 4 4
5. 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU 1.3. Gán giá trị ban đầu cho mảng int a[5] = {3, 6, 8, 1, 12}; a[0] = 3, a[1] = 6, a[2] = 8, int a[10] = {0}; a[0]=a[1]=a[2]=a[3]= =a[9]=0 5 5
6. 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU 1.4. Truy xuất Vị trí 0 1 2 3 4 A[0] A[1] A[2] A[3] A[4] 6 6
7. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 1. Nhập/Xuất mảng 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”; } 7 7
8. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU void main ( ){ int a[MAX] , n; cout >n; NhapMang (a,n); cout<<“Cac gia tri cua mang vua nhap: ”<<endl; XuatMang (a,n); } 8 8
9. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU Xuất các phần tử thỏa điều kiện 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]; } 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]; 9 } 9
10. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 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) cout<<a[i]<<“\t”; } 10 10
11. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 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 x) cout<<a[i]<<“\t”; } 11 11
12. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 2.2. Đếm 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; 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; 12 12 }
13. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU Ví dụ 1: Đếm các phần tử có giá trị là số nguyên tố bool LaSNT(int k) { int d = 0; for (int i = 1; i <= k; i++) if (k % i == 0) d++; return (d == 2); } int DemSNT(int a[], int n){ int d = 0; for (int i = 0; i<n; i++) if (LaSNT(a[i]) ==true) d++; return d; 13 }
14. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU Ví dụ 2: Đếm các phần tử có trong mảng mà giá trị nhỏ hơn x 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; } 14
15. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 2.3. 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; 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; 15 15 }
16. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 2.4. Kiểm tra mảng có thỏa đk cho trước Trường hợp 1: 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. Mẫu 1: bool KiemTraTonTaiXXX(int a[], int n){ for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện) return true; return false; } 16 16
17. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU Trường hợp 2: 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. Mẫu 2: bool KiemTraXXX(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; } 17 17
18. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU Ví dụ 1: Kiểm tra xem mảng có tồn tại số lẻ không? bool KiemTraTonTaiLe(int a[], int n){ foreach (int giatri in a) if (giatri % 2 != 0) return true; return false; } 18 18
19. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 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; } 19 19
20. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 2.5. Tính toán các phần tử trong mảng 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; } 20 20
21. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU Ví dụ: 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; } 21 21
22. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 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; } 22 22
23. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU Ví dụ: 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; 23 } 23
24. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 2.6. Sắp xếp Minh họa thuật toán 12 2 8 5 1 6 4 i=1 j=i=2 j=i=3 j=i=4 j=i=5 j=i=6 j=i=7 24 24
25. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 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; } 25 25
26. 3. MẢNG 2 CHIỀU 3.1 Giới thiệu  Mảng hai chiều thực chất là mảng một chiều trong đó mỗi phần tử của mảng là một mảng một chiều, và được truy xuất bởi hai chỉ số dòng và cột.  Từ khái niệm trên ta có thể đưa ra một khái niệm về mảng nhiều chiều như sau: mảng có từ hai chiều trở lên gọi là mảng nhiều chiều. 26
27. 3. MẢNG 2 CHIỀU 3.2. Khai báo Cách 1: [ ]; Ví dụ: int A[5][10]; // Khai báo mảng int gồm 5 dòng, 10 cột float b[7][8]; // Khai báo mảng float gồm 7 dòng, 8 cột Cách 2 : ; Ví dụ: int A ; // Khai báo mảng động 2 chiều kiểu int float B ; // Khai báo mảng động 2 chiều kiểu float 27
28. 3. MẢNG 2 CHIỀU 3.3. Truy xuất Để truy xuất các thành phần của mảng hai chiều ta phải dựa vào chỉ số dòng và chỉ số cột. Ví dụ: int A[3][4] = { {2,3,9,4} , {5,6,7,6} , {2,9,4,7} }; Với các khai báo như trên ta có: A[0][0] = 2; A[0][1] = 3; A[1][1] = 6; A[1][3] = 6; 28
29. 3. MẢNG 2 CHIỀU 3.4. Các thao tác  Nhập/ xuất  Tìm kiếm  Đếm  Tính tổng/ trung bình  Sắp xếp dòng/ cột  Xóa dòng/ cột  Chèn thêm dòng/ cột 29
30. 3. MẢNG 2 CHIỀU 3.4. Ma trận vuông  Số dòng = Số cột  Đường chéo chính củama trận vuông: chỉsô ́ dòng = chỉsô ́ cột  Đường chéo phụ của ma trận vuông: chỉsô ́ cột + chỉsô ́ dòng = kích thước - 1 Chéo chính Chéo phụ 30
31. 4. CHUỖI KÝ TỰ 4.1. Giới thiệu Chuỗi ký tự là một dãy các phần tử, mỗi phần tử có kiểu ký tự. Khai báo cách 1: char [ ] ; Ví dụ: char chuoi[25]; Khai báo 1 mảng kiểu ký tự tên là chuoi có 25 phần tử (lưu được 24 ký tự, ký tự 25 là ký tự kết thúc chuỗi „\0‟ ) Khai báo cách 2: char * ; Ví dụ : char *chuoi; Chuỗi ký tự không giới hạn chiều dài 31
32. 4. CHUỖI KÝ TỰ 4.2. Nhập cin.getline(chuoi, số ký tự tối đa); Ví dụ: char *str; str = new char [30]; cin.getline(str, 30); 32
33. 4. CHUỖI KÝ TỰ 4.3. Các hàm thư viện –  Tính độ dài của chuỗi s int strlen(char s[]);  Sao chép nội dung chuỗi nguồn vào chuỗi đích strcpy(char đích[], char nguồn[]);  Chép n ký tự từ chuỗi nguồn sang chuỗi đích. Nếu chiều dài nguồn < n thì hàm sẽ điền khoảng trắng cho đủ n ký tự vào đích strncpy(char đích[], char nguồn[], int n); 33
34. 4. CHUỖI KÝ TỰ  Nối chuỗi s2 vài chuỗi s1 strcat(char s1[],char s2[]);  Nối n ký tự đầu tiên của chuỗi s2 vào chuỗi s1 strncat(char s1[],char s2[],int n);  So sánh 2 chuỗi s1 và s2 theo nguyên tắc thứ tự. Phân biệt chữ hoa và thường. Trả về: 0: nếu s1 bằng s2. >0: nếu s1 lớn hơn s2. <0: nếu s1 nhỏ hơn s2. int strcmp(char s1[],char s2[]); 34
35. 4. CHUỖI KÝ TỰ  So sánh n ký tự đầu tiên của s1 và s2, giá trị trả về tương tự hàm strcmp() int strncmp(char s1[],char s2[], int n);  So sánh chuỗi s1 và s2 nhưng không phân biệt hoa thường, giá trị trả về tương tự hàm strcmp() int stricmp(char s1[],char s2[]);  So sánh n ký tự đầu tiên của s1 và s2 nhưng không phân biệt hoa thường, giá trị trả về tương tự hàm strcmp() int strnicmp(char s1[],char s2[], int n); 35
36. 4. CHUỖI KÝ TỰ  Tìm sự xuất hiện đầu tiên của ký tư c trong chuỗi s. Trả về: NULL: nếu không có Địa chỉ c: nếu tìm thấy char *strchr(char s[], char c);  Tìm sự xuất hiện đầu tiên của chuỗi s2 trong chuỗi s1. Trả về: NULL: nếu không có Ngược lại: Địa chỉ bắt đầu chuỗi s2 trong s1 char *strstr(char s1[], char s2[]); 36
37. 4. CHUỖI KÝ TỰ Tách chuỗi: Nếu s2 có xuất hiện trong s1: Tách chuỗi s1 thành hai chuỗi: Chuỗi đầu là những ký tự cho đến khi gặp chuỗi s2 đầu tiên, chuỗi sau là những ký tự còn lại của s1 sau khi đã bỏ đi chuỗi s2 xuất hiện trong s1. Nếu s2 không xuất hiện trong s1 thì kết quả chuỗi tách vẫn là s1. char *strtok(char s1[], char s2[]); 37
38. 5. KIỂU CÓ CẤU TRÚC 5.1. Giới thiệu Cấu trúc thực chất là một kiểu dữ liệu do người dùng định nghĩa bằng cách sử dụng các kiểu dữ liệu cơ sở thành một kiểu dữ liệu phức hợp nhiều thành phần 38
39. 5. KIỂU CÓ CẤU TRÚC 5.2. Khai báo Cú pháp 1: struct struct SinhVien { { ; char MSSV[6] ; ; char HoTenSV[30]; bool Phai ; ; float Toan, Ly, Hoa; }; }; struct struct SinhVien SV; 39
40. 5. KIỂU CÓ CẤU TRÚC 5.2. Khai báo Cú pháp 2: typedef struct typedef struct { { ; char MSSV[6] ; ; char HoTenSV[30]; bool Phai ; ; float Toan, Ly, Hoa; } ; }Sinhvien; SinhVien SV; 40
41. 5. KIỂU CÓ CẤU TRÚC 5.3. Khởi tạo cấu trúc  Việc khởi tạo cấu trúc có thể được thực hiện trong lúc khai báo biến cấu trúc.  Các trường của cấu trúc được khởi tạo được đặt giữa 2 dấu { và }, chúng được phân cách nhau bởi dấu phẩy (,). struct SinhVien SV={„sv01‟,‟nguyen thi lan‟,0,6.0,7.5,8.0}; 41
42. 5. KIỂU CÓ CẤU TRÚC 5.4. Truy xuất từng trường trong biến cấu trúc Cú pháp: . ; s = SV.HoTenSV; // nguyen thi lan 42
43. 5. KIỂU CÓ CẤU TRÚC 5.5. Mảng cấu trúc  Cách khai báo tương tự như mảng một chiều hay ma trận (Kiểu dữ liệu nhưng kiểu dữ liệu của mỗi phần tử là kiểu dữ liệu có cấu trúc).  Cách truy cập phần tử trong mảng cũng như truy cập trên mảng một chiều hay ma trận. Nhưng do từng phần tử có kiểu cấu trúc nên phải chỉ định rõ cần lấy thành phần nào. 43
44. 5. KIỂU CÓ CẤU TRÚC struct PhanSo { int tu, mau; }; struc PhanSo ps; void main() { int n; //Kích thước của mảng PhanSo a[100]; //Mảng các phân số //Các lệnh } 44
45. 5. KIỂU CÓ CẤU TRÚC  Do kiểu dữ liệu có cấu trúc thường chứa rất nhiều thành phần nên khi viết chương trình loại này ta cần lưu ý:  Xây dựng hàm xử lý cho một kiểu cấu trúc.  Muốn xử lý cho mảng cấu trúc, ta gọi lại hàm xử lý cho một kiểu cấu trúc đã được xây dựng bằng cách dùng vòng lặp. 45
46. 5. KIỂU CÓ CẤU TRÚC Bài tập 1. Định nghĩa kiểu: struct Hoso{ char Hoten[40]; float Diem; char Loai[10]; } Viết chương trình nhập thôn tin của n học sinh (Họ tên, điểm), xếp loại như sau: Điểm 9,10 Giỏi Điểm 7,8 Khá Điểm 5,6 Trung bình Điểm <5 Không đạt In DS như sau: XEP LOAI VAN HOA Họ tên Diem Xep loai Nguyen Thi Lan 8 Khá 46 Tran Van Diep 4 Khong dat
47. 5. KIỂU CÓ CẤU TRÚC Bài tập 2. Viết chương trình khai báo kiểu dữ liệu để biểu diễn một phân số. Hãy viết hàm thực hiện những công việc sau:  Rút gọn phân số.  Tính tổng, hiệu, tích, thương hai phân số (kết quả phải tối giản)  So sánh hai phân số. 47
48. 6. KIỂU TẬP TIN - FILE 6.1. Giới Thiệu  Tập tin văn bản: tập tin dùng để ghi các ký tự lên đĩa theo các dòng.  Tập tin nhị phân: tập tin dùng để ghi các cấu trúc dạng nhị phân (được mã hoá). 48
49. 6. KIỂU TẬP TIN - FILE 6.2. Thao tác với tập tin  Bước 1: Mởtậ p tin để đọc/ ghi.  Bước 2: Các xứ lý trêntậ p tin.  Bước 3: Đóng tập tin. 49
50. 6. KIỂU TẬP TIN - FILE 6.3. Lớp fstream -  Mở file fstream::open()  Đọc file fstream::Operator >>  Ghi dữ liệu vào file fstream::Operator <<  Đóng file fstream::close() 50
51. 6. KIỂU TẬP TIN - FILE  Tạo tập tin văn bản void main() { fstream file(“d:\\file_text.txt”, ios::out); file<<“Write to file"; file.close(); } 51
52. 6. KIỂU TẬP TIN - FILE  Đọc toàn bộ tập tin văn bản void main() { char str[2000]; fstream file(“d:\\file_text.txt”, ios::in); while(file >> str) cout << str ; file.close(); } 52
53. 6. KIỂU TẬP TIN - FILE  Đọc từng dòng tập tin văn bản void main() { char str[2000]; fstream file(“d:\\file_text”, ios::in); while(!file.eof()) { file.getline(str,2000); cout <<str; } file.close(); } 53
54. The End. 54