实验难度： A □ B □ C □序号学号姓名成绩
指导教师（签名）
学期：2017秋季学期
任课教师:
实验题目:
组员及组长:
承担工作：
联系电话:
电子邮件:
完成提交时间：年月日
一、【实验构思（Conceive）】(10%)
（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）
1.基本思路：用无向网表示校区内的各建筑的平面图，图中顶点表示主要建筑，存放建筑的编号、名称、简介等信息，图中的边表示建筑间的道路，存放路径长度等信息，将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，边上的权值表示距离；根据用户的输入信息用迪杰斯特拉算法计算出任意两个地点之间的最短路径，并用二维数组来存储相关的信息，输出给用户；同时用数组存储各个地点的相关信息，当用户输入要了解的地点名称是，调用相关函数输出该地点的相关信息给用户。
2、在程序中运用到了图的相关知识以及迪杰斯特拉算法和哈密尔顿图的遍历等，无向图的相关知识和相关操作，还有图的存储及相关的数据结构。
二、【实验设计(Design)】(20%)
（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）
主程序模块：该模块包含一个main函数，在main函数中调用其他函数和子程序。int main()
{
int v0, v1;
int i, num;
char flag;
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; 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');
return 0;
}
流程图：
子程序模块包括：地点列表函数、输出函数、哈密尔顿图的遍历函数、迪杰斯特拉算法判断最短路径函数、创建图的函数。
各模块之间的调用关系：在主函数中调用列表函数，输出个地点，同时调用最短路径判断函数，计算出两地点之间的最短路径；调用输出函数来输出相关的信息给用户，调用图的创建函数来创建校园个地点所表示的无向图。在哈密尔顿图的遍历函数中递归调用该函数本身来实现校园内所有地点的遍历。
核心关键算法：
迪杰斯特拉算法：
void ShortPath(int num)//迪杰斯特拉算法最短路径函数，num为入口点的编号
{
int v, w, i, t;//v, w, i为计数变量
int final[NUM];
int min;
for (v = 0; v{
final[v] = 0;//假设从顶点num到顶点v没有最短路径
D[v] = g.arc[num][v].adj;//将与之相关的权值放入D中存放
for (w = 0; wP[v][w] = 0;
if (D[v]<20000)//存在路径
{
P[v][num] = 1;//存在标志位为1
P[v][v] = 1;//自身到自身
}
}
D[num] = 0;
final[num] = 1;//初始化num顶点属于S集合
//***********************************************
//开始主循环，作为更新。每次求得num到某个顶点的最短路径，并将其加入到S集合for (i = 0; i{
min = Max;//当前所知离顶点num的最近距离
for (w = 0; wif (!final[w])//w顶点离num顶点更近
{
