#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#define Max 32767
#define NUM 11
typedef struct ArcCell{
int adj; // 相邻接的景点之间的路程
char *info;
}ArcCell; // 定义边的类型
typedef struct VertexType{
int number; // 景点编号
char *sight; // 景点名称
char *description; // 景点描述
}VertexType; // 定义顶点的类型
typedef struct{
VertexType vex[NUM]; // 图中的顶点,即为景点
ArcCell arcs[NUM][NUM]; // 图中的边,即为景点间的距离
int vexnum,arcnum; // 顶点数,边数
}MGraph; // 定义图的类型
MGraph G; // 把图定义为全局变量
int P[NUM][NUM]; // //
long int D[NUM]; // 辅助变量存储最短路径长度
int x[13]={0};
void CreateUDN(int v,int a); // 创建图的函数
void pingmu(); //屏幕输出函数
void introduce();
void ShortestPath(int num); //最短路径函数
void output(int sight1,int sight2); //输出函数
void PrintMGraph();
char Menu(); // 主菜单
void search();
;// 查询景点信息
char SearchMenu(); // 查询子菜单
void HaMiTonian(int); // 哈密尔顿图的遍历
void NextValue(int);
void display(); // 显示遍历结果
void main() // 主函数
{ int v0,v1;
char ck;
system("color 1A");//背景颜色显示函数
CreateUDN(NUM,11);
do
{
ck=Menu();
switch(ck)
{
case'1':
introduce();//介绍函数
printf("\n\n\t\t\t%-25s\n\n",G.vex[0].description);
getchar();
getchar();
break;
case '2':
system("cls");
pingmu();
printf("\n\n\t\t\t请选择起点景点(1~10):");
scanf("%d",&v0);
printf("\t\t\t请选择终点景点(1~10):");
scanf("%d",&v1);
ShortestPath(v0); // 计算两个景点之间的最短路径
output(v0,v1); // 输出结果
printf("\n\n\t\t\t\t请按回车键继续...\n");
getchar();
getchar();
break;
case '3':search();
break;
case '4':
system("cls");
pingmu();//屏幕输出函数,输出操作界面
x[0]=1;
HaMiTonian(1);
printf("\n\n\t\t\t\t请按回车键继续...\n");
getchar();
getchar();
break;
case'5':
PrintMGraph();
printf("\n\n\t\t\t\t请按回车键继续...\n");
getchar();
getchar();
break;
};
}while(ck!='e');
}
char Menu() // 主菜单 //
{
char c;
int flag;
do{
flag=1;
system("cls");
pingmu();
introduce();
printf("\n\t\t┏━━━━━━━━━━━━━━━━━━━┑\n");
printf("\t\t┃ ┃\n");
printf("\t\t┃ 1.学校简介 ┃\n");
printf("\t\t┃ 2.查询景点路径 ┃\n");
printf("\t\t┃ 3.查询景点信息 ┃\n");
printf("\t\t┃ 4.查看参观路线 ┃\n");
printf("\t\t┃ 5.查询各景点之间的距离 ┃\n");
printf("\t\t┃ e.退出 ┃\n");
printf("\t\t┃ ┃\n");
printf("\t\t┗━━━━━━━━━━━━━━━━━━━┛\n");
printf("\t\t\t\t请输入您的选择:");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='e')
flag=0;
}while(flag);
return c;
}
char SearchMenu() // 查询子菜单
{
char c;
int flag;
do{
flag=1;
system("cls");
pingmu();
introduce();
printf("\n\t\t┏━━━━━━━━━━━━━━━━━━┑\n");
printf("\t\t┃ ┃\n");
printf("\t\t┃ 1、按照景点编号查询 ┃\n");
printf("\t\t┃ 2、按照景点名称查询 ┃\n");
printf("\t\t┃ e、返回 ┃\n");
printf("\t\t┃ ┃\n");
printf("\t\t┗━━━━━━━━━━━━━━━━━━┛\n");
printf("\t\t\t请输入您的选择:");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='e')
flag=0;
}while(flag);
return c;
}
void search() // 查询景点信息
{
int num;
int i;
char c;
char name[20];
do
{
system("cls");
c=SearchMenu();
switch (c)
{
case '1':
system("cls");
introduce();
pingmu();
printf("\n\n\t\t请输入您要查找的景点编号:");
scanf("%d",&num);
for(i=0;i<NUM;i++)
{
if(num==G.vex[i].number)
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
printf("\n\t\t\t按任回车返回...");
getchar();
getchar();
break;
}
}
if(i==NUM)
{
printf("\n\n\t\t\t没有找到!");
printf("\n\n\t\t\t按回车键返回...");
getchar();
getchar();
}
break;
case '2':
system("cls");
pingmu();
introduce();
printf("\n\n\t\t请输入您要查找的景点名称:");
scanf("%s",name);
for(i=1;i<NUM;i++)
{
if(!strcmp(name,
G.vex[i].sight))
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
printf("\n\t\t\t按回车键返回...");
getchar();
getchar();
break;
}
}
if(i==NUM)
{
printf("\n\n\t\t\t没有找到!");
printf("\n\n\t\t\t按回车键返回...");
getchar();
getchar();
}
break;
}
}while(c!='e');
}
void CreateUDN(int v,int a) // 创建图的函数
{
int i,j;
G.vexnum=v; // 初始化结构中的景点数和边数
G.arcnum=a;
for(i=1;i<G.vexnum;++i) G.vex[i].number=i; // 初始化每一个景点的编号
// 初始化没一个景点名及其景点描述
G.vex[0].sight="学校简介";
G.vex[1].sight="北校门";
G.vex[2].sight="校史馆";
G.vex[3].sight="联谊馆";
G.vex[4].sight="思源学堂";
G.vex[5].sight="田径场";
G.vex[6].sight="5,6号食堂";
G.vex[7].sight="四号教学楼";
G.vex[8].sight="五号教学楼";
G.vex[9].sight="南校门";
G.vex[10].sight="图书馆";
// 这里把所有的边假定为32767,含义是这两个景点之间是不可到达
for(i=1;i<G.vexnum;++i)
{
for(j=1;j<G.vexnum;++j)
{
G.arcs[i][j].adj=Max;
G.arcs[i][j].info=NULL;
}
}
//下边是可直接到达的景点间的距离,由于两个景点间距离是互相的,
// 所以要对图中对称的边同时赋值。
G.arcs[1][7].adj=G.arcs[7][1].adj=50;
G.arcs[1][2].adj=G.arcs[2][1].adj=60;
G.arcs[1][3].adj=G.arcs[3][1].adj=100;
G.arcs[3][7].adj=G.arcs[7][3].adj=20;
G.arcs[4][5].adj=G.arcs[5][4].adj=50;
G.arcs[3][4].adj=G.arcs[4][3].adj=10;
G.arcs[6][9].adj=G.arcs[9][6].adj=1200;
G.arcs[5][10].adj=G.arcs[10][5].adj=500;
G.arcs[5][7].adj=G.arcs[7][5].adj=100;
G.arcs[4][6].adj=G.arcs[6][4].adj=20;
G.arcs[6][10].adj=G.arcs[10][6].adj=650;
G.arcs[6][5].adj=G.arcs[5][6].adj=70;
G.arcs[7][8].adj=G.arcs[8][7].adj=400;
G.arcs[8][10].adj=G.arcs[10][8].adj=50;
G.arcs[9][10].adj=G.arcs[10][9].adj=1100;
}
// 打印出邻接矩阵
void PrintMGraph()
{
int i,j;
printf("\n ====================================================================\n\n ");
for(i=1;i<G.vexnum;++i)
{
printf(G.vex[i].sight);
}
printf("\n");
for(i=1;i<G.vexnum;++i)
{
printf("\n\n",G.vex[i].sight);
for(j=1;j<G.vexnum;++j)
{
if(G.arcs[i][j].adj==Max)
printf(" @ ");
else
printf("%d ",G.arcs[i][j].adj);
}
}
printf("\n\n\n\n==========================================================================================\n\n\n");
}
void introduce() // 介绍函数
{
int i;
for(i=1;i<=NUM;i++)
{
G.vex[0].description="海南大学是2007年8月由华南热带农业大学和原海南大学合并组建而成的省属综合性重点大学,\n 是海南省人民政府与教育部、财政部共建高校和国家“211工程”重点建设高校,同时还是国家大学生文化素质教育基地、全国华文教育基地、\n\t国家“中西部高校综合能力提升工程”高校、国家教育体制改革试点高校、全国大学生英语教学改革示范高校、全国毕业生就业典型经验高校和教育部\n\t“卓越工程师教育培养计划”高校,是具有推荐优秀应届本科毕业生免试攻读硕士研究生资格的高校、国家建设高水平大学公派研究生出国留学资格的\n\t高校和接受中国政府奖学金来华留学生资格的高校。";
G.vex[1].description="走过海口最长最美的桥——世纪大桥,右行500米就来到了海大北门";
G.vex[2].description="新建的方形楼,记录着海大的成长过程";
G.vex[3].description="联谊馆也是学校的体育馆,海口羽毛球爱好者经常来这里比赛";
G.vex[4].description="拥有海南大学最大的报告厅,能容纳1000多人,是海大最漂亮的建筑之一。";
G.vex[5].description="我们学校最大的运动场,学校师生经常来这锻炼身体,每年各个校区都要到这 里来搞运动会";
G.vex[6].description="这有我们学校的5,6号食堂,价格有点贵,里面的饭菜可以想象。。。";
G.vex[7].description="这是我们学校的4号教学楼,有4座6层楼,是同学们每天上课学习的地方";
G.vex[8].description="这是我们学校最大的教学楼系,雅思,托福经常在这考试,也是同学们自习的好地方";
G.vex[9].description="学校的南校门,从这里出去,有很多餐馆和小吃,都还算便宜,每晚\n\t 同学一般都来这聚餐";
G.vex[