校园导游系统数据结构图

.-

西安郵電學院

数据结构实验报告

题目：校园导游系统

院系名称：计算机学院

专业名称：计算机科学与技术

班级：1006

学生姓名：****

学号（8位）：*****

指导教师：******

设计起止时间：2011年12月12日~2011年12月16日

.-

一.题目要求

1、设计学校的校园平面图，

地点（地点名称、地点介绍）不少于10个。

2、提供图中任意地点相关信息的查询。

3、提供图中任意地点的问路查询：

1）任意两个地点之间的一条最短（中转最少）的简单路径；

2）任意两个景点的最佳访问路线（带权）查询；

3）任意两个地点之间的所有路径。

4、地点和道路的扩充以及撤销；

地点基本信息的文件存储。(附加：加分题)

二．概要设计

1．功能模块的调用关系图

2．各个模块详细的功能描述。

1.首先，main()函数调用loge()函数，输出欢迎界面，然后调用showmenu()函数来选择用户所要进行的操作。其中showmenu()函数就是一个菜单供使用者来选择他所要进行的相关操作，比如信息的查询，最短路径查询之类。

2.browser()函数，用于输出校园平面图，给用户提供校园的景点分布状况，方便用户选择景点参观。

3.Search()函数，用于查询用户所选的景点信息，用户需要输入要查询的景点编号，函数会对编号进行判断，如果是合法输入，则在屏幕上输出该景点的相关信息，包括景点名字，景点的相关介绍，否则返回重新输入。

4.SearchAllpath()函数，用于查询用户所选的任意两个景点间的所有路径，用户需要输入要查询的起始景点编号，函数会对编号进行判断，如果是合法输入，用户需要输入要查询的终点景点编号，函数会对编号进行判断，如果是合法输入，则在屏幕上输出输查询的两个景点间的所有路径，否则返回重新输入。函数使用深度遍历DeepFirstSeach()查找路径。

5.Wellway()函数，用于查询用户所选的任意两个景点间的最短路径，用户需要输入要查询的起始景点

.-

编号，函数会对编号进行判断，如果是合法输入，用户需要输入要查询的终点景点编号，函数会对编号进行判断，如果是合法输入，则在屏幕上输出输查询的两个景点间的最短路径，否则返回重新输入。函数的生成主体是迪杰斯特拉算法来计算出起点到终点之间的最短路径。

6.minway()函数，用于查询用户所选的任意两个景点间的最佳路径（即中转最少），用户需要输入要查询的起始景点编号，函数会对编号进行判断，如果是合法输入，用户需要输入要查询的终点景点编号，函数会对编号进行判断，如果是合法输入，则在屏幕上输出输查询的两个景点间的最短路径，否则返回重新输入。

7.CreatUDN()函数，创建的图，它是MGraph型，G->vexnum表示顶点的个数；G->arcnum表示边数。CreatUDN()函数的功能就是实现图的创建，将已知的景点的一些信息，转换成图的信息，并进行存储。

三．详细设计（主要函数的程序流程图）

1.任意两个地点之间的一条最短（中转最少）的简单路径

利用遍历的思想，遍历图找出一条最佳最佳的的路径，让它遍历所有景点。往下遍历，访问标志位，若访问过在下次就不用访问。若找完一个分支在下次重新遍历。

zz[0]->zhi=m;

zz[0]->front=NULL;

flag[m]=1;

for(top=0;top<20;top++)

{

for(i=0;i<20;i++)

{

if(G->arcs[zz[top]->zhi][i].adj!=INFINITY&&i==n)

{

printf("%s\n",G->vexs[n].name);

printf("%s\n",G->vexs[zz[top]->zhi].name);

zz[top]=zz[top]->front;

while(zz[top]!=NULL)

{

printf("%s\n",G->vexs[zz[top]->zhi].name);

zz[top]=zz[top]->front;

}

getch();

return;

}

else if(G->arcs[zz[top]->zhi][i].adj!=INFINITY&&flag[i]==0)

{

zz[++j]->zhi=i;

zz[j]->front=zz[top];

flag[i]=1;

}

}

}

.-

2.任意两个景点的最佳访问路线（带权）查询

