《算法与数据结构课程设计报告.doc》由会员分享，可在线阅读，更多相关《算法与数据结构课程设计报告.doc（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法与数据结构课程设计报告系（院）： 计算机科学学院 专业班级： 计科11101 姓 名： 袁斌 学 号： 指导教师： 周云才 设计时间： 2013.6.17 - 2012.6. 29 设计地点： 12教机房 报告目录一、课程设计目的 03二、设计任务及要求 03三、需求分析 04四、总体设计 04五、详细设计与实现 含代码和实现界面 06六、课程设计小结 17七、部分重要代码 18一、课程设计目的：1能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2提高程序设计和调试能力。学生通过上机实习
2、，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。4训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5培养根据选题需要选择学习书籍，查阅文献资料的自学能力二、设计任务及要求：设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下：1 无向图的基本操作及应用： 创建无向图的邻接矩阵（5.1.1）； 创建无向图的邻接表（5.1.2）； 无向图的深度优先遍历（5.1.3）； 无向图的广度优先遍历（5.1.4）。2 无向网的基
3、本操作及应用 创建无向网的邻接矩阵（5.2.1）； 创建无向网的邻接表（5.2.2）； Prim求最小生成树（5.2.3）； Kruskal求最小生成树（5.2.4）。3 有向图的基本操作及应用 创建有向图的邻接矩阵（5.3.1）； 创建有向图的邻接表（5.3.2）； 拓扑排序（5.3.3）。4 有向网的基本操作及应用 创建有向网的邻接矩阵（5.4.1）； 创建有向网的邻接表（5.4.2）； 关键路径（5.4.3）； 单源最短路径（5.4.4）； 每对顶点之间的最短路径（5.4.5）。三、需求分析：按照需求，需要设计四种图、两种存储结构、创建四种图的个两种存储结构的操作（8个）、其他基本操作、
4、多级菜单显示，图的操作有用到了线性表、栈和队列的基本操作。在老师给出了多级菜单现实的代码后，我们需要做的只是将函数写入其中。四、总体设计：我用的软件是Visual C+6.0。将不同的操作分在了不同的包里面。如右图所示。Typedef.h包里面是所有的相关结构定义；UDG_Operation.h包里面是有关于无向图的有关操作；UDN_Operation.h包里面是有关于无向网的有关操作；DG_Operation.h包里面是有关于有向图的有关操作；DN_Operation.h包里面是有关于有向网的有关操作；Queue_Operation.h包里面是有关队列的有关操作；Stack_Operatio
5、n.h包里面是顺序栈的有关操作。包的引用很有规范，如下：#include stdafx.h#include iostream#include#include stdlib.h#include#include#include malloc.h using namespace std;int visited20;#include Typedef.h#include Queue_Operation.h#include Stack_Operation.h#include UDG_Operation.h#include UDN_Operation.h#include DG_Operation.h#inc
6、lude DN_Operation.h菜单由于老师已经给出，主要就是将函数带上参数写入代码。在菜单选择后触发函数，得出结果。函数总结：创建无向图的邻接矩阵：CreatUDG_M(MG);打印无向图的邻接矩阵：dispgraph_MG(MG);创建无向图的邻接表：CreatUDG_ALG(ALG);打印无向图的邻接表：dispgraph_G(ALG);无向图的深度优先遍历：DFSTraverse(ALG);无向图的广度优先遍历：BFSTraverse(ALG);创建无向网的邻接矩阵：CreatUDN_M(MN);打印无向网的邻接矩阵：dispgraph_MN(MN);创建无向网的邻接表：Crea
7、tUDN_ALG(ALN);打印无向网图的邻接表：dispgraph_N(ALN);Prim算法求最小生成树：MiniSpanTree(MN,1);kraskal算法求最小生成树：kruskal();创建有向图的邻接矩阵： CreatDG_M(MG);打印有向图的邻接矩阵：dispgraph_MG(MG);创建有向图的邻接表：CreatDG_ALG(ALG);打印有向图的邻接表：dispgraph_DG_G(ALG);拓扑排序：TopologicalSort(ALG);创建有向网的邻接矩阵：CreatDN_M(MN);打印有向网的邻接矩阵：dispgraph_MN(MN);创建有向网的邻接表：
8、CreatDN_ALG(ALN);打印有向网的邻接表：dispgraph_DN_G(ALN);求关键路径：CriticalPath(ALN);求单源顶点最短路径：ShorttestPath_DIJ(MN,1);求每对顶点间最短路径：ShorttestPath_FLOYD(MN);大体设计就是这么一个流程。还有一些有关于循环队列和顺序栈的操作，这里就不一一列出了。五、详细设计与实现（含代码和实现界面）：5.0储存所有定义和预处理的包（typedef.h）5.0.1预处理：#define MAXVEX 30/最大结点的个数#define MAXCOST 1000/最大权值#define STACK
9、INCREMENT 10/栈的增量typedef char VertexType;/结点信息类型5.0.2图的邻接矩阵存储结构：typedef structVertexType vexsMAXVEX;/顶点信息 int arcsMAXVEXMAXVEX; int vexnum,arcnum;/顶点数、边数MGraph;5.0.3图的邻接表存储结构：typedef struct arcnodeint adjvex; /邻接点序号int w; /边或狐上的权struct arcnode *next;/指向下一条弧的指针ArcNode;typedef struct vnode VertexType
10、data; /顶点信息int indegree; /该点的度ArcNode *firstarc; /指向下一个边结点Vnode,AdjListMAXVEX;typedef structAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数ALGraph;5.0.4循环队列和栈的顺序存储表示a.在处理无向图的广度优先遍历用到了循环队列极其简单操作。/栈的顺序存储表示typedef structint *base;int *top;int Stacksize;SqStack; /队列定义typedef struct SqQueueint *base; int
11、front;int rear;SqQueue;5.0.5多级菜单展示主菜单：次级菜单展示：5.1无向图的基本操作及应用（UDG_Operation.h）5.1.1创建无向图的邻接矩阵用一个二维数组实现的。测试用如右图的无向图。测试结果： 5.1.2创建无向图的邻接表主要运用指针，运用链式分配存取空间。测试结果：5.1.3无向图的深度遍历无向图的深度优先遍历我采取的是用邻接表的方式。从图中的某个顶点出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历，直至途中所有和v有路径相同的顶点都被访问到，若此时还有顶点未被访问，则另选图中一个未曾被访问的顶点做起始点，重复上述过程，直到所有顶点
12、被访问完。测试结果：5.1.4无向图的广度优先遍历广度优先遍历也是利用邻接表，从顶点v出发访问v后依次访问v的各个未曾访问的邻接点，直到所有的邻接点被访问。若此时图中尚有顶点未被访问，则选择途中另一个未曾被访问的结点作为起始点重复上述过程。测试结果：5.2无向网的基本操作及应用（UDN_Operation.h）5.2.1创建无向网的邻接矩阵和无向图的几乎差不多，只是当两个顶点之间存在边时，存的是边的权值，不存在边时用-1表示。测试结果：5.2.2创建无向图的邻接表与无向图的几乎一样，只是把权值存入其中。测试结果：5.2.3prim算法求最小生成树主要利用无向网邻接矩阵的存取方式操作的，还需要用
13、到一个标志数组。测试结果： 5.2.4kraskal算法求最小生成树主要是如何判断两个顶点是否属于同一分支，这里用一个数组记录。测试结果： 5.3.1创建有向图的邻接矩阵有向图的邻接矩阵和无向图的邻接矩阵实现过程一样，只是存的弧是有顺序的。测试结果： 5.3.2创建有向图的邻接表有向图的邻接表的实现过程和无向图的过程几乎一样，只是存取弧是有顺序。测试结果：5.3.3拓扑排序有向图的拓扑排序主要用到栈，采用的是有向图的邻接表的存取方法。测试结果： 5.4.1创建有向网的邻接矩阵和无向网的邻接矩阵思想一样，其中两顶点有边时，存入他们的权值，弧也是有方向的。测试结果：5.4.2创建有向网的邻接表实现
14、过程与无向网的邻接表的实现过程一样，只是这里两点的边有方向。测试结果： 5.4.3求关键路径主要是求取每个活动的最早和最迟发生时间，这里用到拓扑排序的思想求最早发生时间和逆拓扑排序的思想求最迟发生时间。测试结果：5.4.4求单源顶点最短路径的问题运用了迪杰斯特拉算法，用了网的邻接矩阵存取方式。所求的无向网如右图。测试结果：5.4.5求每对顶点间最短路径的问题采用了弗洛依德算法，采用的也是有向网的邻接矩阵的存取方式。测试结果：六、课程设计小结：1难点与收获：这次是我第一次用Visual Studio 2008编写小程序，以前只是用它来做过一些动态网页，所以一开始使用的不是很熟悉，比如：包的导入顺
15、序这个问题也是让我找了半天先用到的必需放在前面。后来的编写过程也不是很顺利。书上都是一些伪码，使我不得不再到网上多看一些代码来做参考，但是也还是会遇到十分不好解决的问题。有一些算法很是复杂，参考再多也不能看懂。一般都还是得再去请教他人。代码做出来后，有的问题不是什么简单的语法问题，而是逻辑问题。这种是最难找的，不过我还是想起了以前老师教的一种方法：设置断点，新加入做参考的变量一步一步的调试。用这个方法着实解决了一些变量的问题，如未初始化、没有加&改变数据。通过这一次的课设，我深深的体会到了编写代码所必须的性格：耐心、细心。在遇到问题是一定要静下心来，不要急躁，细心的查看代码，耐心的调试。在这些
16、过程当中，确实会感到急躁，但是一旦在我们解决问题后，总是会有一种成就感油然而生。我想这应该是学习计算机的人们都会有的感觉吧。在今后的学习中我定将继续努力，继续享受这份学习计算机编程的乐趣。2可以改进的地方我知道我程序写的不完美，有许多可改进的地方，但是在目前我还不知道具体需要从哪里下手改进，如果我知道我一定会用我觉得好的方法去编写。不得不说，我现在的水平和理解能力有限，有待提高的地方还有很多。学习编程的路程是艰辛的，我现在自己独立编写代码，独立思考的能力还是太有限了，代码参考的成分居多，希望以后我可以更加独立的去完成任务。七、部分重要代码：UDG_Operation.h 无向图的深度优先遍历和
17、广度优先遍历。/无向图的深度优先遍历void DFS(ALGraph ALG,int v)ArcNode *p;int v1=ALG.verticesv.data;coutv1adjvex=0)DFS(ALG,p-adjvex);p=p-next;void DFSTraverse(ALGraph ALG)int v;for(v=1;v=ALG.vexnum;v+)visitedv=0;cout该图的深度优先遍历结果:;for(v=1;v=ALG.vexnum;v+)if(visitedv=0)DFS(ALG,v);coutfront=Q-rear=0; coutALG.verticesv.da
18、taadjvex=0)v=p-adjvex;coutALG.verticesv.datanext;void BFSTraverse(ALGraph ALG)int v;for(v=1;v=ALG.vexnum;v+)visitedv=0;cout该图的广度优先遍历结果:;for(v=1;v=ALG.vexnum;v+)if(visitedv=0)BFS(ALG,v);UDN_Operation.h prim算法和kruskal算法求最小生成树/prim算法求最小生成树void MiniSpanTree(MGraph G,int u) int i,i1;int j,j1;int k=INT_MA
19、X;j1=u;structint lowcost;/各边上当前最小权值int adjvex;/权值依附的顶点的序号closedgeMAXVEX;for(j=1;j=G.vexnum ;j+) /初始化辅助数组if(j!=u)closedgej.lowcost =G.arcs uj;if(G.arcs uj!=-1)closedgej.adjvex =u;elseclosedgej.adjvex =0;elseclosedgej.lowcost =0;for(i=1;i=G.vexnum-1 ;i+)k=INT_MAX;for(i1=1;i1=G.vexnum ;i1+) /找到当前最小的边if
20、(i1!=u&closedgei1.lowcost !=-1&closedgei1.lowcost !=0)if(closedgei1.lowcost k)k=closedgei1.lowcost ;u=closedgei1.adjvex ;j1=i1;coutG.vexs u;coutG.vexs j1endl;closedgej1.lowcost =0;for(j=1;j=G.vexnum ;j+) /添加新的结点if(closedgej.lowcost !=-1)if(G.arcs j1j!=-1&G.arcs j1jclosedgej.lowcost&closedgej.lowcost
21、 !=0 )closedgej.lowcost =G.arcs j1j;closedgej.adjvex =j1;elseclosedgej.lowcost =G.arcs j1j;closedgej.adjvex =j1;/kruskal算法求最小生成树int rMAXVEX+1;/记录点的顺序int pMAXVEX+1;/判断是结点否属于同一分支数组int choMAXVEX*(MAXVEX-1)/2+1=0;/记录边的顺序int n;/顶点数int m;/边数struct edgeint u;/起始点编号int v;/终点编号int w;/权值eMAXVEX*(MAXVEX-1)/2+1
22、;void Init()int i;for(i=1;i=MAXVEX;i+)pi=i;ri=0;bool cmp(edge a,edge b) /判断两条边权值的大小return a.w ry)ry=x;elsepx=y;if(rx=ry)ry+;void kruskal()coutnm;int i,j;for(i=1;i=m;i+)cout请输入第iei.u ei.v ei.w ;Init();sort(e+1,e+m+1,cmp);int cnt=0;for(i=1;i=m;i+)if(Find(ei.u )!=Find(ei.v )cnt+;Union(ei.u ,ei.v );cho+
23、cho0=i;if(cnt=n-1)break;for(j=1;j=cho0;j+)coutechoj.u echoj.v ;DG_Operation.h 拓扑排序void TopologicalSort(ALGraph ALG)int i;int k;int count=0;ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode);SqStack S;InitStack(S);for(i=1;i=ALG.vexnum ;i+)if(ALG.vertices i.indegree =0)Push(S,i);while(S.top !=S.base )Pop(S,
24、i);coutALG.vertices i.data next)k=p-adjvex ;ALG.vertices k.indegree -;if(ALG.vertices k.indegree =0)Push(S,k);if(countALG.vexnum )cout该有向图中存在环endl;return;DN_Operation.h 关键路径，单源顶点最短路径问题每对顶点间最短路径问题/求关键路径int veMAXVEX;int vlMAXVEX;/求最早发生时间int TopologicalOrder(ALGraph ALN,SqStack &T)int i;int k;int count
25、=0;ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode);SqStack S;InitStack(S);for(i=1;inext )k=p-adjvex ;ALN.vertices k.indegree -;if(ALN.vertices k.indegree =0)Push(S,k);if(vei+p-w vek)vek=vei+p-w ;if(countALN.vexnum )cout该有向图中存在环endl;return false;elsereturn true;void CriticalPath(ALGraph ALG)int i,j,k,du
26、t;int ee,el;SqStack T;InitStack(T);ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode);for(i=1;i=ALG.vexnum ;i+)vei=0;if(!TopologicalOrder(ALG,T)return;for(i=1;inext)k=p-adjvex ;dut=p-w;if(vlk-dutvlj)vlj=vlk-dut;for(i=1;inext)k=p-adjvex ;dut=p-w;ee=vei;el=vlk-dut;if(ee=el)coutALG.vertices i.data( dut ALG.v
27、erticesk.data endl; /单源顶点最短路径问题struct int length;int pre;distMAXVEX;structint dataMAXVEX;int top;s;void ShorttestPath_DIJ(MGraph MN,int v0)int i,j,k,min;int finalMAXVEX;for(i=1;i0)disti.pre =v0;elsedisti.pre =0;distv0.pre =0;finalv0=1;for(i=1;iMN.vexnum ;i+)min=INT_MAX;for(j=1;j=MN.vexnum ;j+)if(fin
28、alj!=1)&(distj.length 0)min=distj.length ;k=j;finalk=1;for(j=1;j=MN.vexnum;j+ )if(MN.arcs kj!=-1)&(!finalj)&(distj.length !=-1)&(min+MN.arcs kjdistj.length )distj.length =min+MN.arcskj;distj.pre =k;if(MN.arcs kj!=-1)&(!finalj)&(distj.length =-1)distj.length =min+MN.arcs kj;distj.pre =k;for(i=1;i=MN.
29、vexnum ;i+)coutMN.vexsv0 MN.vexs i:disti.length(;s.top =-1;s.data +s.top =i;j=disti.pre ;while(j)s.data +s.top =j;j=distj.pre ;while(s.top !=-1)coutMN.vexs s.data s.top- ;cout)endl;/每对顶点最短路径问题void find(int PMAXVEXMAXVEXMAXVEX,MGraph MN,int a,int b)int k;for(k = 1; k = MN.vexnum; k+)if(Pabk=1 & k!=a
30、& k!=b)find(P,MN,a,k);printf(%ct,MN.vexs k);find(P,MN,k,b);void ShorttestPath_FLOYD(MGraph MN)int u,v,w;int DMAXVEXMAXVEX;int PMAXVEXMAXVEXMAXVEX;for(v=1;v=MN.vexnum ;+v)for(w=1;w=MN.vexnum ;w+)Dvw=MN.arcs vw;for(u=1;u=MN.vexnum ;u+)Pvwu=0;if(Dvw!=-1)/v到w有直接路径Pvwv=1;Pvww=1;for(u=1;u=MN.vexnum ;u+)fo
31、r(v=1;v=MN.vexnum ;v+)for(w=1;w=MN.vexnum ;w+)if(Dvu+DuwDvw&Dvu!=-1&Duw!=-1)Dvw=Dvu+Duw;for(int i=1;i=MN.vexnum ;i+)Pvwi=Pvui|Puwi;if(Dvw=-1&Dvu!=-1&Duw!=-1)Dvw=Dvu+Duw;for(int i=1;i=MN.vexnum ;i+)Pvwi=Pvui|Puwi;for(u=1;u=MN.vexnum ;u+)for(v=1;v=MN.vexnum ;v+)if(Duv!=-1&u!=v)coutMN.vexs u到MN.vexs v的最短距离是：;coutMN.vexs ut ;find(P,MN,u,v);coutMN.vexs v ;cout长度为Duv;coutendl;指导老师意见：成绩: 教师签名： 年 月 日