C语言校园导航系统

课程设计报告

课程设计题目： 校园导航

专 业： 计算机科学与技术 班 级： 1230701 学 号： 2

学生姓名： 胡玖龙 指导教师： 刘志锋

2014年6月19日

1 / 17

实验题目:

校园导航系统

实验时间：

2014/6/16-2014/6/19

实验地点：

软件楼402

实验目的：

综合运用所学的数据结构知识解决一个关于学校导航系统的问题，侧重对图的相关内容特别是求最短路径的应用，使得能进一步熟悉掌握数据结构的基础知识，进一步提升自己的解决问题和编程调试能力，为后续专业课程的学习打下基础。

实验要求：

设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从某个场所到达另一场所的最佳路径。

求最短路径用Dijkstra或Floryd算法实现。

2 / 17

实现思路：

先分析需求，本程序的主要目的是提供本学校地点的路径查询,并提供其他各种信息查询服务。 需求：

1、提供校园平面图，使得能直观的了解学校。 2、提供地点信息查询，为各地点提供简短的介绍。 3、提供任意两地点间最短路径查询，并计算总路程。

根据要求，先将校园平面图信息抽象为无向网，用邻接矩阵存储。

需求1：

定义map()函数，功能是输出校园的平面图。可简单的通过printf()函数实现。

需求2：

定义Query()函数，功能是查询输出地点信息。可直接输出无向网中的顶点信息。

需求3：

根据输入的起点和终点，运用Floryd算法，求出最短路径，计算路径长度并输出。

考虑到使用者并不一定需要使用所有的功能，所以开始时需要一个选择菜单。定义Menu()函数，功能是提供功能选择。 输入1，选择查看学校平面图 输入2，选择查看各地点信息

输入3，选择查找两地点间最短路径 输入4，退出程序

3 / 17

总流程图： 开始 执行Menu函数 输入选择i Y i=4? N 1 3 i=？ 2 平面图模块 地点信息查询模块 结束

4 / 17

求最短路径模块 平面图模块流程图：

结束 输出校园平面图 开始 地点信息查询模块流程图：

输出各地点编号

5 / 17

开始 输入查询地点编号 执行Query()函数 输出地点信息 结束 求最短路径模块流程图：

开始 输出各地点编号 输入起点地点编号 输入终点地点编号 运用Floyd算法求出最短路径 输出最短路径和路程 结束

实现过程：

从学校的平面图中选取出12个比较重要的地点，将其抽象成无向带权网并用邻接矩阵来表示。以图中的顶点代表地点，存放地点名称、编号、简介等信息，权值代表两地之间的距离。最短路径用Floyd算法求出。

地点间距离用地图软件测出。

6 / 17

将得到的信息绘制成无向网：

1 170

200 2 150 30 300 3 6 150 4 30 500 170 5

7. 160 100 570 8 160

9

180 100 20 10 11 12

程序用到的函数：

MGraph InitGraph(MGraph &G) //构造校园图 void Menu() //初始菜单 void Map() //校园平面图

Void Number() //输出地点编号，在其他操作中会用到 void Query(MGraph G) //查找函数，可以输出地点名称和介绍 void floyd(MGraph G) //floyd算法 void shortestPath_Floyd(MGraph &G) //求最短路径 void main(); //主函数

（1） 图的存储结构：

typedef struct { char name[30]; //地点名称 int num;

//地点编号

char introduction[200]; //地点介绍

7 / 17

1. 体育馆 2. 北区宿舍 3. 图书馆 4. 樱花广场 5. 三教 6. 东门 7. 青春广场 8. 西区食堂 9. 西区宿舍 10. 南区食堂 11. 南区宿舍 12. 南门

}VertexType;

