数据结构课程设计-校园导航系统

安徽省巢湖学院计算机与信息工程学院

课程设计报告

课程名称 课题名称 校园导航系统 专 业 计算机科学与技术 班 级 学 号 10012097 姓 名 吴宗林 联系方式 [1**********] 指导教师 江家宝 20 11 年 12 月 29 日

目 录

1、数据结构课程设计任务书 . ............................................................................................... 1

1.1、题目 . ...................................................................................................................... 1

1.2、要求 . ...................................................................................................................... 1

2、详细设计 . ........................................................................................................................ 1

2.1、程序中所采用的数据结构及存储结构的说明 . ......................................................... 1

2.2、算法的设计思想 . .................................................................................................... 2

3、调试与测试： . ................................................................................................................. 2

3.1、调试方法与步骤： ................................................................................................. 2

3.2、测试结果的分析与讨论： ...................................................................................... 2

4、时间复杂度的分析： ....................................................................................................... 4

5、源程序清单和执行结果 ................................................................................................... 5

6、C 程序设计总结 .............................................................................................................. 9

7、致谢 .............................................................................................................................. 10

8、参考文献 . ...................................................................................................................... 10

1、数据结构课程设计任务书

1.1、题目

校园导航问题

1.2、要求

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

1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。

2）为来访客人提供图中任意景点相关信息的查询。

3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。

2、详细设计

模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等；

2.1、程序中所采用的数据结构及存储结构的说明

（1）图。采用邻接矩阵存储，其中图所用到的结构体为：

typedef struct

{

SeqList vertices; //表示图中的顶点

int Edge[MaxVertices][MaxVertices]; //表示图中的边

int numOfEdge; //表示图中边的数目

}AdjMGraph;

（2）景点。用顺序表存储。所用到的结构体为：

typedef struct

{

char name[20]; //顶点名称

int code; //顶点代号

char introduction[50]; //顶点信息简介

}DataType;

（3）景点之间的连接描述，所用到的结构体为：

typedef struct

{

int row;

int col;

int weight;

}RowColWeight;

用图来存放所提供的所有景点，然后用线性表来存放每一个景点的信息，其

中包括景点的名称，代号，信息简介，以及其它的一些信息。这样就将对景点的

操作，变成对图中各顶点的操作 。

2.2、算法的设计思想

根据题目分析，对于信息查询与修改功能，设计如下：

1，输入景点名称

2，从线性表头扫描到表尾，

if(找到该景点) 输出景点结构体信息

else 输出提示信息找不到该顶点

实现查找最短路径，设计如下：

1， 景点名称

2，根据输入的信息找到它们所在的线性表中的位置

3，调用Floyd 算法找出最短路径

4，输出信息

3、调试与测试：

3.1调试过程中遇到的问题与解决方案：

