数据结构课设报告

第1页数据结构课程设计报告系（院）：计算机科学学院专业班级：计科11205班姓名：小专学号：201203396指导教师：詹炜老师设计时间：2014.6.11-2014.6.19设计地点：12教机房第2页目录一、课程设计目的************************************第3页二、设计任务及要求**********************************第3页三、设计方案****************************************第4页四、总体分析****************************************第5页五、实现过程及代码**********************************第9页六、输出界面****************************************第34页七、课程设计总结***********************************第41页第3页一．设计目的1．能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3．初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5．培养根据选题需要选择学习书籍，查阅文献资料的自学能力。二．设计任务及要求设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下：1．无向图的基本操作及应用①创建无向图的邻接矩阵②创建无向图的邻接表③无向图的深度优先遍历④无向图的广度优先遍历2．无向网的基本操作及应用①创建无向网的邻接矩阵②创建无向网的邻接表③求最小生成树3．有向图的基本操作及应用①创建有向图的邻接矩阵②创建有向图的邻接表③拓扑排序4．有向网的基本操作及应用①创建有向网的邻接矩阵②创建有向网的邻接表③关键路径④单源最短路径⑤每对顶点之间的最短路径三．设计方案由课程设计任务书，按照要求，需要设计有向图、有向网、无向图、无向网四种图，邻接矩阵、邻接表两种数据存储结构，共十六种基本操作及应用，三层以上的显示菜单。图的操作中又包含有有关线性表、栈和队列的基本操作。由于显示菜单已给出，剩下的只是把函数写入其中，而线性表、栈和队列的基本操作并不复杂，很容易实现，我们只有完成图的相关操作即可。图的操作都是以两种存储结构为基础的，邻接矩阵存储结构和邻接表存储结构，如四种图（有向图，有向网，无向图，无向网）的创建，其他的操作都是在四种图创建后才开始进行的。所以，首先必须理解两种存储结构的定义。图的邻接矩阵存储结构即图的数组表示法。用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。用邻接矩阵存储结构的图具有以下几点特征：第4页（一）：顶点数：vexnum，边（弧）数：arcnum，图的种类：kind；（二）：邻接矩阵：arcs(1顶点关系类型:adj2相关信息:info)；（三）：顶点向量（顶点名）：vers[]；其优点是以二维数组表示有n个顶点的图时，需存放n顶点的信息和n*n个弧的信息存储量。借助于邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求各个顶点的度。缺点其时间复杂度是O（n*n）,例如，构造一个具有n个顶点和e条边的无向网的时间复杂度为O（n*n+e*n）。图的邻接表存储结构是图的一种链式存储结构。对图中的每个顶点建立一个单链表，每个结点有三个域组成，邻接点域adjvex（弧尾在邻接表链表中的位序），链域nextarc（下一条弧），数据域info(权值)。还要建立一个邻接表链表，用以存放顶点名data和后继指针firstarc,表头结点以顺序结构的形式存储，便于随机访问任一顶点的单链表。邻接表存储结构的优点在于其时间复杂度小。除此之外，还有十字链表存储结构和多重链表存储结构。由于，没有用到他们，故不再详细描述。树的深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。从图中的某个顶点出发，访问此顶点，然后依次从该顶点出发深度优先搜索遍历图，直至图中所有与该顶点有关的路径都被访问到；此时图中若还有顶点未被访问到，则另选图中的一个未被访问的顶点作为起始点，重述上述过程，直至所有顶点都被访问到。广度优先搜索遍历类似于树的按层次遍历的过程。以某个顶点为起始顶点，由近至远，依次访问和该顶点有路径相通的且路径长度为1，2，3，······的顶点。当图中所有顶点都被访问到后，就完成了图的广度优先搜索遍历。求无向网的最小生成树问题有两种算法：Prima算法和Kruskal算法。Prima算法是从网中的某个顶点出发，选择与该顶点有路径的所有顶点中路径最小的一条路径，从该最小路径的另一顶点出发，重复上述过程，直至图中所有顶点都被访问完成。Kruskal算法是从网中找出所有路径最小的一条路径，记下已访问该路径的两个顶点，再次从图中找出剩下路径中的最小路径，重复上述过程，直至所有顶点都被访问完成，按访问的顺序依次输出各顶点，即构造了一棵最小生成树。由某个集合上的一个偏序得到该集合的一个全序的操作就叫做拓扑排序。如何进行拓扑排序呢？（1）在有向图中选择一个没有前驱的顶点并输出；（2）在图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，就得到了一个拓扑有序序列。求关键路径的算法如下(1)输入e条弧，建立AOE网的存储结构；(2)从源点v0出发,令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间。如果得到的拓扑有序序列中的顶点个数小于网中的顶点数，则说明网中存在环，不能求关键路径，算法终止；否则执行第三步。(3)从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]；(4)根据各顶点的和值，求每条弧的最早开始时间e(s)和最迟开始时间e(s)，若某条弧满足条件e(s)=l(s)，则为关键活动。从某个源点到其余各顶点的最短路径问题：若从v到vi有弧，则D[i]为弧上的权值，否则D[i]为无穷大。显然，长度为D[j]=Min{D[i]|vi属于V}的路径就是从v出发的长度最短的一条路径。四．总体分析第5页第一步：根据设计任务，设计DOS菜单。例如选择1之后应该类似于第二步：设计菜单voidShowMainMenu(){cout\n;cout***************图的基本操作及应用******************\n;cout*1无向图的基本操作及应用*\n;cout*2无向网的基本操作及应用*\n;cout*3有向图的基本操作及应用*\n;cout*4有向网的基本操作及应用*\n;cout*5退出*\n;cout***************************************************\n;}voidUDG(){MGraphMG;ALGraphALG;intn;do{cout\n;cout***************无向图的基本操作及应用***************\n;cout*1创建无向图的邻接矩阵*\n;cout*2创建无向图的邻接表*\n;cout*3无向图的深度优先遍历*\n;第6页cout*4无向图的广度优先遍历*\n;cout*5退出*\n;cout****************************************************\n;cinn;switch(n){case1:CreatUDG_M(MG);break;case2:CreatUDG_ALG(ALG);break;case3:break;case4:break;default:if(n!=5)cout错误，重新输入\n;}}while(n!=5);}voidUDN(){MGraphMN;ALGraphALN;intn;do{cout\n;cout***************无向网的基本操作及应用***************\n;cout*1创建无向网的邻接矩阵*\n;cout*2创建无向网的邻接表*\n;cout*3prim算法求最小生成树*\n;cout*4kraskal算法求最小生成树*\n;cout*5退出*\n;cout****************************************************\n;cinn;switch(n){case1:CreatUDN_M(MN);break;case2:CreatUDN_ALG(ALN);dispgraph_N(ALN);第7页break;case3:break;case4:break;default:if(n!=5)cout错误，重新输入\n;}}while(n!=5);}voidDG(){intn;do{cout\n;cout***************有向图的基本操作及应用***************\n;cout*1创建有向图的邻接矩阵*\n;cout*2创建有向图的邻接表*\n;cout*3拓扑排序*\n;cout*4退出*\n;cout****************************************************\n;cinn;switch(n){case1:break;case2:break;case3:break;default:if(n!=4)cout错误，重新输入\n;}}while(n!=4);}voidDN()第8页{intn;do{cout\n;cout***************有向网的基本操作及应用***************\n;cout*1创建有向网的邻接矩阵*\n;cout*2创建有向网的邻接表*\n;cout*3关键路径*\n;cout*4单源顶点最短路径问题*\n;cout*5每对顶点间最短路径问题*\n;cout*6退出*\n;cout****************************************************\n;cinn;switch(n){case1:break;case2:break;case3:break;case4:break;case5:break;default:if(n!=6)cout错误，重新输入\n;}}while(n!=6);}voidmain(){intn;do{ShowMainMenu();cinn;switch(n){case1:UDG();break;case2:第9页UDN();break;case3:DG();break;case4:DN();break;default:if(n!=5)cout错误，重新输入\n;}}while(n!=5);}无论多少级菜单，都可以用这种模式实现，并且当前菜单不用担心前面的问题，只需编写当前的功能函数。五．实现过程及代码（1）源代码如下：#includeiostream#includemalloc.husingnamespacestd;#defineOK1#defineTRUE1#defineFALSE0#defineINFINITY1000#defineMAX_VERTEX_NUM20#defineMAXQSIZE100#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefintVertexType;//顶点类型typedefintVRType;//权值类型typedef