数据结构课程设计报告.doc

数据结构课程设计报告

37
2020年4月19日
文档仅供参考

河 南 工 程 学 院

课程设计报告书

姓 名 李永轩
学 号 10913126
学 院 计算机学院
专业班级 计算机科学与技术 1242
专业课程 数据结构
指导老师 李 芳

6 月20日

河南工程学院计算机学院

课程设计报告书

课程设计题目： 校园导航程序设计

课程设计时间： 6月16日～6月20日

课程设计地点： 3号实验楼C405
课程设计单位： 计算机学院

指导教师： 李芳 学院院长： 曲宏山

本组组长
刘皓冉
本组成员
刘皓冉、李永轩
设计题目
校园导航程序设计
本人分工
资料查询、代码编制、代码调试

考核项目
考核内容
得分
平时考核
（30分）出勤情况、态度、效率、协作精神；知识掌握情况、基本操作技能、知识应用能力、获取知识能力

设计思想
（20分）需求分析能力，算法分析设计能力

编码、调试分析
（30分）编制代码能力，调试分析能力

文档资料
（20分）表示能力、文档写作能力和文档的规范性

总评成绩

指导教师评语：

等 级：
评阅人： 职称：
年 月 日

目 录

1、设计目标…………………………………1
2、课题分析与设计………………………....1
1.课题需求分析………………………...1
2.存储结构设计………………………...4
3.算法设计……………………………...5
4.程序流程图…………………………...7
3、程序清单…………………………………7
4、测试……………………………………..19
1．测试数据……………………………19
2.测试结果及分析…………………….19
5总结……………………………………...26
1.收获………………………………….26
2.不足………………………………….27
3.算法改进分析……………………….27
1 设计目标
1. 设计学校平面图，包含十四个景点；
2. 实现景点的查询介绍；
3. 设计程序求出两个景点之间最短的距离。
4. 经过实习，锻炼实际动手能力，增加相关知识，明确数据结构课程在软件开发中的重要性。

2 课题分析与设计
２．１　课题需求分析
为完成整个导航系统的实现，需要对其所有功能清楚明白，选择正确高效的算法解决产生的问题，最后实现程序的正确运行。设计思路如下：
（1）结合本校的实际情况，选出14个景点； 
（2）为选出的14个景点赋上相关信息内容（名称、序号、简介信息、以及路径权值等等）； 
（3）根据14个景点用邻接矩阵存储校园图，并依照景点相关信息进行创立。  
（4）把纸质上的内容，利用C编程语言编写查找景点相关信息的程序。
（5）根据人为赋值的路径权值，计算任意两个景点之间的最短路径。 
（6）用主函数将所有板块合并，生产一个菜单界面呈现在用户面前。 
因此，可将系统分为以下三个核心：图的初始化、图的遍历、求最佳路线。
2.1.1校园景点选取
根据我校情况，选取了以下十四处景点：
编号
名称
编号
名称
编号
名称
1
大西门
2
小西门
3
2号实验楼
4
3号实验楼
5
1-3号教学楼
6
4-6号教学楼
7
B区宿舍
8
图书馆
9
南门
10
大学生活动中心
11
商业活动中心
12
小东门
13
东门
14
A区宿舍

2.1.2图的初始化 
由于邻接矩阵特殊的存储方式，及便于快速的查找两个顶点之间的边上的权值。因此，校园图采用带权的邻接矩阵存储。 
决定了图的存储方式后，以河南工程学院14个景点地图作为蓝本，将校园地图抽象化成顶点与边构成的图形式，如图2.1.1所示，途中数字代表路线的权值。
20
2
1
2． 2
15
10

10
15
4
3

3 4
20
15
15

6
5
5 6
10
100

20
7

20
9
8
9 8 7
15
25
20
20

10
10
14
10

11
10 14 11
25
20
20

13
12

12 13
图2.1.1 校园景点抽象图
2.1.3 图的遍历 
图的遍历是图中最基本的操作。图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。导航图需要把每条路径的信息展示出来，及需要读取每两个顶点间的路径信息。由于采用了带权的邻接矩阵存储结构进行存储，因此需要针对这一存储结构对路线进行遍历操作。其遍历算法如图2.1.2所示。
插入信息内容内容

For循环语句
（i=0；i<顶点数；i++）
N

