数据结构课程设计报告.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<i;j++)
Y
Y
N
Y
开始
结束

如果路径存在
输出该路径信息
N

图2.1.2 遍历算法示意图
2.1.4 求最短路径
基于本程序中图的存储是邻接矩阵结构存储的图结构，因而采用适合该存储结构的迪杰斯特拉算法用于解决求最短路径的问题。
迪杰斯特拉提出了一个按路径长度递增的持续产生最短路径的算法，其基本思想是：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对于vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v，…，vk，就将vk加入集合S中，并将路径v，…，vk，vi，与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合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中的元素个数<n）
2.1 在dist[n]中求最小值，其下标为k（则vk为正在生成的终点）；
2.2 输出dist[j]和path[j]；
2.3 修改数组dist和path;
2.4 将顶点vk添加到数组s中；

２．２　存储结构设计
1.创立校园图：
（1）依照河南工程学院的地图，先手工画好14个景点的草图，再用C语言输出抽象化的校园地图。
（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,w∈V且P(v,w),<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 <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include<windows.h>
#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]<t){
t=G->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]<t){
t=d[i]+G->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