#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#define Max 32767
#define NUM 48
typedef struct ArcCell
{
int adj; /* 相邻接的景点之间的路程 */
}ArcCell; /* 定义边的类型 */
typedef struct VertexType
{
int number; /* 景点编号 */
char* view; /* 景点名称 */
char* desc; /* 景点描述 */
}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[48]={0};
void CreateUDN(int v,int a); /* 造图函数 */
void shuoming(); /*说明函数*/
void ShortestPath(int num); /*最短路径函数*/
void output(int sight1,int sight2); /*输出函数*/
char Menu(); /* 主菜单 */
void search(); /* 查询景点信息 */
char SearchMenu(); /* 查询子菜单 */
void HaMiTonian(int); /*哈密尔顿图的遍历*/
void NextValue(int);
void display(); /* 显示遍历结果 */
void main() /* 主函数 */
{
int v0,v1;
char ck;
CreateUDN(NUM,198);
do
{
ck=Menu();
switch(ck)
{
case '1':
system("cls");
shuoming(); /* 输出景点列表 */
printf("\n\n\t\t\t请选择起点景点（0～47）：");
scanf("%d",&v0);
printf("\t\t\t请选择终点景点（0～47）：");
scanf("%d",&v1);
ShortestPath(v0); /* 计算两个景点之间的最短路径 */
output(v0,v1); /* 输出结果 */
printf("\n\n\t\t\t\t请按任意键继续...\n");
getchar();
getchar();
break;
case '2':
search();
break;
case '3':
system("cls");
shuoming();
x[0]=1;
HaMiTonian(1);
printf("\n\n\t\t\t\t请按任意键继续...\n");
getchar();
getchar();
break;
}
}while(ck!='t');
}
char Menu() /* 主菜单 */
{
char c;
int flag;
do{
flag=1;
system("cls");
shuoming();
printf("\n"); /* 输出景点列表 */
printf("\t\t\t┏━━━━━━━━━━━━━━━┑\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┃ 1、查询景点路径 ┃\n");
printf("\t\t\t┃ 2、查询景点信息 ┃\n");
printf("\t\t\t┃ 3、推荐参观路线 ┃\n");
printf("\t\t\t┃ t、退出 ┃\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
printf("\t\t\t\t请输入您的选择：");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='3'||c=='t')
flag=0;
}while(flag);
return c;
}
char SearchMenu() /* 查询子菜单 */
{
char c;
int flag;
do{
flag=1;
system("cls");
shuoming();
printf("\n");
printf("\t\t\t┏━━━━━━━━━━━━━━━┑\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┃ 1、按照景点编号查询 ┃\n");
printf("\t\t\t┃ 2、按照景点名称查询 ┃\n");
printf("\t\t\t┃ t、返回 ┃\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
printf("\t\t\t\t请输入您的选择：");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='t')
flag=0;
}while(flag);
return c;
}
void search() /* 查询景点信息 */
{
int num;
int i;
char c;
char name[40];
do
{
system("cls");
c=SearchMenu();
switch (c)
{
case '1':
system("cls");
shuoming();
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].desc);
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");
shuoming();
printf("\n\n\t\t请输入您要查找的景点名称：");
scanf("%s",name);
for(i=0;i<NUM;i++)
{
if(!strcmp(name,G.vex[i].view))
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-30s\n\n",G.vex[i].desc);
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!='t');
}
void CreateUDN(int v,int a) /* 造图函数 */
{
int i,j;
G.vexnum=v; /* 初始化结构中的景点数和边数 */
G.arcnum=a;
for(i=0;i<G.vexnum;++i)
G.vex[i].number=i; /* 初始化每一个景点的编号 */
/* G.vex[0].view ="南大门"; G.vex[1].view ="音乐楼"; G.vex[2].view ="学生会堂";
G.vex[3].view ="停车场"; G.vex[4].view ="博雅楼"; G.vex[5].view ="观物山";
G.vex[6].view ="办公楼"; G.vex[7].view ="田径场"; G.vex[8].view ="润泽苑";
G.vex[9].view ="实训楼"; G.vex[10].view="馥园餐厅"; G.vex[11].view="东门";
G.vex[12].view="体育中心"; G.vex[13].view="次出口"; G.vex[14].view="篮球场";
G.vex[15].view="足球场"; G.vex[16].view="篮球场"; G.vex[17].view="听心湖";
G.vex[18].view="惟行楼"; G.vex[19].view="图书馆"; G.vex[20].view="美术楼";
G.vex[21].view="农学楼"; G.vex[22].view="医学楼"; G.vex[23].view="惟真楼";
G.vex[24].view="惟实楼"; G.vex[25].view="西门"; G.vex[26].view="聂耳广场";
G.vex[27].view="篮球场"; G.vex[28].view="篮球场"; G.vex[29].view="网球场";
G.vex[30].view="青年中心"; G.vex[31].view="澄明苑"; G.vex[32].view="博文楼";
G.vex[33].view="博识楼"; G.vex[34].view="停车场"; G.vex[35].view="飨园餐厅";
G.vex[36].view="足球场"; G.vex[37].view="篮球场"; G.vex[38].view="篮球场";
G.vex[39].view="国际学术交流中心"; G.vex[40].view="高尔夫球场"; G.vex[41].view="专家公寓";
G.vex[42].view="青年职工公寓"; G.vex[43].view="产业孵化基地"; G.vex[44].view="南大门";
G.vex[45].view="自机学院实训用房"; G.vex[46].view="城建学院实训用房"; G.vex[47].view="实训基地";*/
/* 初始化没一个景点名及其景点描述 */
/* G.vex[0].desc ="本校的正大门"; G.vex[1].desc ="音乐学院专用教学楼"; G.vex[2].desc ="举办文艺会的场所";
G.vex[3].desc ="停放车辆的地下车场"; G.vex[4].desc ="中和楼"; G.vex[5].desc ="校园的一座小山";
G.vex[6].desc ="教务处"; G.vex[7].desc ="田径场"; G.vex[8].desc ="宿舍共14栋超市校园警卫";
G.vex[9].desc ="实训基地"; G.vex[10].desc="食堂、教工和回族食堂"; G.vex[11].desc="东门";
G.vex[12].desc="室内体育馆"; G.vex[13].desc="次出口"; G.vex[14].desc="篮球场";
G.vex[15].desc="足球场"; G.vex[16].desc="篮球场"; G.vex[17].desc="美丽的小湖";
G.vex[18].desc="教学楼 含医务室、展览馆"; G.vex[19].desc="图书馆"; G.vex[20].desc="美术学院专用教学楼";
G.vex[21].desc="农学院专用教学楼"; G.vex[22].desc="医学院专用教学楼"; G.vex[23].desc="教学楼";
G.vex[24].desc="惟实楼"; G.vex[25].desc="西门"; G.vex[26].desc="校园的主要广场";
G.vex[27].desc="篮球场"; G.vex[28].desc="篮球场"; G.vex[29].desc="网球场";
G.vex[30].desc="排练舞蹈的基地"; G.vex[31].desc="学生宿舍、超市、新知图书";G.vex[32].desc="教学楼";
G.vex[33].desc="博识楼"; G.vex[34].desc="停车场"; G.vex[35].desc="飨园餐厅";
G.vex[36].desc="足球场"; G.vex[37].desc="篮球场"; G.vex[38].desc="篮球场";
G.vex[39].desc="国际学术交流"; G.vex[40].desc="高尔夫球场"; G.vex[41].desc="专家公寓";
G.vex[42].desc="青年职工公寓"; G.vex[43].desc="产业孵化基地"; G.vex[44].desc="南大门";
G.vex[45].desc="自机学院实训用房"; G.vex[46].desc="城建学院实训用房"; G.vex[47].desc="实训基地";*/
/* 这里把所有的边假定为20000，含义是这两个景点之间是不可到达 */
/*for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j)
G.arcs[i][j].adj=Max;
G.arcs[0][1].adj =G.arcs[1][0].adj =100;
G.arcs[0][3].adj =G.arcs[3][0].adj =150 ;
G.arcs[0][4].adj =G.arcs[4][0].adj =50;
G.arcs[0][6].adj =G.arcs[6][0].adj =700;
G.arcs[0][7].adj =G.arcs[7][0].adj =800;
G.arcs[0][8].adj =G.arcs[8][0].adj =500;
G.arcs[0][11].adj =G.arcs[11][0].adj =1000;
G.arcs[0][13].adj =G.arcs[13][0].adj =1500;
G.arcs[0][19].adj =G.arcs[19][0].adj =1100;
G.arcs[0][25].adj =G.arcs[25][0].adj =1500;
G.arcs[0][44].adj =G.arcs[44][0].adj =2100;
G.arcs[1][2].adj =G.arcs[2][1].adj =20;
G.arcs[1][4].adj =G.arcs[4][1].adj =100;
G.arcs[2][3].adj =G.arcs[3][2].adj =70;
G.arcs[2][4].adj =G.arcs[4][2].adj =150;
G.arcs[3][5].adj =G.arcs[5][3].adj =70;
G.arcs[3][7].adj =G.arcs[7][3].adj =550;
G.arcs[3][19].adj =G.arcs[19][3].adj =800;
G.arcs[3][20].adj =G.arcs[20][3].adj =300;
G.arcs[3][21].adj =G.arcs[21][3].adj =70;
G.arcs[4][5].adj =G.arcs[5][4].adj =200;
G.arcs[4][7].adj =G.arcs[7][4].adj =100;
G.arcs[4][19].adj =G.arcs[19][4].adj =600;
G.arcs[5][6].adj =G.arcs[6][5].adj =250;
G.arcs[5][19].adj =G.arcs[19][5].adj =200;
G.arcs[5][20].adj =G.arcs[20][5].adj =350;
G.arcs[6][7].adj =G.arcs[7][6].adj =150;
G.arcs[6][18].adj =G.arcs[18][6].adj =270;
G.arcs[6][19].adj =G.arcs[19][6].adj =600;
G.arcs[7][8].adj =G.arcs[8][7].adj =200;
G.arcs[8][9].adj =G.arcs[9][8].adj =150;
G.arcs[8][10].adj =G.arcs[10][8].adj =50;
G.arcs[8][12].adj =G.arcs[12][8].adj =300;
G.arcs[8][14].adj =G.arcs[14][8].adj =160;
G.arcs[10][11].adj =G.arcs[11][10].adj =350;
G.arcs[11][12].adj =G.arcs[12][11].adj =200;
G.arcs[12][13].adj =G.arcs[13][12].adj =250;
G.arcs[13][17].adj =G.arcs[17][13].adj =130;
G.arcs[13][25].adj =G.arcs[25][13].adj =950;
G.arcs[13][27].adj =G.arcs[27][13].adj =180;
G.arcs[13][31].adj =G.arcs[31][13].adj =550;
G.arcs[14][15].adj =G.arcs[15][14].adj =120;
G.arcs[15][16].adj =G.arcs[16][15].adj =20;
G.arcs[15][18].adj =G.arcs[18][15].adj =150;
G.arcs[16][17].adj =G.arcs[17][16].adj =190;
G.arcs[17][18].adj =G.arcs[18][17].adj =60;
G.arcs[17][19].adj =G.arcs[19][17].adj =200;
G.arcs[17][26].adj =G.arcs[26][17].adj =280;
G.arcs[17][27].adj =G.arcs[27][17].adj =170;
G.arcs[17][30].adj =G.arcs[30][17].adj =150;
G.arcs[17][35].adj =G.arcs[35][17].adj =400;
G.arcs[18][19].adj =G.arcs[19][18].adj =100;
G.arcs[18][26].adj =G.arcs[26][18].adj =240;
G.arcs[18][30].adj =G.arcs[30][18].adj =400;
G.arcs[19][20].adj =G.arcs[20][19].adj =230;
G.arcs[19][26].adj =G.arcs[26][19].adj =30;
G.arcs[20][22].adj =G.arcs[22][20].adj =150;
G.arcs[21][22].adj =G.arcs[22][21].adj =50;
G.arcs[22][23].adj =G.arcs[23][22].adj =100;
G.arcs[23][24].adj =G.arcs[24][23].adj =150;
G.arcs[23][25].adj =G.arcs[25][23].adj =50;
G.arcs[23][32].adj =G.arcs[32][23].adj =50;
G.arcs[24][26].adj =G.arcs[26][24].adj =50;
G.arcs[24][33].adj =G.arcs[33][24].adj =50;
G.arcs[25][26].adj =G.arcs[26][25].adj =350;
G.arcs[25][32].adj =G.arcs[32][25].adj =50;
G.arcs[25][44].adj =G.arcs[44][25].adj =500;
G.arcs[26][30].adj =G.arcs[30][26].adj =260;
G.arcs[26][35].adj =G.arcs[35][26].adj =200;
G.arcs[27][28].adj =G.arcs[28][27].adj =20;
G.arcs[28][29].adj =G.arcs[29][28].adj =20;
G.arcs[29][30].adj =G.arcs[30][29].adj =200;
G.arcs[29][31].adj =G.arcs[31][29].adj =200;
G.arcs[30][31].adj =G.arcs[31][30].adj =200;
G.arcs[31][35].adj =G.arcs[35][31].adj =120;
G.arcs[31][36].adj =G.arcs[36][31].adj =200;
G.arcs[31][37].adj =G.arcs[37][31].adj =180;
G.arcs[32][33].adj =G.arcs[33][32].adj =180;
G.arcs[32][38].adj =G.arcs[38][32].adj =600;
G.arcs[32][39].adj =G.arcs[39][32].adj =160;
G.arcs[33][34].adj =G.arcs[34][33].adj =20;
G.arcs[33][39].adj =G.arcs[39][33].adj =150;
G.arcs[33][40].adj =G.arcs[40][33].adj =200;
G.arcs[34][35].adj =G.arcs[35][34].adj =230;
G.arcs[35][38].adj =G.arcs[38][35].adj =150;
G.arcs[35][40].adj =G.arcs[40][35].adj =300;
G.arcs[36][37].adj =G.arcs[37][36].adj =50;
G.arcs[37][38].adj =G.arcs[38][37].adj =50;
G.arcs[38][45].adj =G.arcs[45][38].adj =50;
G.arcs[39][40].adj =G.arcs[40][39].adj =200;
G.arcs[39][41].adj =G.arcs[41][39].adj =50;
G.arcs[40][41].adj =G.arcs[41][40].adj =50;
G.arcs[40][42].adj =G.arcs[42][40].adj =50;
G.arcs[41][42].adj =G.arcs[42][41].adj =50;
G.arcs[42][43].adj =G.arcs[43][42].adj =50;
G.arcs[43][44].adj =G.arcs[44][43].adj =100;
G.arcs[44][46].adj =G.arcs[46][44].adj =100;
G.arcs[45][46].adj =G.arcs[46][45].adj =50;
G.arcs[45][47].adj =G.arcs[47][45].adj =150;
G.arcs[46][47].adj =G.arcs[47][46].adj =150;*/
}
void shuoming() /* 说明函数 */
{
int i,k=0;
printf("\n\t\t******************欢迎烟台大学校园导航旅游程序****************\n");
printf("\t__________________________________________________________________\n");
printf("\t\t景点名称\t\t↓\t景点描述\n");
printf("\t________________________________↓_________________________________\n");
for(i=0;i<NUM;i++)
{
printf("\t%c (%2d)%-10s\t\t↓\t%-30s%c\n",25,i,G.vex[i].view,G.vex[i].desc,24); /* 输出景点列表 */
k=k+1;
}
printf("\t________________________________↓_________________________________\n");
}
void ShortestPath(int num) /* 迪杰斯特拉算法最短路径函数 num为入口点的编号 */
{·
int v,w,i,t; /* i、w和v为计数变量 */
int final[NUM]; /* */
int min;
for(v=0;v<NUM;v++)
{
final[v]=0; /* 假设从顶点num到顶点v没有最短路径 */
D[v]=G.arcs[num][v].adj;/* 将与之相关的权值放入D中存放 */
for(w=0;w<NUM;w++) /* 设置为空路径 */
P[v][w]=0;
if(D[v]<32767) /* 存在路径 */
{
P[v][num]=1; /* 存在标志置为一 */
P[v][v]=1; /* 自身到自身 */
}
}
D[num]=0;
final[num]=1; /* 初始化num顶点属于S集合 */
/* 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 */
for(i=0;i<NUM;++i) /* 其余G.vexnum-1个顶点 */
{
min=Max; /* 当前所知离顶点num的最近距离 */
for(w=0;w<NUM;++w)
if(!final[w]) /* w顶点在v-s中 */
if(D[w]<min) /* w顶点离num顶点更近 */
{
v=w;
min=D[w];
}
final[v]=1; /* 离num顶点更近的v加入到s集合 */
for(w=0;w<NUM;++w) /* 更新当前最短路径极其距离 */
if(!final[w]&&((min+G.arcs[v][w].adj)<D[w])) /*不在s集合，并且比以前所找到的路径都短就更新当前路径 */
{
D[w]=min+G.arcs[v][w].adj;
for(t=0;t<NUM;t++)
P[w][t]=P[v][t];
P[w][w]=1;
}
}
}
void output(int sight1,int sight2) /* 输出函数 */
{
int a,b,c,d,q=0;
a=sight2; /* 将景点二赋值给a */
if(a!=sight1) /* 如果景点二不和景点一输入重合，则进行... */
{
printf("\n\t从%s到%s的最短路径是",G.vex[sight1].view,G.vex[sight2].view);/* 输出提示信息 */
printf("\t(最短距离为 %dm.)\n\n\t",D[a]); /* 输出sight1到sight2的最短路径长度，存放在D[]数组中 */
printf("\t%s",G.vex[sight1].view); /* 输出景点一的名称 */
d=sight1; /* 将景点一的编号赋值给d */
for(c=0;c<NUM;++c)
{
gate: /* 标号，可以作为goto语句跳转的位置 */
P[a][sight1]=0;
for(b=0;b<NUM;b++)
{
if(G.arcs[d][b].adj<32767&&P[a][b]) /* 如果景点一和它的一个临界点之间存在路径且最短路径 */
{
printf("-->%s",G.vex[b].view); /* 输出此节点的名称 */
q=q+1; /* 计数变量加一，满8控制输出时的换行 */
P[a][b]=0;
d=b; /* 将b作为出发点进行下一次循环输出，如此反复 */
if(q%48==0)
printf("\n");
goto gate;
}
}
}
}
}
void HaMiTonian(int m) /* 哈密顿图的遍历 */
{
if(m>48)
return;
L: NextValue(m);
if(x[m]==0)
return;
if(m==7&&G.arcs[0][x[48]-1].adj!=20000)
display();
else
HaMiTonian(m+1);
goto L;
}
void NextValue(int k)
{
int j;
l:x[k]=(x[k]+1)%10;
if(x[k]==0)
return;
if(G.arcs[x[k-1]-1][x[k]-1].adj!=20000)
{
for(j=0;j<k;j++)
if(x[j]==x[k])
goto l;
return;
}
else
goto l;
}
void display()
{
int i=0;
printf("\n\n\t");
for(i=0;i<48;i++)
printf("%s->",G.vex[x[i]-1].view);
printf("出口");
printf("\n");
}