Bài tập lớn cấu trúc dữ liệu và giải thuật | Đại học Kinh tế Kỹ thuật Công nghiệp
Mô tả: Xây dựng và so sánh các thuật toán tìm kiếm như Tìm kiếm tuyến tính (Linear Search) và Tìm kiếm nhị phân (Binary Search). Mô tả: Sử dụng cấu trúc dữ liệu cây nhị phân tìm kiếm (Binary Search Tree - BST) để quản lý thông tin sinh viên như mã số, tên, và điểm số. Kết quả: Chương trình cho phép người dùng thao tác với danh sách sinh viên qua các chức năng thêm, tìm kiếm, xóa và duyệt.
Môn: Cấu trúc dữ liệu và giải thuật (KTKTCN)
Trường: Đại học Kinh tế kỹ thuật công nghiệp
Thông tin:
Tác giả:
Preview text:
ajaaaaksljdiwjihdi NHÓM 6 1. Lê Anh Tú 2. Hồ Sỹ Qúy 3. Phạm Thị Hà Anh 4. Thái Thị Quỳnh Ngân
5. Nguyễn Thị Thu Hiền #include using namespace std; // Khoi tao node co 2 truong: struct Node { int info; Node *pNext; };
/* khoi tao cau truc list voi 2 con tro*/ struct SingleList {
Node *pHead; // Node dau pHead
Node *pTail; // Node cuoi pTail };
/* Ham khoi tao gia tri node dau va node cuoi */
void Init(SingleList &list) { list.pHead=list.pTail=NULL; } /*Ham tao node trong dslk */ Node *CreateNode(int d) { Node *pNode=new Node; if(pNode!=NULL) { pNode->info=d; pNode->pNext=NULL; } else {
cout<<"Khong the tao node"; } return pNode;} // Ham dem so node trong dslk:
int SizeOfList(SingleList list) { Node *pTmp=list.pHead; int nSize=0; while(pTmp!=NULL) { pTmp=pTmp->pNext; nSize++; } return nSize; }
void InsertFirst(SingleList &list,int d) { Node *pNode=CreateNode(d); if(list.pHead==NULL) { list.pHead=list.pTail=pNode; } else { pNode->pNext=list.pHead; list.pHead=pNode; } }
/* chen node vao cuoi danh sach */
void InsertLast(SingleList &list,int d) { Node *pNode=CreateNode(d); if(list.pHead==NULL) { list.pHead=list.pTail=pNode; } else { list.pTail->pNext=pNode; list.pTail=pNode; } } // Ham xoa node co gia tri X
int removeAll(SingleList &list, int x){ int count = 0; Node *p = list.pHead; Node *preX = list.pHead; while(p != NULL){ if(p->info == x){ Node *r = p;
// Neu x = Node dau tien => Delete First if(p == list.pHead){
list.pHead = list.pHead->pNext; p = list.pHead; preX = list.pHead; }else{ preX->pNext = p->pNext; p = p->pNext; } count++; delete r; continue;
// Neu != Node dau va == x => Xoa node do va duyet tiep } preX = p; p = p->pNext; } return count;
// Tra ve count de dem so node bi xoa } /* Ham xuat dslk: */
void PrintList(SingleList list) { Node *pTmp=list.pHead; if(pTmp==NULL) {
cout<<"DANH SACH RONG!!"; return; } while(pTmp!=NULL) {
cout<info<<" => "; pTmp=pTmp->pNext; } cout<<"NULL"; }
// Ham tinh tong gia tri cac node trong dslk:
float sumOfNodes(SingleList &list) { Node* ptr = list.pHead; int sum = 0; while (ptr != NULL) { sum += ptr->info; ptr = ptr->pNext; } return sum; }
//Ham sap xep cac node trong dslk:
void SortNode(SingleList &list) {
for(Node *p = list.pHead; p != NULL; p = p->pNext) {
for(Node *q = p->pNext; q != NULL; q = q->pNext) { if(p->info > q->info) { int x=p->info; p->info=q->info; q->info=x; } } } } void Menu() {
cout<<"\n\t\t============================================================ ===========\n";
cout<<"\n\t\t+------------------------------< MENU >-------------------------------+";
cout<<"\n\t\t| * HAY LUA CHON CONG VIEC BAN MUON THUC HIEN * |";
cout<<"\n\t\t+---------------------------------------------------------------------+";
cout<<"\n\t\t| 1. Nhap danh sach |";
cout<<"\n\t\t| 2. Hien thi danh sach |";
cout<<"\n\t\t| 3. Trung Binh cong cac phan tu |";
cout<<"\n\t\t| 4. Them nut vao dau danh sach |";
cout<<"\n\t\t| 5. Xoa nut co gia tri bat ki trong danh sach |";
cout<<"\n\t\t| 6. Sap xep theo thu tu tang dan cua truong info |";
cout<<"\n\t\t| 7.Exit - thoat khoi chuong trinh |";
cout<<"\n\t\t+---------------------------------------------------------------------+"; } int main() { SingleList list; Init(list);
int n, d, valueFirst, valueDel,lc; laplai: Menu();
cout<<"\n\n[+] Moi ban nhap lua chon: "; cin>>lc; switch(lc) { case 1:
cout<<"\n[-] Nhap vao so node trong dslk don: "; cin>>n; for(int i=0; i{
cout<<"[-] Nhap gia tri node thu "<cin>>d; InsertLast(list,d); } goto laplai; case 2:
cout<<"\n [-] DSLK vua nhap la: "; PrintList(list); goto laplai; case 3: float Average;
Average = sumOfNodes(list) / SizeOfList(list);
cout<<"\n[-] Trung binh cong cac node trong mang = "< goto laplai; case 4:
cout<<"\n[-] Nhap gia tri them vao dau: "; cin>>valueFirst;
InsertFirst(list, valueFirst);
cout<<"\n[-] Danh sach sau khi them: "; PrintList(list); goto laplai; case 5:
cout<<"\n[-] Nhap vao gia tri muon xoa: "; cin>>valueDel;
if(removeAll(list, valueDel) != 0){ removeAll(list, valueDel);
cout<<"[-] Danh sach sau khi xoa la: "; PrintList(list); }else{
cout<<"[!] Khong tim thay node->info = "< } goto laplai; case 6:
cout<<"\n[-] Danh sach truoc khi sap xep: "; PrintList(list); SortNode(list);
cout<<"\n[-] Danh sach sau khi sap xep: "; PrintList(list); goto laplai; case 7:
cout<<"\n\t\t\t\t* BAN DA KET THUC CHUONG TRINH! *"; break; default:
cout<<"Nhap sai lua chon, moi ban nhap lai. \n"; goto laplai; } }