利用迪杰特斯拉算法，求v0到其余顶点的最短路径D[],p [][]是用来存放各路径的权值，借助辅助数组final[]标志,是否当前顶点属于final(1,属于)。for(v=0;vvexnum;v++) {

final[v]=0;

D[v]=G->arcs[v0][v].adj;

for(w=0;wvexnum;w++)

p[v][w]=0;

if(D[v]

{

p[v][v0]=1;p[v][v]=1;

}

}

D[v0]=0;final[v0]=1;

for(i=1;ivexnum;i++)

{

min=INFINITY;

for(w=0;wvexnum;w++)

if(!final[w])

if(D[w]

final[v]=1;

for(w=0;wvexnum;w++)

if(!final[w]&&(min+G->arcs[v][w].adj

{

D[w]=min+G->arcs[v][w].adj;

.-

for(x=0;xvexnum;x++)

p[w][x]=p[v][x];

p[w][w]=1;

}

}

v=v1;

w1=v0;

printf("%s",G->vexs[v0].name);

do

{

flag=0;min=INFINITY;

for(w=0;wvexnum;w++)

{

if(p[v][w]&&w!=v0)

{

flag=1;

if(D[w]

{

j=w;

min=D[w];

}

}

}

.-

3.任意两个地点之间的所有路径

利用深度优先的思想，遍历图找出所有的路径，让它遍历所有景点。利用递归的思想，往下历，访问标志位，若访问过在下次就不用访问。{

int s;

if(v[k]==j)/*找到一条路径*/

{

count++;/*路径的条数值加1*/

printf("第%d条:",count);

for(s=1;s

printf("%s->",G->vexs[v[s]].name);

printf("%s\n",G->vexs[v[s]].name);

}

for(s = 1;svexnum;s++)

{

if(s!=i)/*保证找到的是简单路径*/

{

if(G->arcs[v[k]][s].adj!=INFINITY&&visited[s]==0)

/*当vk与vs之间有边存在且vs未被访问过*/

{

visited[s]=1; /*置访问标志位为1,即已访问的*/

v[k+1]=s; /*将顶点s加入到v数组中*/

DeepFirstSeach(G,i,j,k+1); /*递归调用之*/

visited[s]=0; /*重置访问标志位为0，即未访问的，以便该顶点能被重新使用*/

}

}

}

}若找完一个分支在下次重新遍历。

.-

四．测试数据及运行结果

.- 1．正常测试数据和运行结果

.-

2．异常测试数据及运行结果

.-

.-

五．调试情况，设计技巧及体会

1．改进方案

本次实习设计总体上来说是成功的，我在规定的时间内完成了老师交代的任务，并让程序能够运行起来，可以说大体上没有问题，当然在细节上还有需要改进的地方；

合理之处：

①对于老师所提出的问题要求很好并及时的解决了；

②程序运行整体上没有大的错误；

③对于各大模块划分清晰，知道先做什么后做什么；

④程序运行后界面漂亮，用户使用方便；

⑤合理恰当的把书上所学的关于图的知识应用到程序设计之中，使程序明了可读性较高。

不合理之处：

①程序之中存在一些小毛病，不能100%的运行无误；

②关于文件存储这一模块掌握的不是很好，所创建的图不能很好的保存到文件之中；

③程序设计中最短路径（中转最少）显示的时候是倒着显示

改进方案：

对于程序存在的小问题一个个的仔细排除，精尽量做到准确无误；对于文件和最短路径的设计应多参考相关书籍，找到合理正确的解决方法，将图存储到指定的文件中去，并且使最短路径在输出的时候能够以正确的顺序输出。

2．体会

这次课程设计给我的感触很多，课程设计没开始之前我总是在想今年的课程设计会不会象去年那样辛苦，但是这一周下来我当然也感到累，也有心情烦躁的时候，体会到调试成功时的那种喜悦。

课程设计之前老师让我们自己先想好设计思路，都要做哪些模块。那天下午编了一下午，没什么成就

.-

弄得我很心烦，再想到快要考试，那种急于求成的心更迫切，自己很难平静。第二天老师检查时我什麽都没有，看到同学的程序我开始着急了，但那会我只有一个念头我得从新开始，由于对图不是很了解，我就从读写模块开始，就使用简单的C语知识，那天早上将那两个模块给拿下了。下机后我在寝室开始编程，开始进入真正的图部分，边思考怎样可以将它们联系起来，边进行调试。对编程兴趣很浓，直到晚上十点我已经将老师的要求完成差不多。

这些日子是很辛苦，但我学到了很多东西，理解了图的运用，还和同学一起分享调试成功的那种喜悦，我完成的早，同学有问题会让我帮助，在帮他们的过程中我也学会了很多种不同的思想，让我对图有了更深刻的理解。

当然，我要感谢学校领导精心给我们安排的这次实习操作，更感谢我们的程序设计老师，是她给了我们一个相对轻松有趣的环境，让我们感到在设计中没有压力,在她的帮助下,我终于完成了本次课程设计的任务。

。

代码

#include

#include

#include

#include

#include

#define INFINITY 10000 /*无穷大*/

#define MAX_VERTEX_NUM 40

#define MAX 40

typedef struct ArCell

{

int adj; //路径长度

}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct //图中顶点表示主要景点，存放景点的编号、名称、简介等信息，s

{

char name[30];

int num;

int x;

int y;

char introduction[500];//简介

}infotype;

struct zui //最短路径记录结构体

{

int zhi;

struct zui *front;

};

typedef struct

{

infotype vexs[MAX_VERTEX_NUM];

AdjMatrix arcs;

int vexnum,arcnum;

}MGraph;

.-

MGraph b;

void showmenu();

void loge(); //启动动画

void Wellway(MGraph * ); // 计算任意两个景点之间的最短路径MGraph InitGraph(void); //初始化

void browser(); //浏览校园全景

void Search(MGraph *G); //查看景点信息

MGraph *CreatUDN(MGraph *G); //创建图

void SearchAllpath(MGraph *G); //查找两点间所有路径

void minway(MGraph *G);

MGraph *CreatUDN(MGraph *G);

int openfile(MGraph *G);

int writefile(MGraph *G);

int writefile(MGraph *G)

{

FILE *fp;

int i;

fp = fopen("xiaoyuanxinxi.txt", "w");

if(fp == NULL)

{

printf("打开失败！");

return FALSE;

}

for(i = 0; i < 20; i++)

fwrite(&G , sizeof(MGraph), 1 ,fp);

return TRUE;

fclose(fp);

}

int openfile(MGraph *G)

{

FILE *fp;

int i = 0;

int t = 0;

fp = fopen("xiaoyuanxinxi.txt", "r");

if(fp == NULL)

{

printf("文件为空，无景点信息，请按任意键返回添加!");

return FALSE;

}

while(!feof(fp))

{

fread(&G, sizeof(MGraph), i, fp);

i++;

}

for(t=0;t

.-

{

printf("%d %s %s",G->vexs[t].num,G->vexs[t].name,G->vexs[t].introduction);

printf("\n");

}

fclose(fp);

return i;

}

void main(void)

{

int k;

system("mode con: cols=140 lines=130");

loge();

b=InitGraph();

system("cls");

printf(" 欢迎进入西安邮电大学校园导游咨询系统\n");

Sleep(1000);

do

{

while(1)

{

showmenu();

printf("请选择:");

scanf("%d",&k);

if(k<0||k>6)

{

printf("输入有误请重新输入\n");

scanf("%d",&k);

}

else break;

}

switch(k)

{

case 1:browser();system("cls");break;

case 2:Search(&b);system("cls");break;

case 3:SearchAllpath(&b);system("cls");break;

case 4:Wellway(&b);system("cls");break;

case 5:minway(&b);system("cls");break;

case 6:CreatUDN(&b);system("cls");break;

case 0:exit(0);

}

}while(1);

}

void showmenu()

{

printf(" ************************************\n");

printf(" $ 主要景点列表$ \n");

printf(" $ 建议观看$ \n");

printf(" ************************************\n");

printf(" <12> 田操场<09> 西邮小湖\n");

.- printf(" <2> 教学楼A<14> 体育馆\n");

printf(" <3> 教学楼B<10> 图书馆\n");

printf(" <5> 1号实验楼<6> 2号实验楼\n");

printf(" <7> 3号实验楼<11> 校医院\n");

printf(" <8> 大学生活动中心<4> 喷泉\n");

printf(" <13> 美食广场<15> 旭日苑\n");

printf(" 1.查看学校景点分布图\n");

printf(" 2.查询景点简介查询\n");

printf(" 3.查询某两个景点间所有的路径\n");

printf(" 4.任意两景点之间的最佳路径\n");

printf(" 5.任意两景点之间的最短路径\n");

printf(" 6.建图并保存到文件\n");

printf(" 0.退出\n");

}

void loge()

{

printf("\t\t\t\t\t\t\t");

printf("欢"); Sleep(100);

printf("迎"); Sleep(100);

printf("进"); Sleep(100);

printf("入"); Sleep(100);

printf("西"); Sleep(100);

printf("安"); Sleep(100);

printf("邮"); Sleep(100);

printf("电"); Sleep(100);

printf("大"); Sleep(100);

printf("学"); Sleep(100);

printf("校"); Sleep(100);

printf("园"); Sleep(100);

printf("导"); Sleep(100);

printf("游"); Sleep(100);

printf("系"); Sleep(100);

printf("统"); Sleep(100);

printf("\n");

}

MGraph InitGraph()

{

MGraph G;

int i,j;

G.vexnum=20;

G.arcnum=18;

for(i=0;i

G.vexs[i].num=i;

strcpy(G.vexs[0].name,"大门");

strcpy(G.vexs[1].name,"行政楼");

strcpy(G.vexs[2].name,"教学楼A");

strcpy(G.vexs[3].name,"教学楼B");

strcpy(G.vexs[4].name,"喷泉");

strcpy(G.vexs[5].name,"一号实验楼");

strcpy(G.vexs[6].name,"二号实验楼");

strcpy(G.vexs[7].name,"三号实验楼");

.-

strcpy(G.vexs[8].name,"大学生活动中心");

strcpy(G.vexs[9].name,"西邮小湖");

strcpy(G.vexs[10].name,"图书馆");

strcpy(G.vexs[11].name,"校医室");

strcpy(G.vexs[12].name,"田径场");

strcpy(G.vexs[13].name,"美食广场");

strcpy(G.vexs[14].name,"体育馆");

strcpy(G.vexs[15].name,"旭日苑");

strcpy(G.vexs[16].name,"男生宿舍");

strcpy(G.vexs[17].name,"女生宿舍");

strcpy(G.vexs[18].name,"超市");

strcpy(G.vexs[19].name,"篮球场");

strcpy(G.vexs[0].introduction,"学校大门,出门坐车的地方门口有600,有616（到火车站）有321等，平常学生外出坐车的地方。");

strcpy(G.vexs[1].introduction,"我只想说句脏话，因为我不熟，很少去，应该是行政的吧....遇此问题你可以关闭本系统了，答案...我也不清楚。");

strcpy(G.vexs[2].introduction,"教学楼A，此教学楼上课率是80%以上，基本上绝大多数可都在这上。");

strcpy(G.vexs[3].introduction,"教学楼B，除了教学楼A就是本楼了，也是上课的地方，只是一般上大课的时候来。");

strcpy(G.vexs[4].introduction,"学校的小喷泉，只有节日或一些领导来的时候喷一下，对与学生使用价值不大，能不能看到看人品！。");

strcpy(G.vexs[5].introduction,"一号实验楼，我想想...好像是电子工程学院的，很多实验都在里面做。");

strcpy(G.vexs[6].introduction,"二号实验楼，恩，是本院，计算机学院的，虽然去的少，（除了班长每天去导员那报道常去外，就是被导员叫去挨骂，其他一般没事不去）");

strcpy(G.vexs[7].introduction,"三号实验楼，哎，我真不清楚了，反正能做实验，不知道，用户关系统吧...");

strcpy(G.vexs[8].introduction,"各种演出，各种浪，各种蛋疼，都在这");

strcpy(G.vexs[9].introduction,"俗称**湖（和谐词），男女约会的地方，主席的大明湖畔。");

strcpy(G.vexs[10].introduction,"恩，图书还行吧，找资料，上网（1元/小时），各种实习");

strcpy(G.vexs[11].introduction,"学校的医院，大家都懂得,医生技术差动不动就是挂点滴,还很贵。设施...，不能多说....");

strcpy(G.vexs[12].introduction,"上体育课，举行运动会，还有个足球场。");

strcpy(G.vexs[13].introduction,"一个吃饭的地方，味道还行，价格不是很贵，挺多人去的。");

strcpy(G.vexs[14].introduction,"一般有个篮球赛什么的会在这举行，能坐挺多人的。");

strcpy(G.vexs[15].introduction,"另一个吃饭的地方，相对美广，本人觉得稍微干净一点，价格可能略贵，但还能接受，我是比较喜欢来在。");

strcpy(G.vexs[16].introduction,"一个充满骚包的地方，哎，一个光棍节什么的，各种鬼哭狼叫，哎，我去....。");

strcpy(G.vexs[17].introduction,"女生宿舍，所实话，进去过，但没进去过里面，哎...当时就该一把把门推开，然后说，不好意思，同学推得...（别说你不想）");

strcpy(G.vexs[18].introduction,"超市啊，这我不介绍了，请我吃东西，我带你去，不然自己找去....。");

strcpy(G.vexs[19].introduction,"第一：上体育课的地方，第二：打球的地方（够详细了）。");

G.vexs[0].x=1;G.vexs[0].y=3;

.- G.vexs[1].x=1;G.vexs[1].y=3;

G.vexs[2].x=2;G.vexs[2].y=3;

G.vexs[3].x=1;G.vexs[3].y=2;

G.vexs[4].x=2;G.vexs[4].y=2;

G.vexs[5].x=2;G.vexs[5].y=1;

G.vexs[6].x=3;G.vexs[6].y=1;

G.vexs[7].x=3;G.vexs[7].y=2;

G.vexs[8].x=3;G.vexs[8].y=3;

G.vexs[9].x=3;G.vexs[9].y=4;

G.vexs[10].x=4;G.vexs[10].y=1;

G.vexs[11].x=5;G.vexs[11].y=1;

G.vexs[12].x=5;G.vexs[12].y=3;

G.vexs[13].x=6;G.vexs[13].y=1;

G.vexs[14].x=6;G.vexs[14].y=3;

G.vexs[15].x=6;G.vexs[15].y=4;

G.vexs[16].x=1;G.vexs[16].y=3;

G.vexs[17].x=1;G.vexs[17].y=3;

G.vexs[18].x=1;G.vexs[18].y=3;

G.vexs[19].x=1;G.vexs[19].y=3;

for(i=0;i

for(j=0;j

G.arcs[i][j].adj=INFINITY;

G.arcs[1][2].adj=70;

G.arcs[0][1].adj=20;

G.arcs[0][2].adj=20;

G.arcs[1][2].adj=40;

G.arcs[2][3].adj=10;

G.arcs[0][4].adj=30;

G.arcs[4][5].adj=35;

G.arcs[5][6].adj=10;

G.arcs[6][7].adj=10;

G.arcs[7][11].adj=40;

G.arcs[11][13].adj=20;

G.arcs[13][17].adj=30;

G.arcs[4][10].adj=50;

G.arcs[10][19].adj=25;

G.arcs[10][14].adj=45;

G.arcs[14][15].adj=30;

G.arcs[15][18].adj=20;

G.arcs[4][8].adj=50;

G.arcs[8][9].adj=10;

G.arcs[9][12].adj=40;

G.arcs[12][16].adj=30;

G.arcs[0][3].adj=25;

G.arcs[1][3].adj=40;

G.arcs[1][4].adj=25;

G.arcs[3][4].adj=30;

G.arcs[0][10].adj=60;

G.arcs[0][11].adj=70;

G.arcs[0][12].adj=70;

G.arcs[2][7].adj=35;

G.arcs[1][9].adj=50;

G.arcs[4][19].adj=80;

G.arcs[0][18].adj=200;

G.arcs[4][12].adj=95;

G.arcs[6][9].adj=40;

G.arcs[7][9].adj=60;

.-

G.arcs[11][8].adj=80;

G.arcs[13][14].adj=20;

G.arcs[13][12].adj=80;

G.arcs[12][19].adj=60;

G.arcs[16][18].adj=20;

G.arcs[16][17].adj=50;

G.arcs[12][14].adj=20;

G.arcs[13][16].adj=90;

G.arcs[2][17].adj=160;

G.arcs[11][17].adj=90;

G.arcs[9][15].adj=100;

G.arcs[17][19].adj=50;

G.arcs[10][16].adj=80;

G.arcs[10][17].adj=100;

G.arcs[10][13].adj=90;

for(i=1;i

for(j=1;j

G.arcs[i][j].adj=G.arcs[j][i].adj;

return G;

}//InitGraph end

void browser()

{

printf("§·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·§\n");

printf("§17.女生宿舍区18.超市16男生宿舍§\n");

printf("§┃┃┃§\n");

printf("§┃15.旭日苑┃§\n");

printf("§┃┃┃§\n");

printf("§┃┃┃§\n");

printf("§┃┃┃§\n");

printf("§┃┃┃§\n");

printf("§┃┃┃§\n");

printf("§┃14.体育馆┃§\n");

printf("§┃┃┃§\n");

printf("§13.美食广场19.篮球场┃┃§\n");

printf("§┃┃┃┃§\n");

printf("§11. 校医室┃┃12.田径场§\n");

printf("§┃┃┃┃§\n");

.-

printf("§┃━━10.图书馆┃§\n");

printf("§7.三号实验楼┃┃§\n");

printf("§┃┃9.西邮小湖§\n");

printf("§ 6.二号实验楼┃┃§\n");

printf("§┃┃┃§\n");

printf("§ 5.一号实验楼┃8.大学生活动中心§\n");

printf("§┃┃┃§\n");

printf("§━━━━━━━━━━4.喷泉━━━━━━━━━━━§\n");

printf("§┃§\n");

printf("§ 3.教学楼 B ┃§\n");

printf("§┃┃§\n");

printf("§ 2.教学楼A━━━━━━━━━━━━━━━━━━━━━━━1.行政楼§\n");

printf("§┃§\n");

printf("§0.大门§\n");

printf("§§\n");

printf("§·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·§\n");

printf("按任意键继续!\n");

getch();

}

void minway(MGraph *G) //中转最短~

{

int m,n,i,top;

int j=0;

int flag[20]={0};

struct zui *zz[20];

for(i=0;i<20;i++)

zz[i]=(struct zui *)malloc(sizeof (struct zui));

printf("请输入起始点代号：");

scanf("%d",&m);

printf("请输入目的的点代号：");

scanf("%d",&n);

if(m<0||m>20||n<0||n>20||m==n)

{

printf("输入错误，按任意键继续~！");

.-

getch();

return ;

}

zz[0]->zhi=m;

zz[0]->front=NULL;

flag[m]=1;

for(top=0;top<20;top++)

{

for(i=0;i<20;i++)

{

if(G->arcs[zz[top]->zhi][i].adj!=INFINITY&&i==n)

{

printf("%s\n",G->vexs[n].name);

printf("%s\n",G->vexs[zz[top]->zhi].name);

zz[top]=zz[top]->front;

while(zz[top]!=NULL)

{

printf("%s\n",G->vexs[zz[top]->zhi].name);

zz[top]=zz[top]->front;

}

getch();

return;

}

else if(G->arcs[zz[top]->zhi][i].adj!=INFINITY&&flag[i]==0)

{

zz[++j]->zhi=i;

zz[j]->front=zz[top];

flag[i]=1;

}

}

}

}

void Wellway(MGraph * G) // 计算任意两个景点之间的最短路径{

int v,w,w1,i,j,v1,min,t=0,x,flag=1,v0;

int final[20], D[20], p[20][20];

while(flag)

{

printf("请输入一个起始景点编号:");

scanf("%d",&v0);

if(v0<0||v0>G->vexnum)

{

printf("景点编号不存在!请重新输入景点编号:");

scanf("%d",&v0);

}

if(v0>=0&&v0vexnum)

flag=0;

}

flag=1;

while(flag)

{

printf("请输入一个目的地景点编号:");

scanf("%d",&v1);

if(v1<0||v1>G->vexnum)

{

printf("景点编号不存在!请重新输入景点编号:");

.-

scanf("%d",&v1);

}

if(v1>=0&&v1vexnum)

flag=0;

}

for(v=0;vvexnum;v++)

{

final[v]=0;

D[v]=G->arcs[v0][v].adj;

for(w=0;wvexnum;w++)

p[v][w]=0;

if(D[v]

{

p[v][v0]=1;p[v][v]=1;

}

}

D[v0]=0;final[v0]=1;

for(i=1;ivexnum;i++)

{

min=INFINITY;

for(w=0;wvexnum;w++)

if(!final[w])

if(D[w]

final[v]=1;

for(w=0;wvexnum;w++)

if(!final[w]&&(min+G->arcs[v][w].adj

{

D[w]=min+G->arcs[v][w].adj;

for(x=0;xvexnum;x++)

p[w][x]=p[v][x];

p[w][w]=1;

}

}

v=v1;

w1=v0;

printf("%s",G->vexs[v0].name);

do

{

flag=0;min=INFINITY;

for(w=0;wvexnum;w++)

{

if(p[v][w]&&w!=v0)

{

flag=1;

if(D[w]

{

j=w;

min=D[w];

}

}

}

if(flag)

{

if(G->vexs[w1].xvexs[j].x)

printf("向东走%dm",G->arcs[w1][j].adj);

if(G->vexs[w1].x>G->vexs[j].x)

printf("向西走%dm",G->arcs[w1][j].adj);

本文来源：https://www.bwwdw.com/article/pfxl.html