数据结构与算法专题实验报告.doc

附录A：报告格式 数据结构与算法专题实验报告         n 目 录附录A：报告格式1第一部分 题目3第1题 约瑟夫环31 题目32 目标33 设计思想34 算法描述45 程序流程图56 源程序5第2题 大数阶乘91 题目92 目标93 设计思想94 算法描述105 程序流程图116 源程序11第3题 图的遍历131 题目132 目标133 设计思想134 算法描述145 程序流程图156 源程序15第4题 最短路径191 题目192 目标193 设计思想194 算法描述205 程序流程图216 源程序23第二部分 体会与建议271体会与收获272建议与意见28第一部分 题目第1题 约瑟夫环1 题目： 用循环链表实现约瑟夫（Yoseph）环整数）开始任选一个正整数作为报数值m，自第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他持有的密码作为新的m值，从他的顺时针方向的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。编写完整的程序求出出列的顺序。2 目标： 1输入：从键盘输入人数n，n个人的密码以及初始m值。输入时应有提示，并有纠错措施。2输出：输出结果写入文件，包括n、n个密码、m和出列顺序。3 设计思想： 1 用单链表的数据结构实现约瑟夫环。2 创建单链表默认第i个结点的序号为i,获得第i个结点的数据（第个人的密码，并使其具有纠错功能， 用while 语句判断所输入的结点总数与第个个结点的数据是否在允许的范围内，如果在，则继续下去，如果不在，则返回重新输入。3 约瑟夫环中人员相继有规律的出列其实质是在单链表中连续删除结点直至剩余最后一个结点，当然它还满足一定的条件，那就是每删除一个结点后，下一个待删除的结点是从删除的结点的下一个结点开始计数，数到删除的结点的数据时，再次删除结点。4用文件输出则直接调用文件读取函数即可实现文件输出。4 算法描述： step1:定义单链表数据结构； step2: creat( )函数 /创建但链表，默认第i个结点的序号为i；a. 输入总的结点数 n，并判断其是否在允许的范围内，如果不在，则返回，重新输入；b. for(i<n)申请空间，输入密码，判断其是否在0，MAX范围内，如不在，返回，重新输入； step3: Disp(Yoseph* L) /出列函数，实现题设要求 while（p的下已个结点不是p） if(初始密码为1)则输出第i个结点,带回p->code并删除该结点，p=p->next else，从第i个结点计数，数到第m个结点，带回p->code并删除该结点，p=p->next； step4: fopen("t.out","w")实现文件的输出； step5: 主函数5 程序流程图： 6 源程序： / 用循环链表实现Yoseph环:#include<fstream.h> /实现文件输出的头文件#include<stdlib.h>#include<stdio.h>#define NUM 50static int aNUM; / 用来存放人数和初始密码值及出队序列int j=2,n;struct Yoseph /定义单链表数据结构 int num; int code; Yoseph *next;Yoseph* creat( ) /创建单链表 int i,k=0; Yoseph *L,*p,*q;int n; printf("请输入总人数:n"); scanf("%d",&n); a0=n; L=p=(struct Yoseph*)malloc(sizeof(Yoseph); p->num=1; printf("请输入第1个人手中所持的密码：n"); scanf("%d",&p->code); while(p->code<1|p->code>30) /设置密码的范围 printf("输入错误!请重新输入：n"); scanf("%d",&p->code); aj=p->code;j+; for(i=2;i<=n;+i) q=(struct Yoseph*)malloc(sizeof(Yoseph); /为循环单链表申请空间 q->num=i; p->next=q; p=q; printf("请输入第%d个人手中所持的密码：n",i); scanf("%d",&q->code); while(q->code<1|q->code>20) printf("输入错误!请重新输入:n"); /纠错功能 scanf("%d",&q->code); aj=q->code; j+; p->next=L; return L; void Disp(Yoseph* L) /输出出队序列 int k, m; struct Yoseph *p=L,*q; printf("请输入初始值: n"); scanf("%d",&m); a1=m; printf("出列顺序如下："); while(p->next!=p) /直到剩下最后一个结点才退出 if(m=1) printf("%3d",p->num); aj+=p->num; q->next=p->next; m=p->code; p=p->next; else for(k=1;k<m;+k) / 计数到第m个将此结点删除 q=p; p=p->next; printf("%3d",p->num); aj+=p->num; q->next=p->next; m=p->code; /带回被删除的结点的数据，即出列的人手中的密码 p=p->next; printf("%3d",p->num); printf("n"); aj=p->num; printf("出列完毕!"); printf("n"); void main( ) /主函数 int j; Yoseph * L; FILE *fpt; L=creat( ); Disp(L); fpt=fopen("t.out","w"); / 调用文件输出语句，实现将结果存放在名为t.out的文件当中 fprintf(fpt,"总人数为:"); fprintf(fpt,"%3dn",a0); fprintf(fpt,"初始密码为："); fprintf(fpt,"%3dn",a1); fprintf(fpt,"n"); fprintf(fpt,"前%d个为密码,后%d个为出列人序号：",a0); for(j=2;j<n+2;j+) /输出程序运行完毕后出列序列 fprintf(fpt,"%3d",aj); for(j=n+2;j<NUM;j+) if(aj!=0) fprintf(fpt,"%3d",aj); fclose(fpt);返回第2题 大数阶乘1 题目： 求N！（N>10）2 目标： 1. 掌握大数的处理方法 2. 编程实现时应该考虑边界条件的处理。3 设计思想： 1 为实现大数阶乘，我们来看下面的分析：0！=1；1！=1； 2！=1+1；（1！加2次） 3！=2+2+2；（2！加3次） 4！=6+6+6+6；（3！加4次）n!=(n-1)!+(n-1)!+(n-1)!+(n-1)!+(n-1)!( (n-1)!加n次)1！=1；2！=1+1；3！=2+2+2；4！=6+6+6+6； n!=(n-1!)!+(n-1)!+ +(n-1)! （加n次）算n!要先算（n-1）!,然后再把它相加n次，可以用类似竖式加法实现。aMAXa3 a2 a1 a0 + aMAXb3 b2 b1 b0 aMAXa3 a2 a1 a02 还要考虑边界条件，负数无法求阶乘，太大的数求阶乘太耗时间，故确定范围0，NUM，在此范围内程序继续执行，超出这个范围，则返回重新输入。3 对一个数来说最高位不可能为0，设置从aMAXnumber开始扫描，遇到第一个不为0的数位时开始输出。4 算法描述： step1:定义数组的最大位数，定义存放最后结果和分布结果的数组a和b；step2: 输入并判断，符合，则继续，不符合，返回重新输入；step3: while(0<n<MAXnumber) a.初始化两个数组，a0=1,，输入所要求阶乘的那个数n；b.for语句（j<n） 把每次求得的一个中间结果从a数组中复制到b数组中，for 语句（m<j）实现把b数组中所得的结果相加j次得j! step4:输出 ，从a数组的最后一个元素向前扫描，遇到第一个不为0的数字开始输出。5 程序流程图： 6 源程序： #include<iostream.h>#define MAXnumber 3000 /定义数组的最大长度void main( ) int aMAXnumber,bMAXnumber; /定义存放结果的数组 int i,j,m,k,r,n; char ch='y' while(ch!='n') cout<<"请输入你所想求阶乘的那个数:"<<endl; cin>>n; if(n>1000) /设置大数的边界条件，大数求阶乘比较慢 cout<<"你所输入的数字太大，请重新输入!"<<endl; cin>>n; while(n<0) /设置边界条件，负数无法求阶乘 cout<<"对不起，输入错误,请重新输入！"<<endl; cin>>n; for(i=1;i<MAXnumber;+i) ai=0; a0=1; for(j=2;j<=n;+j) for(i=0;i<MAXnumber;+i) bi=ai; for(m=1;m<j;+m) for(i=0;i<MAXnumber;+i) /用类似于竖式加法实现阶乘 r=ai+bi; if(r>9) ai+1+; ai=r%10; k=MAXnumber-1; / 从数组末一个元素开始扫描，当遇到第一个不为0 的元素时开始输出 while(ak=0) -k; cout<<n<<"!=" for(i=k;i>=0;-i) cout<<ai; cout<<endl; cout<<"输入继续吗？是请键入“y”,退出键入“n”!"<<endl; cin>>ch; 返回第3题 图的遍历1 题目 现用Diskstra算法实现求最短路径2 目标 1.结点部少于30；2.可以从键盘或从文件输入结点数据，包括顶点信息、边、权等。3.从用户指定的顶点为起始点，输出该结点到其余各顶点的最短路径长度机器路径。3 设计思想 1 我采用二维数组实现输出图的邻接矩阵，对应行和列为顶点序号。2 在创建图时，设置顶点个数范围，设置顶点，权值，边数的范围。3 再输入边时采用以0，0，0结束，就是当我们把顶点，顶点，权值都输入0时，输入结束。4 最短路径设置双重循环，求得最短路径。4 算法描述： step1:定义顶点最大个数，无穷大时的权值为10000，存放边的n维数组costMAXMAX，最短路径distMAX；step2:定义无向图数据结构；step3: creatgraph() /创建无向图a. 输入图的顶点个数，并判断0<n<=MAX,如果不是，则返回重新输入；b. while（s！=0|e！=0|len！=0）输入顶点，顶点，权值，并判断s>=0&&s<n&&e>=0&&e<n&&len>0，如果不是，则返回，重新输入，最后以0，0，0结束输入；step4: shortdjs() /求最短路径a. for 语句（i<n）初始化权值，设置一个最短路径的起始点经过边数b. for语句（i<n） for语句（j<n）寻找第I个结点到V0的直接路径； for 语句（i<n）寻找V0到第j 个结点的所有路径并把最小的放到disti中；step5: dispath() /输出最短路径step6: 直接调用creatgraph(), shortdjs(), dispath()三个函数。5 程序流程图： 6 源程序： / 无向图的最短路径#include <iostream.h>#define MAX 30 /顶点的最大个数#define up 1000 /当两顶点之间的权值为无穷大时，输出1000int costMAXMAX; /邻接表int distMAX,n; / 最短路径struct int num; int pnodeMAX; /途中经过的顶点 pathMAX; void creatgraph() /创建无向图 int i,j,s,e,len,contin=1; cout<<"请输入图的顶点个数: " cin>>n;if (n<1|n>=MAX) /纠错功能cout<<"输入错误，请重新输入"<<endl;cin>>n;for(i=0;i<n;i+) /初始化无向图 for(j=0;j<n;j+) costij=costji=up; costii=0;cout<<"输入各边,以0,0,0表示结束: "<<endl; i=1;while(contin=1) /设置输入条件 cout<<"t第"<<i<<"条边->顶点，顶点，权值: n" cin>>s>>e>>len; if (s=0&&e=0&&len=0) / 当它们都为0时就退出输入 contin=0; else if (s>=0&&s<n&&e>=0&&e<n&&len>0) costse =costes=len; / 实现无向图的操作 i+; else cout<<"tt边值错误，请重新输入!"<<endl; void shortdjs() /寻找最短路径的算法函数的实现 int sMAX; int mindis,dis,i,j,v0=0,u; for(i=0;i<n;i+) disti=costv0i; pathi.pnode0=v0; pathi.num=0; si=0; sv0=1;for(i=1;i<n;i+) mindis=up; for (j=1;j<n;j+) if(sj=0&&distj<mindis) u=j; mindis=distj; su=1; /当su=1时表示权值为无穷大for (j=1;j<n;j+)if(sj=0) dis=distu+costuj; if(distj>dis) distj=dis; pathj.num+; pathj.pnodepathj.num=u; pathi.num+;pathi.pnodepathi.num=i; void dispath() / 输出最短路径 int i,j; cout<<endl<<"从v0到各顶点的最短路径长度如下:"<<endl; cout<<endl<<"t(起点->终点) 最短长度 最短路径"<<endl<<endl; for(i=1;i<n;i+) cout<<"t(V0->V"<<i<<"): " ; if(disti<up) cout<<disti<<" (" else cout<<"10000 ("for (j=0;j<pathi.num;j+) cout<<"V"<<pathi.pnodej<<"," cout<<"V"<<pathi.pnodepathi.num<<")"<<endl;void main () /主函数 creatgraph(); /直接调用三个函数就行 shortdjs(); dispath();返回第4题 最短路径1 题目： 创建一个具有n（n1）个顶点的无向图的邻接矩阵，并对其按照“深度优先搜索”和“广度优先搜索”方法进行遍历。2 目标： 1.编写C程序予以实现。2.程序要求能输入图的顶点数、边数以及边的关系，并自动生成邻接矩阵。3.结果输出邻接矩阵和遍历的路径。4.熟悉无向图的两种遍历算法。3 设计思想： 1 考虑用一个n维数组来存放无向图，若两个结点之间有边，则n维数组对应下标的那个元素值为1，否则为0；2 在输入图的顶点数和边数时我充分考虑了边界条件，顶点数G.vexnum在0，MAXV范围内，边数在0，G.vexnum*(G.vexnum-1)/2范围内，在这个范围内，程序继续向下执行，否则返回重新输入；3 输出邻接矩阵的实质是输出 n维数组，我用两重循环来实现；4 深度优先遍历我采用迪杰特斯拉算法，不过要在此算法中间加一个判断，所有的结点是否都已经遍历过，如果是就退出，如果不是，则按顺序从序号小的开始向大的寻找，找到一个没有遍历过的结点继续调用深度优先遍历算法；5 广度优先遍历我采用了非递归算法，其实质和深度优先遍历算法相同；6 在主函数中直接调用CreatGraph(G)， DispMatrix(G) ，DepthDisp(G,v) ，WidthDisp(G)函数即可。4 算法描述： step1:设置无向图最多的顶点数/ 这个设置为了更好的输出邻接矩阵；step2: 定义无向图的数据结构；step3:实现生成无向图函数CreatGraph(G)a. 输入顶点数n，判断它是否在允许的范围内，不在则返回重新输入；b. 输入无向图的边数G.arcnum，判断它是否在允许的范围内，不在则返回重新输入 ；c. 输入边，for语句(k=1 to G.arcnum) 输入两顶点v,w，判断v!=w & 0<v<=Gverxnum & 0<w<=Gverxnum ,如果是在n维数组中第v行第w列和第w行第v列元素都为1，否则返回重新输入；step4:实现输出邻接矩阵函数 DispMatrix(Graph &G) ， 双重for循环实现输出无向图的邻接矩阵；step5:实现深度优先遍历的递归算法函数DepthDisp(Graph &G,int v) a. 从v开始遍历，设置计数器num=0 ，并置顶点v已访问；b. for语句（i=1 to G.vexnum）判断 G.arcsvi!=0&&visitedi=0，如果是递归调用深度优先遍历的递归算法函数DepthDisp(G, i)，如果不是则退出；c. 用for和if 语句判断是否所有的顶点都已经遍历完，if num<G.vexnumfor (i=1 to G.vexnum ) if (visitedi=1) i+如果不是，则继续调用 深度优先遍历的递归算法函数 DepthDisp(G,i)；step6:实现广度优先遍历的非递归算法函数 WidthDisp(Graph &G)a. 输入广度优先遍历的出发点m ,判断0<m< G.vexnum,如果不是，则返回重新输入；b. for （ i=1 to G.vexnum）判断第i个顶点与第m之间是否有边，有边则输出，k+,判断k=G.vexnum,等于，则退出，遍历完毕，不等于，转到与m有边的顶点继续遍历，要是有边的都已经遍历过，继续找一个没有遍历的顶点，继续；step7: 主函数直接调用CreatGraph(G)， DispMatrix(G) ，DepthDisp(G,v) ，WidthDisp(G)函数即可；5 程序流程图： 1 创建无向图函数的流程图如下：2深度优先遍历函数实现的流程图如下：3 实现广度优先遍历的流程图如下：6 源程序 /二,不带权值的无向图的遍历: #include<iostream.h>#define MAXV 20 /定义顶点的最大个数struct Graph / 定义无向图的数据结构 int vexsMAXV;int arcsMAXV MAXV;int vexnum, arcnum; static int visitedMAXV;void CreatGraph(Graph &G) / 实现创建无向图的函数 int i, j, k, v, w;cout<<"请输入顶点数："cin>>G.vexnum;while(G.vexnum> MAXV) cout<<"图的顶点数超限，请重新输入：" /纠错功能 cin>>G.vexnum; cout<<"请输入边数："cin>>G.arcnum;while(G.arcnum> G.vexnum*(G.vexnum-1)/2) /V个顶点最多V(V-1)/2个顶点 cout<<"图的边数超限，请重新输入：" cin>>G.arcnum; for(i=0;i<=G.vexnum;i+)for(j=0;j<=G.vexnum;j+) G.arcsij=0;for(k=1;k<=G.arcnum;k+) cout<<"请输入第"<<k<<"条边所连接的两个顶点：" cin>>v>>w; G.arcsvw=G.arcswv=1; / 无向图void DispMatrix(Graph &G) / 输出邻接矩阵 int i, j;cout<<" 邻接矩阵为："<<endl;for(i=1;i<=G.vexnum;+i) cout<<" "<<i;cout<<endl;for(i=1;i<=G.vexnum;+i) /默认第i个顶点的序号为i cout<<i<<" " for(j=1;j<=G.vexnum;+j) cout<<G.arcsij<<" " cout<<endl;void DepthDisp(Graph &G,int v) / 深度优先遍历的递归算法 int i; int num=0; cout<<v<<" "visitedv=1; num+; for(i=1;i<=G.vexnum;i+) if(G.arcsvi!=0&&visitedi=0) DepthDisp(G, i); if(num<G.vexnum) /判断所有顶点是否都遍历完，如果没有继续遍历for(i=1;i<=G.vexnum;i+)if (visitedi=1)i+;else DepthDisp(G,i);void WidthDisp(Graph &G) / 广度优先遍历的非递归算法 int i, j=0, k=0, l, m, n=1, flag=1;int aMAXV;for(i=0;i<G.vexnum;i+) ai=0; cout<<"请输入广度优先遍历的出发顶点:" cin>>m; while(m<0|m>G.vexnum) cout<<" 输入的顶点不存在！请重新输入：" / 纠错功能 cin>>m; cout<<"广度优先遍历的序列为：" cout<<m<<" " ak=m; while(flag) for(i=1;i<=G.vexnum;i+) if(G.arcsmi!=0) for(l=0;l<=k; ) if(i!=al) l+; else break; if(l>k) cout<<i<<" " k+; ak=i; n+; if(n!=G.vexnum) /判断是否所有的顶点都已经遍历过，如果没有则继续寻找没有遍历的顶点继续遍历 m=a+j; else flag=0; cout<<endl;void main( ) Graph G; /生成一个图 int i,v;cout<<"首先生成无向图： "<<endl;CreatGraph(G);DispMatrix(G);for(i=0;i<G.vexnum;i+) visitedi=0;cout<<"请输入深度优先遍历的出发顶点：" cin>>v;DepthDisp(G,v); /调用三个函数cout<<endl;WidthDisp(G);返回第二部分 体会与建议1体会与收获： 通过这次的实验,使我学会了很多原来在上数据结构理论课时所无法学 到的知识,比如说怎样把一个程序尽可能地去完善,让它具有健壮性,还有通过这次的时间环节我也对上半年学习的数据结构又复习了一遍，以前，我总觉得数据结构上的东西比较抽象，不知道怎样去运用，现在我知道了而且也会用简单的数据结构编写程序。下面我想具体谈一下我在做每一道题时的体会。在做约瑟夫换时我很深刻地理解了循环单链表的用法，还有C语言中有关文件输出的有关操作，我想假如没有这次的实验课我是不会去回去复习它们的。在做第二题时我一开始就想到了用数组来一位一位的存储一个很大的数，但现在我发现还有更好的方法，比如像链表，因为在每一次操作的时候它很有效到避免了把所有的结点都扫描一遍，而只用到了那些有效位这就大大提高了运算的速度。在做第三题时我学回了用数组来存储图，也学会了最短路径算法的实质。在做第四题图的遍历时我一开始就遇到了困难，用DIJ算法时发现它对非连通图无法完全遍历，结果我又是看书，又是调试，不过最后还是成功了这是让我最欣慰的。2建议与意见：1. 觉得在计算机专业的课程安排上应该多一些实践环节，比如C语言，C+面向对象程序设计，数据结构，汇编语言，编译原理，数字逻辑，数值计算方法等等。作为我们计算机专业的学生来说要的就是实际操作的经验和在实际问题中处理问题的能力，这些能力从哪里来，就是从这些实验环节中获取。2. 我觉得学校应该尽量多点时间把实验室开放,这样才能把大家的积极性调动起来,也可以组建一些对编程有极大兴趣的小组搞一些小的项目,来提高我们解决实际问题的能力。3. 在这次下过程中，我有好几道题都是因为有漏洞没得到好成绩，我觉得我们的理论课堂应当多涉及一些关于怎样消除程序当中的BUG的问题，我觉得这对提高我们编程的能力很有帮助，而且我们也希望多了解此类的知识。返回