數(shù)據(jù)結構課程設計(內包五個程序源代碼)(共22頁)

1、精選優(yōu)質文檔-傾情為你奉上 數(shù)據(jù)結構課程設計 網(wǎng)絡工程112班 趙凡舉 9 數(shù)據(jù)結構課程設計實驗報告【完成題目1】猴子選大王【問題描述】一堆猴子都有編號，編號是1，2，3 .m ,這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。【基本要求】輸入數(shù)據(jù)：輸入m,n。 m,n 為整數(shù)，n<m；輸出形式：中文提示按照m個猴子，數(shù)n 個數(shù)的方法，輸出為大王的猴子是幾號 ，建立一個函數(shù)來實現(xiàn)此功能?！舅惴ㄔO計】采用頭指針和尾指針指針，將m個猴子編號構成環(huán)，從第一個開始數(shù)，數(shù)到第n個猴子，將其淘汰，即第

2、n-1個的后繼變成第n+1個，然后從第n+1個開始數(shù)，如此循環(huán)，直到剩下最后一個即為大王【源代碼】#include<iostream>using namespace std;struct Node int data; struct Node *next;int main() struct Node *head, *s, *q, *t; int n, m, count=0, i; cout<<"輸入猴子個數(shù)m"<<endl; cin>>m; cout<<"輸入淘汰第幾個n"<<endl

