实验报告1

江西理工大学数据结构设计报告数据结构课程设计报告图的最短路径算法的实现C语言实现班级：计算机102姓名：沈亚伟指导教师：董跃华成绩：________________信息工程学院2012年6月14日江西理工大学数据结构设计报告目录1需求分析........................................................................................................................................11.1设计题目：图的最短路径算法的实现.............................................................................11.2设计内容.............................................................................................................................11.3设计提示.............................................................................................................................12.概要设计........................................................................................................................................22.1所有抽象数据类型定义.....................................................................................................22.2层次调用关系.....................................................................................................................22.3设计平面图.........................................................................................................................33详细分析........................................................................................................................................43.1设计思路.............................................................................................................................43.2主函数的详细设计.............................................................................................................43.3文件的读取.........................................................................................................................53.4解析字符串的详细设计.....................................................................................................53.5求最短路径的详细.............................................................................................................64.调试分析........................................................................................................................................75.测试结果........................................................................................................................................85.1菜单的测试.........................................................................................................................85.2查看校园内所有信息的测试.............................................................................................85.3查询校园内景点的信息.....................................................................................................85.4查询校园两个景点的最短路径.........................................................................................95.5退出的测试.........................................................................................................................96.参考文献.....................................................................................................................................107.附录............................................................................................................................................117.1文本文件...........................................................................................................................117.2源程序...............................................................................................................................11江西理工大学数据结构设计报告11需求分析1.1设计题目：图的最短路径算法的实现1.2设计内容设计校园平面图，所含景点不少于8个。以图中顶点表示学校内各景点，存放景点的名称、景点介绍信息等；以边表示路径，存放路径长度信息。要求将这些信息保存在文件graph.txt中，系统执行时所处理的数据要对此文件分别进行读写操作。1．从文件graph.txt中读取相应数据,创建一个图,使用邻接矩阵表示图；2．景点信息查询：为来访客人提供校园任意景点相关信息的介绍；3．问路查询：为来访客人提供校园任意两个景点之间的一条最短路径。选做内容（对文件进行操作，相应信息变化后，再次进行景点信息查询和问路查询时应该有所体现）1.修改一个已有景点的相关信息；2.增加一个新景点及其相关信息；3.增加一条新的路径；4.删除一个景点及其相关信息；5.删除一条路径。1.3设计提示1.校园道路是双向通行的，可设校园平面图是一个带权的无向图，用邻接矩阵表示此无向网。typedefstruct{charname[100];charinfo[10000];}VertexType;//顶点结构typedefstruct{VertexTypevexs[10];intarcs[100][100];//邻接矩阵intvexnum,arcnum;//顶点个数，边的个数2.将图的顶点信息和边的信息用数据文件graph.txt存储，数据文件格式可以设置如下形式：图中顶点数边的数目景点名称景点信息始点终点路径长度如可以在文件graph.txt中存储以下数据：815女生宿舍有南北两栋，6层南门经青春大道通往学校北门……正门主楼80正门图书馆400江西理工大学数据结构设计报告22.概要设计2.1所有抽象数据类型定义DispMat(MGraphg)操作结果：输出邻接矩阵g初始条件：图已经建立getFile(charfileName[],char*array[],int&count)操作结果：得到文件的信息初始条件：文件存在getInfo(int&vex,int&arc,char*array)操作结果：得到从文件中的顶点个数和边的个数初始条件：文件存在setVertexTypeInfo(MGraphg,char*arrayVer[])操作结果：设置VertexType的信息初始条件：图已经建立setVertexTypeInfo(MGraphg,char*arrayMGraph[],int&count)操作结果：设置无向图的基本信息初始条件：图已经建立ppath(MGraphg,intpath[][MAXV],inti,intj)操作结果：计算最短路径初始条件：图已经建立DisPath(MGraphg,intA[][MAXV],intpath[][MAXV],inti,intj)操作结果：输出最短路径初始条件：图已经建立2.2层次调用关系如图2.2所示：图2.2层次调用图江西理工大学数据结构设计报告32.3设计平面图如图2.3.1,2.3.2所示：图2.3.1学校平面图图2.3.2学校平面图缩略带距离版江西理工大学数据结构设计报告43详细分析3.1设计思路主函数流程图:（如图3.1所示）图3.1主函数流程图3.2主函数的详细设计主函数是一个程序的主体，当我们要进行我们所需要的操作的时候我们就要根据主函数中的显示信息和它给我们的相关的提示信息来进行所需要的操作。所以需要设置一个循环，只要用户不退出就让用户一直去查询。主要算法如下：while(n!=4){switch(n){case1:printf();for(inti=0;ig.vexnum;i++){printf(%d.%s\n,i+1,g.vexs[i].name);}江西理工大学数据结构设计报告5printf();break;case2:printf();if(m9&&m0){printf(g.vexs[m-1].name,g.vexs[m-1].info);printf();}break;cas