文档库
文档库 最新最全的文档下载
当前位置：文档库 › (强烈推荐)校园导航系统数据结构毕业论文报告书

(强烈推荐)校园导航系统数据结构毕业论文报告书

课程设计报告书

课程名称数据结构

设计题目校园导航系统

专业班级计算机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 设计时间

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：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.各模块调用关系如下：

4.3详细设计

1.有向网节点结构体类型定义：

typedef struct

{

char name[100] ;

int number;

char introduce[100];

}Vertex;

2. 主程序和其它主要函数伪码算法

1）主程序

int main()

{

char i;

printf(" Welcome to use the shandong university of science and technology of navigation system\n\n\n\n");

init();

map();

char c;

do

{

printf("Please enter the 's' to query the shortest path\n");

printf("Please enter the 'i' to query information\n");

printf("Please input 'e' to exit the program\n\n\n");

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("\n\n\n\t\t\t\tThank you for you use\n\n\n");

return 0;

}

else

{

printf("input error!!!\n");

continue;

}

}while(1);

return 0;

}

2）赋值init函数

void init()

{

int i, j;

vertex[1].number = 1;

strcpy(vertex[1].name,"Area C dormitory building");

strcpy(vertex[1].introduce, "Area C student rest area");

vertex[2].number = 2;

strcpy(vertex[2].name, "Area A dormitory building");

strcpy(vertex[2].introduce,"Area A student rest area");

vertex[3].number = 3;

strcpy(vertex[3].name, "Area B dormitory building");

strcpy(vertex[3].introduce,"Area B student rest area");

vertex[4].number = 4;

strcpy(vertex[4].name, "Area C restaurant");

strcpy(vertex[4].introduce,"Area C student dining area");

vertex[5].number = 5;

strcpy(vertex[5].name,"Area A restaurant");

strcpy(vertex[5].introduce,"Area A student dining

area");

vertex[6].number = 6;

strcpy(vertex[6].name,"Area B restaurant");

strcpy(vertex[6].introduce,"Area B student dining area");

vertex[7].number = 7;

strcpy(vertex[7].name,"library");

strcpy(vertex[7].introduce,"Student borrowing books area");

*vertex[7].number = 8;

strcpy(vertex[7].name,"Area A restaurant");

strcpy(vertex[7].introduce,"Area A student dining area");*

vertex[8].number = 8;

strcpy(vertex[8].name,"No. 1 teaching building");

strcpy(vertex[8].introduce,"Students in class area");

vertex[9].number = 9;

strcpy(vertex[9].name,"No. 13 teaching building");

strcpy(vertex[9].introduce,"Information institute, college building");

for(i = 1; i < MAX_VERTEX_NUM; ++i)

{

for(j = 1; j < MAX_VERTEX_NUM; ++j)

{

dist[i][j] = INFINITY;

}

}

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[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(" the science and technology of Shandong university map\n");

printf("\n\n");

printf(" (1)Area 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 printf(" | | | \n");

printf(" | | | \n");

printf(" | | | \n");

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

}

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) {

return;

}

else

{

printf("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)

{

shortest[i][j] = dist[i][j];

path[i][j] = 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(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;

}

}

}

}

}

6）输出路径Path算法

void Path(int i, int j)*最短路径的输出*

{

int u = 0;

int a,b;

a = i;

b = j;

if(shortest[i][j] != INFINITY)

{

printf("\nThe shortest path from %s to %s is:\n\n",vertex[i].name,vertex[j].name);

printf("%s",vertex[i].name);

while(path[i][j] != 0)

u = path[i][j];

while(path[i][u] != 0)

{

u = path[i][u];

}

printf("--%s",vertex[u].name);

i = u;

}

printf("--%s;\n",vertex[j].name);

printf("\nThe shortest distance is:%d meters.\n",shortest[a][b]);

}

}

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. 函数的调用关系

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.");

printf("\n\n");

printf(" (1)Area C dormitory building---(2)Area A dormitory building---(3)Area B dormitory building\n");

printf(" | | | \n");

printf(" | | | \n");

printf(" | |

| \n");

restaurant\n");

printf(" | | | \n");

printf(" | | | \n");

printf(" | | | \n");

building\n");

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

}

void init()

{

int i, j;

vertex[1].number = 1;

strcpy(vertex[1].name,"Area C dormitory building");

strcpy(vertex[1].introduce, "Area C student rest area");

vertex[2].number = 2;

strcpy(vertex[2].name, "Area A dormitory building");

strcpy(vertex[2].introduce,"Area A student rest area");

vertex[3].number = 3;

strcpy(vertex[3].name, "Area B dormitory building");

strcpy(vertex[3].introduce,"Area B student rest area");

vertex[4].number = 4;

strcpy(vertex[4].name, "Area C restaurant");

strcpy(vertex[4].introduce,"Area C student dining area");

vertex[5].number = 5;

strcpy(vertex[5].name,"Area A restaurant");

strcpy(vertex[5].introduce,"Area A student dining area");

vertex[6].number = 6;

strcpy(vertex[6].name,"Area B restaurant");

strcpy(vertex[6].introduce,"Area B student dining area");

vertex[7].number = 7;

strcpy(vertex[7].name,"library");

strcpy(vertex[7].introduce,"Student borrowing books area");

*vertex[7].number = 8;

strcpy(vertex[7].name,"Area A restaurant");

strcpy(vertex[7].introduce,"Area A student dining area");*

vertex[8].number = 8;

strcpy(vertex[8].name,"No. 1 teaching building");

strcpy(vertex[8].introduce,"Students in class area");

vertex[9].number = 9;

strcpy(vertex[9].name,"No. 13 teaching building");

strcpy(vertex[9].introduce,"Information institute, college building");

for(i = 1; i < MAX_VERTEX_NUM; ++i)

{

for(j = 1; j < MAX_VERTEX_NUM; ++j)

{

dist[i][j] = INFINITY;

相关文档
相关文档 最新文档

侵权投诉  © 2013-2023 www.wendangku.net  站点地图 | 手机版

闽ICP备11023808号-7  本站文档均来自互联网及网友上传分享，本站只负责收集和整理，有任何问题可通过上访投诉通道进行反馈