#define INFINITY 10000
#define MAX_VERTEX_NUM 40
#define MAX 40
#include<>
#include<>
#include<>
#include<>
typedef struct ArCell
{
int adj; /*路径长度*/
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct/*图中顶点表示主要景点,存放景点的编号、名称、简介等信息, */ {
char name[30];
int num;
char introduction[100];/*简介*/
}infotype;
typedef struct
(
{
infotype vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
MGraph b;
void cmd(void);
MGraph InitGraph(void);
void show1();
(
void list();
void Menu(void);
void ShortestPath_DIJ(MGraph * G);
void Search(MGraph *G);
int LocateVex(MGraph *G,char* v);
/**********主函数************************/
void main(void)
{
system("color 5f"); /*修改控制台的颜色信息,改为白字蓝底的模式*/ system("mode con: cols=140 lines=130"); /*设置批处理运行时窗口大小的*/ "
cmd();
}
/********自定义函数***************/
/* cmd函数(根据目录选择要进行的项目)*/
void cmd(void)
{
char k;
b=InitGraph();
show1();
Menu();
~
while(1)
{
scanf("\n%c",&k);
switch(k)
{
case'x':
system("cls");
show1();
Menu();
list();
;
ShortestPath_DIJ(&b);
printf("---------------------------------欢迎您的使用--------------------------------\n");
printf("\n请您继续选择服务:");
break;
case'y':
system("cls");
Menu();
list();
Search(&b);
printf("---------------------------------欢迎您的使用--------------------------------\n"); (
printf("\n请您继续选择服务:");
break;
case'z':
system("cls");
printf(" ┏━━━━━━━━━━━━━━━━━━━━┓\n");
printf(" ┃感谢使用┃\n");
printf(" ┃安徽建筑术大学┃\n");
printf(" ┃智能导航系统┃\n");
printf(" ┗━━━━━━━━━━━━━━━━━━━━┛\n");
exit(0);
~
default:
printf("输入信息错误！\n请输入x或y或z.\n");
break;}}
}
/* 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点*/
void ShortestPath_DIJ(MGraph * G)
]
{
int v,w,i,min,t=0,x,flag=1,v0,v1,have[100],k;
int final[20], D[20], p[23][23];
while(flag)
{
printf("请输入起始景点编号:\n");
scanf("%d",&v0);
if(v0<0||v0>G->vexnum)
printf("景点编号不存在!");
，
printf("请输入终止景点编号:\n");
scanf("%d",&v1);
if(v1<0||v1>G->vexnum)
printf("景点编号不存在!");
if(v0>=0&&v0
}
for(v=0;v
{
！
final[v]=0;
D[v]=G->arcs[v0][v].adj;
for(w=0;w
p[v][w]=INFINITY;
if(D[v] { p[v][v0]=1; p[v][v]=1; } } > D[v0]=0; final[v0]=1; have[0]=v0; for(i=1;i { min=INFINITY; for(w=0;w if(!final[w]) if(D[w] { { v=w; min=D[w]; } final[v]=1; have[k]=v; k++; for(w=0;w if(!final[w]&&((min+(G->arcs[v][w].adj)) { D[w]=min+G->arcs[v][w].adj; : for(x=0;x p[w][x]=p[v][x]; p[w][w]=1; } } for(i=0;i { if(p[v1][have[i]]==1){ printf("-->%s",G->vexs[have[i]].name);} } … if((v1-v0)==1)printf("\n路径长度:%d\n",G->arcs[v0][v1]); else printf("\n路径长度:%d\n",D[v1]); }um,G->vexs[k].name,G->vexs[k].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); }择出发点和目的地┃\n"); printf(" ┃y.查看景点信息┃\n"); printf(" ┃z.退出系统┃\n"); printf(" ┗━━━━━━━━━━━━━━━━━━━━┛\n"); printf("请选择服务"); ~ } /*MGraph函数（图的构建）*/ MGraph InitGraph(void) { MGraph G; int i,j; =17; um=i; strcpy[0].name,"学校北门"); strcpy[0].introduction,"学校的正门，气势宏伟"); strcpy[1].name,"宿舍楼1"); ￥ strcpy[1].introduction,"睡觉的地方"); strcpy[2].name,"宿舍楼2"); strcpy[2].introduction,"睡觉的地方"); strcpy[3].name,"宿舍楼15"); strcpy[3].introduction,"，，，，，，，，"); strcpy[4].name,"九月桥"); strcpy[4].introduction,"连接生活区和教学区的桥。"); strcpy[5].name,"主教楼"); strcpy[5].introduction,"教学，开会"); strcpy[6].name,"图书馆"); strcpy[6].introduction,"安静当学霸的地方"); strcpy[7].name,"日月广场"); strcpy[7].introduction,"有漂亮喷泉的广场"); strcpy[8].name,"体育场"); strcpy[8].introduction,"运动健身的地方"); strcpy[9].name,"还在建"); strcpy[9].introduction,"学校新修的实验楼，灰常高大上"); strcpy[10].name,"南食堂"); strcpy[10].introduction,"不好吃"); for(i=0;i<;i++) … for(j=0;j<;j++) [i][j].adj=INFINITY; [0][1].adj=50; [1][2].adj=15; [1][3].adj=40; [2][3].adj=30; [0][3].adj=90; [3][4].adj=30; [4][9].adj=1000; [4][5].adj=20; ` [5][6].adj=10; [6][7].adj=8; [6][8].adj=12; [7][8].adj=7; [0][9].adj=30; [9][10].adj=500; [10][11].adj=25; [11][12].adj=8; [12][13].adj=5; [13][14].adj=10; [12][14].adj=10; [14][15].adj=150; [15][16].adj=3; [5][15].adj=150; [4][15].adj=30; [1][11].adj=300; [8][14].adj=40; for(i=0;i<;i++) for(j=0;j<;j++) [j][i].adj=[i][j].adj; return G; }//InitGraph end
相关主题
文本预览