毕业论文校园导航系统数据结构课程设计报告书

课程设计报告书

课程名称 数据结构 设计题目 校园导航系统 专业班级 计算机11-4 班

目录

1.设计时间……………………………………………… 2 2.设计目的……………………………………………… 2 3.设计任务……………………………………………… 2 4.设计内容……………………………………………… 2

4.1需求分析………………………………………………… 2 4.2总体设计………………………………………………… 3 4.3详细设计………………………………………………… 4 4.4测试与分析………………………………………………12

4.4.1测试…………………………………………………………12 4.4.2分析…………………………………………………………13

4.5 附录………………………………………………………14

5 总结与展望…………………………………………… 20 6.参考文献……………………………………………… 21 7.成绩评定……………………………………………… 21

1

1 设计时间 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米。 2

4．测试数据包括在正确的输入及输出结果及含有错误的输入及输出结果： Input：s Output: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: 3 Output:@name: Area B dormitory building @introduction:Area B student rest area input：e output：Thank you for you use 4.2总体设计 1．抽象数据类型定义 typedef struct { char name[100] ; int number; char introduce[100]; }Vertex; 2．主程序模块的整体流程 1、进入主函数，调用init()，map()。 2、选择“s”，调用shortestpath函数，并同时调用floyd和way函数。 3、选择“i”，调用information函数 4、选择“e”，退出。 3.各模块调用关系如下： 3

shortestpath s 主函数 e i Exit Information 4.3详细设计 1.有向网节点结构体类型定义： typedef struct { char name[100] ; int number; char introduce[100]; }Vertex; 2. 主程序和其它主要函数伪码算法 1）主程序 int main() { char i; printf(\navigation system\\n\\n\\n\\n\ init(); map(); char c; do { printf(\ printf(\ 4

printf(\ loop: scanf(\ 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(\ return 0; } else 5

{ printf(\ continue; } } }while(1); return 0; } 2）赋值init函数 void init() { int i, j; vertex[1].number = 1; strcpy(vertex[1].name,\ strcpy(vertex[1].introduce, \ vertex[2].number = 2; strcpy(vertex[2].name, \ strcpy(vertex[2].introduce,\ vertex[3].number = 3; strcpy(vertex[3].name, \ strcpy(vertex[3].introduce,\ vertex[4].number = 4; strcpy(vertex[4].name, \ strcpy(vertex[4].introduce,\ vertex[5].number = 5; strcpy(vertex[5].name,\ strcpy(vertex[5].introduce,\ vertex[6].number = 6; strcpy(vertex[6].name,\ 6

strcpy(vertex[6].introduce,\ vertex[7].number = 7; strcpy(vertex[7].name,\ strcpy(vertex[7].introduce,\ /*vertex[7].number = 8; strcpy(vertex[7].name,\ strcpy(vertex[7].introduce,\ vertex[8].number = 8; strcpy(vertex[8].name,\ strcpy(vertex[8].introduce,\ vertex[9].number = 9; strcpy(vertex[9].name,\ strcpy(vertex[9].introduce,\ for(i = 1; i < MAX_VERTEX_NUM; ++i) { for(j = 1; j < MAX_VERTEX_NUM; ++j) { } } for(i = 1; i < MAX_VERTEX_NUM; ++i) { dist[i][i] = 0; } dist[1][2] = dist[2][1] = 20; dist[2][3] = dist[3][2] = 40; dist[1][4] = dist[4][1] = 50; dist[2][5] = dist[5][2] = 30; dist[3][6] = dist[6][3] = 50; dist[i][j] = INFINITY; 7

dist[4][5] = dist[5][4] = 70; dist[5][6] = dist[6][5] = 90; dist[4][7] = dist[7][4] = 100; dist[5][8] = dist[8][5] = 120; dist[6][9] = dist[9][6] = 80; dist[7][8] = dist[8][7] = 60; dist[8][9] = dist[9][8] =120; } 3）输出山东科技大学平面图的map函数 void map() { printf(\map\\n\ printf(\printf(\C dormitory building---(2)Area A dormitory building---(3)Area B dormitory building\\n\ printf(\ | | | \\n\ printf(\ | | | \\n\ printf(\ | | | \\n\ printf(\ (4)Area C restaurant ------(5)Area A restaurant-----------------------(6)Area B restaurant\\n\ printf(\ | | | \\n\ printf(\ | | | \\n\ printf(\ | | 8

| \\n\ printf(\ (7)library---------------(8)No. 1 teaching building-------------(9)No. 13 teaching building\\n\ printf(\} 4）输出地点信息的information函数 void Information() { int number; while(1) { printf(\ } } 5）最短路径floyd函数 void floyd()/*弗洛伊德算法*/ { int i, j, u; } else { } printf(\return; printf(\scanf(\if(number < MAX_VERTEX_NUM && number > 0) { 9

for(i = 1; i < MAX_VERTEX_NUM; ++i) { } for(u = 1; u < MAX_VERTEX_NUM; ++u) { } } 6）输出路径Path算法 void Path(int i, int j)/*最短路径的输出*/ { int u = 0; int a,b; a = i; for(i = 1; i < MAX_VERTEX_NUM; ++i) { } for(j = 1; j < MAX_VERTEX_NUM; ++j) { } if(shortest[i][j] > (shortest[i][u] + shortest[u][j])) { } shortest[i][j] = shortest[i][u] + shortest[u][j]; path[i][j] = path[j][i] = u; for(j = 1; j < MAX_VERTEX_NUM; ++j) { } shortest[i][j] = dist[i][j]; path[i][j] = 0; 10

b = j; if(shortest[i][j] != INFINITY) { printf(\printf(\while(path[i][j] != 0) { u = path[i][j]; while(path[i][u] != 0) { u = path[i][u]; } } 7）调用floyd和Path的最短路径shortestpath算法 void shortestpath() { int i, j; while(1) { printf(\scanf(\if(i > 0 && i < MAX_VERTEX_NUM && j > 0 && j < MAX_VERTEX_NUM) { } printf(\printf(\} printf(\i = u; 11

} } } floyd(); //printf(\Path(i,j); return; 3. 函数的调用关系 map main Init Shortsetpath() exit Information() s e i 4.4测试与分析 4.4.1测试 1）打开程序后，出现我校平面图和菜单选项，如图所示 12

2） 2）选“i”，查询对应地点的信息，如输入“3”，而后会继续输出菜单，如图所示 3）选“s”，查询两点之间的信息，如输入“1 7”，而后会继续输出菜单，如图所示 4）选“e”，推出程序，如图所示 4.4.2分析 13

1.本次作业的核心是利用弗洛伊德算法计算给定图中两点最短距离；给出图中所要求点的信息。在调试过程中，除了简单语法错误外，就是对弗洛伊德算法的理解和实现，以及菜单的设置，这是我以前没有实现过的。出于简单化，并没有对有向图中各个点进行输入，而是在程序中直接赋值。 2.在对各个功能操作的实现上，由于有弗洛伊德算法时间复杂度大多数是O(n3)，空间上增加了二维数组，空间复杂度为O(n+s)。 4.5 附录 Map.h #include #include //#include #define MAX_VERTEX_NUM 10 #define INFINITY 10000000 typedef struct { char name[100]; int number; char introduce[100]; }Vertex; Vertex vertex[MAX_VERTEX_NUM]; int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int shortest[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; void map() { printf(\ printf(\ printf(\building\\n\ printf(\ | | | \\n\ printf(\ | | | \\n\ 14

本文来源：https://www.bwwdw.com/article/iq3h.html