Kỹ thuật lập trình - Bài 6: Một số bài toán kiểu cấu trúc - Ngô Hữu Dũng

Kỹ thuật lập trình Bài 6 – Một số bài toán kiểu cấu trúc TS. Ngô Hữu Dũng Bài toán phân số Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017152  Xây dựng dữ liệu cấu trúc  Tử số  Mẫu số  Viết hàm nhập giá trị  Điều kiện nhập: Mẫu số ≠ 0  Cách 1: Hàm trả về kiểu cấu trúc  Không có đối số  Kiểu trả về của hàm là cấu trúc  Cách 2: Truyền tham biến  Đối số là tham biến  Hàm không có kiểu trả về 1. struct t_phso{ 2. int tuso, mauso; 3. }; 4. struct t_phso nhapPS(); 5. void nhapPS2(struct t_phso*); Hàm nhập phân số - Trả về kiểu cấu trúc Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017153 1. struct t_phso nhapPS(){ // Trả về kiểu struct 2. struct t_phso ps; 3. printf("Nhap tu so: "); 4. scanf("%d",&ps.tuso); 5. do{ 6. printf("Nhap mau so (!=0): "); 7. scanf("%d",&ps.mauso); 8. }while(ps.mauso==0); // Kiểm tra mẫu số 9. return ps; 10.} 11.struct t_phso a; 12.a = nhapPS(); // Gán giá trị của hàm cho biến Hàm nhập phân số - Truyền tham biến Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017154 1. void nhapPS2(struct t_phso *ps)// Tham biến 2. { 3. printf("Nhap tu so: "); 4. scanf("%d",&ps->tuso); // Dùng dấu -> 5. do{ 6. printf("Nhap mau so (!=0): "); 7. scanf("%d",&ps->mauso); 8. }while(ps->mauso==0); // Kiểm tra mẫu số 9. } 10.struct t_phso b; 11.nhapPS2(&b); // Gọi hàm, tham biến: &b Chú ý C và C++ Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017155  Hàm bên là cách viết của C++  Khai báo biến, đối số không cần viết struct phía trước  Dùng dấu & cho tham biến  Báo lỗi ở trình biên dịch C chuẩn 1. void nhapPS3(t_phso &); 2. void nhapPS3(t_phso &ps) 3. { 4. printf("Nhap tu so: "); 5. scanf("%d",&ps.tuso); 6. do{ 7. printf("Nhap mau so: "); 8. scanf("%d",&ps.mauso); 9. }while(ps.mauso==0); 10.} 11.t_phso a; 12.nhapPS3(a); Tham biến và kiểu con trỏ Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017156  Trong C chuẩn, để truyền tham biến, ta dùng kiểu con trỏ  Kiểu con trỏ  Lưu địa chỉ của ô nhớ chứa biến  Khai báo:  * ;  Ví dụ: int * p;  Sử dụng:  p: Địa chỉ ô nhớ của biến  *p: Giá trị của biến  Sẽ học kỹ ở phần sau 1. int x=20; // Biến nguyên 2. int *p; // Biến con trỏ 3. p = &x; // Gán địa chỉ 4. printf("x = %d \n", x); 5. printf("&x = %x \n", &x); 6. printf("p = %p \n", p); 7. printf("*p = %d \n", *p); 8. p = NULL; // Giá trị rỗng 9. printf("p = %p.", p); Truyền tham biến dùng kiểu con trỏ Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017157 1. void swap (int *px, int *py) // Hoán vị 2. { 3. int temp = *px; // Dùng dấu * 4. *px = *py; // để truy cập giá trị 5. *py = temp; 6. } 7. int a = 5, b = 3; 8. swap(&a, &b); // Truyền địa chỉ của biến 9. printf("a = %d, b = %d", a, b); Mảng kiểu cấu trúc Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017158  Khai báo mảng một chiều  Kiểu cấu trúc phân số  Tối đa 10 phần tử  Viết hàm nhập giá trị cho mảng  Input: Mảng, số phần tử của mảng  Output: Nhập giá trị cho các phân số 1. #define MAX 10 2. void nhapMangPS(struct t_phso [], int); 3. // Khai báo prototype, có thể dùng [] hoặc không cho đối số kiểu mảng 4. struct t_phso mps[MAX]; Hàm nhập mảng kiểu cấu trúc Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017159 1. void nhapMangPS(struct t_phso m[], int n) 2. { 3. int i; 4. for(i=0;i<n;i++) 5. { 6. printf("Nhap phan so thu %d: \n",i+1); 7. m[i] = nhapPS(); // Gọi hàm nhập ps 8. } 9. } 10.// Cách viết: for(int i = 0;) là C++ 11.// m[] là tham biến, không cần dùng con trỏ Nhập mảng kiểu cấu trúc Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017160 1. // Khai báo mảng kiểu cấu trúc 2. struct t_phso mps[MAX]; 3. // Nhập số phần tử của mảng 4. do{ 5. printf("So phan tu cua mang (1..%d): ",MAX); 6. scanf("%d",&n); 7. }while(!(n>0 && n<=MAX));//Kiểm tra điều kiện 8. // Hoặc while(nMAX); 9. nhapMangPS(mps,n); // Gọi hàm nhập mảng 10.// Truyền tham biến cho mảng không cần truyền địa chỉ (&mps) Hàm nhập mảng kiểu cấu trúc – dùng con trỏ Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017161 1. void nhapMangPS(struct t_phso *m, int n) 2. { 3. int i; 4. for(i=0;i<n;i++) 5. { 6. printf("Nhap phan so thu %d: \n",i+1); 7. m[i] = nhapPS(); 8. } 9. } 10.struct t_phso mps[MAX]; 11.nhapMangPS(&mps,n); Phép toán trên mảng cấu trúc Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017162  Viết hàm tính tổng các phân số trên mảng  Input: Mảng phân số kiểu cấu trúc, số phần tử của mảng  Output: Trả về kết quả là phân số kiểu cấu trúc  Gợi ý giải thuật  Viết hàm tính tổng hai phân số  Quy đồng mẫu số  Thực hiện phép cộng tử số  Rút gọn phân số kết quả Tìm ước số chung lớn nhất của tử số và mẫu số (viết hàm riêng) Chia tử số và mẫu số cho ước số chung lớn nhất  Lần lượt gọi hàm tính tổng hai phân số để tính tổng mảng các phân số Tổng mảng phân số Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017163 1. struct t_phso congMangPS(struct t_phso[], int); 2. struct t_phso congPS(struct t_phso, struct t_phso); 3. int UCLN(int, int); 4. struct t_phso congMangPS(struct t_phso mps[],int n) 5. { 6. struct t_phso ketqua = mps[0]; 7. int i; 8. for (i=1;i<n;i++) 9. ketqua = congPS(ketqua, mps[i]); 10. return ketqua; 11. } Cộng hai phân số Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017164 1. struct t_phso congPS(struct t_phso ps1, struct t_phso ps2) 2. { 3. struct t_phso psKQ; 4. int uocso; 5. psKQ.mauso=ps1.mauso*ps2.mauso; 6. psKQ.tuso=ps1.tuso*ps2.mauso+ps2.tuso*ps1.mauso; 7. // Rút gọn – Có thể làm hàm riêng 8. uocso = UCLN(psKQ.tuso,psKQ.mauso); 9. psKQ.tuso/=uocso; 10. psKQ.mauso/=uocso; 11. return psKQ; 12. } Ước số chung lớn nhất Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017165 1. int UCLN(int a, int b) 2. { 3. if(a<0)a=-a; //abs(a) 4. if(b<0)b=-b; //abs(b) 5. if(a==0||b==0)return a+b; 6. while(a!=b) 7. if (a>b) a-=b; 8. else b-=a; 9. return a; 10.} Vận dụng mảng cấu trúc - Quản lý điểm Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017166  Viết chương trình quản lý điểm và phân tích thống kê lớp học (20sv)  Mỗi bảng ghi sinh viên gồm: ID, tên, giới tính, điểm thường kỳ, giữa kỳ, cuối kỳ và điểm tổng kết (20% ĐTK + 30% ĐGK + 50% ĐCK).  Chương trình hiển thị menu danh sách các tác vụ để người dùng lựa chọn  1. Thêm một bảng ghi sinh viên  2. Xem tất cả danh sách bảng điểm của sinh viên  3. Xóa một bảng ghi sinh viên  4. Cập nhật một bảng ghi sinh viên  5. Tìm kiếm sinh viên bằng ID  6. Hiển thị sinh viên có số điểm cao nhất, thấp nhất  7. Sắp xếp danh sách sinh viên theo điểm tổng kết  8. Thoát chương trình Cấu trúc dữ liệu, header Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017167 1. #define MAX 20 2. typedef struct{ 3. int ID; 4. char name[50]; 5. char sex[10]; 6. float regular; 7. float midterm; 8. float final; 9. float total; 10.}t_student; 1. // Prototype - header 2. void addRecord(t_student, int*); 3. void showAllRecords(t_student, int); 4. void deleteRecord(t_student, int*); 5. void updateRecord(t_student, int); 6. void findStudent(t_student, int); 7. void showMaxScore(t_student, int); 8. void sortByScore(t_student, int); 9. int search(t_student, int, int); 10. void updateID(t_student, int, int); 11. void showRecord(t_student, int); 12. void deleteID(t_student, int*, int); 13. void showMenu(); Chương trình chính Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017168 1. void main(){ 2. t_student records[MAX]; // Mảng cấu trúc 3. int n=0, act; 4. do{ 5. showMenu(); // Gọi hàm hiển thị menu 6. printf("Enter your action: "); 7. scanf("%d", &act); 8. switch(act){ 9. case 1: addRecord(records,&n); break; 10. case 2: showAllRecords(records,n);break; 11. case 3: deleteRecord(records,&n);break; 12. case 4: updateRecord(records,n);break; 13. case 5: findStudent(records,n);break; 14. case 6: showMaxScore(records,n);break; 15. case 7: sortByScore(records,n);break; 16. } 17. }while(act!=8); 18. } Hiển thị menu Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017169 1. void showMenu() 2. { 3. printf("---------MENU - Student records---------\n"); 4. printf("1. Add a record\n"); 5. printf("2. Show all student records\n"); 6. printf("3. Delete a record\n"); 7. printf("4. Update a record\n"); 8. printf("5. Find a student by ID\n"); 9. printf("6. Show student who gets max total score\n"); 10. printf("7. Sort records by total score\n"); 11. printf("8. Exit\n"); 12. } Chức năng 1 - Thêm bảng ghi Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017170 1. void addRecord(t_student rec[],int *n) 2. { 3. int sID; 4. do{ 5. printf("Enter student ID: "); 6. scanf("%d",&sID); 7. if(search(rec,*n,sID)>-1) // Gọi hàm search 8. printf("This ID already exists\n"); 9. }while (search(rec,*n,sID)>-1); // Kiểm tra ID 10. updateID(rec,sID,*n); // Gọi hàm updateID 11. printf("Student %d was added\n", sID); 12. (*n)++; // Tăng số bảng ghi 13. } Hàm tìm kiếm Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017171 1. int search(t_student rec[],int n, int sID) 2. { 3. int i; 4. for(i=0;i<n;i++) 5. if(rec[i].ID==sID) 6. return i; 7. return -1; 8. } 9. // Nếu tìm thấy, trả về vị trí 10.// Nếu không tìm thấy, trả về -1 Cập nhật thông tin cho một ID Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017172 1. void updateID(t_student rec[],int sID, int n) 2. { 3. rec[n].ID=sID; 4. printf("Enter name: "); scanf("%s",&rec[n].name); 5. printf("Enter sex: "); scanf("%s",&rec[n].sex); 6. printf("Enter regular score: "); 7. scanf("%f",&rec[n].regular); 8. printf("Enter midterm score: "); 9. scanf("%f",&rec[n].midterm); 10. printf("Enter final score: "); 11. scanf("%f",&rec[n].final); 12. rec[n].total=0.2*rec[n].regular+0.3*rec[n].midterm+0.5 *rec[n].final; 13. } Chức năng 2 - Hiển thị tất cả các bảng ghi Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017173 1. void showAllRecords(t_student rec[],int n) 2. { 3. int i; 4. printf("-------All student records--------\n"); 5. printf("ID\tName\t\tSex\tReg\tMid\tFin\tTotal\n"); 6. for (i=0;i<n;i++) 7. showRecord(rec,i);// Gọi hàm hiển thị 1 bảng ghi 8. } Hiển thị 1 bảng ghi Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017174 1. void showRecord(t_student rec[],int i) 2. { 3. printf("%d\t",rec[i].ID); 4. printf("%-16s ",rec[i].name); 5. printf("%-8s",rec[i].sex); 6. printf("%.1f\t",rec[i].regular); 7. printf("%.1f\t",rec[i].midterm); 8. printf("%.1f\t",rec[i].final); 9. printf("%.2f\n",rec[i].total); 10.} Chức năng 3 – Xóa bảng ghi Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017175 1. void deleteRecord(t_student rec[],int *n) 2. { 3. int sID,num; 4. do{ 5. printf("Enter student ID to delete: "); 6. scanf("%d",&sID); 7. num = search(rec,*n,sID); 8. if(num==-1) 9. printf("ID not exist\n"); 10. }while(num==-1); 11. deleteID(rec,n,num); // Gọi hàm xóa bảng ghi 12. printf("Student %d was delelted\n", sID); 13. } Hàm xóa bảng ghi thứ num Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017176 1. void deleteID(t_student rec[],int *n,int num) 2. { 3. int i; 4. for (i=num+1;i<*n;i++) 5. rec[i-1]=rec[i]; // Dồn bảng ghi về trước 6. (*n)--; // Giảm số bảng ghi 7. } Chức năng 4 – Cập nhật bảng ghi Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017177 1. void updateRecord(t_student rec[],int n) 2. { 3. int sID,num; 4. do{ 5. printf("Enter student ID to update: "); 6. scanf("%d",&sID); 7. num = search(rec,n,sID); 8. if(num==-1) 9. printf("ID not exist\n"); 10. }while(num==-1); 11. updateID(rec,sID,num); // Gọi hàm, đã định nghĩa 12. printf("Student %d was updated\n", sID); 13. } Chức năng 5 – Tìm kiếm một bảng ghi Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017178 1. void findStudent(t_student rec[],int n) 2. { 3. int sID,num; 4. do{ 5. printf("Enter student ID: "); 6. scanf("%d",&sID); 7. num = search(rec,n,sID); 8. if(num==-1) 9. printf("ID not exist\n"); 10. }while(num==-1); 11. printf("ID\tName\t\tSex\tReg\tMid\tFin\tTotal\n"); 12. showRecord(rec,num); // Gọi hàm, đã định nghĩa 13. } Chức năng 6 – Tìm sinh viên có điểm cao nhất Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017179 1. void showMaxScore(t_student rec[],int n) 2. { 3. int i,max; 4. max=0; 5. for(i=1;i<n;i++) 6. if (rec[max].total<rec[i].total) 7. max=i; 8. printf("ID\tName\t\tSex\tReg\tMid\tFin\tTotal\n"); 9. showRecord(rec,max); // Gọi hàm, đã định nghĩa 10. } Chức năng 7 – Sắp xếp bảng ghi theo điểm Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017180 1. void sortByScore(t_student rec[],int n) 2. { 3. int i,j; 4. for (i=0;i<n;i++) // Sắp xếp nổi bọt 5. for (j=0;j<=n-2-i;j++) 6. if (rec[j].total<rec[j+1].total) 7. { 8. t_student temp = rec[j]; 9. rec[j]=rec[j+1]; 10. rec[j+1]=temp; 11. } 12. showAllRecords(rec,n); // Gọi hàm, đã định nghĩa 13. }