3、; cin>>n; if(i=1)cout<<"大王是"<<m<<endl;elsefor(i=0; i<m; i+) s=(struct Node *)malloc(sizeof(struct Node); s->data=i+1; s->next=NULL; if(i=0) head=s; q=head; else q->next=s; q=q->next; q->next=head; q=head; do count+; if(count=n-1) t=q->next;q->

4、;next=t->next; count=0; q=q->next; while(q->next!=q); cout<<"大王是"<<q->data<<endl;return 0;運行演示【收獲及體會】猴子選大王問題，也可以用數(shù)組來實現(xiàn)，所用思想一樣，查到第n個就將其刪除，從下一個繼續(xù)數(shù)，構成環(huán)是要有語句q=head; 【完成題目2】隨機整數(shù)排序問題【問題描述】針對隨機產(chǎn)生2000個以上的整數(shù)，采用多種方法進行排序，并顯示排序結果，比較各種算法的效率。【基本要求】1. 為了提高效率，所產(chǎn)生的隨機整數(shù)可以用文件保存，

5、供各排序算法共用；2. 為了更好地進行比較，采用3種以上方法實現(xiàn)排序，并分別保存排序結果；3. 記錄每種排序所耗費的時間?！舅惴ㄔO計】隨機整數(shù)的產(chǎn)生srand(time(0);for(i=1;i<=n;i+)ai=rand();n可以控制個數(shù)，采用冒泡，選擇，歸并三種排序方法，計算時間的算法為start = clock(); .finish = clock(); tim = (double)(finish - start) / CLOCKS_PER_SEC; 省略號為排序代碼，tim即為排序耗費時間【源代碼】#include <stdlib.h> #include <i

6、ostream> #include <time.h>using namespace std;void mergesort(int *num,int start,int end);void merge(int *num,int start,int middle,int end);void mergesort(int *num,int start,int end)int middle;if(start<end) middle=(start+end)/2;mergesort(num,start,middle);mergesort(num,middle+1,end);merge

7、(num,start,middle,end);void merge(int *num,int start,int middle,int end)int n1=middle-start+1; int n2=end-middle;int *L=new intn1+1;int *R=new intn2+1;int i,j=0,k;for (i=0; i<n1; i+) *(L+i)=*(num+start+i); *(L+n1)=;for (i=0; i<n2; i+) *(R+i)=*(num+middle+i+1);*(R+n2)=;i=0;for (k=start; k<=e

8、nd; k+) if(Li<=Rj) numk=Li;i+;else numk=Rj;j+;int main()clock_t start, finish; double duration; int n,i,j,t,b;float tim;int a;cout<<"輸入個數(shù)(以內)"<<endl;cin>>n;srand(time(0); for(i=1;i<=n;i+)ai=rand();cout<<"產(chǎn)生的隨機數(shù):"<<endl;for(j=1;j<=n;j+)cout&l

9、t;<aj<<"t"cout<<endl;while(1)cout<<"*選擇*"<<endl;cout<<"(1)冒泡排序"<<endl;cout<<"(2)選擇排序"<<endl;cout<<"(3)歸并排序"<<endl;cout<<"(4)退出"<<endl;cin>>b;if(b=4)break;switc

10、h(b)case 1:start = clock(); for(j=1;j<=n;j+)for(i=1;i<=n-j;i+)if(ai>ai+1)t=ai;ai=ai+1;ai+1=t;cout<<"冒泡排序結果"<<endl;for(j=1;j<=n;j+)cout<<aj<<"t"cout<<endl;finish = clock(); tim = (double)(finish - start) / CLOCKS_PER_SEC; cout<<"

11、;用時:"<<endl<<tim<<endl;break;case 2: start = clock(); for(i=1;i<n;i+) intk=i; for(j=i+1;j<=n;j+) if(aj<ak)k=j; t=ak; ak=ai; ai=t; cout<<"選擇排序結果"<<endl;for(j=1;j<=n;j+)cout<<aj<<"t"cout<<endl;finish = clock(); tim =

12、(double)(finish - start) / CLOCKS_PER_SEC; cout<<"用時:"<<endl<<tim<<endl; break;case 3:start = clock(); mergesort(a,0,n);cout<<"歸并排序結果"<<endl;for (i=1; i<=n; i+) cout<<ai<<"t"cout<<endl;finish = clock(); tim = (dou

13、ble)(finish - start) / CLOCKS_PER_SEC; cout<<"用時:"<<endl<<tim<<endl;break;return 0;運行演示【收獲及體會】在本程序所采用的三種方法里邊，歸并排序所耗費的時間最短，計算時間的算法start（）和finish（）之間放所要計算時間的代碼，即可得出時間【完成題目3】數(shù)制轉換【問題描述】在日常生活中，常常使用各種編碼，如身份證號碼、電話號碼和郵政編碼等，這些編碼都是由十進制數(shù)組成的。同理，在計算機中采用由若干位二進制數(shù)組成的編碼來表示字母、符號、漢字和顏

14、色等非數(shù)值信息。十進制數(shù)N和其他進制數(shù)的轉換是計算機實現(xiàn)計算的基本算法，數(shù)制間轉換的實質是進行基數(shù)的轉換。【基本要求】設計實現(xiàn)十進制數(shù)與二進制數(shù)之間的數(shù)制轉換程序，要求進行某種數(shù)制轉換后，輸入相應的格式正確的數(shù)值（也可以是混合小數(shù)的形式），程序按照設定的算法執(zhí)行，給出相對應的進制數(shù)數(shù)值，對于輸入數(shù)據(jù)的合法性可以不做檢查。【算法設計】將輸入數(shù)定義為float類型，先將整數(shù)部分和小數(shù)部分分開，分別進行轉換，整數(shù)部分依次除以2，把余數(shù)存進數(shù)組，輸出時倒著輸出，并輸出小數(shù)點小數(shù)部分依次乘以2，輸出時正序輸出【源代碼】#include <iostream>using namespace st

15、d; int main() int a,b,i,w=0,m,n,j,du,u,g; int s100;float c,d,e,f; cout<<"輸入整數(shù)或小數(shù)"<<endl; cin>>c; cout<<"準確度(小數(shù)點后幾位)"<<endl;cin>>du; d=c;n=c;u=du;while(a!=0)w+;a=n/2;b=n%2; n=a;sw=b;cout<<"轉換結果"<<endl;for(i=w;i>0;i-)cout

16、<<si;cout<<"."j=w+1; n=d/1; e=d-n;while(du) w+;f=e*2;g=f/1;e=f-g;sw=g;du-;for(m=j;m<u+j;m+)cout<<sm;cout<<endl;return 0;運行演示【收獲及體會】小數(shù)進行數(shù)值轉換時，要先將小數(shù)部分和整數(shù)部分分開，分別進行轉換，轉換時涉及的差積商余運算還有類型轉換，此題目可以用數(shù)據(jù)結構棧來實現(xiàn)【完成題目4】宿舍管理查詢系統(tǒng)【問題描述】 為宿舍管理人員編寫一個宿舍管理查詢系統(tǒng)【基本要求】1. 采用交互工作方式；2. 可以增加、

17、刪除、修改信息；3. 建立數(shù)據(jù)文件 ，數(shù)據(jù)文件按關鍵字（姓名、學號、房號）進行排序；4. 查詢（按姓名、學號、房間號查詢）；5. 打印任一查詢結果（可以連續(xù)操作）?！舅惴ㄔO計】用結構體來實現(xiàn)，增加，刪除，排序，查找，修改分模塊來實現(xiàn)switch,case實現(xiàn)操作選擇 【源代碼】#include <iostream>#include <memory> #include <fstream>#include <windows.h>using namespace std;struct comm_info char name16; long num;cha

18、r f16; ; int main() system("color 75");struct comm_info s300,t;int i=0,w,m=0,f=0;char c20; int count=3;char name20,pwd20;while(count!=0) cout<<"請輸入用戶名："<<endl;cin>>name;cout<<"請輸入密碼："<<endl;cin>>pwd;count-;if(strcmp(name,"zhaofan

19、")=0 && strcmp(pwd,"123")=0)m+;count=0;else cout<<"密碼或用戶名錯誤您還有"<<count<<"次機會"<<endl;if(count=0)cout<<"密碼錯誤次數(shù)達到最大限制！程序即將退出！"<<endl;if(m)ifstream fin1("f1.dat",ios:binary);memset(s,0,300*sizeof(comm_info

20、); for(w=0;w<300;w+) fin1.read(char*)&sw, sizeof(comm_info);if(!sw.num=0) f+;i=f;fin1.close();while(1)system("cls");cout<<" 歡迎使用宿舍管理系統(tǒng)"<<endl;cout<<endl<<"1 增加"<<endl;cout<<"2 查詢"<<endl;cout<<"3 刪除&qu

21、ot;<<endl;cout<<"4 修改"<<endl;cout<<"5 排序"<<endl; cout<<"6 當前操作下所有數(shù)據(jù)"<<endl;cout<<"7 將已處理數(shù)據(jù)寫入文"<<endl;cout<<"8 退出"<<endl;cin>>w;if(w=8)break;switch(w)case 1:cout<<"增加數(shù)據(jù)

22、"<<endl;do cout<<"第"<<i+1<<"個"<<endl;ofstream fout1("f1.dat",ios:app);ofstream fout2("f2.txt",ios:app);if(!fout1) cout<<"Cannot open binary file. "<<endl;exit(0);if(!fout2) cout<<"Cannot open

23、text file. "<<endl;exit(0);cout<<"輸入姓名："cin>>;cout<<"輸入學號："cin>>si.num;cout<<"輸入房號："cin>>si.f;fout1.write(char*)&si, sizeof(comm_info ); /把記錄寫入二進制文件/把記錄寫入文本文件fout2<<"學號："<<si.num<<endl

24、<<"房號："<<si.f<<endl<<"姓名："<<<<endl;fout1.close();fout2.close();i+; cout<<"數(shù)據(jù)錄入成功，繼續(xù)錄入嗎(y/n)"<<endl;cin>>c; int a=0;doif(strcmp(c,"y")&&strcmp(c,"n") cout<<"指令錯誤！請重新輸入！&qu

25、ot; cin>>c; elsea=1;while(a=0);while(strcmp(c,"y")=0);break;case 2:cout<<"查詢"<<endl; int m=0; if(i<1) cout<<"沒有成員"<<endl; m+; _sleep(3000); if(m) break; cout<<"1 按姓名查找"<<endl; cout<<"2 查找組"<<en

26、dl; cout<<"3 退回主菜單"<<endl; int a=0,b,d=0; char name20; cin>>b; if(b=3) break; switch(b) case 1: do cout<<"按姓名查找"<<endl<<"請輸入姓名："<<endl; cin>>name; for(int j=0;j<i;+j) if(strcmp(name,)=0) cout<<"姓名：&quo

27、t;<<<<endl; cout<<"學號："<<sj.num<<endl; cout<<"房號："<<sj.f<<endl; d+; if(d) cout<<"存在，是否繼續(xù)姓名操作（y/n）"<<endl; else cout<<"不存在,是否繼續(xù)姓名操作（y/n）"<<endl; cin>>c; do if(strcmp(c,"y&

28、quot;)&&strcmp(c,"n") cout<<"指令錯誤！請重新輸入！" cin>>c; else a=1; while(a=0); while(strcmp(c,"y")=0); break; case 2: do cout<<"按小組查找"<<endl<<"輸入組名"<<endl; char f16; int d=0; cin>>f; for(int j=0;j<i;+j) i

29、f(strcmp(f,sj.f)=0) cout<<"姓名："<<<<endl; cout<<"學號："<<sj.num<<endl; cout<<"房號："<<sj.f<<endl; d+; if(d) cout<<"已經(jīng)找到，是否繼續(xù)房號查找操作（y/n）"<<endl; else cout<<"不存在,是否繼續(xù)房號操作（y/n）"&l

30、t;<endl; cin>>c; do if(strcmp(c,"y")&&strcmp(c,"n") cout<<"指令錯誤！請重新輸入（y/n）！" cin>>c; else a=1; while(a=0); while(strcmp(c,"y")=0); break; break;case 3:doint a=0,b,d=0,num=0,m=0;char name20;cout<<"按姓名刪除"<<endl&

31、lt;<"請輸入姓名："<<endl;cin>>name;for(int j=0;j<i;+j) if(strcmp(name,)=0)cout<<"姓名："<<<<endl;cout<<"學號："<<sj.num<<endl;cout<<"房號："<<sj.f<<endl;m+;b=j;if(m>0)cout<<"找

32、到，是否刪除（y/n）"<<endl;elsecout<<"沒有或數(shù)據(jù)已經(jīng)刪除，自動跳轉."<<endl;_sleep(2000);break;cin>>c;doif(strcmp(c,"y")&&strcmp(c,"n") cout<<"指令錯誤！請重新輸入！" cin>>c; elsea=1;while(a=0);if(strcmp(c,"n")=0)break;else for( b;b<

33、;i;b+)sb=sb+1;d+;i-;if(d>0)cout<<"刪除成功，是否繼續(xù)刪除操作（y/n）"<<endl;cin>>c; doif(strcmp(c,"y")&&strcmp(c,"n") cout<<"指令錯誤！請重新輸入！" cin>>c; elsea=1;while(a=0); while(strcmp(c,"y")=0);break;case 4:do cout<<"修改

34、信息"<<endl<<"請輸入姓名："<<endl; char name20;int d=0,a=0,num;cin>>name;for(int j=0;j<i;+j) if(strcmp(name,)=0) cout<<"姓名："<<<<endl;cout<<"學號："<<sj.num<<endl;cout<<"房號："<<sj

35、.f<<endl;d+;num=j; if(d)cout<<"存在，是否修改（y/n）"<<endl;elsecout<<"不存在,自動跳轉."<<endl;_sleep(3000);break;cin>>c;doif(strcmp(c,"y")&&strcmp(c,"n") cout<<"指令錯誤！請重新輸入！" cin>>c; elsea=1;while(a=0);if(strcm

36、p(c,"n")=0)break;elsecout<<"輸入新姓名："cin>>;cout<<"輸入新學號："cin>>snum.num;cout<<"輸入新房號："cin>>snum.f;cout<<"修改成功,是否繼續(xù)進行修改操作(y/n)"cin>>c; doif(strcmp(c,"y")&&strcmp(c,"n")

37、cout<<"指令錯誤！請重新輸入！" cin>>c; elsea=1;while(a=0); while(strcmp(c,"y")=0);break;case 5:int m=0;if(i<1)cout<<"沒有成員"<<endl;m+;_sleep(3000);if(m)break; cout<<"1 按姓名排序"<<endl;cout<<"2 按學號排序"<<endl;cout<&

38、lt;"3 按房號排序"<<endl;cout<<"4 退出"<<endl;int a=0,b,d=0;cin>>b;if(b=4)break;switch(b)case 1:cout<<"按姓名排序"<<endl;for(int p=0;p<i-1;p+)for(int j=0;j<i-p-1;+j) if(strcmp(,sj+1.name)>0)t=sj;sj=sj+1;sj+1=t;cout<<"排序正

39、在進行."<<endl;_sleep(1500);cout<<"排序成功，自動跳轉."_sleep(1000);break;case 2:cout<<"按學號排序"<<endl;for(int p=0;p<i-1;p+)for(int j=0;j<i-p-1;+j) if(sj.num>sj+1.num)t=sj;sj=sj+1;sj+1=t;cout<<"排序正在進行."<<endl;_sleep(1500);cout<<

40、"排序成功，自動跳轉."_sleep(1000);break;case 3:cout<<"按房號排序"<<endl;for(int p=0;p<i-1;p+)for(int j=0;j<i-p-1;+j) if(strcmp(sj.f,sj+1.f)>0)t=sj;sj=sj+1;sj+1=t;cout<<cout<<"排序正在進行."<<endl;_sleep(1500);cout<<"排序成功，自動跳轉."_sleep(1

41、000);break;break;case 6:int j;cout<<"當前操作下所有數(shù)據(jù)(包括文件數(shù)據(jù))"<<endl; for( j=0;j<i;+j) cout<<endl;cout<<"第"<<j+1<<"名:"<<endl;cout<<"學號："<<sj.num<<endl;cout<<"房號："<<sj.f<<endl; cout<<"輸入任意鍵返回主菜單"<<endl;cin>>c; break; case 7: ofstream fout1("f1.dat");ofstream fout2("f2.txt");for( int j=0;j<i;j+)fout1.write(char*)&sj, sizeof(comm_info ); /把記錄寫入二進制文件/把記錄寫入文本文件fout2<<"第"<<j+