数据结构课程设计蚌埠学院计算机科学与技术系课程设计任务书目录1 引言 (4)1.1 问题的提出 (4)1.2任务与功能简介 (4)1.2.1任务 (4)1.2.2功能简介 (4)2 程序运行平台 (5)3 总体设计与模块分析 (6)3.1抽象数据类型定义 (6)3.2主程序模块的整体流程 (6)3.3各模块调用和函数关系如下 (6)4 程序的主要功能实现 (8)4.1 main()——主函数 (8)4.2赋值init函数 (8)4.3输出蚌埠学院校园导航平面图的map函数 (10)4.4菜单menu函数 (11)4.5输出地点信息的information函数 (12)4.7输出路径way函数 (13)4.8调用floyd和way的最短路径shortestpath算法 (14)5系统测试 (15)5.1系统运行后主界面 (15)5.2查询最短路径 (16)5.3查询地点信息 (17)致谢 (19)参考文献 (20)附录 (21)1 引言为了加深对《数据结构》这一课程所学内容的进一步理解与巩固，我们这一组按课程设计要求完成了校园导航系统的设计。
1.1 问题的提出我们这次基于对导航这个热门问题的研究设计了简易校园导航系统，我们的导航平面图中至少包括8个以上校园的场所，每两个场所间可以有不同的路，且路长也可能不同，给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离，利用校园导航系统计算出给定的起点到终点之间的最近距离及线路。
本导航系统能够很好的向同学们提供距离与地点的详细信息。
1.2任务与功能简介1.2.1任务（1）本次作业的核心是利用弗洛伊德算法计算给定有向网中两点最短距离；给出有向网中所要求点的信息。
在调试过程中，除了简单语法错误外，就是对弗洛伊德算法的理解和实现，以及菜单的设置，这是我以前没有实现过的。
出于简单化，并没有对有向图中各个点进行输入，而是在程序中直接赋值。
（2）在对各个功能操作的实现上，由于有弗洛伊德算法时间复杂度大多数是O(n3)，空间上增加了二维数组，空间复杂度为O(n+s)。
1.2.2功能简介程序所能达到的功能：(1) map——输出蚌埠学院导航平面图。
(2) init()——按相应编号输入各个节点内容，对相应路径赋值的函数。
(3) menu()——菜单函数(4) information()——输出简介的函数(5) way()——最短路径的输出函数(6) shortestpath()——调用弗洛伊德和最短路径输出的函数(7) main()——主函数2 程序运行平台本次课程设计我们采用的运行平台是 visual C++6.0,该平台是由Visual C++6.0由Microsoft开发, 它不仅是一个C++编译器，而且是一个基于Windows 操作系统的可视化集成开发环境（integrated development environment，IDE）。
Visual C++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。
Visual C++已成为专业程序员进行软件开发的首选工具。
虽然微软公司推出了Visual C++.NET(Visual C++7.0)，但它的应用有很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。
所以实际中，更多的是以Visual C++6.0为平台。
Visual C++6.0以拥有“语法高亮”，自动编译功能以及高级除错功能而著称。
比如，它允许用户进行远程调试，单步执行等。
还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。
其编译及创建预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。
这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。
3 总体设计与模块分析3.1抽象数据类型定义有向网节点结构体类型typedef struct{char name[10] ;int number;char introduce[100];}vertex;3.2主程序模块的整体流程1、进入主函数，调用init，map和menu函数。
2、选择“s”，调用shortestpath函数，并同时调用floyd和way函数。
并返回调用menu函数。
3、选择“i”，调用information函数。
并返回调用menu函数。
4、选择“e”，退出。
3.3各模块调用和函数关系如下4 程序的主要功能实现4.1 main()——主函数是程序执行的入口，主函数用于使用者便于使用者选择使用导航系统的功能int main()/*主函数*/{char i;printf("\t\t\t欢迎使用蚌埠学院校园导航系统\n\n");init();map();/*输出地图，提示使用者*/while (1){i=menu();switch(i){case 's':shortestpath();break;case 'i':information();break;case 'e':printf("\n\n\n\t\t\t\t谢谢使用!\n");return 0;default :printf("输入错误！\n");break;}}}4.2赋值init函数init函数主要用于初始化校园平面图中的地点信息void init()//初始化信息函数{int i,j;//对平面图中的各个地点信息进行输入，运用strcpy函数ver[1].number =1;strcpy(ver[1].name,"重行楼");strcpy(ver[1].introduce,"教师办公场所\n");ver[2].number =2;strcpy(ver[2].name,"B教学楼");strcpy(ver[2].introduce,"日常上课，学习知识的地方\n");ver[3].number =3;strcpy(ver[3].name,"北操场");strcpy(ver[3].introduce,"假草，球门，尽情施展脚法的好地方\n");ver[4].number =4;strcpy(ver[4].name,"西大门");strcpy(ver[4].introduce,"学生外出的常用通道\n");ver[5].number =5;strcpy(ver[5].name,"图书馆");strcpy(ver[5].introduce,"查阅资料，努力学习的理想之所\n");ver[6].number =6;strcpy(ver[6].name,"第一食堂");strcpy(ver[6].introduce,"校内最好的食堂\n");ver[7].number =7;strcpy(ver[7].name,"行政楼");strcpy(ver[7].introduce,"行政机构\n");ver[8].number =8;strcpy(ver[8].name,"南操场");strcpy(ver[8].introduce,"以男生为主的真草操场\n");ver[9].number =9;strcpy(ver[9].name,"学生公寓");strcpy(ver[9].introduce,"学生休息生活场所\n");ver[10].number =10;strcpy(ver[10].name,"体育馆");strcpy(ver[10].introduce,"学校的室内体育馆，遮风挡雨的理想运动场所\n");ver[11].number =11;strcpy(ver[11].name,"高知公寓");strcpy(ver[11].introduce,"校职工的住宿地\n");for(i=1;i<=Num;i++)/*对存储距离的距离矩阵取值进行初始化，全定义为最大{for(j=1;j<=Num;j++){edge[i][j]=Maxedge;}}for(i=1,j=1;i<=Num,j<=Num;i++,j++)//对存储距离的矩阵的取值进行正确赋值，由于我校均来回可达，故对路径正反同时赋值{edge[i][j]=0;}edge[1][2]=edge[2][1]=90;edge[1][4]=edge[4][1]=110;edge[2][3]=edge[3][2]=80;edge[2][5]=edge[5][2]=150;edge[3][6]=edge[6][3]=130;edge[4][5]=edge[5][4]=200;edge[4][7]=edge[7][4]=70;edge[5][6]=edge[6][5]=160;edge[5][8]=edge[8][5]=300;edge[6][9]=edge[9][6]=60;edge[7][8]=edge[8][7]=80;edge[7][10]=edge[10][7]=120;edge[8][9]=edge[9][8]=50;edge[8][10]=edge[10][8]=30;edge[9][11]=edge[11][9]=40;edge[10][11]=edge[11][10]=30;}4.3输出蚌埠学院校园导航平面图的map函数map函数用于显示蚌埠学院校园导航平面图，给使用程序者以直观认识void map(){printf("\t\t蚌埠学院校园导航平面图(括号内为相对应的数字编号)\n");printf("\n\n");printf("\t 重行楼(1)————B教学楼(2)—————北操场(3)\n");printf("\t | | |\n");printf("\t 西大门(4)—————一图书馆(5)————第一食堂(6)\n");printf("\t | | |\n");printf("\t 行政楼(7)————南操场(8)————学生公寓(9) \n");printf("\t | | |\n");printf("\t -——————体育馆(10)————高知公寓(11) \n");}4.4菜单menu函数char menu()/*菜单函数*/{char i;printf("输入“s”以查询最短路径\n");printf("输入“i”以查询信息\n");printf("输入“e”以退出程序\n");printf("请输入对应的英文小写字母，谢谢：\n\t");scanf("%s",&i);return i;}4.5输出地点信息的information函数当使用者选择显示地点信息功能时将调用此函数实现该功能void information()/*输出简介函数*/{int i;while(1){printf("请输入查询地点的编号：\n\t");scanf("%d",&i);if(i<=Num&&i>=1){printf("\n@名称：%s\n#简介：%s\n",ver[i].name,ver[i].introduce);return;}else{printf("输入有误！");return;}}}4.6最短路径floyd函数floyd算法说明：对于从v i到v j的弧，进行n次试探：首先考虑路径v i,v0,v j是否存在，如果存在，则比较v i,v j和v i,v0,v j的路径长度，取较短者为从v i到v的中间顶点的序号不大于0的最短路径。