For循环语句
(j=0;j为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。如图2.1.3所示。
集合S
集合V-S
V

Vk
Vi

图2.1.3 图的遍历算法执行效果示意图
辅助数组dist[n]：元素dist[i]表示当前找到的从源点到终点vi的最短路径的长度。初态为:若从v到vi有弧，则dist[i]为弧上的权值；否则置dist[i]为∞。若当前求得的终点为vk,则根据下式进行迭代：
dist[i]=min{dist[i],dist[k]+arc[k][i]} 1≦i≦n
辅助数组path[n]:元素path[i]是一个串，表示当前所找到的从源点到终点vi的最短路径。初态为：若从v到vi有弧，则path[i]为“vvk”，否则置path[i]为空串。
数组s[n]：存放源点和已经生成的终点（即集合S），初态为只有一个源点v。
算法的伪代码描述是：
1.初始化数组dist、path和s；
2.while（s中的元素个数化的校园地图。
（2）再用C语言定义节点个数N，编写函数name( )为景点赋值各类信息项，函数information( )，输入各个景点的简介。
（3）读入道路的起始点，为邻接矩阵的边赋相应的值。
2．利用函数travgraph来查找景点信息。
3．创立一个校园图creat(Matrix_Graph *G)，然后为相应的边赋上现实意义上的权值。
4．用path( )函数来求任意两景点之间的最短路径。
5. 如果不查询则调用exit( )函数退出。
5．用main函数来输出导游界面。

２．３　算法设计
1 抽象数据类型图的定义 
ADT Mgraph{数据对象V:V是具有相同特性的数据元素的集合，即顶点集。 数据关系：Mgraph=(V,R)。其中，R={|v,w∈V且P(v,w),表示从v到w的一条弧}。 
基本操作： 
}//ADT Mgraph
2 程序中包含的模块
（1）主程序模块
void main()//主函数
{定义主界面的显示；
初始化河南工程学院景点地图creat(&G)；
景点地图的输出打印printf（）；
选择景点而且打印相关信息void travgraph（）；
起点终点的选择和最短路径显示void path()；
程序的退出；}
void clrscr(){ //清屏
system("cls");}
typedef int AdjMatrix[MAX][MAX]; //邻接矩阵
typedef struct{ //点的结构
int vexs[MAX];
AdjMatrix arcs;}Matrix_Graph;
typedef struct{ //景点信息结构
char name[20];
char information[100];
struct edgenode *link;}vexnode;
typedef struct edgenode{ //边和点的结构
int adjvex;
int length;
char info[10];
char info2[100];
struct edgenode *next;}edgenode, *Node;
typedef struct Edge{ //边的结构
int lengh;
int ivex, jvex;
struct Edge *next;}EdgeType;
typedef struct{ //景点代表数字和名称
int num;
char name[20];}vertex;
typedef struct{ //顶点和边最大值
vertex vexs[MAX];
int edges[MAX][MAX];}adjmax;
void Name(int i){ //景点名称的选择和输出
switch(i){…}}
void Information(inti){ //景点介绍
switch(i){…}}
void travgraph(vexnode g[],int n,adjmax adj){ //查找指定景点信息
void creat(Matrix_Graph *G)//图的初始化，权值的录入
void path(Matrix_Graph *G,int s,int e){ //求最短路径

２．４　程序流程图

３　程序清单
//程序名称：校园导航系统
//程序员：刘皓冉、李永轩
//编写时间： 6月
#include
#include
#include
#include
#include
#define N 14 //节点数，即景点数
#define MAX 100 //最大值
#define MAXedg 100
void clrscr(){
system("cls");}
typedef int AdjMatrix[MAX][MAX];
typedef struct{
int vexs[MAX];
AdjMatrix arcs;}Matrix_Graph;
typedef struct{ //定义结构体包括名称信息和link信息
char name[20];
char information[100];
struct edgenode *link;}vexnode;
typedef struct edgenode{
int adjvex;
int length;
char info[10];
char info2[100];
struct edgenode *next;}edgenode, *Node;
typedef struct Edge{
int lengh;
int ivex, jvex;
struct Edge *next;}EdgeType;
typedef struct{
int num;
char name[20];}vertex;
typedef struct{
vertex vexs[MAX];
int edges[MAX][MAX];}adjmax;
void Name(int i){ //景点名称
switch(i){
case 1:printf("1:大西门\n\n");break;
case 2:printf("2:小西门\n\n");break;
case 3:printf("3:2号实验楼\n\n");break;
case 4:printf("4:3号实验楼\n\n");break;
case 5:printf("5:1-3号教学楼\n\n");break;
case 6:printf("6:4-6号教学楼\n\n");break;
case 7:printf("7:B区宿舍\n\n");break;
case 8:printf("8:图书馆\n\n");break;
case 9:printf("9:南门\n\n");break;
case 10:printf("10:学生活动中心\n\n");break;
case 11:printf("11:商业活动中心\n\n");break;
case 12:printf("12:小东门\n\n");break;
case 13:printf("13:东门\n\n");break;
case 14:printf("14:A区宿舍\n\n");break;
default:printf("景点编号输入错误！请输入1-14的数字编号！\n\n"); break;}}
void Information(int i){ //景点介绍
switch(i){
case 1:printf("大西门：学校西门，正对107国道\n\n");break;
case 2:printf("小西门：正对沙窝里商业区\n\n");break;
case 3:printf("2号实验楼：为原老师办公处\n\n");break;
case 4:printf("3号实验楼：为原老师办公、学生会及校广播记者站办公处\n\n");break;
case 5:printf("1-3号教学楼：上课及自习教室\n\n");break;
case 6:printf("4-6号教学楼：上课及自习教室\n\n");break;
case 7:printf("B区宿舍：全部女生及部分男生宿舍\n\n");break;
case 8:printf("图书馆：学校标志性建筑，藏书办公学习处\n\n");break;
case 9:printf("南门：学校南门，南苑位于此处\n\n");break;
case 10:printf("学生活动中心：大礼堂，各个社团办公室等\n\n\n");break;

case 11:printf("商业活动中心：校内超市，移动联通电信营业点，澡堂等\n\n");break;
case 12:printf("小东门：学校小东门，正对行政楼\n\n");break;
case 13:printf("东门：学校东门正对商业处\n\n");break;
case 14:printf("A区宿舍：大部分男生宿舍\n\n");break;
default:printf("景点编号输入错误！请输入1->14的数字编号！\n\n"); break;}}
void travgraph(vexnode g[],int n,adjmax adj){ //查找指定景点信息
int i=1,flag=1,len;
char ch;
printf("\t\t请输入您要查询的地点序号:\n\n");
printf("\t\t1.大西门 2.小西门 3.2号实验楼\n");
printf("\t\t4.3号实验楼 5.1-3号教学楼 6.4-6号教学楼\n");
printf"\t\t7.B区宿舍 8.图书馆 9.南门\n");
printf("\t\t10.学生活动中心 11.商业活动中心 12.小东门\n");
printf("\t\t13.东门 14.A区宿舍\n");
printf("\t\t你的选择是:");
scanf("%d",&len);
getchar();
printf("\t\t此地点的名称是:");
Name(len);
printf("\t\t此地点的介绍是:");
Information(len);
do{
printf("\t\t是否继续? Y/N \n");
printf("\t\t你的选择是:");
scanf("%c",&ch);
getchar();
if(ch=='Y'||ch=='y'){
clrscr();
flag=1;
i=1;
printf("\t\t请再次输入您要查询的地点序号:\n\n");
printf("\t\t1.大西门 2.小西门 3.2号实验楼\n");
printf("\t\t4.3号实验楼 5.1-3号教学楼 6.4-6号教学楼\n");
printf("\t\t7.B区宿舍 8.图书馆 9.南门\n");
printf("\t\t10.学生活动中心 11.商业活动中心 12.小东门\n");
printf("\t\t13.东门 14.A区宿舍\n");
printf("\t\t你的选择是:");
scanf("%d",&len);
getchar();
printf("\t\t此地点的名称是:");
Name(len);
printf("\t\t此地点的介绍是:");
Information(len);
continue;}
else{
flag = 0;
printf("\t\t请再次按回车键返回至主菜单");
}
break;}
while(1);}
void creat(Matrix_Graph *G) //创立校园图，给相应的边赋权值
{
int i,j;
for(i=1;i<=N;i++)
G->vexs[i]=i;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
G->arcs[i][j]=0;
G->arcs[1][2]=20;G->arcs[1][4]=10;G->arcs[1][3]=10;G->arcs[1][8]=15;
G->arcs[2][4]=15;G->arcs[2][7]=10;
G->arcs[3][1]=10;G->arcs[3][9]=20;G->arcs[3][5]=15;
G->arcs[4][1]=10;G->arcs[4][6]=15;G->arcs[4][2]=15;
G->arcs[5][3]=15;G->arcs[5][8]=10;
G->arcs[6][4]=15;G->arcs[6][8]=10;
G->arcs[7][2]=10;G->arcs[7][11]=20;G->arcs[7][8]=20;G->arcs[7][14]=15;
G->arcs[8][5]=10;G->arcs[8][6]=10;G->arcs[8][7]=20;G->arcs[8][9]=20;G->arcs[8][10]=20;G->arcs[8][1]=15;
G->arcs[9][3]=20;G->arcs[9][8]=20;G->arcs[9][10]=25;
G->arcs[10][8]=20;G->arcs[10][9]=25;G->arcs[10][14]=10;G->arcs[10][12]=20;G->arcs[10][13]=25;
G->arcs[11][7]=20;G->arcs[11][14]=10;G->arcs[11][13]=20;
G->arcs[12][10]=20;
G->arcs[13][10]=25;G->arcs[13][11]=20;G->arcs[13][14]=5;
G->arcs[14][10]=10;G->arcs[14][11]=10;G->arcs[14][7]=15;G->arcs[14][13]=5;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
if(G->arcs[i][j]==0)
G->arcs[i][j]=MAX;}
void path(Matrix_Graph *G,int s,int e){ //求任意两景点之间的最短路径
int i,j,u,c=1,t,v;
int r[N+1][N+1];
int T[N],flag[N],d[N];
for(i=0;i<=N;i++)
for(j=0;j<=N;j++)
r[i][j]=0;
for(i=1;i<=N;i++){
T[i]=-1;flag[i]=1;d[i]=MAX;}
flag[s]=0;
while(c<=N){
t=MAX;
for(i=1;i<=N;i++)
if(flag[i]&&G->arcs[s][i]arcs[s][i];v=i;r[v][1]=v;}
for(i=1;i<=c;i++)
for(j=1;j<=N;j++)
if(flag[j]&&d[i]+G->arcs[T[i]][j]arcs[T[i]][j];v=j;
if(r[v][0]!=-1){
u=1;
while(r[T[i]][u]!=0){
r[v][u]=r[T[i]][u];u++;}}
r[v][u]=v;}
r[v][0]=-1;T[c]=v;flag[v]=0;d[c]=t;c++;}
printf("\n最短路径是以下这条:\n(%d)",s);j=1;
while(r[e][j]!=0){
printf("-->(%d)",r[e][j]);j++;}printf("\n\n");
}
void main() //主函数输出导游界面
{system("Color B1");
int i,j;
Matrix_Graph G;creat(&G);int n = 0;
vexnode g[MAX];
EdgeType e[MAXedg];
adjmax adj;
char choice='x';
while(1){
clrscr();
printf("\n\t\t\t★欢迎使用河南工程学院校园导航系统★"); //主界面
printf("\n\n\n\n\t\t\t ***校-园-导-航***");
printf("\n\t\t ┌─────────────────┐\n");
printf("\t\t 自 │ 1. 河南工程学院地图: │ 博\n");
printf"\t\t │ 2. 校园地点简介: │\n");
printf("\t\t 强 │ 3. 查找两点间最短路径: │ 学 \n");
printf("\t\t │ 0. 退出 │ \n");
printf("\t\t 不 ├─────────────────┤ 精\n");
printf("\t\t │ 制作人：刘皓冉、李永轩 │\n");
printf("\t\t 息 ├─────────────────┤ 艺\n");
printf("\t\t │ 校址：新郑龙湖中山北路1号 │\n");
printf("\t\t └─────────────────┘\n\n");
printf("\t\t 请输入你的选择(0-3): ");
choice = getchar();
switch(choice){
case '1':clrscr(); //校园地图
printf("\t\t **河南工程学院地图******* \n");
printf(" ┌─────────────────────────────────────┐\n");
printf(" │ #1.大西门#←────────→#2.小西门# │\n");
printf(" │ ↗ ↑ ↖ ↗ ↑ │\n")
printf(" │ ╱ │ ╲ ___╱ │ │\n");
printf(" │ ↙ │ ↘ ↙ │ │\n");
printf(" │ #3.2号实验楼#←──┼─→#4.3号实验楼# │ │\n");
printf(" │ ↗ ↑ │ ↑ │ │\n");
printf(" │ ╱ │ │ │ │ │\n");
printf(" │ │ ↓ │ ↓ ↓ │\n")
printf(" │ │#5.1-3号教学楼#←──┼─→#6.4-6号教学楼#←→#7.B区宿舍# │\n");
printf(" │ │ ↖ │ ↗ ↗ ↗ ↑ │\n");
printf(" │ │ ╲ │ ╱ ____________╱ ╱ │ │\n");
printf(" │ ↓ ↘ ↓ ↙ ↙ │ │ │\n");
printf(" │#9.南门#←───────→#8.图书馆# │ │ │\n");
printf(" │ ↖________ ↑ ╱ │ │\n");
printf(" │ ↘ ↓ ↙ ↓ │\n");
printf(" │ #10.学生活动中心#←─→#14.A区宿舍#←─→#11.商业活动中心# │\n");
printf(" │ ↗ ↖_______ ↑ __________↗ │\n");
printf(" │ ↙ ↘ ↓ ↙ │\n");
printf(" │ #12.小东门# #13.东门# │\n");
printf(" └─────────────────────────────────────┘\n");
printf("\t\t输入回车键返回菜单");getchar();getchar();break;
case '2':clrs