圖書管理系統，數組存儲和鏈表存儲
#include <bits/stdc++.h> using namespace std; fstream in,out; int n=0; string temp[4]; struct book { string isbn; string name; double price; }b[205]; inline bool Check()//時間O（n）,空間O（1）。檢查是否讀入圖書信息 { if(n==0) { cout<<"請先選擇1讀取圖書信息\n"; return false; } return true; } inline void Input()//時間O（n）,空間O（1）。讀入圖書信息 { in.open("book.txt",ios::in); if(!in) { cout<<"未找到book.txt\n"; return; } n=1; for(int i=1;i<=4;++i)in>>temp[i]; while(!in.eof()) { in>>b[n].isbn>>b[n].name>>b[n].price; n++; } in.close(); } inline void Output()//時間O（n）,空間O（1）。輸出圖書信息 { if(Check()) { cout<<temp[1]<<"\n"<<left<<setw(15)<<temp[2]<<"\t"<<left<<setw(50)<<temp[3]<<"\t"<<left<<setw(5)<<temp[4]<<"\n"; for(int i=1;i<n;++i) { cout<<left<<setw(15)<<b[i].isbn<<"\t"<<left<<setw(50)<<b[i].name<<"\t"<<left<<setw(5)<<b[i].price<<"\n"; } } } inline void Length()//時間O（1）,空間O（1）。輸出圖書總冊數 { if(Check())cout<<"共"<<n-1<<"本書"<<endl; } inline void Find()//時間O（n）,空間O（1）。遍歷查找圖書 { if(Check()) { cout<<"請輸入要查找的圖書名字\n"; bool flag=false; string str; cin>>str; for(int i=1;i<n;++i) { if(str==b[i].name) { flag=true; cout<<left<<setw(15)<<b[i].isbn<<"\t"<<left<<setw(50)<<b[i].name<<"\t"<<left<<setw(5)<<b[i].price<<"\n"; } } if(flag==false)cout<<"沒有收錄該圖書\n"; } } inline void Get()//時間O（1）,空間O（1）。直接訪問圖書 { if(Check()) { cout<<"請輸入你要查看的序號\n"; int num; cin>>num; if(num<1||num>n-1) { cout<<"輸入非法\n"; return; } cout<<left<<setw(15)<<b[num].isbn<<"\t"<<left<<setw(50)<<b[num].name<<"\t"<<left<<setw(5)<<b[num].price<<"\n"; } } inline void Update()//時間O（n）,空間O（1）。將圖書信息存入book_out.txt文件里 { out.open("book_out.txt",ios::out); out<<temp[1]<<"\n"<<left<<setw(15)<<temp[2]<<"\t"<<left<<setw(50)<<temp[3]<<"\t"<<left<<setw(5)<<temp[4]<<"\n"; for(int i=1;i<n;++i) { out<<left<<setw(15)<<b[i].isbn<<"\t"<<left<<setw(50)<<b[i].name<<"\t"<<left<<setw(5)<<b[i].price<<"\n"; } out.close(); } inline void Insert()//時間O（n）,空間O（1）。在數組中插入新元素 { if(Check()) { int num; cout<<"請輸入要插入圖書的位置\n"; cin>>num; if(num<1||num>n) { cout<<"輸入非法\n"; return; } for(int i=n;i>num;--i) { b[i].isbn=b[i-1].isbn; b[i].name=b[i-1].name; b[i].price=b[i-1].price; } cout<<"請依次輸入要插入的圖書ISBN號，書名，價格\n"; cin>>b[num].isbn>>b[num].name>>b[num].price; n++; Update(); } } inline void Delete()//時間O（n）,空間O（1）。在數組中刪除元素 { if(Check()) { int num; cout<<"請輸入要刪除圖書的位置\n"; cin>>num; if(num<1||num>n-1) { cout<<"輸入非法\n"; return; } for(int i=num;i<n-1;++i) { b[i].isbn=b[i+1].isbn; b[i].name=b[i+1].name; b[i].price=b[i+1].price; } n--; Update(); } } inline void BubbleSort()//時間O（n^2）,空間O（1）。冒泡排序 { if(Check()) { for(int i=1;i<n-1;++i) { for(int j=1;j<n-i;++j) { if(b[j].price>b[j+1].price) { swap(b[j],b[j+1]); } } } Update(); } } inline void QuickSort(int left,int right)//時間O（nlog2n）,空間O（nlogn）。快速排序 { if(left>=right)return; int i=left,j=right; double temp=b[left].price; while(i<j) { while(b[j].price>=temp&&i<j)--j; swap(b[i],b[j]); while(b[i].price<=temp&&i<j)++i; swap(b[i],b[j]); } QuickSort(left,i-1); QuickSort(i+1,right); return; } inline void QueryMax()//時間O（n）,空間O（1）。查詢最大值 { if(Check()) { double mmax=b[1].price; int flag=1; for(int i=2;i<n;++i) { if(b[i].price>mmax) { flag++; mmax=b[i].price; } } for(int i=1;i<n;++i) { if(b[i].price==mmax) { cout<<left<<setw(15)<<b[i].isbn<<"\t"<<left<<setw(50)<<b[i].name<<"\t"<<left<<setw(5)<<b[i].price<<"\n"; } } } } inline void Inverse()//時間O（n）,空間O（1）。逆序存儲圖書信息 { if(Check()) { for(int i=1;i<=n/2;++i) { swap(b[i],b[n-i]); } } } int main() { while(1) { int opt; printf("歡迎使用圖書管理系統,請輸入整數來實現你需要的功能\n" "1.圖書數據加載，使用數組進行存儲\n" "2.輸出所有圖書信息\n" "3.總圖書冊數\n" "4.輸入要查找圖書的名字\n" "5.輸入要查找圖書的序號\n" "6.插入一本圖書\n" "7.刪除一本圖書\n" "8.按價格冒泡排序\n" "9.按價格快速排序\n" "10.查詢價格最大的圖書\n" "11.逆序存儲數據\n" "0.退出\n"); scanf("%d",&opt); switch(opt) { case 1:Input();break; case 2:Output();break; case 3:Length();break; case 4:Find();break; case 5:Get();break; case 6:Insert();break; case 7:Delete();break; case 8:BubbleSort();break; case 9:if(Check()){QuickSort(1,n-1),Update();}break; case 10:QueryMax();break; case 11:Inverse();break; case 0:return 0;break; } } return 0; }
#include <bits/stdc++.h> using namespace std; fstream in,out; int n=0; string temp[4]; struct Book { string isbn; string name; double price; }; inline void quicksort(Book b[],int left,int right)//時間O（nlog2n）,空間O（log2n）。利用數組進行快速排序 { if(left>=right)return; int i=left,j=right; double temp=b[left].price; while(i<j) { while(b[j].price>=temp&&i<j)--j; swap(b[i],b[j]); while(b[i].price<=temp&&i<j)++i; swap(b[i],b[j]); } quicksort(b,left,i-1); quicksort(b,i+1,right); return; } class book { private: string isbn; string name; double price; book *next; static book *head; static book *tail; public: book():next(NULL) { head=tail=this; } book(string a,string b,double c):isbn(a),name(b),price(c),next(NULL){} bool Check()//時間O（n）,空間O（1）。檢查是否讀入圖書信息 { if(n==0) { cout<<"請先選擇1讀取圖書信息\n"; return false; } return true; } void Input()//時間O（n）,空間O（n）。讀入圖書信息 { in.open("book.txt",ios::in); if(!in) { cout<<"未找到book.txt\n"; return; } n=1; tail=head; for(int i=1;i<=4;++i)in>>temp[i]; while(!in.eof()) { string a,b; double c; in>>a>>b>>c; tail->next=new book(a,b,c); tail=tail->next; n++; } in.close(); } void Output()//時間O（n）,空間O（1）。輸出圖書信息 { if(Check()) { cout<<temp[1]<<"\n"<<left<<setw(15)<<temp[2]<<"\t"<<left<<setw(50)<<temp[3]<<"\t"<<left<<setw(5)<<temp[4]<<"\n"; book *now=head; while(now->next) { now=now->next; cout<<left<<setw(15)<<now->isbn<<"\t"<<left<<setw(50)<<now->name<<"\t"<<left<<setw(5)<<now->price<<"\n"; if(now->next==NULL)break; } } } void Length()//時間O（1）,空間O（1）。輸出圖書總冊數 { if(Check())cout<<"共"<<n-1<<"本書"<<endl; } void Find()//時間O（n）,空間O（1）。遍歷查找圖書 { if(Check()) { cout<<"請輸入要查找的圖書名字\n"; book *now=head; bool flag=false; string str; cin>>str; while(now->next) { now=now->next; if(now->name==str) { flag=true; cout<<left<<setw(15)<<now->isbn<<"\t"<<left<<setw(50)<<now->name<<"\t"<<left<<setw(5)<<now->price<<"\n"; if(now->next==NULL)break; } } if(flag==false)cout<<"沒有收錄該圖書\n"; } } void Get()//時間O（n）,空間O（1）。遍歷訪問圖書 { if(Check()) { cout<<"請輸入你要查看的序號\n"; int num; cin>>num; if(num<1||num>n-1) { cout<<"輸入非法\n"; return; } book *now=head; while(num--)now=now->next; cout<<left<<setw(15)<<now->isbn<<"\t"<<left<<setw(50)<<now->name<<"\t"<<left<<setw(5)<<now->price<<"\n"; } } void Update()//時間O（n）,空間O（1）。將圖書信息存入book_out.txt文件里 { out.open("book_out.txt",ios::out); out<<temp[1]<<"\n"<<left<<setw(15)<<temp[2]<<"\t"<<left<<setw(50)<<temp[3]<<"\t"<<left<<setw(5)<<temp[4]<<"\n"; book *now=head; while(now->next) { now=now->next; out<<left<<setw(15)<<now->isbn<<"\t"<<left<<setw(50)<<now->name<<"\t"<<left<<setw(5)<<now->price<<"\n"; if(now->next==NULL)break; } out.close(); } void Insert()//時間O（n）,空間O（1）。在鏈表指定位置中插入新元素 { if(Check()) { int num; cout<<"請輸入要插入圖書的位置\n"; cin>>num; if(num<1||num>n) { cout<<"輸入非法\n"; return; } string a,b; double c; cout<<"請依次輸入要插入的圖書的ISBN號，書名，價格\n"; cin>>a>>b>>c; book *now=head; while(now->next) { num--; if(num==0) { break; } now=now->next; } book *temp=new book(a,b,c); temp->next=now->next; now->next=temp; n++; Update(); } } void Delete()//時間O（n）,空間O（1）。在鏈表指定位置中刪除元素 { if(Check()) { cout<<"請輸入要刪除圖書的位置\n"; int num; cin>>num; if(num<1||num>n-1) { cout<<"輸入非法\n"; return; } book *now=head; while(--num)now=now->next; book *temp=now->next->next; delete now->next; now->next=temp; n--; Update(); } } void BubbleSort()//時間O（n^2）,空間O（1）。冒泡排序，采用交換相鄰兩點的數據域的方法 { if(Check()) { book *now=head; book *tmp1; book *tmp2; double temp1; string temp2,temp3; for(int i=1;i<n-1;++i) { now=head->next; for(int j=1;j<n-i;++j) { tmp1=now; tmp2=now->next; if(tmp1->price>tmp2->price) { temp1=tmp1->price; tmp1->price=tmp2->price; tmp2->price=temp1; temp2=tmp1->isbn; tmp1->isbn=tmp2->isbn; tmp2->isbn=temp2; temp3=tmp1->name; tmp1->name=tmp2->name; tmp2->name=temp3; } now=now->next; } } Update(); } } void QuickSort(int left,int right)//時間O（nlog2n）,空間O（n）。將數據存儲到數組中進行快速排序，再重新存儲到鏈表中 { if(Check()) { book *now=head; int t=1; Book *b=new Book[n]; while(now->next) { now=now->next; b[t].isbn=now->isbn; b[t].name=now->name; b[t].price=now->price; t++; if(now->next==NULL)break; } quicksort(b,left,right); tail=head; for(int i=1;i<t;++i) { tail->next=new book(b[i].isbn,b[i].name,b[i].price); tail=tail->next; } Update(); } } void QueryMax()//時間O（n）,空間O（1）。查詢最大值 { if(Check()) { book *now=head; double mmax=0; while(now->next) { now=now->next; if((now->price)>mmax) { mmax=now->price; } if(now->next==NULL)break; } now=head; while(now->next) { now=now->next; if(now->price==mmax) { cout<<left<<setw(15)<<now->isbn<<"\t"<<left<<setw(50)<<now->name<<"\t"<<left<<setw(5)<<now->price<<"\n"; } } } } void Inverse()//時間O（n）,空間O（n）。逆序存儲圖書信息 { if(Check()) { book *pre=NULL; book *phead=head; book *now=NULL; while(phead!=NULL) { now=phead->next;//保存剩余鏈表 phead->next=pre;//斷開剩余鏈表頭結點pHead，指向pre pre=phead;//pre更新 phead=now;//phead更新 } tail=head; for(int i=1;i<n;++i) { tail->next=new book(pre->isbn,pre->name,pre->price); pre=pre->next; tail=tail->next; } } } }List; book *book::head; book *book::tail; int main() { while(1) { int o; printf("歡迎使用圖書管理系統,請輸入整數來實現你需要的功能\n" "1.圖書數據加載，使用鏈表進行存儲\n" "2.輸出所有圖書信息\n" "3.總圖書冊數\n" "4.輸入要查找圖書的名字\n" "5.輸入要查找圖書的序號\n" "6.插入一本圖書\n" "7.刪除一本圖書\n" "8.按價格冒泡排序\n" "9.按價格快速排序\n" "10.查詢價格最大的圖書\n" "11.逆序存儲數據\n" "0.退出\n"); scanf("%d",&o); switch(o) { case 1:List.Input();break; case 2:List.Output();break; case 3:List.Length();break; case 4:List.Find();break; case 5:List.Get();break; case 6:List.Insert();break; case 7:List.Delete();break; case 8:List.BubbleSort();break; case 9:List.QuickSort(1,n-1);break; case 10:List.QueryMax();break; case 11:List.Inverse();break; case 0:return 0;break; } } return 0; }
存在的一些BUG已經修改，可參照來完成實驗一前20題。
浙公網安備 33010602011771號