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.

ajaaaaksljdiwjihdi
NHÓM 6
1. Anh
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 <iostream>
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<<pTmp->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<n; i++)
{
cout<<"[-] Nhap gia tri node thu "<<i+1<<": ";
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 = "<<Average<<endl;
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 = "<<valueDel<<endl;
}
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;
}
}
| 1/9

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; } }