TRƯỜNG ĐẠI HỌC MỞ HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO BÀI TẬP LỚN MÔN:CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Nhóm 6 Đề 6 :Bài Toán Quản Lý Học Tập Của Học Sinh Phổ Thông Giảng viên hướng dẫn : Ths Trịnh Thị Xuân Sinh viên thực hiện: Nguyễn Huy Hải -2010A01 Nguyễn Quốc Hiếu -2010A04 Đặng Quang Huy -2010A04 Hoàng Trọng Mạnh -2010A03 Hà Nội 2021 1 Mục lục: I.Xác định bài toán……………………………………………………….Tìm cấu trúc dữ liệu biểu diễn bài toán……………………………….trang 3 Các chức năng cần đạt được của bài toán là:……………………….Lập trình –cài đặt…………………………………………………….trang 6 Liên kết đơn………………………………………………………….trang 6 Liên kết đôi………………………………………………………….trang 30 Ngăn xếp Stack…………………………………………………….Lập bộ test…………………………………………………………….trang 79 1 PHÂN CÔNG VÀ KẾ HOẠCH THỰC HIỆN HỌ VÀ TÊN CÔNG VIỆC THỜI GIAN GHI CHÚ THỰC HIỆN Nguyễn Huy Hải DSLK Đơn Hoàn thành Nguyễn Quốc Hiéu DSLK Đôi Hoàn thành Hoàng Trọng Mạnh Ngăn xếp Hoàn thành Đặng Quang Huy DSLK Đơn Hoàn thành 2 I. Xác định bài toán. Quản lý điểm học sinh trung học là công việc quản lý thông tin điểm của tất cả các môn học của một học sinh. Công tác quản lý điểm phục vụ cho học sinh là chủ yếu .Từ đó, học sinh có thể biết được kết quả mình đạt đưuọc sau mỗi kì học.
Ngoài ra, quản lý điểm học sinh còn giúp nhà trường theo dõi được tình hình học tập của từng học sinh trong trường. Từ đó, có thể đưa ra hình thức khen thưởng hay cảnh cáo đối với từng học sinh. Xác định CSDL biểu diễn bài toán. Đối tượng được quản lý bài toán bao gồm: Học sinh,Môn học, Bảng điểm - HỌC SINH : Mã học sinh, tên học sinh, giới tính, ngày sinh, địa chỉ - MÔN HỌC: Mã môn, tên môn, số buổi, số tiết.
- BẢNG ĐIỂM : Mã điểm, mã học sinh, mã môn học, điểm miệng, điểm 15 phút, điểm 1 tiết, điểm trung bình.Thuật toán Chương trình khi chạy ban đầu xuất xuất hiện danh sách lựa chọn chức năng: 1. Quản lý danh sách học sinh 2. Quản lý danh sách môn học 3 3. Quản lý danh sách bảng điểm Mời bạn chọn: Nếu chọn số 1, gồm các chức năng sau: 1.1 Nhập danh sách học sinh từ bàn phím 1.2 In danh sách học sinh lên màn hình 1.3 Lưu danh sách học sinh vào file 1.4 Đọc danh sách học sinh từ file 1.5 Tìm kiếm học sinh theo mã học sinh 1.6 Tìm kiếm học sinh theo lớp 1.7 Sắp xếp danh sách học sinh tăng dần theo mã học sinh 1.8 Thêm một học sinh mới 1.9 Xoá một học sinh ……………… ……………… Mời bạn chọn: Nếu bạn chọn số 2, gồm các chức năng: 2.1 Nhập và hiện danh sách môn học và ghi dữ liệu.2 Hiện danh sách môn học.3 In tên môn học có số tiết > x.4 Sắp xếp danh sách theo thứ tự giảm dần số buổi học.5 Đếm số môn học.6 Hiện những môn có số buổi >10.7 Tính tổng số buổi trong danh sách.8 Đọc dữ liệu từ file.
Mời bạn chọn: Nếu bạn chọn số 3, gồm các chức năng: 3.1 Nhập danh sách điểm và ghi dữ liệu 3.2 Hiện danh sách điểm lên màn hình.3 Tìm kiếm bảng điểm theo mã học sinh.4 Hiện bảng điểm có điểm trung bình cao nhất.5 Xóa thông tin bảng điểm ở đầu.6 Sắp xếp danh sách bảng điểm theo thứ tự tăng dần của điểm trung bình.7 Hiện thông tin bảng điểm có điểm trung bình lớn hơn x.8 Sửa thông tin bảng điểm theo mã học sinh.9 Đọc dữ liệu từ file ……………… ……………… Mời bạn chọn: 5 IV- Lập trình cài đặt Code liên kết đơn: #include<iostream> #include<iomanip> #include<string> #include<stdio.h> using namespace std; struct HOCSINH { string hoTen,gioiTinh,ngaySinh,diaChi; int maHs; }; struct NodeHocSinh { HOCSINH info; 6 struct NodeHocSinh *next; /* data */ }; struct List { NodeHocSinh *Head; NodeHocSinh *Tail; /* data */ }; //khoi tao danh sach rong struct List h; void initHs(List &h) { h.Tail=NULL; } NodeHocSinh *getNode(HOCSINH x) { NodeHocSinh *p; p=new NodeHocSinh; if(p==NULL) { cout<<"Loi!"; 7 exit(1); } else p->info=x; p->next=NULL; return p; } void addFirst(List &h, NodeHocSinh*p) { if(h.Head; } else { p->next=h.Head=p; } } void nhap1Hs(HOCSINH &x) { 8 cout<<"Nhap ma hoc sinh: ";cin>>x.maHs; cout<<"Nhap ten hoc sinh: "; cin.ignore(); getline(cin,x.hoTen); cout<<"Nhap gioi tinh: ";cin>>x.gioiTinh; cout<<"Nhap ngay sinh: ";cin>>x.ngaySinh; cout<<"Nhap dia chi: ";cin>>x.diaChi; } void in1Hs(HOCSINH x) { // ma ten gioi tinh ngaysinh diachi cout<<"\n"<<setw(7)<<x.maHs; cout<<setw(12)<<x.hoTen; cout<<setw(12)<<x.gioiTinh; cout<<setw(12)<<x.ngaySinh; cout<<setw(12)<<x.diaChi<<endl; } void nhapdshs(List &h) { int n; NodeHocSinh *p; HOCSINH x; cout<<"Nhap so hoc sinh: ";cin>>n; 9 for(int i=0;i<n;++i) { nhap1Hs(x); p=getNode(x); addFirst(h,p); } } void indshs(List &h) { NodeHocSinh *p; cout<<" =====Danh sach hoc sinh====== "<<endl; cout<<setw(7)<<" Ma "<<setw(12)<<" Ho ten "<<setw(12)<<" Gioi tinh "<<setw(12)<<" Ngay sinh "<<setw(12)<<" Dia chi "<<endl; for(p=h.Head;p!=NULL;p=p->next) { in1Hs(p->info); } } 10 //DANH SACH LIEN KET DON MON HOC struct Monhoc { string tenMonhoc; int maMh,soTiet,soBuoi; }; struct NodeMonhoc { Monhoc info; NodeMonhoc *next; }; struct ListMonhoc { NodeMonhoc *Head; NodeMonhoc *Tail; }; struct ListMonhoc m; void initMh(ListMonhoc &m) { m.Tail=NULL; } NodeMonhoc *getNodem(Monhoc x) 11 { NodeMonhoc *q; q=new NodeMonhoc; if(q==NULL) { cout<<"Loi! "; exit(1); } else q->info=x; q->next=NULL; return q; } void addFirstMonhoc(ListMonhoc &m,NodeMonhoc *q) { if(m.Tail; } else q->next=m.Head=q; } void nhapmonhoc(Monhoc &x) { cout<<"Nhap ma mon hoc: ";cin>>x.maMh; cout<<"Nhap ten mon hoc: "; cin.ignore(); getline(cin,x.tenMonhoc); cout<<"Nhap so buoi hoc: ";cin>>x.soBuoi; cout<<"Nhap so tiet hoc: ";cin>>x.soTiet; } void hienmonhoc(Monhoc x) { cout<<"\n"<<setw(7)<<x.maMh; cout<<setw(10)<<x.tenMonhoc; cout<<setw(14)<<x.soTiet; cout<<setw(8)<<x.soBuoi<<endl; } void nhapDsmh(ListMonhoc &m) { int n; cout<<"Nhap so mon hoc: ";cin>>n; Monhoc v; 13 for(int i=0;i<n;++i) { nhapmonhoc(v); NodeMonhoc *q=getNodem(v); addFirstMonhoc(m,q); } } void hienDsmh(ListMonhoc &m) { NodeMonhoc *q; cout<<" ================Danh sach mon hoc=================="<<endl; cout<<setw(7)<<" Ma mon hoc "<<setw(10)<<" Ten mon hoc "<<setw(10)<<" So tiet "<<setw(8)<<" So buoi "<<endl; for(q=m.Head;q!=NULL;q=q->next) { hienmonhoc(q->info); } } //DANH SACH BANG DIEM struct BangDiem { int maHocSinh, maDiem,maMonHoc,sohocsinh,somonhoc; 14 float diemMieng,diem15p,diem1tiet,diemTB; Monhoc dsmh[20]; HOCSINH ds[20]; }; struct NodeDiem { BangDiem info; struct NodeDiem *next; }; struct ListDiem { NodeDiem *Head; NodeDiem *Tail; }; struct ListDiem b; void initBd(ListDiem &b) { b.Tail=NULL; } NodeDiem *getNodeD(BangDiem x) { 15 NodeDiem *p; p=new NodeDiem; if(p==NULL) { cout<<"Loi! "; exit(1); } else p->info=x; p->next=NULL; return p; } void addFirstBang(ListDiem &b,NodeDiem *p) { if(b.Head; } else { p->next=b.Head=p; 16 } } void nhapBang(BangDiem &x) { cout<<"Nhap ma bang diem: ";cin>>x.maDiem; cout<<"Nhap ma hoc sinh: ";cin>>x.maHocSinh; cout<<"Nhap ma mon hoc: ";cin>>x.maMonHoc; cout<<"Nhap diem mieng: ";cin>>x.diemMieng; cout<<"Nhap diem 15p: ";cin>>x.diem15p; cout<<"Nhap diem 1 tiet: ";cin>>x.diem1tiet*3)/6; } void hienBang(BangDiem x) { cout<<"\n"<<setw(10)<<x.maDiem; cout<<setw(12)<<x.maHocSinh; cout<<setw(15)<<x.maMonHoc; cout<<setw(15)<<x.diemMieng; cout<<setw(15)<<x.diem15p; cout<<setw(15)<<x.diem1tiet; cout<<setw(15)<<x.diemTB<<endl; 17 } void nhapDsBang(ListDiem &b) { int n; cout<<"Nhap so bang diem: ";cin>>n; BangDiem x; NodeDiem *p; for(int i=0;i<n;++i) { cout<<"Nhap bang diem thu"<<i+1<<endl; nhapBang(x); p=getNodeD(x); addFirstBang(b,p); } } void hienDsBang(ListDiem &b) { NodeDiem *p; cout<<"-----------------------DANH SACH BANG DIEM----------------------------"<<endl; cout<<setw(10)<<"Ma diem"<<setw(12)<<"Ma hoc sinh"<<setw(15)<<"Ma mon hoc"<<setw(15)<<"Diem mieng"<<setw(15)<<"Diem 15p"<<setw(15)<<"Diem 1tiet"<<setw(15)<<"Diem TB"; for(p=b.Head;p!=NULL;p=p->next) 18 { hienBang(p->info); } } void ghiFile2(ListDiem &b) { FILE *f; NodeDiem *p = b.Head; f=fopen("Bangdiem.dat","wb"); while(p!=NULL) { fwrite(&p->info,sizeof(BangDiem),1,f); p=p->next; } fclose(f); cout<<"\n ghi file thanh cong!"<<endl; } void docFile2(ListDiem &b) { FILE *f; BangDiem x; 19 NodeDiem *p = b.Head; initBd(b); f=fopen("Bangdiem.dat","rb"); while(true) { fread(&x,sizeof(BangDiem),1,f); if(feof(f))break; addFirstBang(b,getNodeD(x)); } fclose(f); cout<<"Doc file thanh cong "<<endl; hienDsBang(b); } NodeDiem *timKiembangtheoMa(ListDiem &b,int k) { NodeDiem *p; for(p=b.Head;p!=NULL;p=p->next) { if(p->info.maHocSinh==k) break; } return p; } 20 void bangMax(ListDiem &b) { NodeDiem *p; float max=b.Head;p!=NULL;p=p->next) { if(max<p->info.diemTB) { max=p->info.Head;p!=NULL;p=p->next) { if(max==p->info.diemTB) { hienBang(p->info);cout<<p->info.diemTB; } } } void removeBang(ListDiem &b) { NodeDiem *p; if(b.Head->next; delete p; if(b.Tail=NULL; } } void sapxepTang(ListDiem &b) { BangDiem tg; NodeDiem *p,*q; for(p=b.Head;p!=NULL;p=p->next) { for(q=p->next;q!=NULL;q=q->next) { if(p->info.diemTB) { tg=p->info; p->info=q->info; q->info=tg; } 22 } } hienDsBang(b); } // hien thong tin bang diem co diem tb >x void hienTT(ListDiem &b) { float x; cout<<"Nhap x:";cin>>x; NodeDiem *p; for(p=b.Head;p!=NULL;p=p->next) { if(p->info.diemTB>x) { hienBang(p->info); } } } // sua thong tin bang diem theo ma hoc sinh. void suaBangDiem(ListDiem &b) { BangDiem x; NodeDiem *p; 23 int masua; cout<<"Nhap ma hoc sinh can sua:";cin>>masua; bool check = false; for(p=b.Head;p!=NULL;p=p->next) { if(p->info.maHocSinh==masua) { nhapBang(p->info); check =true; break; } } if(check == false) { cout<<"Khong tim thay bang diem!"; } else { cout<<" DANH SACH BANG DIEM SAU KHI SUA "<<endl; hienDsBang(b); } } 24 void menuBangDiem() { BangDiem x; ListDiem b; initBd(b); FILE *f; NodeDiem *p; int chon; do { cout<<"\n 1.Nhap danh sach bang diem va ghi du lieu.Hien danh sach bang diem .Tim kiem bang diem theo ma hoc sinh.Hien bang diem co diem trung binh cao nhat.Xoa thong tin bang diem o dau"; cout<<"\n 6.Sap xep danh sach theo thu tu tang dan cua diem TB"; cout<<"\n 7.Hien thong tin bang co diem TB >x"; cout<<"\n 8.Sua thong tin bang diem theo ma hoc sinh"; cout<<"\n 9.Doc du lieu tu file .Thoat!"; cout<<"\n Moi chon:";cin>>chon; 25 switch (chon) { case 1: nhapDsBang(b); ghiFile2(b); break; case 2: hienDsBang(b); break; case 3: int k; cout<<"Nhap k:"; cin>>k; p=timKiembangtheoMa(b,k); if(p==NULL) { cout<<"Khong tim thay"; exit(1); } else cout<<"Tim thay"<<endl; { hienBang(p->info); } break; case 4: bangMax(b); 26 break; case 5: removeBang(b); cout<<"==================DANH SACH BANG DIEM SAU KHI XOA=============="<<endl; hienDsBang(b); break; case 6: sapxepTang(b); break; case 7: hienTT(b); break; case 8: suaBangDiem(b); break; case 9: docFile2(b); // hienDsBang(b); default: break; } } while (chon!=0); } int main() { List h; 27 initHs(h); NodeHocSinh *p; HOCSINH x; Monhoc v; ListMonhoc m; initMh(m); FILE *f; NodeMonhoc *q; int chon; do { cout<<"\n 1.Nhap va hien danh sach hoc sinh"; cout<<"\n 2.Nhap va hien danh sach mon hoc"; cout<<"\n 3.Danh sach bang diem"; cout<<"\n 0.Thoat"; cout<<"\n Moi chon:";cin>>chon; switch (chon) { case 1: nhapdshs(h); indshs(h); break; 28 case 2: nhapDsmh(m); hienDsmh(m); break; case 3: menuBangDiem(); break; default: break; } } while (chon!=0); return 0; } Code liên kết đôi: #include<iostream> #include<iomanip> #include<string> #include<stdio.h> using namespace std; struct HOCSINH { string hoTen,gioiTinh,ngaySinh,diaChi; 29 int maHs; }; struct NodeHocSinh { HOCSINH info; NodeHocSinh *next; NodeHocSinh *prev; /* data */ }; struct List { NodeHocSinh *Head; NodeHocSinh *Tail; /* data */ }; //khoi tao danh sach rong struct List h; void hai(List &h) { h.Tail=NULL; 30 } NodeHocSinh *getNode(HOCSINH x) { NodeHocSinh *p; p=new NodeHocSinh; if(p==NULL) { cout<<"Loi!"; exit(1); } else p->info=x; p->next=NULL; p->prev=NULL; return p; } void addFirst(List &h, NodeHocSinh*p) { if(h.Head; 31 } else { p->next=h.Head=p; } } void nhap1(HOCSINH &x) { cout<<"Nhap ma hoc sinh: ";cin>>x.maHs; cout<<"Nhap ten hoc sinh: "; cin.ignore(); getline(cin,x.hoTen); cout<<"Nhap gioi tinh: ";cin>>x.gioiTinh; cout<<"Nhap ngay sinh: ";cin>>x.ngaySinh; cout<<"Nhap dia chi: ";cin>>x.diaChi; } void in1(HOCSINH x) { // ma ten gioi tinh ngaysinh diachi cout<<"\n"<<setw(7)<<x.maHs; cout<<setw(10)<<x.hoTen; 32 cout<<setw(15)<<x.gioiTinh; cout<<setw(15)<<x.ngaySinh; cout<<setw(15)<<x.diaChi; } void nhapds(List &h) { int n; NodeHocSinh *p; HOCSINH x; cout<<"Nhap so hoc sinh: ";cin>>n; for(int i=0;i<n;++i) { nhap1(x); p=getNode(x); addFirst(h,p); } } void inds(List &h) { NodeHocSinh *p; cout<<" =====Danh sach hoc sinh====== "<<endl; 33 cout<<setw(7)<<" Ma "<<setw(10)<<" Ho ten "<<setw(15)<<" Gioi tinh "<<setw(15)<<" Ngay sinh "<<setw(15)<<" Dia chi "<<endl; for(p=h.Head;p!=NULL;p=p->next) { in1(p->info); } } //DANH SACH LIEN KET DON MON HOC struct Monhoc { string tenMonhoc; int maMh,soTiet,soBuoi; }; struct NodeMonhoc { Monhoc info; struct NodeMonhoc *next; struct NodeMonhoc *prev; }; struct ListMonhoc 34 { NodeMonhoc *Head; NodeMonhoc *Tail; }; struct ListMonhoc m; void hai1(ListMonhoc &m) { m.Tail=NULL; } NodeMonhoc *getNodem(Monhoc v) { NodeMonhoc *q; q=new NodeMonhoc; if(q==NULL) { cout<<"Loi! "; exit(1); } else q->info=v; q->next=NULL; q->prev=NULL; 35 return q; } void addFirstMonhoc(ListMonhoc &m,NodeMonhoc *q) { if(m.Tail; } else { q->next=m.Head=q; } } void nhapmonhoc(Monhoc &v) { cout<<"Nhap ma mon hoc: ";cin>>v.maMh; cout<<"Nhap ten mon hoc: "; cin.ignore(); getline(cin,v.tenMonhoc); 36 cout<<"Nhap so buoi hoc: ";cin>>v.soBuoi; cout<<"Nhap so tiet hoc: ";cin>>v.soTiet; } void hienmonhoc(Monhoc v) { cout<<"\n"<<setw(7)<<v.maMh; cout<<setw(14)<<v.tenMonhoc; cout<<setw(15)<<v.soTiet; cout<<setw(8)<<v.soBuoi; } void nhapDsmh(ListMonhoc &m) { Monhoc x; int n; cout<<"Nhap so mon hoc: ";cin>>n; for(int i=0;i<n;++i) { nhapmonhoc(x); NodeMonhoc *q=getNodem(x); addFirstMonhoc(m,q); } } void hienDsmh(ListMonhoc &m) 37