typedef struct{ （2） {

for(i=0;iint i,j; G.vexNum=12; G.arcNum=16;

for(i=1;i<=G.vexNum;i++)

G.vexs[i].num=i; strcpy(G.vexs[1].name,\"体育馆\"); strcpy(G.vexs[2].name,\"北区宿舍\");

strcpy(G.vexs[2].introduction,\"学校北区的宿舍\"); strcpy(G.vexs[3].name,\"图书馆\");

strcpy(G.vexs[3].introduction,\"有着丰富的藏书，是学习、自习的好地方\"); strcpy(G.vexs[4].introduction,\"有很多樱花树，适合早读\"); strcpy(G.vexs[5].name,\"三教\");

strcpy(G.vexs[5].introduction,\"学校的教学区\"); strcpy(G.vexs[6].name,\"东门\");

strcpy(G.vexs[6].introduction,\"学校的正门\"); strcpy(G.vexs[7].name,\"青春广场\");

strcpy(G.vexs[7].introduction,\"经常有各种各样的社团活动\"); strcpy(G.vexs[8].name,\"西区食堂\");

strcpy(G.vexs[8].introduction,\"西区的食堂，饭菜很好吃\"); strcpy(G.vexs[9].name,\"西区宿舍\");

strcpy(G.vexs[9].introduction,\"学校西区的宿舍，既有男生宿舍也有女生宿舍\"); strcpy(G.vexs[10].name,\"南区食堂\"); strcpy(G.vexs[11].name,\"南区宿舍\"); strcpy(G.vexs[12].name,\"南门\"); VertexType vexs[MAX]; //地点

int arcs[MAX][MAX]; //存储图的邻接矩阵 int vexNum,arcNum; //地点数，路径数

}MGraph;

构造校园图：

MGraph InitGraph(MGraph &G) //构造校园图

strcpy(G.vexs[1].introduction,\"有田径场及各种体育活动场馆\");

strcpy(G.vexs[4].name,\"樱花广场\");

strcpy(G.vexs[10].introduction,\"南区食堂，饭菜很好吃\"); strcpy(G.vexs[11].introduction,\"学校南区的宿舍，全是男生宿舍\"); strcpy(G.vexs[12].introduction,\"学校的南门，比较小\");

8 / 17

for(j=0;jG.arcs[i][j]=INFINITY; //不存在的路径长度设为无穷大 G.arcs[0][1]=170; G.arcs[1][2]=200; G.arcs[1][4]=150; G.arcs[2][3]=30; G.arcs[2][4]=150; G.arcs[2][5]=300; G.arcs[3][4]=30; G.arcs[4][6]=170; G.arcs[4][7]=160; G.arcs[5][6]=500; G.arcs[5][10]=570; G.arcs[6][7]=100; G.arcs[7][8]=160; G.arcs[9][10]=100; G.arcs[10][11]=20; }

for(j=0;jG.arcs[j][i]=G.arcs[i][j];

G.arcs[8][9]=180;

for(i=0;ireturn G;

（3）菜单模块：

void Menu() //初始菜单 { }

printf(\"\\n\\n 东华理工大学校园导游系统\\n\");

printf(\" ┏━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\"); printf(\" ┃编号┃ 功 能 ┃\\n\"); printf(\" ┣━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━┫\\n\"); printf(\" ┃ 1 ┃ 查 看 学 校 平 面 图 ┃\\n\"); printf(\" ┃ 2 ┃ 查 看 地 点 信 息 ┃\\n\"); printf(\" ┃ 3 ┃ 查 找 两 地 点 间 最 短 路 径 ┃\\n\"); printf(\" ┃ 4 ┃ 退 出 ┃\\n\"); printf(\" ┗━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━┛\\n\"); printf(\"输入你的选择：\");

9 / 17

（4）平面图模块：

void Map() //校园平面图 {

printf(\"\\n\");

printf(\" ┃ ┃

\\n\");

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

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

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

printf(\" ┗━━━┳━━━┛ \\n\");

printf(\" ┃ printf(\" ┏━━━┻━━━┓ printf(\" ┃ ┃ printf(\" ┏━━━━━━━━━┳━━━┫ 2.北区宿舍 ┣━━━┓ printf(\" ┃ ┃ ┃ ┃ ┃ printf(\" ┃ ┃ ┗━━━━━━━┛ ┃ printf(\" ┃┏━━━━━━━┓┃ ┃ printf(\" ┃┃ ┃┃ ┃ printf(\" ┏━━┓┃┃ ┃┃ ┣┓ printf(\" ┃ ┣╋┫ 3.图书馆 ┣┫ ┃┃6. printf(\" ┃ 4. ┃┃┃ ┃┃ ┃┃东

printf(\" ┃ 樱 ┃┃┃ ┃┣━━━━━━━━━━━━━━━┫┃门 printf(\" ┃ 花 ┃┃┗━━━━━━━┛┃ ┃┃ printf(\" ┃ 广 ┃┃┏━━━━━━━┓┃ ┃┃ printf(\" ┃ 场 ┃┃┃ ┃┃ ┣┛ printf(\" ┃ ┃┃┃ ┃┃ ┃ printf(\" ┃ ┣┻┫ 5.三教 ┣┫ ┃ printf(\" ┗━━┛ ┃ ┃┃ ┃ printf(\" ┃ ┃┃ ┃ printf(\" ┗━━━━━━━┛┣━━━━┳━━━━━━━━━━┫ printf(\" ┃┏━━━┻━━━┓ ┃ printf(\" ┏━━━━━━━┓┃┃ ┃ ┃ printf(\" ┃ ┃┃┃ ┃ ┃ printf(\" ┃ ┃┃┃ 7.青春广场 ┃ ┃ printf(\" ┃ 8.西区食堂 ┣╋┫ ┃ ┃ printf(\" ┃ ┃┃┃ ┃ ┃ printf(\" ┃ ┃┃┃ ┃ ┃ printf(\" ┗━━━━━━━┛┃┗━━━━━━━┛ ┃ printf(\" ┃ ┃ printf(\" ┏━━━━━━━┓┃ ┃ printf(\" ┃ ┃┃ ┃ printf(\" ┃ ┃┃ ┃ printf(\" ┃ 9. ┃┃ ┃ printf(\" ┃ 西 ┃┃ ┃

printf(\" ┃ 区 ┣┫ ┃ 10 / 17

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

printf(\" ┃ 宿 ┃┃ ┃ \\n\"); printf(\" ┃ 舍 ┃┃ ┃ \\n\");

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

printf(\" ┃ ┃┃ ┃ \\n\"); printf(\" ┗━━━━━━━┛┃ ┃ \\n\");

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

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

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

printf(\" ┃ ┃┃┃ ┃ ┃ printf(\" ┃ ┃┃┃ ┃ ┏┻┓ printf(\" ┃ 10.南区食堂 ┣┻┫ 11.南区宿舍 ┣━┫ ┃ printf(\" ┃ ┃ ┃ ┃ ┗━┛ printf(\" ┃ ┃ ┃ ┃ 12.南门 printf(\" ┗━━━━━━━┛ ┃ ┃

printf(\" ┗━━━━━━━━━━━┛ printf(\"请按任意键继续!\"); getch(); }

（5）地点编号函数：

Void Number() //输出地点编号，在其他操作中会用到 {

int v;

printf(\"\\n\\n┏━━┳━━━━━━┓\\n\"); printf(\"┃编号┃地点名称 ┃\\n\"); for(v=1;v<=G.vexNum;v++){ printf(\"┃%-4d┃%-12s┃\\n\.vexs[v].num,G.vexs[v].name);

}

printf(\"┗━━┻━━━━━━┛\\n\");

}

（6）地点信息查询模块：

void Query(MGraph G) //查找函数，可以输出地点名称和介绍 { int k,i=1; Number(); while(i) { printf(\"请输入要查询的地点编号,输入0退出:\");

scanf(\"%d\

11 / 17

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

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

}

}

if(k<0||k>G.vexNum) { }

printf(\"%d.%s %-62s\\n\\n\.vexs[k].num,G.vexs[k].name,G.vexs[k].introduction); if(k==0) i=0;

printf(\"地点编号不存在!请重新输入地点编号:\"); scanf(\"%d\

（7）Floyd算法求最短路径：

int D[MAX][MAX],Path[MAX][MAX]; void floyd(MGraph G) //Floyd算法 { }

void shortestPath_Floyd(MGraph &G) //求最短路径 {

int i,j,p,m,k; int b[100]; floyd(G); Number(); do{

printf(\"请输入起点编号:\");

scanf(\"%d\scanf(\"%d\printf(\"请输入终点编号:\"); int i,j,k;

for(i=0;ifor(j=0;jfor(k=0;kfor(i=0;ifor(j=0;jif(D[i][k]+D[k][j]D[i][j]=D[i][k]+D[k][j]; Path[i][j]=Path[k][j];

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

if(i!=j&&G.arcs[i][j]12 / 17

}

if(i==j)

printf(\"起点和终点一样，请重新输入\\n\");

else if(i>12||i<0||j>12||j<0) printf(\"输入错误，请重新输入\\n\"); i=i-1;j=j-1; if(i!=j){ }

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

printf(\"起点：%s，终点：%s\\n最短路径：\.vexs[i+1].name,G.vexs[j+1].name); p=Path[i][j];

if(p==-1) printf(\"empty\\n\");

else{

m=0;b[m++]=j;

while(p!=i){b[m++]=p; p=Path[i][p];}

}while(i==j||i>12||i<0||j>12||j<0);

b[m]=i;

for(k=m;k>0;k--) printf(\"%s->\.vexs[b[k]+1].name); printf(\"%s,路程为%d米\\n\.vexs[b[0]+1].name,D[i][j]); }

（8）主函数：

void main() //主函数 {

InitGraph(G); int i;

Menu(G);

scanf(\"%d\ //输入选择 while(i!=4) //输入4，则退出 {

switch(i)

{ //每次选择后会调用清屏函数，使界面美观 }

scanf(\"%d\ }

}

case 1:system(\"CLS\");Map();Menu(G);break; //若输入1，则输出平面图

case 2:system(\"CLS\");Query(G);Menu(G);break; //若输入2，则查找并输出地点名称和介绍 case 3:system(\"CLS\");shortestPath_Floyd(G);Menu(G);break; //若输入3，则找出最短路径 case 4:;break;

default:printf(\"输入错误,清重新输入\\n\");

13 / 17

运行结果：

图1：

初始菜单，输入1查看学校平面图，输入2查看地点信息，输入3查找两地点间最短路径，输入4退出。

图2：

查看地点信息

输入要查询的地点编号，输入错误则出现错误提示，并重新输入。输入0则返回初始菜单。

14 / 17

图3：

查看学校平面图

15 / 17

图4.1：

查找两地间最短路径

输入起点和终点编号，则会计算出最短路径和路程

图4.2：

若输入的起点或终点编号错误，则出现错误提示，并重新输入。

16 / 17

实验总结：

程序能满足实验要求，较好的实现的了各个功能，做到了实用方便，但仍有很多不足之处，主要是以下几点：

1.按要求将校园平面图信息抽象为无向网用邻接矩阵存储，能较好的表现校园各地点信息，并能方便地使用Floyd算法查找最短路径，但邻接矩阵不适用与两顶点之间有多条边的情况，所以对于有道路直接相连的两地点，只取路程最短的路，虽然对于各功能没有影响，但平面图的信息并没有全部存储。

2.同时由于地点本身有长度和面积，并不能完全抽象为一个顶点，对于没有道路直接相连的地点，因为中间要经过其他地点，而经过的地点的长度并未算在路程内，所以计算出的路程长度要比实际长度略短。

3.对于输出校园平面图的功能，只简单的用printf()函数输出，用一个个符号组成平面图，这个方法费时费力，但还没有找到更好的方法。

心得体会：

通过完成这次课程设计，我学会了综合运用所学的数据结构知识解决一个具体的问题，尤其是熟悉了对图的相关内容的应用，更加深入的了解了求最短路径算法的原理，使得能进一步熟悉掌握数据结构的基础知识，并在编写程序的过程中，掌握了很多编程技巧，学会了使用一些新的功能函数，进一步提升了自己的解决问题和编程调试的能力。并且意识到编程要有条理和规划。对于一个项目，要先分析需求，再将不同需求划分成各个模块。编程过程中要注意代码格式，要添加必要的注释，这样可以减少很多不必要的麻烦。

17 / 17