Bài giảng 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

Nội dung text: Bài giảng 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

1. 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
2. Bài toán phân số  Xây dựng dữ liệu cấu trúc 1. struct t_phso{  Tử số 2.  Mẫu số int tuso, mauso;  Viết hàm nhập giá trị 3. };  Điều kiện nhập: Mẫu số ≠ 0  Cách 1: Hàm trả về kiểu cấu trúc 4. struct t_phso nhapPS();  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 5. void nhapPS2(struct t_phso*);  Hàm không có kiểu trả về 152 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
3. Hàm nhập phân số - Trả về kiểu cấu trúc 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 153 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
4. Hàm nhập phân số - Truyền tham biến 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 154 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
5. Chú ý C và C++ 1. void nhapPS3(t_phso &);  Hàm bên là cách viết 2. void nhapPS3(t_phso &ps) của C++ 3. {  Khai báo biến, đối số 4. printf("Nhap tu so: "); không cần viết struct 5. scanf("%d",&ps.tuso); phía trước 6. do{ 7. printf("Nhap mau so: ");  Dùng dấu & cho tham 8. scanf("%d",&ps.mauso); biến 9. }while(ps.mauso==0);  Báo lỗi ở trình biên 10.} dịch C chuẩn 11.t_phso a; 12.nhapPS3(a); 155 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
6. Tham biến và kiểu con trỏ  Trong C chuẩn, để truyền tham 1. int x=20; // Biến nguyên biến, ta dùng kiểu con trỏ 2. int *p; // Biến con trỏ  Kiểu con trỏ  Lưu địa chỉ của ô nhớ chứa biến 3. p = &x; // Gán địa chỉ  Khai báo: 4. printf("x = %d \n", x);  * ; 5.  Ví dụ: int * p; printf("&x = %x \n", &x); 6. printf("p = %p \n", p);  Sử dụng: 7. printf("*p = %d \n", *p);  p: Địa chỉ ô nhớ của biến 8. p = NULL; // Giá trị rỗng  *p: Giá trị của biến 9. printf("p = %p.", p);  Sẽ học kỹ ở phần sau 156 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
7. Truyền tham biến dùng kiểu con trỏ 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); 157 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
8. Mảng kiểu cấu trúc  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]; 158 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
9. Hàm nhập mảng kiểu cấu trúc 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ỏ 159 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
10. Nhập mảng kiểu cấu trúc 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); 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) 160 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
11. Hàm nhập mảng kiểu cấu trúc – dùng con trỏ 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); 161 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12. Phép toán trên mảng cấu trúc  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ố 162 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
13. Tổng mảng phân số 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. } 163 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
14. Cộng hai phân số 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. } 164 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
15. Ước số chung lớn nhất 1. int UCLN(int a, int b) 2. { 3. if(a b) a-=b; 8. else b-=a; 9. return a; 10.} 165 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
16. Vận dụng mảng cấu trúc - Quản lý điểm  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 166 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
17. Cấu trúc dữ liệu, header 1. #define MAX 20 1. // Prototype - header 2. void addRecord(t_student, int*); 2. typedef struct{ 3. void showAllRecords(t_student, int); 4. void deleteRecord(t_student, int*); 3. int ID; 5. void updateRecord(t_student, int); 4. char name[50]; 6. void findStudent(t_student, int); 7. void showMaxScore(t_student, int); 5. char sex[10]; 8. void sortByScore(t_student, int); 6. float regular; 9. int search(t_student, int, int); 7. float midterm; 10. void updateID(t_student, int, int); 11. void showRecord(t_student, int); 8. float final; 12. void deleteID(t_student, int*, int); 9. float total; 13. void showMenu(); 10.}t_student; 167 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
18. Chương trình chính 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. } 168 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
19. Hiển thị menu 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. } 169 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
20. Chức năng 1 - Thêm bảng ghi 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. } 170 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
21. Hàm tìm kiếm 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 171 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
22. Cập nhật thông tin cho một ID 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. } 172 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
23. Chức năng 2 - Hiển thị tất cả các bảng ghi 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. } 173 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
24. Hiển thị 1 bảng ghi 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.} 174 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
25. Chức năng 3 – Xóa bảng ghi 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. } 175 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
26. Hàm xóa bảng ghi thứ num 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. } 176 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
27. Chức năng 4 – Cập nhật bảng ghi 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. } 177 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
28. Chức năng 5 – Tìm kiếm một bảng ghi 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. } 178 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
29. Chức năng 6 – Tìm sinh viên có điểm cao nhất 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. } 179 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
30. Chức năng 7 – Sắp xếp bảng ghi theo điểm 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. } 180 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng