校园导航系统数据结构课程设计报告书.doc

课程设计报告书课程名称 数据结构 设计题目 校园导航系统 专业班级 计算机11-4 班 目录1.设计时间 22.设计目的 23.设计任务 24.设计内容 24.1需求分析 24.2总体设计 34.3详细设计 44.4测试与分析124.4.1测试124.4.2分析134.5 附录145 总结与展望 206.参考文献 217.成绩评定 211 设计时间 2013年12月3日2 设计目的1加深对数据结构这一课程所学内容的进一步理解与巩固2通过完成课程设计，逐渐培养自己的编程能力；3培养给出题目后，构建框架，用计算机解决的能力；4通过调试程序积累调试C程序设计的经验； 3设计任务给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离，利用校园导航系统计算出给定的起点到终点之间的最近距离及线路。4 设计内容 4.1需求分析 1程序所能达到的功能： (1) map输出山东科技大学平面图。(2) init()按相应编号输入各个节点内容，对相应路径赋值的函数。(3) floyd()- -弗洛伊德求最短路径(4) information()输出简介的函数(5) Path()最短路径的输出函数(6) shortestpath()调用弗洛伊德和最短路径输出的函数(7) main()主函数2输入的形式和输入值的范围：输入数字和字母： 字母：以s查询最短路径；以i查询信息；以e退出程序。 数字：从1到9输入。3输出的形式：从A到B得最短路径为： A-到-C-到-D-到-B 最短距离为：xxx米。4测试数据包括在正确的输入及输出结果及含有错误的输入及输出结果：Input：sOutput:Please enter the number two to query : 1 7 Output：The shortest path from Area C dormitory building to library is: Area C dormitory building-Area C restaurant-library; The shortest distance is:150meters.Input：i Output:Please enter the number of query site: 3Output:name: Area B dormitory building introduction:Area B student rest areainput：e output：Thank you for you use 4.2总体设计1抽象数据类型定义typedef structchar name100 ;int number; char introduce100;Vertex;2主程序模块的整体流程 1、进入主函数，调用init()，map()。2、选择“s”，调用shortestpath函数，并同时调用floyd和way函数。3、选择“i”，调用information函数4、选择“e”，退出。3.各模块调用关系如下： 主函数 e i s shortestpath Information Exit4.3详细设计1.有向网节点结构体类型定义：typedef structchar name100 ;int number; char introduce100;Vertex;2. 主程序和其它主要函数伪码算法1）主程序int main() char i; printf(" Welcome to use the shandong university of science and technology of navigation systemnnnn"); init(); map(); char c; do printf("Please enter the 's' to query the shortest pathn"); printf("Please enter the 'i' to query informationn"); printf("Please input 'e' to exit the programnnn"); loop: scanf("%c",&c); if(c >= 'A' && c <= 'Z') c += 32; if(c = 'n') goto loop; if(c != 'n') if(c = 's') shortestpath(); continue; else if(c = 'i') Information(); continue; else if(c = 'e') printf("nnnttttThank you for you usennn"); return 0; else printf("input error!n"); continue; while(1); return 0;2）赋值init函数void init()int i, j;vertex1.number = 1;strcpy(vertex1.name,"Area C dormitory building"); strcpy(vertex1.introduce, "Area C student rest area"); vertex2.number = 2; strcpy(vertex2.name, "Area A dormitory building"); strcpy(vertex2.introduce,"Area A student rest area"); vertex3.number = 3; strcpy(vertex3.name, "Area B dormitory building"); strcpy(vertex3.introduce,"Area B student rest area"); vertex4.number = 4; strcpy(vertex4.name, "Area C restaurant"); strcpy(vertex4.introduce,"Area C student dining area"); vertex5.number = 5; strcpy(vertex5.name,"Area A restaurant"); strcpy(vertex5.introduce,"Area A student dining area"); vertex6.number = 6; strcpy(vertex6.name,"Area B restaurant"); strcpy(vertex6.introduce,"Area B student dining area"); vertex7.number = 7; strcpy(vertex7.name,"library"); strcpy(vertex7.introduce,"Student borrowing books area"); /*vertex7.number = 8; strcpy(vertex7.name,"Area A restaurant"); strcpy(vertex7.introduce,"Area A student dining area");*/ vertex8.number = 8; strcpy(vertex8.name,"No. 1 teaching building"); strcpy(vertex8.introduce,"Students in class area"); vertex9.number = 9; strcpy(vertex9.name,"No. 13 teaching building"); strcpy(vertex9.introduce,"Information institute, college building"); for(i = 1; i < MAX_VERTEX_NUM; +i) for(j = 1; j < MAX_VERTEX_NUM; +j) distij = INFINITY; for(i = 1; i < MAX_VERTEX_NUM; +i) distii = 0; dist12 = dist21 = 20; dist23 = dist32 = 40; dist14 = dist41 = 50; dist25 = dist52 = 30; dist36 = dist63 = 50; dist45 = dist54 = 70; dist56 = dist65 = 90; dist47 = dist74 = 100; dist58 = dist85 = 120; dist69 = dist96 = 80; dist78 = dist87 = 60; dist89 = dist98 =120;3）输出山东科技大学平面图的map函数void map()printf(" the science and technology of Shandong university mapn");printf("nn");printf(" (1)Area C dormitory building-(2)Area A dormitory building-(3)Area B dormitory buildingn");printf(" | | | n");printf(" | | | n");printf(" | | | n");printf(" (4)Area C restaurant -(5)Area A restaurant-(6)Area B restaurantn");printf(" | | | n");printf(" | | | n");printf(" | | | n");printf(" (7)library-(8)No. 1 teaching building-(9)No. 13 teaching buildingn"); printf("nnn");4）输出地点信息的information函数void Information()int number;while(1)printf("Please enter the number of query site:");scanf("%d",&number);if(number < MAX_VERTEX_NUM && number > 0)printf("nname: %snintroduction:%sn",vertexnumber.name,vertexnumber.introduce);return;elseprintf("input error!n");5）最短路径floyd函数void floyd()/*弗洛伊德算法*/int i, j, u;for(i = 1; i < MAX_VERTEX_NUM; +i)for(j = 1; j < MAX_VERTEX_NUM; +j)shortestij = distij;pathij = 0;for(u = 1; u < MAX_VERTEX_NUM; +u)for(i = 1; i < MAX_VERTEX_NUM; +i)for(j = 1; j < MAX_VERTEX_NUM; +j)if(shortestij > (shortestiu + shortestuj)shortestij = shortestiu + shortestuj;pathij = pathji = u;6）输出路径Path算法void Path(int i, int j)/*最短路径的输出*/int u = 0;int a,b;a = i;b = j; if(shortestij != INFINITY)printf("nThe shortest path from %s to %s is:nn",vertexi.name,vertexj.name);printf("%s",vertexi.name);while(pathij != 0)u = pathij;while(pathiu != 0) u = pathiu;printf("-%s",vertexu.name);i = u;printf("-%s;n",vertexj.name);printf("nThe shortest distance is:%d meters.n",shortestab);7）调用floyd和Path的最短路径shortestpath算法void shortestpath()int i, j;while(1)printf("Please enter the number two to query :");scanf("%d%d", &i, &j);if(i > 0 && i < MAX_VERTEX_NUM && j > 0 && j < MAX_VERTEX_NUM)floyd();/printf("=n");Path(i,j);return;3. 函数的调用关系exitexit mainMain Init map e i s Information() exit Shortsetpath()4.4测试与分析4.4.1测试1） 打开程序后，出现我校平面图和菜单选项，如图所示2）2） 选“i”，查询对应地点的信息，如输入“3”，而后会继续输出菜单，如图所示 3）选“s”，查询两点之间的信息，如输入“1 7”，而后会继续输出菜单，如图所示4）选“e”，推出程序，如图所示4.4.2分析1.本次作业的核心是利用弗洛伊德算法计算给定图中两点最短距离；给出图中所要求点的信息。在调试过程中，除了简单语法错误外，就是对弗洛伊德算法的理解和实现，以及菜单的设置，这是我以前没有实现过的。出于简单化，并没有对有向图中各个点进行输入，而是在程序中直接赋值。2.在对各个功能操作的实现上，由于有弗洛伊德算法时间复杂度大多数是O(n3)，空间上增加了二维数组，空间复杂度为O(n+s)。4.5 附录Map.h#include <stdio.h>#include <string.h>/#include <map.h>#define MAX_VERTEX_NUM 10#define INFINITY 10000000typedef struct char name100;int number;char introduce100;Vertex;Vertex vertexMAX_VERTEX_NUM;int distMAX_VERTEX_NUMMAX_VERTEX_NUM;int shortestMAX_VERTEX_NUMMAX_VERTEX_NUM;int pathMAX_VERTEX_NUMMAX_VERTEX_NUM;void map()printf(" the science and technology of Shandong university mapn");printf("nn");printf(" (1)Area C dormitory building-(2)Area A dormitory building-(3)Area B dormitory buildingn");printf(" | | | n");printf(" | | | n");printf(" | | | n");printf(" (4)Area C restaurant -(5)Area A restaurant-(6)Area B restaurantn");printf(" | | | n");printf(" | | | n");printf(" | | | n");printf(" (7)library-(8)No. 1 teaching building-(9)No. 13 teaching buildingn"); printf("nnn");void init()int i, j;vertex1.number = 1;strcpy(vertex1.name,"Area C dormitory building"); strcpy(vertex1.introduce, "Area C student rest area"); vertex2.number = 2; strcpy(vertex2.name, "Area A dormitory building"); strcpy(vertex2.introduce,"Area A student rest area"); vertex3.number = 3; strcpy(vertex3.name, "Area B dormitory building"); strcpy(vertex3.introduce,"Area B student rest area"); vertex4.number = 4; strcpy(vertex4.name, "Area C restaurant"); strcpy(vertex4.introduce,"Area C student dining area"); vertex5.number = 5; strcpy(vertex5.name,"Area A restaurant"); strcpy(vertex5.introduce,"Area A student dining area"); vertex6.number = 6; strcpy(vertex6.name,"Area B restaurant"); strcpy(vertex6.introduce,"Area B student dining area"); vertex7.number = 7; strcpy(vertex7.name,"library"); strcpy(vertex7.introduce,"Student borrowing books area"); /*vertex7.number = 8; strcpy(vertex7.name,"Area A restaurant"); strcpy(vertex7.introduce,"Area A student dining area");*/ vertex8.number = 8; strcpy(vertex8.name,"No. 1 teaching building"); strcpy(vertex8.introduce,"Students in class area"); vertex9.number = 9; strcpy(vertex9.name,"No. 13 teaching building"); strcpy(vertex9.introduce,"Information institute, college building"); for(i = 1; i < MAX_VERTEX_NUM; +i) for(j = 1; j < MAX_VERTEX_NUM; +j) distij = INFINITY; for(i = 1; i < MAX_VERTEX_NUM; +i) distii = 0; dist12 = dist21 = 20; dist23 = dist32 = 40; dist14 = dist41 = 50; dist25 = dist52 = 30; dist36 = dist63 = 50; dist45 = dist54 = 70; dist56 = dist65 = 90; dist47 = dist74 = 100; dist58 = dist85 = 120; dist69 = dist96 = 80; dist78 = dist87 = 60; dist89 = dist98 =120;void Information()int number;while(1)printf("Please enter the number of query site:");scanf("%d",&number);if(number < MAX_VERTEX_NUM && number > 0)printf("nname: %snintroduction:%sn",vertexnumber.name,vertexnumber.introduce);return;elseprintf("input error!n");void floyd()/*弗洛伊德算法*/int i, j, u;for(i = 1; i < MAX_VERTEX_NUM; +i)for(j = 1; j < MAX_VERTEX_NUM; +j)shortestij = distij;pathij = 0;for(u = 1; u < MAX_VERTEX_NUM; +u)for(i = 1; i < MAX_VERTEX_NUM; +i)for(j = 1; j < MAX_VERTEX_NUM; +j)if(shortestij > (shortestiu + shortestuj)shortestij = shortestiu + shortestuj;pathij = pathji = u;void Path(int i, int j)/*最短路径的输出*/int u = 0;int a,b;a = i;b = j;/printf("=1n");if(shortestij != INFINITY)/printf("=2n");printf("nThe shortest path from %s to %s is:nn",vertexi.name,vertexj.name);printf("%s",vertexi.name);while(pathij != 0)u = pathij;while(pathiu != 0) u = pathiu;printf("-%s",vertexu.name);i = u;printf("-%s;n",vertexj.name);printf("nThe shortest distance is:%d meters.n",shortestab);void shortestpath()int i, j;while(1)printf("Please enter the number two to query :");scanf("%d%d", &i, &j);if(i > 0 && i < MAX_VERTEX_NUM && j > 0 && j < MAX_VERTEX_NUM)floyd();/printf("=n");Path(i,j);return;Map.c#include <stdio.h>#include <map.h>int main() char i; printf(" Welcome to use the shandong university of science and technology of navigation systemnnnn"); init(); map(); char c; do printf("Please enter the 's' to query the shortest pathn"); printf("Please enter the 'i' to query informationn"); printf("Please input 'e' to exit the programnnn"); loop: scanf("%c",&c); if(c >= 'A' && c <= 'Z') c += 32; if(c = 'n') goto loop; if(c != 'n') if(c = 's') shortestpath(); continue; else if(c = 'i') Information(); continue; else if(c = 'e') printf("nnnttttThank you for you usennn"); return