关于最短路径的输出问题。在进行最短路径输出时，我刚开始时只能正序输出，具体的描述为：比如，我要查寻从东区到东湖的最短路径，那么它能正确输出结果，他的形式为：东区 ——>主楼 ——>西体育馆 ——>隧道 ——>北大门 ——>东湖。但是，当我逆向输出时，得到的结果却有点问题，经过分析调试后，找到了错误的所在。在找最短路径的时候我用的是Floyd 算法，在这个算法中有三重循环，形式均为：for(k=0;k

另外，在做这个题时也还出现过一些其他的小问题，不过都比较容易解决，这里我就不再列出了……

3.2、测试结果的分析与讨论：

（测试要写出测试用例及每个用例结果的的截图）

4、时间复杂度的分析：

1，相关信息的查询。在这个操作中允许使用者输入一个景点名称，然后再根据景点名称来或取其相关的信息，这个操作要扫描线性表，其时间复杂度为o(n)，空间复杂度为o(n)；

2，最短路径查询。实现这个功能用到了Floyd 算法，他用到了一个三重的for()循环，故其时间复杂度为o(n^3)，空间复杂度为o(1)；

5、源程序清单和执行结果

(清单中应有足够的注释)

school.cpp //程序源文件

AdjMGraph.h //图的相关操作头文件

AdjMGraphCreat.h //创建图的头文件

SeqList.h //线性表操作头文件

Floyd.h //Floyd算法头文件

Operation.h //自己所定义的一些操作的头文件

Inquiry.h //查询信息包含的头文件

// 详细school.cpp 程序源文件

#include

#include

#include

#define MaxSize 20 //线性表的最大数组空间

#define MaxVertices 20 //景点个数所允许的最大值

#define MaxWeight 1000 //无穷边权值

#include "Floyd.h"

#include "AdjMGraphCreat.h"

#include "Inquiry.h"

AdjMGraph G;

#include "Operation.h"

void main()

{

//初始景点信息

DataType a[]={{“学生第二食堂",10," 学生的主要就餐点"},{"男生宿舍",11," 一共有

八栋"},{"操场",12," 最新的塑胶跑道和人工草坪"} ,{"物理楼",13," 拥有各种实

验器材"},{"博学楼",14," 学生上课集中地"},{"草地",15," 休闲娱乐的好地方

"},{"老教",16," 学校最早的教学楼"},{"女生宿舍",17," 一共七栋"},{"小门",18,"

可以通往半汤镇"},{"图书馆",19," 藏书50万册"}};

//邻接矩阵的表示

RowColWeightrcw[]={{0,1,20},{0,2,30},{0,3,35},{1,0,20},{1,3,20},{2,0,30},{2,3,15},{2,4,30},{3,0,35},{3,1,20},{3,2,15},{3,4,30},{4,2,30},{4,3,30},{4,5,10},{5,4,10},{5,6,35}

,{5,8,8},{6,5,35},{6,7,20},{6,8,25},{6,9,5},{7,6,20},{7,8,10},{8,5,8},{8,6,25},{8,7,10},{9,6,5}; int n=10,e=28; //景点数与边数

Creat(&G,a,rcw,n,e); //构造图

menu();

}

// 详细Floyd.h 头文件

void Floyd(int cost[][MaxVertices],int n,int weight[][MaxVertices],int path[][MaxVertices]) {

//初始化

int i,j,k;

for(i=0;i

{

for(j=0;j

{

weight[i][j]=cost[i][j];

path[i][j]=-1;

}

}

//n次递推

for(k=0;k

{

for(i=0;i

{

for(j=0;j

{

if(weight[i][j]>weight[i][k]+weight[k][j])

{

weight[i][j]=weight[i][k]+weight[k][j];

path[i][j]=k;

}

}

}

}

}

//详细Inquiry.h 头文件

void Information(AdjMGraph G, char scenery[])

{

int i;

for(i=0;i

{

if(strcmp(G.vertices.list[i].name,scenery)==0)

{

printf("您输入的景点的名称是： %s\n",G.vertices.list[i].name);

printf("您输入的景点的代码为： %d\n",G.vertices.list[i].code);

printf("您输入的景点的相关信息有： %s\n\n",G.vertices.list[i].introduction);

break;

}

}

if(i==G.vertices.size)

{

printf("您所查询的景点不在我们所提供的范围内！\n\n");

}

}

void Path(AdjMGraph G,char sceneryname[], char sceneryname1[])

{

int i,j,k,n,m,count=0;

n=G.vertices.size;

int weight[MaxVertices][MaxVertices],path[MaxVertices][MaxVertices]; int value[MaxVertices];

for(i=0;i

{

if(strcmp(G.vertices.list[i].name,sceneryname)==0)

{

j=i;

}

if(strcmp(G.vertices.list[i].name,sceneryname1)==0)

{

k=i;

}

}

Floyd(G.Edge,n,weight,path);

m=path[j][k];

printf("最短路径为： %d\n",weight[j][k]);

if(m==-1)

{

printf("从 %s 点到 %s 景点的最短路径为：\n",sceneryname,sceneryname1); printf("%s ——>%s\n",sceneryname,sceneryname1);

}

else

{

while(m!=-1)

{

value[count]=m;

if(j

else j=m;

m=path[j][k];

count++;

}

printf("从 %s 点到 %s 景点的最短路径为：\n",sceneryname,sceneryname1); printf("%s——>",sceneryname);

if(j

{

for(i=count-1;i>=0;i--)

{

printf("%s——>",G.vertices.list[value[i]].name);

}

printf("%s\n",sceneryname1);

}

else

{

for(i=0;i

{

printf("%s——>",G.vertices.list[value[i]].name);

}

printf("%s\n",sceneryname1);

}

}

}

//详细Operation.h 头文件

void menu();

//查询景点信息的函数

void Information1()

{

char sceneryname[20];

printf("请输入您所想要查询的景点的名称： ");

scanf("%s",sceneryname);

Information(G ,sceneryname);

menu();

}

//查询最短路径的函数

void Path1()

{

char sceneryname[20],sceneryname1[20];

printf("请输入你要查询的两景点的名称： ");

scanf("%s%s",sceneryname,sceneryname1);

Path(G,sceneryname,sceneryname1);

menu();

printf("\n");

}

//菜单

void menu()

{

int n;

puts("\t\t****************菜单**********************\n");

puts("\t\t\t1,相关信息查询");

puts("\t\t\t2,最短路径查询");

puts("\t\t*******************************************\n");

printf("请选择您想进行的操作： ");

scanf("%d",&n);

switch(n)

{

case 1:

{

Information1();

break;

}

case 2:

{

Path1();

break;

}

}

}

另外，还有AdjMGraphCreat.h ，AdjMGraph.h 和SeqList.h 由于他们在书上已经出现过了，这里我就不再把他们的源程序清单打印出来了 。

6、C 程序设计总结

本程序在刚开始调试时有许多错误，但在我的努力及同学的帮助下都被一一克服，现在在操作本程序时可根据提示进行相关操作，能正确输出结果。在刚开始的几次调试中曾经出现过不能运行、不能产生十以内随机数字、不能随机出现加减、不会正确输出结果、不能进行循环练习等等问题。经过我的努力及同学的帮助，这些问题得到克服，并且使程序的功能也得到了一定的完善。现在它能对出错的题目发出报警声，并且给出正确答案。最后还能分别输出对错的题数及所得分数。

在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写好课本知识的

同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。除此之外，我还得到了一些有用的教训：写程序时必须要细心，不能输错一个字符标点，就连全角半角也得注意。在修改时要有耐心，编译出错后必须逐个错误去改正，绝不能心急浮躁，否则修改之后还会有新的错误。

7、致谢

能够完成这次课程设计必须感谢C++语言课程老师徐荣泉、袁洪军同学（他帮我修改了几处重要错误，同时启发我完善了该程序的功能）。

8、参考文献

1. 《数据结构（C 语言版）》清华大学出版社，严蔚敏 吴伟民 编著

2. 《C++语言程序设计（第四版）》清华大学出版社，郑莉 何江舟 编著

3.http:\\www.baidu.com