《数据结构》实验报告
◎实验题目: 数据结构课程设计（无向连通网的问题求解）
◎实验目的：通过本次课程设计，掌握无向连通网的性质，熟悉其关于最短哈密尔顿回路以及最短路径的求解。
◎实验内容：对于具有n(n>=10)个顶点的无向连通网，设计一个算法 （1）找出网中最短的哈密尔顿回路；
（2）找出任意两个顶点之间的最短路径，须经过指定1个或2个顶点。 一、需求分析
1.本演示程序中，输入的无向连通网为任意给定的，输入时应该给定无向连通网的大小、范围，即顶点数以及边数，而输出有三个问题的求解答案，分别输出其路径及权值大小。 2.本演示程序为人机对话，用户可以按照提示进行输入，然后选择需要求解的问题，则有结果输出。
3.程序执行的命令包括：
（1）构建无向连通网（2）选择求解问题序号（3）第一个为求解最短哈密顿回路（3）第二个为求解任意两点之间的最短路径，须经过指定1个顶点（4）第三个为求解任意两点之间的最短路径，须经过指定2个顶点（5）结束 4.测试数据：
（1）请输入顶点数和边数(输入格式为:顶点数,边数):11,17
(2) 请输入顶点信息(输入格式为:顶点号):0 1 2 3 4 5 6 7 8 9 10
(3) 请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:): 0,6,5 0,7,4 0,4,3 1,4,1 1,6,8 1,3,2 2,4,6 2,3,3 2,10,7 3,5,8 5,10,3 5,9,8 6,7,1 7,8,4 7,9,6 8,9,2 9,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 请输入路径经过指定的顶点二：3
输出路径是：4->1->3->1->6->7->8->7->6->1
起始点为4终点为1的经过指定点一8以及指定点二3的最短路径为：31 <4>如果选择输入为0，结果为: 结束.
二 概要设计
为了实现上述操作，无向连通网用邻接矩阵存储结构，解决哈密顿回路问题时应用栈。 1. 基本操作：
void hamidun(mgraph &g) 求解最短哈密尔顿回路
int lujing(mgraph g,int v0,int vn,int dist[],int prev[])
求解指定两点之间的最短路径
void ShowPath(mgraph g,int v0,int u,int *dist,int *prev) 输出所求最短路径所经过的顶点
void zhiding1(mgraph g,int v0,int vn,int vx) 求解任意两点之间的最短路径，须经过指定1个顶点 void zhiding2(mgraph g,int v0,int vn,int vx1,int vx2) 求解任意两点之间的最短路径，须经过指定2个顶点 2. 本程序包含六个模块： (1)主程序模块
（2）求解最短哈密尔顿回路模块 （3）求解指定两点之间的最短路径模块 （4）输出所求最短路径所经过的顶点模块
（5）求解任意两点之间的最短路径，须经过指定1个顶点模块 （6）求解任意两点之间的最短路径，须经过指定2个顶点模块 （7）模块调用图 求解最短哈密尔顿 回路模块 主程序模块 求解任意两点之间的最短路径，须经过指定1个顶点模块 求解任意两点之间的最短路径，须经过指定2个顶点模块 求解指定两点之间的最短路径模块 输出所求最短路径所经过的顶点模块 三 详细设计
1.元素类型，结点类型和指针类型： //图中的节点数 #define M 50
//哈密顿回路最长值
#define MAX_LENGTH 1024 //单边最大值
#define MAX_SIDE_LENGTH 30 //节点信息结构 struct Node {
int level; //位于生成树的第几层 int dot; //第几个节点 };
typedef struct {
int edge[M][M]; int N,e;
int vexs[M];
}mgraph; Node s[99];
//记忆最短路径
Node aShortNode[M]; //记忆当前路径 Node aNode[M]; Node node;
2.每个模块的分析： (1)主程序模块 int main() {
int i,j,k,w,v0,vn,vx,vx1,vx2,m; mgraph g;
printf(\请输入顶点数和边数(输入格式为:顶点数,边数):\\n\scanf(\getchar();
printf(\请输入顶点信息(输入格式为:顶点号):\\n\for(i=0;i getchar(); for(i=0;i printf(\请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:):\\n\ for(k=0;k scanf(\g.edge[i][j]=g.edge[j][i]=w; printf(\ printf(\求解最短哈密尔顿回路.\\n\ printf(\求解任意两个顶点之间的经过指定一顶点的最短路径.\\n\ n\
相关推荐：
loading