云南大学软件学院数据结构实验6

实验难度：A□B□C□序号学号姓名成绩指导教师（签名）学期：2017秋季学期任课教师:实验题目:组员及组长:承担工作：联系电话:电子邮件:完成提交时间：年月日云南大学软件学院数据结构实验报告一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）1.基本思路：用无向网表示校区内的各建筑的平面图，图中顶点表示主要建筑，存放建筑的编号、名称、简介等信息，图中的边表示建筑间的道路，存放路径长度等信息，将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，边上的权值表示距离；根据用户的输入信息用迪杰斯特拉算法计算出任意两个地点之间的最短路径，并用二维数组来存储相关的信息，输出给用户；同时用数组存储各个地点的相关信息，当用户输入要了解的地点名称是，调用相关函数输出该地点的相关信息给用户。2、在程序中运用到了图的相关知识以及迪杰斯特拉算法和哈密尔顿图的遍历等，无向图的相关知识和相关操作，还有图的存储及相关的数据结构。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）主程序模块：该模块包含一个main函数，在main函数中调用其他函数和子程序。intmain(){intv0,v1;inti,num;charflag;Create(NUM,11);do{flag=Menu();switch(flag){case'1':system(cls);//清空屏幕的当前内容List();//输出景点列表printf(\n请选择起点景点（0~26）：);scanf(%d,&v0);printf(\n请选择终点景点（0~26）：);scanf(%d,&v1);ShortPath(v0);//求出最短路径Output(v0,v1);//输出结果printf(\n请按任意键继续...\n);getchar();//利用getchar()函数让程序运行到上一行时，等待下下一个按键时才返回getchar();break;case'2':system(cls);List();printf(\n请输入您要查找的景点编号：);scanf(%d,&num);for(i=0;iNUM;i++){if(num==g.vex[i].number){printf(\n你要查找的景点信息如下：);printf(\n%s:,g.vex[i].sight);printf(%s\n\n,g.vex[i].description);printf(\n按任意键返回...);getchar();getchar();break;}}if(i==NUM){printf(\n没有找到！);printf(\n按任意键返回...);getchar();getchar();}break;case'e':exit(0);}}while(flag!='0');return0;}流程图：子程序模块包括：地点列表函数、输出函数、哈密尔顿图的遍历函数、迪杰斯特拉算法判断最短路径函数、创建图的函数。各模块之间的调用关系：在主函数中调用列表函数，输出个地点，同时调用最短路径判断函数，计算出两地点之间的最短路径；调用输出函数来输出相关的信息给用户，调用图的创建函数来创建校园个地点所表示的无向图。在哈密尔顿图的遍历函数中递归调用该函数本身来实现校园内所有地点的遍历。核心关键算法：迪杰斯特拉算法：voidShortPath(intnum)//迪杰斯特拉算法最短路径函数，num为入口点的编号{intv,w,i,t;//v,w,i为计数变量intfinal[NUM];intmin;for(v=0;vNUM;v++){final[v]=0;//假设从顶点num到顶点v没有最短路径D[v]=g.arc[num][v].adj;//将与之相关的权值放入D中存放for(w=0;wNUM;w++)//设置为空路径P[v][w]=0;if(D[v]20000)//存在路径{P[v][num]=1;//存在标志位为1P[v][v]=1;//自身到自身}}D[num]=0;final[num]=1;//初始化num顶点属于S集合//***********************************************//开始主循环，作为更新。每次求得num到某个顶点的最短路径，并将其加入到S集合for(i=0;iNUM;++i)//其余g.vexnum-1个顶点{min=Max;//当前所知离顶点num的最近距离for(w=0;wNUM;++w)//w顶点在V-S中if(!final[w])//w顶点离num顶点更近{if(D[w]min){v=w;min=D[w];}}final[v]=1;//离num顶点更近的v加入到s集合for(w=0;wNUM;++w)//更新当前最短路径及其距离if(!final[w]&&((min+g.arc[v][w].adj)D[w]))//不在s集合且比以前所找到的路径都短就更新当前路径{D[w]=min+g.arc[v][w].adj;for(t=0;tNUM;t++)P[w][t]=P[v][t];P[w][w]=1;}}}哈密尔顿图遍历：voidHaMiTonian(intm)//哈密尔顿图的遍历{if(m26)return;L:NextValue(m);if(x[m]==0)return;if(m==26&&g.arc[0][x[26]-1].adj!=0000)Display();elseHaMiTonian(m+1);gotoL;}三、【实现（Implement）】(30%)（本部分应包括：抽象数据类型各操作的具体实现代码、关键操作的具体算法实现、函数实现，主程序实现等，并给出关键算法的时间复杂度分析。如有界面则需包括界面的关键实现方法等。）typedefstructArcCell{intadj;//相邻矩阵的建筑之间的路程}ArcCell;//定义改的类型typedefstructVertexType{intnumber;//建筑编号char*sight;//建筑名char*description;//建筑描述}VertexType;//定义定点的类型typedefstruct{VertexTypevex[NUM];//图中的顶点，即为景点ArcCellarc[NUM][NUM];//图中的边，即距离intvexnum,arcnum;//顶点数，边数}MGragh;//定义图的类型MGraghg;//把图定义为全局变量抽象数据类型定义：图的存储结构的定义、图的类型的定义、各相关头文件的定义及相关变量存储的大小的定义和各个函数的原型定义：#includestdio.h#includestdlib.h#includestring.h#defineMax10000#defineNUM27typedefstructArcCell{intadj;//相邻矩阵的建筑之间的路程}ArcCell;//定义改的类型typedefstructVertexType{intnumber;//建筑编号char*sight;//建筑名char*description;//建筑描述}VertexType;//定义定点的类型typedefstruct{VertexTypevex[NUM];//图中的顶点，即为景点ArcCellarc[NUM][NUM];//图中的边，即距离intvexnum,arcnum;//顶点数，边数}MGragh;//定义图的类型MGraghg;//把图定义为全局变量intP[NUM][NUM];//用于存储最短路径下标的数组longintD[NUM];//辅助变量存储最短路径长度intx[26]={0};voidCreate(intv,inta);//构造图函数voidList();//列表函数voidShortPath(intnum);//最短路径函数voidOutput(intsight1,intsight2);//输出函数charMenu();//主菜单voidHaMiTonian(int);//哈密尔顿图的遍历voidNextValue(int);voidDisplay();//显示遍历结果整个程序中用的相关的函数，在主函数中调用相关的函数和子程序，用哈密尔顿图的遍历函数实现校园中各地点在无向图中的描述，用迪杰斯特拉算法实现最短路径的判断和计算，设计输出函数来输出相关的信息给用户，各个子程序和相关函数之间调用相关的函数来实现相关的功能，用创建图函数来实现校园内各个地点在图中的表示。在时间复杂度上，迪杰斯特拉算法采用两层循环，其复杂度O(n^2)。四、【测试结果（Testing）】(10%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析，可附截图）开始界面：功能1：当用户输入1时，程序调用相关函数，算出两个地点之间的最短路径并把结果输出给用户，当用户输入1（百家大道）为起始地点，24（梓苑）为终点，程序算出了两点之间的最短路径长度及给出了相关的路径。功能2：当用户输入2时，程序给出相关地点的相关信息：退出：当用户输入e时，程序退出五、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，及存在的问题，所完成实验过程中的具体经验总结、心得）总结及心得：通过本次实验，我对在课堂上学到的有关图的知识有了进一步的了解和认识，对图的存储结构有了更深入的了解，学会了如何用代码来实现图的存储，同时我也对迪杰斯特拉算法有了进一步的了解，知道了如何用迪杰斯特拉算法来计算图中两个顶点之间的最短路径以及如何用哈密尔顿图的遍历算法来实现图的遍历，另外，我也学会了如何把图这种数据结构用到实际的程序中来实现相关的操作，对校园中各个地点如何用图这种数据结构来描述有了一定的了解和认识，学会了如何实现图的遍历及最短路径的判断和相关信息的输出。同时我也学会了如何组织一个程序，包括各个子程序之间的关系和各个函数之间的调用。六、思考题或【项目运作描述（Operate）】(10%)（注：选择C难度的才需要填写“项目运作描述”，其他难度的只需完成思考题）（项目运作描述应包括：项目的成本效益分析，应用效果等的分析。）在作用上，迪杰斯特拉算法每次可以算出单一定点到其他个顶点的最短路径；而弗洛伊德算法可以求出任意两个顶点间的最短路径。在时间复杂度上，迪杰斯特拉算法采用两层循环，其复杂度O(n^2)，弗洛伊德算法采用三层循环，其复杂O（n^3）。七、【代码】(10%)（本部分应包括：完整的代码及充分的注释。注意纸质的实验报告无需包括此部分。格式统一为，字体:Georgia,行距:固定行距12，字号:小五）例如：#includestdio.h#includestdlib.h#includestring.h#defineMax10000#defineNUM27typedefstructArcCell{intadj;//相邻矩阵的建筑之间的路程}ArcCell;//定义改的类型typedefstructVertexType{intnumber;//建筑编号char*sight;//建筑名char*description;//建筑描述}VertexType;//定义定点的类型typedefstruct{VertexTypevex[NUM];//图中的顶点，即为景点ArcCellarc[NUM][NUM];//图中的边，即距离intvexnum,arcnum;//顶点数，边数}MGragh;//定义图的类型MGraghg;//把图定义为全局变量intP[NUM][NUM];//用于存储最短路径下标的数组longintD[NUM];//辅助变量存储最短路