Loading Preview
Sorry, preview is currently unavailable. You can download the paper by clicking the button above.
Trước khi vào bài, bạn đọc hãy chắc chắn rằng đã học qua từ bài 1 đến bài 7 trong seri “Danh sách kề sử dụng mảng” của loại bài cấu trúc dữ liệu và giải thuật. Tất cả các hàm trong bài thực hành này đều được nêu ra trong những bài trước vì thế, nếu quên bạn đọc có thể tự xem lại ở những bài trước.
Trên ngôn ngữ C/C++, viết chương trình thực hiện yêu cầu sau:
- 1. Định nghĩa một cấu trúc Sinh viên bao gồm các trường thông tin như sau: Mã Sinh viên (kiểu số nguyên), tên Sinh viên (kiểu chuỗi ký tự), lớp (kiểu chuỗi ký tự), điểm tổng kết (kiểu số thực), hạnh kiểm (Tốt, khá, trung bình, yếu).
- 2. Cài đặt một cấu trúc danh sách kề cho kiểu dữ liệu Sinh viên, với các thao tác: 1) Khởi tạo danh sách; 2) kiểm tra rỗng, kiểm tra đầy 3) thêm phần tử 4) Tìm kiếm phần tử trong danh sách; 5) Xóa phần tử cuối cùng khỏi danh sách; 6) Duyệt danh sách.
- 3. Chương trình chính: Sử dụng cấu trúc danh sách kề và các thao tác ở trên để:
– Nhập vào một danh sách liên kết kề gồm n Sinh viên (n bất kỳ).
– Hiển thị danh sách đã nhập ra màn hình.
-Liệt kê ra màn hình danh sách tất cả những Sinh viên thuộc lớp “D13CNPM”.
– Xóa phần tử cuối cùng khỏi danh sách.
Hiển thị lại danh sách sau khi xóa ra màn hình.
#include<stdio.h> #include<malloc.h> #include <string.h> struct sinhvien { int masv; char tensv[20]; char lop[20]; float dtk; char hk[15]; }; #define MAX 100 typedef struct DSKe{ sinhvien A[MAX]; int n; }DSKe; void KhoiTao (DSKe &ds){ ds.n = 0; } int KiemTraRong (DSKe ds){ if(ds.n==0) return 1; return 0; } int KiemTraDay (DSKe ds){ if(ds.n== MAX) return 1; return 0; } void Nhap(DSKe &ds){ printf ("Nhap so sinh vien = "); scanf ("%d",&ds.n); for (int i=0;i<ds.n;i++){ printf ("Nhap ma sinh vien : ");fflush(stdin); scanf("%d",&ds.A[i].masv); printf ("Nhap ten sinh vien : ");fflush(stdin); gets(ds.A[i].tensv); printf ("Nhap lop : ");fflush(stdin); gets(ds.A[i].lop); printf ("Nhap diem tong ket : ");fflush(stdin); scanf("%f",&ds.A[i].dtk); printf ("Nhap hanh kiem : ");fflush(stdin); gets(ds.A[i].hk); printf ("\n \n"); } } void DuyetDS (DSKe ds){ printf ("%-20s %-20s %-15s %-20s %-15s\n","Ma sinh vien","Ho ten ","Lop","Diem tong ket","Hanh kiem"); for (int i=0;i<ds.n;i++){ printf ("%-20d %-20s %-15s %-20.2f %-15s\n",ds.A[i].masv,ds.A[i].tensv,ds.A[i].lop,ds.A[i].dtk,ds.A[i].hk); } } void TimKiem(DSKe ds){ int p = 0, d = 0, B[10]; while (p<ds.n){ if (strcmp(ds.A[p].lop, "D13CNPM") == 0){ B[d] = p; d++; } p += 1; } if (d>0){ printf("\nDANH SACH SINH VIEN D13CNPM\n"); printf ("%-20s %-20s %-15s %-20s %-15s\n","Ma sinh vien","Ho ten ","Lop","Diem tong ket","Hanh kiem"); for (int i=0; i<d; i++) printf ("%-20d %-20s %-15s %-20.2f %-15s\n",ds.A[B[i]].masv,ds.A[B[i]].tensv,ds.A[B[i]].lop,ds.A[B[i]].dtk,ds.A[B[i]].hk); } else printf("Khong co phan tu can tim!\n"); } void XoaPhanTuCuoi(DSKe &ds){ //Dich chuyen for (int i=ds.n - 1; i<ds.n-1; i++) ds.A[i] = ds.A[i+1]; ds.n = ds.n - 1; } int main (){ DSKe ds; KhoiTao(ds); Nhap(ds); printf("\nDANH SACH SINH VIEN\n"); DuyetDS(ds); TimKiem(ds); XoaPhanTuCuoi(ds); printf("\nDANH SACH SAU KHI XOA PHAN TU CUOI\n"); DuyetDS(ds); }
Trong hướng dẫn này mình sẽ thực hiện một chương trình quản lý sinh viên sử dụng danh sách liên kết đơn.
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.
Chúng ta sẽ quản lý sinh viên với các thông tin cần thiết và các thao tác thêm, xóa và sắp xếp sinh viên.
Đề bài: Xây dựng chương trình quản lý sinh viên bằng DSLK đơn
Cho một sinh viên có cấu trúc: mã (int), tên (char *). Dùng danh sách liên kết đơn với con trỏ phead để thao tác:
- Khởi tạo list dạng con trỏ
- Thêm node vào cuối danh sách
- Sắp xếp theo mã
- Xóa node
Chương trình quản lý sinh viên sử dụng DSLK đơn
Chúng ta sẽ lần lượt tạo cấu trúc sinh viên, cấu trúc danh sách liên kết đơn và các thao tác liên quan.
Bài viết này được đăng tại [free tuts .net]
Đầu tiên chúng ta cần tạo một cấu trúc sinh viên với mã số sinh viên ma và tên sinh viên ten.
//tao cau truc sinh vien struct SinhVien { int ma; char ten[150]; };
Tiếp đến tạo cấu trúc dữ liệu của danh sách liên kết đơn với giá trị data và con trỏ pNext. Khởi tạo giá trị cho pHead và pTail bằng NULL.
//tao cau truc danh sach lien ket don struct Node { SinhVien *data; Node *pNext; }; struct SingleList { Node *pHead; }; //khoi tao danh sach lien ket don void Initialize(SingleList *&list) { list=new SingleList; list->pHead=NULL; }
Tạo một hàm NhapSinhVien() sử dụng cấu trúc SinhVien để nhập các thông tin của sinh viên như: MSSV và tên sinh viên
SinhVien *NhapSinhVien() { SinhVien *sv=new SinhVien; cout<<"Nhap MSSV:"; cin>>sv->ma; cin.ignore(); cout<<"Nhap ho va ten:"; gets(sv->ten); return sv; }
Bây giờ chúng ta bắt đầu tạo Node với các thông tin của cấu trúc SinhVien, sau đó thêm Node vào cuối danh sách.
//tao node sinh vien Node *CreateNode(SinhVien *sv) { Node *pNode=new Node; if(pNode!=NULL) { pNode->data=sv; pNode->pNext=NULL; } else { cout<<"cap phat bo nho that bai!!!"; } return pNode; } //them node vao cuoi danh sach void InsertLast(SingleList *&list,SinhVien *sv) { Node *pNode=CreateNode(sv); if(list->pHead==NULL) { list->pHead=pNode; } else { Node *pTmp=list->pHead; while(pTmp->pNext!=NULL) { pTmp=pTmp->pNext; } pTmp->pNext=pNode; } }
Sau khi thêm Node vào danh sách ta thực hiện các thao tác theo yêu cầu của đề bài. Đầu tiên là việc sắp xếp các sinh viên theo MSSV.
Ở bài tìm kiếm và sắp xếp trong danh sách liên kết đơn mình đã giới thiệu các bạn thao tác sắp xếp. Dựa vào đó ta chỉ cần biến đổi một chút sẽ có ngay hàm sắp xếp SortList() theo MSSV.
void SortList(SingleList *&list) { for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext) { for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) { SinhVien *svTmp=pTmp->data; SinhVien *svTmp2=pTmp2->data; if(svTmp2->ma<svTmp->ma) { int ma=svTmp->ma; char ten[150]; strcpy(ten,svTmp->ten); svTmp->ma=svTmp2->ma; strcpy(svTmp->ten,svTmp2->ten); svTmp2->ma=ma; strcpy(svTmp2->ten,ten); } } } }
Tương tự như hàm sắp xếp, để xóa một sinh viên dựa vào tên ta thực hiện vòng lặp while lặp từng phần tử trong danh sách. Nếu phần tử đó trùng với phần tử được nhập vào từ bàn phím ta thực hiện delete phần tử đó ra khỏi danh sách.
void RemoveNode(SingleList *&list,int ma) { Node *pDel=list->pHead; if(pDel==NULL) { cout<<"Danh sach rong!"; } else { Node *pPre=NULL; while(pDel!=NULL) { SinhVien *sv=pDel->data; if(sv->ma==ma) break; pPre=pDel; pDel=pDel->pNext; } if(pDel==NULL) { cout<<"khong tim thay MSSV: "<<ma; } else { if(pDel==list->pHead) { list->pHead=list->pHead->pNext; pDel->pNext=NULL; delete pDel; pDel=NULL; } else { pPre->pNext=pDel->pNext; pDel->pNext=NULL; delete pDel; pDel=NULL; } } } }
Sau khi thực hiện tạo các thao tác, ta chỉ cần tạo hàm main() và gọi các thao tác đó ra để sử dụng.
int main(int argc, char** argv) { SingleList *list; Initialize(list); SinhVien *teo=NhapSinhVien(); InsertLast(list,teo); SinhVien *ty=NhapSinhVien(); InsertLast(list,ty); SinhVien *bin=NhapSinhVien(); InsertLast(list,bin); PrintList(list); SortList(list); cout<<"\nSau khi sap xep:\n"; PrintList(list); cout<<"\Ban muon xoa sinh vien co MSSV: "; int ma; cin>>ma; RemoveNode(list,ma); cout<<"\nSau khi xoa:\n"; PrintList(list); }
Full code:
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; //tao cau truc sinh vien struct SinhVien { int ma; char ten[150]; }; //tao cau truc danh sach lien ket don struct Node { SinhVien *data; Node *pNext; }; struct SingleList { Node *pHead; }; //khoi tao danh sach lien ket don void Initialize(SingleList *&list) { list=new SingleList; list->pHead=NULL; } //nhap thong tin sinh vien SinhVien *NhapSinhVien() { SinhVien *sv=new SinhVien; cout<<"Nhap MSSV:"; cin>>sv->ma; cin.ignore(); cout<<"Nhap ho va ten:"; gets(sv->ten); return sv; } //tao node sinh vien Node *CreateNode(SinhVien *sv) { Node *pNode=new Node; if(pNode!=NULL) { pNode->data=sv; pNode->pNext=NULL; } else { cout<<"cap phat bo nho that bai!!!"; } return pNode; } //them node vao cuoi danh sach void InsertLast(SingleList *&list,SinhVien *sv) { Node *pNode=CreateNode(sv); if(list->pHead==NULL) { list->pHead=pNode; } else { Node *pTmp=list->pHead; while(pTmp->pNext!=NULL) { pTmp=pTmp->pNext; } pTmp->pNext=pNode; } } //hien thi danh sach void PrintList(SingleList *list) { Node *pTmp=list->pHead; if(pTmp==NULL) { cout<<"Danh sach rong"; return; } while(pTmp!=NULL) { SinhVien *sv=pTmp->data; cout<<sv->ma<<"\t"<<sv->ten<<"\n"; pTmp=pTmp->pNext; } } //sap xep void SortList(SingleList *&list) { for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext) { for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) { SinhVien *svTmp=pTmp->data; SinhVien *svTmp2=pTmp2->data; if(svTmp2->ma<svTmp->ma) { int ma=svTmp->ma; char ten[150]; strcpy(ten,svTmp->ten); svTmp->ma=svTmp2->ma; strcpy(svTmp->ten,svTmp2->ten); svTmp2->ma=ma; strcpy(svTmp2->ten,ten); } } } } //xoa void RemoveNode(SingleList *&list,int ma) { Node *pDel=list->pHead; if(pDel==NULL) { cout<<"Danh sach rong!"; } else { Node *pPre=NULL; while(pDel!=NULL) { SinhVien *sv=pDel->data; if(sv->ma==ma) break; pPre=pDel; pDel=pDel->pNext; } if(pDel==NULL) { cout<<"khong tim thay MSSV: "<<ma; } else { if(pDel==list->pHead) { list->pHead=list->pHead->pNext; pDel->pNext=NULL; delete pDel; pDel=NULL; } else { pPre->pNext=pDel->pNext; pDel->pNext=NULL; delete pDel; pDel=NULL; } } } } int main(int argc, char** argv) { SingleList *list; Initialize(list); SinhVien *teo=NhapSinhVien(); InsertLast(list,teo); SinhVien *ty=NhapSinhVien(); InsertLast(list,ty); SinhVien *bin=NhapSinhVien(); InsertLast(list,bin); PrintList(list); SortList(list); cout<<"\nSau khi sap xep:\n"; PrintList(list); cout<<"\Ban muon xoa sinh vien co MSSV: "; int ma; cin>>ma; RemoveNode(list,ma); cout<<"\nSau khi xoa:\n"; PrintList(list); cout<<"\n---------------------------\n"; cout<<"Chuong trinh nay duoc dang tai Freetuts.net"; }
Kết quả:
Như vậy là chúng ta đã thực hiện xong chương trình quản lý sinh viên sử dụng danh sách liên kết đơn. Hãy luyện tập thật nhiều nhé, chúc các bạn thực hiện thành công!!!