资源描述：
《数据结构课程设计实验报告-无向图、哈密尔顿回路、最短路径》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、《数据结构》实验报告◎实验题目:数据结构课程设计（无向连通网的问题求解）◎实验目的：通过本次课程设计，掌握无向连通网的性质，熟悉其关于最短哈密尔顿回路以及最短路径的求解。◎实验内容：对于具有n(n>=10)个顶点的无向连通网，设计一个算法（1）找出网中最短的哈密尔顿回路；（2）找出任意两个顶点之间的最短路径，须经过指定1个或2个顶点.一、需求分析1.本演示程序中，输入的无向连通网为任意给定的，输入时应该给定无向连通网的大小、范围，即顶点数以及边数，而输出有三个问题的求解答案，分别输出其路径及权值大小。2.本演示程序为人机对话，用户可以按照提示进行输入，然后选择需要求解的问题，则
2、有结果输出。3.程序执行的命令包括：（1）构建无向连通网（2）选择求解问题序号（3）第一个为求解最短哈密顿回路（3）第二个为求解任意两点之间的最短路径，须经过指定1个顶点（4）第三个为求解任意两点之间的最短路径，须经过指定2个顶点（5）结束4.测试数据：（1）请输入顶点数和边数(输入格式为:顶点数,边数):11,17(2)请输入顶点信息(输入格式为:顶点号):012345678910(3)请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:):0,6,50,7,40,4,31,4,11,6,81,3,22,4,62,3,32,10,73,5,85,10,35,9
3、,86,7,17,8,47,9,68,9,29,10,6(4)请选择操作:<1>如果选择输入为1，结果为：最短哈密尔顿回路为：0->6->7->8->9->5->10->2->3->1->4->0权值为：5+1+4+2+8+3+7+3+2+1+3=39<2>如果选择输入为2，结果为：请输入指定起始点：0请输入指定终点：6请输入路径经过指定的顶点：10输出路径是：0->4->2->10->9->7->6起始点为0终点为6的经过指定点10的最短路径为：29<3>如果选择输入为3，结果为:请输入指定起始点：4请输入指定终点：1请输入路径经过指定的顶点一：8请输入路径经过指定的顶点二：
4、3输出路径是：4->1->3->1->6->7->8->7->6->1起始点为4终点为1的经过指定点一8以及指定点二3的最短路径为：31<4>如果选择输入为0，结果为:结束.二概要设计 为了实现上述操作，无向连通网用邻接矩阵存储结构，解决哈密顿回路问题时应用栈。1.基本操作：voidhamidun(mgraph&g)求解最短哈密尔顿回路intlujing(mgraphg,intv0,intvn,intdist[],intprev[])求解指定两点之间的最短路径voidShowPath(mgraphg,intv0,intu,int*dist,int*prev)输出所求最短路径所
5、经过的顶点voidzhiding1(mgraphg,intv0,intvn,intvx)求解任意两点之间的最短路径，须经过指定1个顶点voidzhiding2(mgraphg,intv0,intvn,intvx1,intvx2)求解任意两点之间的最短路径，须经过指定2个顶点1.本程序包含六个模块：(1)主程序模块（2）求解最短哈密尔顿回路模块（3）求解指定两点之间的最短路径模块（4）输出所求最短路径所经过的顶点模块（5）求解任意两点之间的最短路径，须经过指定1个顶点模块（6）求解任意两点之间的最短路径，须经过指定2个顶点模块（7）模块调用图主程序模块求解任意两点之间的最短路径，
6、须经过指定2个顶点模块求解任意两点之间的最短路径，须经过指定1个顶点模块求解最短哈密尔顿回路模块求解指定两点之间的最短路径模块输出所求最短路径所经过的顶点模块三详细设计1.元素类型，结点类型和指针类型：//图中的节点数#defineM50//哈密顿回路最长值#defineMAX_LENGTH1024//单边最大值#defineMAX_SIDE_LENGTH30//节点信息结构structNode{intlevel;//位于生成树的第几层intdot;//第几个节点};typedefstruct{intedge[M][M];intN,e;intvexs[M];}mgraph;No
7、des[99];//记忆最短路径NodeaShortNode[M];//记忆当前路径NodeaNode[M];Nodenode;2.每个模块的分析：(1)主程序模块intmain(){inti,j,k,w,v0,vn,vx,vx1,vx2,m;mgraphg;printf("请输入顶点数和边数(输入格式为:顶点数,边数):");scanf("%d,%d",&(g.N),&(g.e));getchar();printf("请输入顶点信息(输入格式为:顶点号):");for(i=0;i<
