Bài báo cáo thực hành cấu trúc dữ liệu

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG KHOA CÔNG NGHỆ THÔNG TIN ---—&–--- BÀI BÁO CÁO THỰC HÀNH CẤU TRÚC DỮ LIỆU GIÁO VIÊN HƯỚNG DẪN: HỒ PHAN HIẾU NHÓM THỰC HÀNH: 07B SINH VIÊN THỰC HIỆN: NGUYỄN TRÍ CÔNG LỚP: 09T3 ĐỖ DUY TƯ LỚP : 09T2 ĐÀ NẴNG, 03/2011 ĐỀ BÀI 14: Quản lí thông tin số lượng sinh viên của từng lớp: tên lớp, số lượng sinh viên nam, số lượng sinh viên nữ. Tổ chức cấu trúc dữ liệu thích hợp để biểu diễn các thông tin trên và cài đặt các chức năng: Cập nhật thông tin số lượng sinh viên các lớp (thêm, sửa, xóa). Tính số lượng sinh viên tứng lớp = Số lượng nam + Số lượng nữ Tìm thông tin của một lớp (nhập tên lớp). In ra những lớp có số lượng sinh viên >=100 THUẬT TOÁN VÀ CÔNG VIỆC: -Công việc cần làm, bổ sung thêm 1 số công việc khác. Viết hàm khởi tạo nhập danh sách. Viết hàm nhập danh sách. Viết hàm viết hàm cập nhật danh sách bao gồm các công việc: Cập nhật số lượng sinh viên lớp (Số lượng nam, số lượng nữ). Sửa tên 1 lớp Viết hàm liệt kê thông tin tất cả các lớp. Viết hàm tìm kiếm àthông tin lớp(Nhập tên lớp). Tìm và in ra lớp có tổng số sinh viên >=100. Viết hàm xóa 1 lớp. Tính số lượng sinh viên từng lớp. Hàm hiển thị danh sách. - Xem xét phần viết hàm có sự thay đổi, kiểu trả về của hàm để sử dụng, viết đúng. -Tham khảo các hàm cần thiết để làm, đọc lại các phần đã dạy môn CẤU TRÚC DỮ LIỆU về phần danh sách liên kết trên lớp để viết bài thực hành trên máy tính. -Chi tiết công việc đã làm: Khai báo thư viện, và cấu trúc: //Chuong trinh quan li so luong sinh vien #include #include #include #include // Phan khai bao bien va cau truc int n;// So phan tu danh sach typedef char infor1[10]; typedef int infor2; struct LOP { infor1 tenlop; // ten lop infor2 slnam, slnu;// So luong nam va so luong nu LOP *next;// di den phan tu tiep theo }; typedef LOP *List; List F,p; Viết hàm khởi tạo danh sách. Khởi tạo danh sách: Khi mới khởi tạo danh sách rỗng ta cho F nhận giá trị NULL. void Create(List &F)// Tao danh sach rong { F=NULL; } Viết hàm nhập danh sách từ bàn phím. Viết hàm nhập mới danh sách từ bàn phím, có sử dụng hàm chèn phần tử là hàm “them”, hoặc cũng có thể viết gộp vào trong hàm nhập. Hàm “them” là hàm vừa thêm phần tử vào danh sách, vừa có thứ tự được sắp xếp trong khi thêm vào. void them(List &F,infor1 name,infor2 nnam,infor2 nnu) { List p,before,after; p=new LOP; strcpy((*p).tenlop,name);(*p).slnam=nnu;(*p).slnu=nnam; after=F; while((after!=NULL)&&(strcmp((*after).tenlop,name)<0)) { before=after; after=(*after).next; } (*p).next=after; if(F==after) F=p; else (*before).next=p; } Hàm nhập: void NewCreate(List &F) { int k; F=NULL; do { Nhap: printf("\nNhap ten Lop: "); fflush(stdin);gets(name); if(Search(F,name)) {printf("\nTen da co trong danh sach, vui long nhap lai!"); goto Nhap; } if(strlen(name)>0) { printf(" Nhap so luong nam:");scanf("%d", &nnam); printf(" Nhap so luong nu:");scanf("%d", &nnu); them(F, name, nnam, nnu); } }while(strlen(name)>0); printf("\nNhan ENTER de ve menu chinh"); getch(); } Hàm nhập bao gồm công việc: Nhập tên lớp Nhập số lượng nam Nhập số lượng nữ Trong khi nhập, nếu trùng tên lớp đã có trong danh sách thì báo: printf("\nTen da co trong danh sach, vui long nhap lai!"); để tránh trùng tên, có sử dụng nhãn goto để quay lại nhập lại. Lưu ý: Khi dùng hàm nhập để nhập 1 chuỗi tên, để đơn giản dùng hàm gets(tên_chuỗi); và nhớ dùng lệnh fflush(stdin); để xóa bộ nhớ đệm khi nhập nếu không sẽ có nhiều lỗi xảy ra. Hàm tìm kiếm. List Search(List F, infor1 name) { List p; p=F; while((p!=NULL)&&(strcmp((*p).tenlop,name)!=0)) p=(*p).next; return p; } Tìm kiếm phần tử phần tử tên name trong danh sách. Ta bắt đầu tìm kiếm phần tử đầu tiên được chỉ bởi F trở đi cho đến khi tìm được phần tử cần tìm hoặc đã kiểm tra xong phần tử cuối cùng mà không có thì dừng. Hàm Search(F,name) kiểu List, tìm và trả về địa chỉ của phần tử đầu tiên tìm được hoặc trả về giá trị kiểu NULL nếu tìm không có. Hàm cập nhật thông tin Lớp(Sửa tên LỚP hoặc sửa số lượng sinh viên nam, nữ). void Update(List &F) { char up; printf("\nNhap ten lop can cap nhat: "); fflush(stdin); gets(name); p=Search(F, name); if((p!=NULL)&&(strcmp((*p).tenlop,name)==0)) { strcpy((*p).tenlop,name); printf("\nBan co muon sua ten LOP (y/n)?"); scanf("%c",&up); if(up=='y'){ printf("\nNhap ten lop (New)"); fflush(stdin); gets(name); strcpy((*p).tenlop,name); } if(up=='n') printf("\n Huy bo sua ten lop."); printf("\n so luong nam:"); scanf("%d",&nnam); (*p).slnam = nnam; printf("\n so luong nu:"); scanf("%d",&nnu); (*p).slnu=nnu; printf("\n Da cap nhat thanh cong !"); } else printf("KO ton tai LOP "); printf("\nNhan ENTER de ve menu chinh"); getch(); } Nhập tên LỚP cần tìm kiếm, sử dụng hàm Search(F,name) tìm kiếm trong danh sách nếu có thì trả về con trỏ (*p), và làm các thao tác như sửa tên LỚP, cập nhật số lượng nam, số lượng nữ trong khi con trỏ p!=NULL thì cập nhật. Còn nếu không thì p trả về bằng NULL, thông báo không có tên lớp cần cập nhật. Hàm xóa 1 phần tử ra khỏi danh sách. void DeleteLop(List &F,List name) { List before,after; after=F; while((after!=NULL)&&(after!=name)) { before=after; after=(*after).next; } if(after!=NULL) { if(F==name) F=(*name).next; else (*before).next=(*name).next; delete name; } } Biến con trỏ before chỉ đến phần tử đứng ngay trước phần tử cần xóa, biến con trỏ after chỉ đến ngay sau phần tử chỉ bởi biến before. Hàm hiển thị danh sách void Display(List F) { List p; p=F; if(p==NULL) printf("\nDanh sach rong!"); else { printf("\nDanh sach lop va thong tin"); printf("\n Ten LOP |so luong NAM|So luong NU"); } while(p!=NULL) { printf("\n%10s %10d %10d", (*p).tenlop, (*p).slnam, (*p).slnu); p=(*p).next; } printf("\nNhan ENTER de ve menu chinh");getch(); } Ta liệt kê các phần tử kể từ phần tử đầu tiên được chỉ bởi con trỏ F và dựa vào trường lien kết next để lần lượt liệt kê các phần tử tiếp theo. Biến con trỏ p lần lượt chỉ đến từng phần tử trong danh sách, nếu p==NULL thì thông báo danh sách rỗng! . Còn không thì liệt kê danh sách gồm các cột: “Ten LOP |so luong NAM|So luong NU”. Các hàm thực hiện một số yêu cầu bài tập. Hàm menu dung để in ra thực đơn lựa chọn công việc cần làm, tùy thuộc số lượng công việc sử dụng lệnh ghép switch(n) {case 0: case 1: case 2: case k: case m: } và hàm do{ công việc cần làm } while(điều kiện); void menu() { printf("\n---------------------MENU LUA CHON-----------------------"); printf("\nLua chon cong viec thuc hien quan ly so luong sinh vien:"); printf("\n1. Nhap moi mot danh sach"); printf("\n2. Cap nhat thong tin so luong sinh vien cac lop"); printf("\n3. Tinh so luong sinh vien tung lop"); printf("\n4. Tim thong tin cua 1 lop"); printf("\n5. In ra lop co so luong sinh vien >=100"); printf("\n6. Liet ke danh sach"); printf("\n7. Xoa 1 LOP"); printf("\n0. Thoat"); printf("-----------------------------------------------------------"); } Tính số lượng sinh viên tứng lớp = Số lượng nam + Số lượng nữ void sosvlop(List F) { List p; p=F; printf("\nTong so luong sinh vien lop la:"); printf("\n Ten LOP|Tong so"); while(p!=NULL) { tong=0; tong=(*p).slnam+(*p).slnu; printf("\n%10s %10d", (*p).tenlop,tong); p=(*p).next; } printf("\nNhan ENTER de ve menu chinh"); getch(); } In ra những lớp có số lượng sinh viên >=100 void moreSV(List F) { List p; p=F; printf("\n Ten LOP | Tong so"); while(p!=NULL) { if((*p).slnu+(*p).slnam>=100) printf("\n%10s %17d", (*p).tenlop,(*p).slnu+(*p).slnam); p=(*p).next; } printf("\nNhan ENTER de ve menu chinh"); getch(); } Hàm xóa 1 LỚP. void DeleteLop(List &F,List name) { List before,after; after=F; while((after!=NULL)&&(after!=name)) { before=after; after=(*after).next; } if(after!=NULL) { if(F==name) F=(*name).next; else (*before).next=(*name).next; delete name; } } Biến before đứng trước ngay trước phần tử cần xóa, biến con trỏ after chỉ đến phần tử đứng ngay sau phần tử chỉ bởi biến before. Hàm main() Chương trình chính: main() { char k; Create(F); do{ menu(); printf("\n Nhap cong viec can lam: ");scanf("%d", &cv); switch(cv) { case 0: printf("\nBai tap nhom thuc hanh Cau truc du lieu:"); printf("\nNguyen Tri Cong Lop:09T3|Do Van Tu 09T2"); getch(); break; case 1: NewCreate(F); break; case 2: Update(F); break; case 3: sosvlop(F); break; case 4: printf("\nNhap ten LOP can tim"); fflush(stdin);gets(name); p=Search(F, name); if((p!=NULL)&&(strcmp((*p).tenlop,name)==0)) { printf("\nDanh sach lop va thong tin"); printf("\n Ten LOP|so luong NAM|So luong NU | Tong so"); printf("\n%10s %10d %10d %10d", (*p).tenlop, (*p).slnam, (*p).slnu, (*p).slnam+(*p).slnu); } else printf(" \nKhong co phan tu can tim"); break; case 5: moreSV(F); break; case 6: Display(F); break; case 7: printf("\nNhap ten LOP can tim"); fflush(stdin);gets(name); p=Search(F,name); if(p!=NULL) {printf("\nDanh sach lop va thong tin"); printf("\n Ten LOP |so luong NAM|So luong NU | Tong so"); printf("\n%10s %10d %10d %10d", (*p).tenlop, (*p).slnam, (*p).slnu, (*p).slnam+(*p).slnu); printf("\nBan Co muon xoa (y/n)?");scanf("%c",&k); if(k=='y') {DeleteLop(F,p); printf("\nXoa thanh cong!");} if(k=='n') printf("\n Ban da huy XOA") ; } break; } }while(cv!=0); getch(); } Kết quả màn hình hiện lênh như hình dưới đây: Hàm thực hiện các công việc từ 0 -> 7. Trong khi nhập vào không phải là một số trong bảng thực đơn MENU lựa chọn thì tiếp tục gọi hàm menu(); còn không thì gọi các hàm đã có sẵn trong chương trình để thực hiện công việc cần làm.