校园导游咨询

实验原程序：

#include #include #include #include #define Max 50000 #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(); // 显示遍历结果

int main() // 主函数

{ int v0,v1; char ck;

CreateUDN(NUM,11); do {

ck=Menu(); switch(ck) {

case'1': introduce();

printf(\"\\n\\n\\\%-25s\\n\\n\ getchar(); getchar(); break;

case '2':

system(\"cls\"); pingmu();

printf(\"\\n\\n\\\请选择起点景点（1～10）：\"); scanf(\"%d\

printf(\"\\\请选择终点景点（1～10）：\"); scanf(\"%d\

ShortestPath(v0); // 计算两个景点之间的最短路径 output(v0,v1); // 输出结果

printf(\"\\n\\n\\\\请按回车键继续...\\n\"); getchar(); getchar();

break;

case '3':search(); break;

case '4':

system(\"cls\"); pingmu(); x[0]=1;

HaMiTonian(1);

printf(\"\\n\\n\\\\请按回车键继续...\\n\"); getchar(); getchar(); break;

case'5':

PrintMGraph();

printf(\"\\n\\n\\\\请按回车键继续...\\n\"); getchar(); getchar(); break; };

}while(ck!='e'); }

char Menu() // 主菜单 {

char c; int flag; do{

flag=1;

system(\"cls\"); pingmu(); introduce();

printf(\"\\n\\┏━━━━━━━━━━━━━━━━━━━┑\\n\"); printf(\"\\┃ ┃\\n\"); printf(\"\\┃ 1.学校简介 ┃\\n\"); printf(\"\\┃ 2.查询景点路径 ┃\\n\"); printf(\"\\┃ 3.查询景点信息 ┃\\n\"); printf(\"\\┃ 4.查看参观路线 ┃\\n\"); printf(\"\\┃ 5.查询各景点之间的距离 ┃\\n\"); printf(\"\\┃ e.退出 ┃\\n\");

printf(\"\\┃ ┃\\n\"); printf(\"\\┗━━━━━━━━━━━━━━━━━━━┛\\n\"); printf(\"\\\\请输入您的选择：\"); scanf(\"%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\\┏━━━━━━━━━━━━━━━━━━┑\\n\"); printf(\"\\┃ ┃\\n\"); printf(\"\\┃ 1、按照景点编号查询 ┃\\n\"); printf(\"\\┃ 2、按照景点名称查询 ┃\\n\"); printf(\"\\┃ e、返回 ┃\\n\"); printf(\"\\┃ ┃\\n\"); printf(\"\\┗━━━━━━━━━━━━━━━━━━┛\\n\"); printf(\"\\\请输入您的选择：\"); scanf(\"%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\\请输入您要查找的景点编号：\"); scanf(\"%d\ for(i=0;iif(num==G.vex[i].number) {

printf(\"\\n\\n\\\您要查找景点信息如下:\");

printf(\"\\n\\n\\\%-25s\\n\\n\ printf(\"\\n\\\按任回车返回...\"); getchar(); getchar(); break; } }

if(i==NUM) {

printf(\"\\n\\n\\\没有找到！\");

printf(\"\\n\\n\\\按回车键返回...\"); getchar(); getchar(); }

break; case '2':

system(\"cls\"); pingmu(); introduce();

printf(\"\\n\\n\\请输入您要查找的景点名称：\"); scanf(\"%s\ for(i=1;iif(!strcmp(name, G.vex[i].sight)) {

printf(\"\\n\\n\\\您要查找景点信息如下:\");

printf(\"\\n\\n\\\%-25s\\n\\n\ printf(\"\\n\\\按回车键返回...\"); getchar();

getchar(); break; } }

if(i==NUM) {

printf(\"\\n\\n\\\没有找到！\");

printf(\"\\n\\n\\\按回车键返回...\"); 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// 这里把所有的边假定为50000，含义是这两个景点之间是不可到达 for(i=1;ifor(j=1;jG.arcs[i][j].adj=Max;

G.arcs[i][j].info=NULL; } }

//下边是可直接到达的景点间的距离，由于两个景点间距离是互相的， // 所以要对图中对称的边同时赋值。

G.arcs[1][2].adj=G.arcs[2][1].adj=50; G.arcs[2][3].adj=G.arcs[3][2].adj=50; G.arcs[3][4].adj=G.arcs[4][3].adj=150; G.arcs[4][5].adj=G.arcs[5][4].adj=100; G.arcs[5][6].adj=G.arcs[6][5].adj=50; G.arcs[3][6].adj=G.arcs[6][3].adj=50; G.arcs[2][6].adj=G.arcs[6][2].adj=50; G.arcs[5][7].adj=G.arcs[7][5].adj=100; G.arcs[7][8].adj=G.arcs[8][7].adj=250; G.arcs[8][9].adj=G.arcs[9][8].adj=200; G.arcs[6][8].adj=G.arcs[8][6].adj=300; G.arcs[9][10].adj=G.arcs[10][9].adj=50; G.arcs[6][10].adj=G.arcs[10][6].adj=250; }

// 打印出邻接矩阵

void PrintMGraph() {

int i,j; cout<<\"\\n

====================================================================\\n\\n \";

for(i=1;icout<cout<for(i=1;icout<<\"\\n\\n\"<if(G.arcs[i][j].adj==Max) cout<<\" no \"; else

cout<<\" \"<cout<<\"\\n\\n\\n\\n==========================================================================================\\n\\n\\n\"; }

void introduce() // 介绍函数 {

int i;

for(i=1;i<=NUM;i++) {

G.vex[0].description=\"集美大学的学院\"; G.vex[1].description=\"正门口\";

G.vex[2].description=\"领导办公的地方\"; G.vex[3].description=\"学生上课的地方\";

G.vex[4].description=\"做物理，电工之类的实验，还有语音，计算机实验室\"; G.vex[5].description=\"一条长长的走廊\"; G.vex[6].description=\"学生三餐吃饭的地方\"; G.vex[7].description=\"卖各种生活用品\"; G.vex[8].description=\"上体育课的地方\"; G.vex[9].description=\"学生住的地方\";

G.vex[10].description=\"学院后面，连通集美大学本部\"; } }

void pingmu() // 屏幕输出函数 { int i;

printf(\" 欢迎来到集美大学诚毅学院\\n\");

printf(\" 学校简介\\n\");

printf(\" 学校概况\\n\");

for(i=1;iprintf(\"\\%c\\(%2d)%-20s%c\\\\输出景点列表

} }

void ShortestPath(int num) // 迪杰斯特拉算法最短路径函数 num为入口点的编号 {

int v,w,i,t; // i、w和v为计数变量 int final[NUM]; int min;

for(v=1;vfinal[v]=0; // 假设从顶点num到顶点v没有最短路径

D[v]=G.arcs[num][v].adj;// 将与之相关的权值放入D中存放 for(w=1;wif(D[v]<32767) // 存在路径 {

P[v][num]=1; // 存在标志置为一 P[v][v]=1; // 自身到自身 } }

D[num]=0;

final[num]=1; // 初始化num顶点属于S集合

// 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合

for(i=1;imin=Max; // 当前所知离顶点num的最近距离 for(w=1;wif(!final[w]) // w顶点在v-s中 if(D[w]min=D[w]; }

final[v]=1; // 离num顶点更近的v加入到s集合 for(w=1;wif(!final[w]&&((min+G.arcs[v][w].adj)D[w]=min+G.arcs[v][w].adj; for(t=0;t} } }

void output(int sight1,int sight2) // 输出函数 {

int a,b,c,d,q=0;

a=sight2; // 将景点二赋值给a

if(a!=sight1) // 如果景点二不和景点一输入重合，则进行... {

printf(\"\\n\从%s到%s的最短路径是

\输出提示信息

printf(\"\(最短距离为 %dm.)\\n\\n\\输出sight1到sight2的最短路径长度，存放在D[]数组中

printf(\"\%s\输出景点一的名称 d=sight1; // 将景点一的编号赋值给d for(c=0;cgate:; // 标号，可以作为goto语句跳转的位置 P[a][sight1]=0; for(b=0;bif(G.arcs[d][b].adj<32767&&P[a][b]) // 如果景点一和它的一个临界点之间存在路径且最短路径 {

printf(\"-->%s\输出此节点的名称 q=q+1; // 计数变量加一，满8控制输出时的换行 P[a][b]=0;

d=b; // 将b作为出发点进行下一次循环输出，如此反复 if(q%8==0) printf(\"\\n\"); goto gate; } } } } }

void HaMiTonian(int m) // 哈密尔顿图的遍历 {

if(m>8) return; L: NextValue(m); if(x[m]==0) return;

if(m==7&&G.arcs[1][x[8]-1].adj!=50000) 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!=50000) {

for(j=0;jgoto l; }

void display() {

int i=1;

printf(\"\\n\\n\\"); for(i=1;i<8;i++)

printf(\"%s->\ printf(\"参观结束\"); printf(\"\\n\"); }

测试数据：景点6，从景点4到景点6，从景点7到景点4

运行如下：

三、运行环境： VC++

四、实验中遇到的问题及解决方案：

道路网是稀疏网，程序中会由于编程不严谨出现很多漏洞。

五、实验小结：

通过本次实验了解到图结构的编程中需要注意的问题，进而进一步理解关于图结构的应用。