Kĩ thuật lập trình - Chương 2: Kiểu dữ liệu có cấu trúc

1 Chương 2 KIỂU DỮ LIỆU CÓ CẤU TRÚC KỸ THUẬT LẬP TRÌNH NÂNG CAO TRƯỜNG CAO ĐẲNG CNTT TP.HCM KHOA CÔNG NGHỆ THÔNG TIN Giảng Viên: ThS. Dương Thành Phết Email: phetcm@gmail.com Website: Tel: 0918158670 – facebook.com/DuongThanhPhet 2 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 NỘI DUNG 3 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í). 3 0 1 2 3 4 5 6 7 8 9 Giá trị Vị trí 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU 4 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 [ ] ; 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU 5 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, 5 int a[10] = {0};  a[0]=a[1]=a[2]=a[3]==a[9]=0 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU 6 1.4. Truy xuất Vị trí 0 1 2 3 4 A[0] A[1] A[2] A[3] A[4] 6 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU 7 1. Nhập/Xuất mảng void NhapMang (int a[], int n){ for (int i = 0; i < n; i ++){ cout<<“Nhap phan tu thu “<<i<<“: “; cin>>a[i]; } } 7 void XuatMang (int a[], int n){ for (int i = 0; i < n; i ++) cout<<a[i]<<“\t”; } 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 8 void main ( ){ int a[MAX] , n; cout<<“Nhap kich thuoc mang: “; cin>>n; NhapMang (a,n); cout<<“Cac gia tri cua mang vua nhap: ”<<endl; XuatMang (a,n); } 8 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 9 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]; } 9 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]; } 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 10 Ví dụ 1: Liệt kê các phần tử có giá trị chẵn trong mảng 10 void LietKeChan(int a[], int n){ for (int i = 0; i<n; i++) if (a[i] %2 ==0) cout<<a[i]<<“\t”; } 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 11 Ví dụ 2: Liệt kê các phần tử có giá trị lớn hơn x trong mảng 11 void LietKeLonHonX(int a[], int n, int x){ for (int i = 0; i<n; i++) if (a[i] > x) cout<<a[i]<<“\t”; } 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 12 2.2. Đếm 12 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 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; } 13 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; } Ví dụ 1: Đếm các phần tử có giá trị là số nguyên tố 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 14 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; } 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 15 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 < n; i++) if (a[i] > a[vtmax]) vtmax = i; return vtmax; } 15 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 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; } 16 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. 16 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; } 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 17 17 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; } 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. 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 18 bool KiemTraTonTaiLe(int a[], int n){ foreach (int giatri in a) if (giatri % 2 != 0) return true; return false; } 18 Ví dụ 1: Kiểm tra xem mảng có tồn tại số lẻ không? 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 19 Ví dụ 2: Kiểm tra xem mảng có toàn giá trị âm không? (true: có/ false: không) 19 bool KiemTraToanAm(int a[], int n){ for (int i = 0; i<n; i++) if (a[i] >= 0) return false; return true; } 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 20 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 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 21 Ví dụ: Tính tổng các phần tử có giá trị lẻ trong mảng 21 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; } 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 22 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 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 23 Ví dụ: Tính giá trị trung bình các phần tử có giá trị âm trong mảng 23 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; } 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 24 Minh họa thuật toán 24 2 12 8 5 1 6 4 i=1 j=2 j=5 i j=3 j=4 i j=7 i j=6 i i i 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU 2.6. Sắp xếp 25 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 < n-1; i ++) for(int j = i+1; j < n; j ++) if (a[i] > a[j]) HoanVi(a[i], a[j]); } void HoanVi(int &a, int &b){ int tam = a; a = b; b = tam; }  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 3. MẢNG 2 CHIỀU 3.1 Giới thiệ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 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 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 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ủa ma 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 30 3. MẢNG 2 CHIỀU Chéo chính Chéo phụ 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 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 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 thi ̀ 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 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. Tra ̉ 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 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 4. CHUỖI KÝ TỰ  Tìm sự xuất hiện đầu tiên của ký tư c trong chuỗi s. Tra ̉ 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 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 ky ́ 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. 37 4. CHUỖI KÝ TỰ Nếu s2 không xuất hiện trong s1 thi ̀ kết quả chuỗi tách vẫn là s1. char *strtok(char s1[], char s2[]); 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 5. KIỂU CÓ CẤU TRÚC 5.2. Khai báo 39 5. KIỂU CÓ CẤU TRÚC Cú pháp 1: struct { ; ; .. ; }; struct struct SinhVien { char MSSV[6] ; char HoTenSV[30]; bool Phai ; float Toan, Ly, Hoa; }; struct SinhVien SV; 5.2. Khai báo 40 5. KIỂU CÓ CẤU TRÚC Cú pháp 2: typedef struct { ; ; .. ; } ; typedef struct { char MSSV[6] ; char HoTenSV[30]; bool Phai ; float Toan, Ly, Hoa; }Sinhvien; SinhVien SV; 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}; 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 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. 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 } 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. 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á 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ố. 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 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ên tập tin.  Bước 3: Đóng tập tin. 49 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 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 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 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 6. KIỂU TẬP TIN - FILE 54 The End.