校园导游咨询

滨江学院

《数据结构》课程设计

题 目 校园导游咨询

20102308011

学 号 顾鑫磊 学生姓名 滨江学院 院 系

专 业 计算机科学与技术

指导教师 宣文霞

二Ｏ一二 年五月十五日

一．课程内容

【问题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 【基本要求】

（1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

（3）为来访客人提供图中任意景点相关信息的查询。 【测试数据】

由读者根据实际情况指定。

【实现提示】 一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。

二．合作任务

顾鑫磊：主函数的编写，用来显示校园景点的Outputplace函数的编写看，实验结果的截图记录

1）Outputplace函数的编写

void Outputplace()//输出校园景点名称 {

printf(\"\\\\\\┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\"); printf(\"\\\\\\┃ 滨江学院学校景点一览表 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━┳━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃1.滨江学院校门 ┃2滨江楼 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃3.运动场 ┃4.综合楼 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃5.宿舍区3 ┃6.宿舍区2 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃7.宿舍区1 ┃8.双馨桥 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃9万象桥 ┃10.食堂 ┃\\n\"); printf(\"\\\\\\┗━━━━━━━━━━━━┻━━━━━━━━━━━━┛\\n\");

}

2）主函数 主函数说明 1．创建校园图：

（1）先定义节点个数N，边的最大值（MAXedg），节点（景点名称、景点信息），邻接点，边，顶点向量，当前顶点数和边数。

（2）先给一个节点赋上其相关信息，然后再用p = (Node)malloc(sizeof(edgenode))语句申请下一结点，再给所申请的节点赋上相关信息，直到节点数为N=10为止。 （3）读入道路的起始点，为邻接矩阵的边赋相应的值。

（4）节点和边的相关信息都弄好了后，校园图也就创建好了。

2．利用函数Name给10个节点赋上相应的名称，利用函数Information给各节点添加相应的介绍信息。

3．利用函数searcplace来查找景点信息，要查找景点名称时调用Name函数，要查找景点介绍信息时调用Information函数。

4．手动创建一个校园图creat(Matrix_Graph *G)，然后为相应的边赋上真正的值。 5．用path函数来求任意两景点之间的最短路径。

6．用main函数来输出结果：用switch语句分别输出，要创建校园图时调用creatgraph函数；查找景点相关信息时调用searcplace函数；要查找任意两景点之间的最短路径时，先输入你目前所在的位置，再输入你的目的地，最后调用path函数。

主函数代码： #include #include #include #include #include #define MAX 100000 #define NUM 30

#define FALSE 0 #define TURE 1

