搜索
数据结构课程设计网络工程112班赵凡举201101024229《数据结构课程设计》实验报告【完成题目1】猴子选大王【问题描述】一堆猴子都有编号，编号是1，2，3...m,这群猴子（m个）按照1--m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。【基本要求】输入数据：输入m,n。m,n为整数，nm；输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。【算法设计】采用头指针和尾指针指针，将m个猴子编号构成环，从第一个开始数，数到第n个猴子，将其淘汰，即第n-1个的后继变成第n+1个，然后从第n+1个开始数，如此循环，直到剩下最后一个即为大王【源代码】#includeiostreamusingnamespacestd;structNode{intdata;structNode*next;};intmain(){structNode*head,*s,*q,*t;intn,m,count=0,i;cout输入猴子个数mendl;cinm;cout输入淘汰第几个nendl;cinn;if(i=1)cout大王是mendl;else{for(i=0;im;i++){s=(structNode*)malloc(sizeof(structNode));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-next=t-next;count=0;}q=q-next;}while(q-next!=q);cout大王是q-dataendl;}return0;}运行演示【收获及体会】猴子选大王问题，也可以用数组来实现，所用思想一样，查到第n个就将其删除，从下一个继续数，构成环是要有语句q=head;【完成题目2】随机整数排序问题【问题描述】针对随机产生2000个以上的整数，采用多种方法进行排序，并显示排序结果，比较各种算法的效率。【基本要求】1.为了提高效率，所产生的随机整数可以用文件保存，供各排序算法共用；2.为了更好地进行比较，采用3种以上方法实现排序，并分别保存排序结果；3.记录每种排序所耗费的时间。【算法设计】随机整数的产生srand(time(0));for(i=1;i=n;i++){a[i]=rand();}n可以控制个数，采用冒泡，选择，归并三种排序方法，计算时间的算法为start=clock();......finish=clock();tim=(double)(finish-start)/CLOCKS_PER_SEC;省略号为排序代码，tim即为排序耗费时间【源代码】#includestdlib.h#includeiostream#includetime.husingnamespacestd;voidmergesort(int*num,intstart,intend);voidmerge(int*num,intstart,intmiddle,intend);voidmergesort(int*num,intstart,intend){intmiddle;if(startend){middle=(start+end)/2;mergesort(num,start,middle);mergesort(num,middle+1,end);merge(num,start,middle,end);}}voidmerge(int*num,intstart,intmiddle,intend){intn1=middle-start+1;intn2=end-middle;int*L=newint[n1+1];int*R=newint[n2+1];inti,j=0,k;for(i=0;in1;i++){*(L+i)=*(num+start+i);}*(L+n1)=1000000;for(i=0;in2;i++){*(R+i)=*(num+middle+i+1);}*(R+n2)=1000000;i=0;for(k=start;k=end;k++){if(L[i]=R[j]){num[k]=L[i];i++;}else{num[k]=R[j];j++;}}}intmain(){clock_tstart,finish;doubleduration;intn,i,j,t,b;floattim;inta[100000];cout输入个数(100000以内)endl;cinn;srand(time(0));for(i=1;i=n;i++){a[i]=rand();}cout产生的随机数:endl;for(j=1;j=n;j++)couta[j]\t;coutendl;while(1){cout****选择****endl;cout(1)冒泡排序endl;cout(2)选择排序endl;cout(3)归并排序endl;cout(4)退出endl;cinb;if(b==4)break;switch(b){case1:{start=clock();for(j=1;j=n;j++)for(i=1;i=n-j;i++){if(a[i]a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}}cout冒泡排序结果endl;for(j=1;j=n;j++)couta[j]\t;coutendl;finish=clock();tim=(double)(finish-start)/CLOCKS_PER_SEC;cout用时:endltimendl;}break;case2:{start=clock();for(i=1;in;i++){intk=i;for(j=i+1;j=n;j++){if(a[j]a[k])k=j;t=a[k];a[k]=a[i];a[i]=t;}}cout选择排序结果endl;for(j=1;j=n;j++)couta[j]\t;coutendl;finish=clock();tim=(double)(finish-start)/CLOCKS_PER_SEC;cout用时:endltimendl;}break;case3:{start=clock();mergesort(a,0,n);cout归并排序结果endl;for(i=1;i=n;i++)couta[i]\t;coutendl;finish=clock();tim=(double)(finish-start)/CLOCKS_PER_SEC;cout用时:endltimendl;}break;}}return0;}运行演示【收获及体会】在本程序所采用的三种方法里边，归并排序所耗费的时间最短，计算时间的算法start（）和finish（）之间放所要计算时间的代码，即可得出时间【完成题目3】数制转换【问题描述】在日常生活中，常常使用各种编码，如身份证号码、电话号码和邮政编码等，这些编码都是由十进制数组成的。同理，在计算机中采用由若干位二进制数组成的编码来表示字母、符号、汉字和颜色等非数值信息。十进制数N和其他进制数的转换是计算机实现计算的基本算法，数制间转换的实质是进行基数的转换。【基本要求】设计实现十进制数与二进制数之间的数制转换程序，要求进行某种数制转换后，输入相应的格式正确的数值（也可以是混合小数的形式），程序按照设定的算法执行，给出相对应的进制数数值，对于输入数据的合法性可以不做检查。【算法设计】将输入数定义为float类型，先将整数部分和小数部分分开，分别进行转换，整数部分依次除以2，把余数存进数组，输出时倒着输出，并输出小数点小数部分依次乘以2，输出时正序输出【源代码】#includeiostreamusingnamespacestd;intmain(){inta,b,i,w=0,m,n,j,du,u,g;ints[100];floatc,d,e,f;cout输入整数或小数endl;cinc;cout准确度(小数点后几位)endl;cindu;d=c;n=c;u=du;while(a!=0){w++;a=n/2;b=n%2;n=a;s[w]=b;}cout转换结果endl;for(i=w;i0;i--){couts[i];}cout.;j=w+1;n=d/1;e=d-n;while(du){w++;f=e*2;g=f/1;e=f-g;s[w]=g;du--;}for(m=j;mu+j;m++)couts[m];coutendl;return0;}运行演示【收获及体会】小数进行数值转换时，要先将小数部分和整数部分分开，分别进行转换，转换时涉及的差积商余运算还有类型转换，此题目可以用数据结构栈来实现【完成题目4】宿舍管理查询系统【问题描述】为宿舍管理人员编写一个宿舍管理查询系统【基本要求】1.采用交互工作方式；2.可以增加、删除、修改信息；3.建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序；4.查询（按姓名、学号、房间号查询）；5.打印任一查询结果（可以连续操作）。【算法设计】用结构体来实现，增加，删除，排序，查找，修改分模块来实现switch,case实现操作选择【源代码】#includeiostream#includememory#includefstream#includewindows.husingnamespacestd;structcomm_info{charname[16];longnum;charf[16];};intmain(){system(color75);structcomm_infos[300],t;inti=0,w,m=0,f=0;charc[20];intcount=3;charname[20],pwd[20];while(count!=0){cout请输入用户名：endl;cinname;cout请输入密码：endl;cinpwd;count--;if(strcmp(name,zhaofan)==0&&strcmp(pwd,123)==0){m++;count=0;}else{cout密码或用户名错误您还有count次机会endl;if(count==0)cout密码错误次数达到最大限制！程序即将退出！endl;}}if(m){ifstreamfin1(f1.dat,ios::binary);memset(s,0,300*sizeof(comm_info));for(w=0;w300;w++){fin1.read((char*)&s[w],sizeof(comm_info));if(!s[w].num==0){f++;}}i=f;fin1.close();while(1){system(cls);cout欢迎使用宿舍管理系统endl;coutendl1增加endl;cout2查询endl;cout3删除endl;cout4修改endl;cout5排序endl;cout6当前操作下所有数据endl;cout7将已处理数据写入文endl;cout8退出endl;cinw;if(w==8)break;switch(w){case1:cout增加数据endl;{do{cout第i+1个endl