typedef struct ArcNode {

int length; //路径长度 } ArcNode, *ArcLink; //边结点的定义

typedef struct VertexNode {

int number; //景点的编号 char *name; //景点的名称 char *info; //景点的简介 } VertexNode; //顶点结点的定义

typedef struct Graph

{

VertexNode vertex[NUM];

ArcNode arc[NUM][NUM];

int vexnum,arcnum; //图的顶点数，边数 } Graph; //图的定义

void Map();//校园地图

void CreateGraph();//创建图

void OutputPlace();//输出景点列表 void SearchPlace();//查询景点信息 void SearchPath();//查询最短路径

void Shortpath(int i);//计算最短路径

void Output(int sight1,int sight2);//输出函数

Graph G;

int path[NUM][NUM]; int D[NUM];

void CreateGraph()//创建图 {

int i,j; G.vexnum=10; G.arcnum=20;

for(i=1;iG.vertex[1].name=\"滨江学院校门\";

G.vertex[1].info=\"校门口，人称西苑南门!\\n\"; G.vertex[2].name=\"滨江楼\";

G.vertex[2].info=\"滨江学院主教学楼之一!\\n\";

G.vertex[3].name=\"运动场\";

G.vertex[3].info=\"集足球场，篮球场，排球场以及网球场于一体!\\n\"; G.vertex[4].name=\"综合楼\";

G.vertex[4].info=\"滨江学院主教学楼之一，以及教师办公楼所在地!\\n\"; G.vertex[5].name=\"宿舍区3\";

G.vertex[5].info=\"包括了宿舍楼11，12，13，14，15，16，17，18栋!\\n\"; G.vertex[6].name=\"宿舍区2\";

G.vertex[6].info=\"包括了宿舍楼1，2，3，4，19栋!\\n\"; G.vertex[7].name=\"宿舍区1\";

G.vertex[7].info=\"包括了宿舍楼5，6，7，8，9，10栋!\\n\"; G.vertex[8].name=\"双馨桥\";

G.vertex[8].info=\"可以通往图书馆!\\n\";

G.vertex[9].name=\"万象桥\";

G.vertex[9].info=\"通往中苑以及主田径场等地的桥!\\n\"; G.vertex[10].name=\"食堂\";

G.vertex[10].info=\"有西苑新老食堂两座!\\n\"; for(i=0;ifor(j=0;jG.arc[i][j].length=MAX;

G.arc[1][2].length=G.arc[2][1].length=200; G.arc[1][9].length=G.arc[9][1].length=500; G.arc[2][3].length=G.arc[3][2].length=500; G.arc[2][4].length=G.arc[4][2].length=400; G.arc[4][3].length=G.arc[3][4].length=700;

G.arc[7][3].length=G.arc[3][7].length=500; G.arc[9][3].length=G.arc[3][9].length=600; G.arc[10][3].length=G.arc[3][10].length=600;

G.arc[2][9].length=G.arc[9][2].length=600; G.arc[4][6].length=G.arc[6][4].length=700; G.arc[4][10].length=G.arc[10][4].length=700; G.arc[5][6].length=G.arc[6][5].length=400; G.arc[5][7].length=G.arc[7][5].length=600; G.arc[5][8].length=G.arc[8][5].length=800; G.arc[6][7].length=G.arc[7][6].length=300; G.arc[6][10].length=G.arc[10][6].length=700; G.arc[7][8].length=G.arc[8][7].length=400; G.arc[7][10].length=G.arc[10][7].length=600; G.arc[8][9].length=G.arc[9][8].length=900;

G.arc[3][6].length=G.arc[6][3].length=900; G.arc[10][5].length=G.arc[5][10].length=900; }

void Map()//学校地图 {

printf(\"\\n\\n\"); system(\"cls\");

printf(\"\\\\\\┏━━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\"); printf(\"\\\\\\┃ 滨江学院学院校园图 ┃\\n\"); printf(\"\\\\\\┃ 彭芳 席维超 顾鑫磊 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃ ┏━━━━━━┓ ┃\\n\"); printf(\"\\\\\\┃ ╔══════┫滨江学院校门┃ ┃\\n\"); printf(\"\\\\\\┃ ║ ┗━━━━━┳┛ ┃\\n\"); printf(\"\\\\\\┃ ║ ║ ┃\\n\"); printf(\"\\\\\\┃ ┏┻┓ ║ ┏━━━┓ ┃\\n\"); printf(\"\\\\\\┃ ┃万┃ ┏━━━━━┓ ┃ 综合 ┃ ┃\\n\"); printf(\"\\\\\\┃ ┃象┃ ┃ ┃ ┃ 楼 ┃ ┃\\n\"); printf(\"\\\\\\┃ ┃桥┣══╦════╋ 滨江楼 ┣═┫ ┃ ┃\\n\"); printf(\"\\\\\\┃ ┗┳┛ ║ ┗━━━━━┛ ┻━┳━┛ ┃\\n\"); printf(\"\\\\\\┃ ║ ║ ║ ┃\\n\"); printf(\"\\\\\\┃ ║┏━━╩━━┓ ║ ┃\\n\");

}

printf(\"\\\\\\┃ ║┃ 运动场 ┣═══════════╬ ┃\\n\"); printf(\"\\\\\\┃ printf(\"\\\\\\┃ printf(\"\\\\\\┃ printf(\"\\\\\\┃

║┗━━┳━━┛ ║ ║ ║ ┏━━━┓ ║ ║ ║ ┃ 宿舍┃ ║ ║ ║ ┃ 区┃═╝

┃\\n\"); ┃\\n\"); ┃\\n\"); ┃\\n\");

printf(\"\\\\\\┃ ║ ╬═══╦════┫ 2 ┃ ║ ┃\\n\"); printf(\"\\\\\\┃ ║ ┏┻━┓ ║ ┗━━┳┛ ║ ┃\\n\"); printf(\"\\\\\\┃ ║ ┃宿舍┃ ║ ║ ║ ┃\\n\"); printf(\"\\\\\\┃ ║ ┃ 区┃ ║ ┏━━┻━━┓ ┃\\n\"); printf(\"\\\\\\┃ ║ ┃ 1 ┣═╬════┫ 食堂 ┃ ┃\\n\"); printf(\"\\\\\\┃ ║ ┗┳━┛ ║ ┗━━┳━━┛ ┃\\n\"); printf(\"\\\\\\┃┏━┻━┓ ║ ║ ║ ┏━━━┓ ┃\\n\"); printf(\"\\\\\\┃┃双馨桥┣═╩═══╬═══════╝ ┃ 南 ┃ ┃\\n\"); printf(\"\\\\\\┃┗━━━┛ ┏━━┻━━┓ ┃东╋西┃ ┃\\n\"); printf(\"\\\\\\┃ ╩════┫ 宿舍区 3 ┃ ┃ 北 ┃ ┃\\n\"); printf(\"\\\\\\┃ ┗━━━━━┛ ┗━━━┛ ┃\\n\"); printf(\"\\\\\\┗━━━━━━━━━━━━━━━━━━━━━━━━━━┛\\n\");

void Outputplace()//输出校园景点名称 { }

void SearchPlace()//查询景点信息 {

int i,num; char c='y'; while(c=='y') { system(\"cls\");

printf(\"\\\\\\┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\");

printf(\"\\\\\\┃ 滨江学院学校景点一览表 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━┳━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃1.滨江学院校门 ┃2滨江楼 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃3.运动场 ┃4.综合楼 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃5.宿舍区3 ┃6.宿舍区2 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃7.宿舍区1 ┃8.双馨桥 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃9万象桥 ┃10.食堂 ┃\\n\"); printf(\"\\\\\\┗━━━━━━━━━━━━┻━━━━━━━━━━━━┛\\n\");

Outputplace();

printf(\"\\\\\\请输入您要查找的景点编号：\"); scanf(\"%d\getchar(); system(\"cls\");

if(num>0 && num<=G.vexnum) //判定信息输入正确 {

for(i=1;i<=G.vexnum;i++) if(num==G.vertex[i].number)

{ }

printf(\"\\n\\\\\\景点编号:%d\\n\

printf(\"\\\\\\景点名称:%s\\n\.vertex[i].name); printf(\"\\\\\\景点简介:%s\\n\\n\.vertex[i].info);

} else printf(\"\\\\\\信息输入有误!\\n\"); num=0;

printf(\"\\n\\\\\\是否继续查询景点信息(y/n):\"); c=getchar(); getchar();

}

system(\"cls\"); }

void SearchPath()//查询最短路径 {

int i,j; char c='y'; while(c=='y') {

system(\"cls\"); Outputplace();

printf(\"\\n\\n\\\\\\初始景点编号(1->10):\"); scanf(\"%d\

printf(\"\\\\\\最终景点编号(1->10):\"); scanf(\"%d\ getchar();

if(i>G.vexnum || i<=0 || j>G.vexnum || j<0 || i==j) printf(\"\\\\\\输入信息错误!\\n\\n\");

else {

Shortpath(i);

Output(i,j); }

printf(\"\\n\\\\\\是否继续查询最短路径(y/n):\"); c=getchar(); getchar();

}

system(\"cls\"); }

void Shortpath(int num)//迪杰斯特拉算法最短路径 {

int v,w,i,t;//i、w和v为计数变量//t表示景点个数 int final[NUM]; //标志数组、用来存放顶点的信息

int min;//记录权值、最终输出路径

for(v=0;vfor(w=0;wpath[v][num]=1; //存在标志置为一 path[v][v]=1; //自身到自身

} }

D[num]=0;//初始化新路径

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

//开始主循环,每一次求得num到某个顶点的最短路径，并将其加入到final集合 for(i=0;imin=MAX; //当前所知离顶点num的最近距离 for(w=0;w{

v=w;

min=D[w]; }

final[v]=1; //离num顶点更近的v加入到s集合

for(w=0;wif(!final[w]&&((min+G.arc[v][w].length)}

{ }

D[w]=min+G.arc[v][w].length;//更新路径 for(t=0;tpath[w][t]=path[v][t]; path[w][w]=1;

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

int a,b,c,d,q=0;//a、b、c和d为计数变量//q控制计数变量、用于换行 a=sight2; //将景点二赋值给a

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

路

径

{ printf(\"\\\\\\从%s到%s的最短是:\\n\\n\\\\\\.vertex[sight1].name,G.vertex[sight2].name);//输出提示信息

//输出sight1到sight2的最短路径长度，存放在D[]数组中 printf(\"\%s\.vertex[sight1].name); //输出景点一的名称 d=sight1; //将景点一的编号赋值给d for(c=0;c{

gate:; //标号，可以作为goto语句跳转的位置

path[a][sight1]=0; for(b=0;b{ printf(\"--->%s\.vertex[b].name); //输出此节点的名称 }

q=q+1; //计数变量加一，满8控制输出时的换行 path[a][b]=0;

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

}

}

printf(\"\\n\\n\\\\\\最短距离为 %dm.\\n\\n\\

}

}

void main() {

int x;

system(\"color1B\");

system(\"mode con: cols=120 lines=100\");//调整屏幕显示大小

CreateGraph(); printf(\"\\n\\n\\n\\n\\n\\\\\\\欢迎使用滨江学院学院校园导游系统\\n\\n\\n\"); while(1) {

//Map();

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

printf(\"\\\\\\\┏━━━━━━━━━━┓\\n\"); printf(\"\\\\\\\┃1. 校园全景浏览 ┃\\n\"); printf(\"\\\\\\\┃2. 景点信息查询 ┃\\n\"); printf(\"\\\\\\\┃3. 最短路径查询 ┃\\n\"); printf(\"\\\\\\\┃0. 退出系统 ┃\\n\"); printf(\"\\\\\\\┗━━━━━━━━━━┛\\n\"); printf(\"\\n\\\\\\\请选择您需要的操作(0-3):\"); scanf(\"%d\ getchar(); switch(x)

{

case 1: system(\"cls\");printf(\"\\\\\\\校园全景浏览:\"); Map();break;

case 2: system(\"cls\");printf(\"\\\\\\\景点信息查询:\"); SearchPlace();break; case 3: system(\"cls\");printf(\"\\\\\\\最短路径查询:\"); SearchPath();break; case 0: printf(\"\\n\\\\\\\\");exit(0);

default: system(\"cls\");printf(\"\\\\\\\输入信息错误,请重新输入!\\n\"); break; }

}

}

3）实验结果的截图记录