XXXX大学计算机学院
课 程 设 计
(数据结构)
二○##年一月二十日
课程设计任务书及成绩评定
Ⅰ、题目的目的和要求:
1、设计目的
巩固和加深对数据结构的理解,通过上机实验、调试程序,加深对课本知识的理解,最终使学生能够熟练应用数据结构的知识写程序。
(1)通过本课程的学习,能熟练掌握几种基本数据结构的基本操作。
(2)能针对给定题目,选择相应的数据结构,分析并设计算法,进而给出问题的正确求解过程并编写代码实现。
2、设计题目要求:
问题描述: 用无向网表示你所在学校的校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息,图中的边表示景点间的道路,存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。
要求:
(1) 查询各景点的相关信息;
(2) 查询图中任意两个景点间的最短路径。
(3) 查询图中任意两个景点间的所有路径。
(4) 增加、删除、更新有关景点和道路的信息。
Ⅱ、设计进度及完成情况
Ⅲ、主要参考文献及资料
[1] 严蔚敏 数据结构(C语言版)清华大学出版社 1999
[2] 严蔚敏 数据结构题集(C语言版)清华大学出版社 1999
[3] 谭浩强 C语言程序设计 清华大学出版社
[4] 与所用编程环境相配套的C语言或C++相关的资料
Ⅳ、成绩评定:
设计成绩: (教师填写)
指导老师: (签字)
二○一一 年 一 月 二 十一 日
目 录
第一章 概述……………………………………………………………1
第二章 系统分析………………………………………………………2
第三章 概要设计………………………………………………………3
第四章 详细设计………………………………………………………9
第五章 运行与测试……………………………………………………17
第六章 总结与心得……………………………………………………20
参考文献………………………………………………………………21
第一章 概述
课程设计是实践性教学中的一个重要环节,它以某一课程为基础,可以涉及和课程相关的各个方面,是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用,理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课,是计算机理论和应用的核心基础课程。
数据结构课程设计,要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面,加深对课程基本内容的理解。同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是校园导游咨询。当到一个陌生的地方去旅游时,人们常常需要一个导游为自己在游玩过程中提供服务,比如介绍参观景点的历史背景等相关信息,推荐到下一个景点的最佳路线,以及解答旅游者提出的关于旅游景点的相关问询,等等。对于刚刚来到大学校园的新生,对校园环境不熟悉的情况也是如此,如果能够提供一个程序让新生或来访的客人自主的与机器“对话”来获得相关信息,将会节省人力和时间,而且所提供的信息也能够保证尽可能的准确、详尽。
本实验要求设计一个校园导游程序,为来访的客人提供各种信息查询服务。
第二章 系统分析
1.本校园景点平面图设计的主要目的是为用户提供以下主要信息:第一,为用户展示一个比较全面的校园全景图,让游客做到对所要浏览的校园心中有数,尽可能做到一目了然;第二,当游客置身于景点中时,可以为用户提供平面中某景点到其余各景点的浏览路线及其各自最短路径,以便使用户更好的完成自己的浏览计划,从而节省时间放松身心;第三,为用户提供平面图中任意场所的问路查询,即查询任意两个景点之间的一条最短的简单路径,旨在为用户的旅游大大提高效率;第四,为用户提供平面图中任意场所的相关信息的查询,简单介绍平面图中各景点的特点,概况和相关职能,让用户有选择的进行浏览;第五,为保证景点平面图的完整和准确,本设计提供了用户更新完善平面图的功能;最后本设计本着完整健壮的追求,设计了退出系统环节,让用户用的更舒心。
2.校园平面图设计的基本功能包括:为用户提供当前所在景点到图中任意景点的一条最短路径,及其任意两个场所之间的最短简单路径等等。由于这两个基本功能是基于图结构的实际的景点网络,所以要采用图的邻接矩阵存储结构,又因为校园道路往往是双向通行的,因此该平面图可被看做带各种信息的无向网。故重点是完成计算并记录从某景点到各个场所的最短路径,以及接收用户输入的场所名称,并在计算机的最短路径集合中找到相关项的信息反馈给用户。
3.既为校园景点平面图设计,就需要一个模块来为用户提供一个较全面的校园全景图,以及图中各景点信息的查询服务。那么MGraph InitGraph(void);void Menu();void Browser(MGraph *G);这三个函数实现了呈现校园全景图的功能。而void Search(MGraph *G);int LocateVex(MGraph *G,char* v);这两个函数主要实现的是定位图中某景点并完成该景点的信息查询功能。
4.演示程序是以用户于计算机的对话方式执行,这需要一个模块来完成使用者与计算机语言是转化。
5.程序执行时的命令:本程序为了使用时的方便,采用菜单式的方式来完成程序的演示,几乎不用输入什么特殊的命令,只需按提示输入选者即可。(要注意输入时格式,否者可能会引起一些错误)
6.测试数据。
第三章 概要设计
1、数据结构的设计
由于各个场所通过校园中的道路相连,各个场所和连接它们的道路构成了整个校园的地理环境,所以使用图这种数据结构对它们进行描述。以图中顶点表示校园内的各个场所。应包含场所名称、代号、简介等信息;以边表示连接各个场所的道路,应包含路径的代号、路径长度等信息。一般情况下,校园的道路是双向通行的。因此校园平面图可以看做一个无向网。图的顶点和边均使用结构体类型,整个图的数据结构采用了带权的邻接矩阵的存储方式。
2、算法的设计
本校园景点平面图设计从总体上主要划分了五个模块。
第一模块以表格形式显示校园平面图,平面图中应能够准确地标示场所名称,及其对应各个场所的简介信息;首先用二维数组初始化一个图形G,然后调用Browser(MGraph *G)函数调用并显示这个平面图,主要有以下两个算法
MGraph InitGraph(void)
{
MGraph G;
for(i=0;i<G.vexnum;i++)
{
G.vexs[i].num=i;
strcpy(G.vexs[0].name,"第三食堂");
strcpy(G.vexs[0].introduction,"新建标准化食堂");
strcpy(G.vexs[1].name,"大学生事务中心");
strcpy(G.vexs[1].introduction,"大学生事务中心于20##年6月30日成立,挂靠学生工作处");
strcpy(G.vexs[2].name,"地下超市");
strcpy(G.vexs[2].introduction,"学校两大超市之一,日常生活用品,电子产品等应有尽有");
strcpy(G.vexs[3].name,"信息楼");
strcpy(G.vexs[3].introduction,"多媒体教学场所,设施先进,环境良好");
strcpy(G.vexs[4].name,"图书馆");
strcpy(G.vexs[4].introduction,"藏书464.8万册,设施完备,1楼东区为电子阅览室,环境幽雅");
strcpy(G.vexs[5].name,"体育场");
strcpy(G.vexs[5].introduction,"现代化塑胶跑道,人造草坪,适宜锻炼身体的场所");
strcpy(G.vexs[6].name,"鸿远楼");
strcpy(G.vexs[6].introduction,"正对学校南门的,高层领导办公之地,平时学生的快递也送达那");
strcpy(G.vexs[7].name,"国防教育学院");
strcpy(G.vexs[7].introduction,"学生半军事化管理,是学校的一道亮丽风景线");
strcpy(G.vexs[8].name,"第四餐厅");
strcpy(G.vexs[8].introduction,"紧邻我们的第二水房,干净卫生,饭菜可口");
strcpy(G.vexs[9].name,"校医院");
strcpy(G.vexs[9].introduction,"设施不是很齐全,只能看小病,服务态度挺好");
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=INFINITY;
G.arcs[0][1].adj=50;
G.arcs[0][2].adj=50;
G.arcs[0][6].adj=500;
G.arcs[1][7].adj=200;
G.arcs[2][3].adj=600;
G.arcs[3][4].adj=100;
G.arcs[3][6].adj=60;
G.arcs[4][5].adj=50;
G.arcs[4][8].adj=700;
G.arcs[5][8].adj=800;
G.arcs[6][7].adj=650;
G.arcs[6][9].adj=600;
G.arcs[7][8].adj=100;
G.arcs[8][9].adj=80;
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
G.arcs[j][i].adj=G.arcs[i][j].adj;
return G;
}
} //InitGraph end
void Browser(MGraph *G)
{
Printf()
}
第二个模块实现了任意场所的信息查询功能,要求能够接受用户所输入的场所名称,并将场所的简介信息反馈给用户;本设计用Search函数实现本部分功能,算法如下;void Search(MGraph *G)
{
Printf()
}
第三个模块功能为求单源点到其他各点的最短路径,计算并记录从某个景点到其他各个场所的各自所有最短路径;主要有迪杰斯特拉算法实现如下:
void dijstra( int cost[][N], int v )
{ int dist[N],i,j,w
for (i=0; i<N; i++)
dist[i]=cost[v][i]; //初始化
dist[v]=-dist[v];
for( i=0; i<N; i++)
{ j=mincost(dist); //找非0、非负且最小的dist[j]
if( j==0);break;
dist[j]=-dist[j]; // vj并入U中
for(k=0;k<N;k++) // 调整dist[k]
if(dist[j]>0) // vk是尚未到达的终点
if(-dist[j]+cost[j][k]<dist[k])
dist[k]=-dist[j]+cost[j][k]; //途经vj到达vk的距离更短
}
for ( i=0; i<N; i++)
if(dist[j]<0)
printf(“%d, %d: %d\n”,v,i,-dist[i]);
}
int mincost( int dist[ ])
// 在V-U 集合中找顶点j,dist[j]是dist[ ]中的最小值
{ int i, min, j;
min=MAX;j=0;
for(i=0;i<N;i++)
if(dist[i]>=0&& dist[i]<min)
{min=dist[i];j=i; }
return(j);
}
第四个模块实现了求任意场所的问路查询功能,接收用户所输入的场所编号,并在计算机的最短路径集合中找到相关项的信息反馈给用户,此模块旨在求任意两个场所之间的最短路径;本模块主要用了弗洛伊德算法实现,算法如下:
void Floyd(MGraph *G)
{
for(v=0;v<G->vexnum;v++)
for(w=0;w<G->vexnum;w++)
{
D[v][w]=G->arcs[v][w].adj;
for(u=0;u<G->vexnum;u++)
p[v][w][u]=0;
if(D[v][w]<INFINITY)
{
p[v][w][v]=1;p[v][w][w]=1;
}
}
for(u=0;u<G->vexnum;u++)
for(v=0;v<G->vexnum;v++)
for(w=0;w<G->vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w])
{
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G->vexnum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}
第五个模块实现了图形的插入删除更新功能,保证景点平面图及时更新准确为用户提供景点及路径信息;此部分有两个算法如下:
MGraph * CreatUDN(MGraph *G)//初始化图形,接受用户输入
{
scanf("%d%d",&G->vexnum,&G->arcnum);
printf("请输入景点的编号:、名称、简介:\n");
for(i=0;i<G->vexnum;i++)
{
printf("景点编号:");
scanf("%d",&G->vexs->num);
printf("景点名称:");
scanf("%s",G->vexs[i].name);
printf("景点简介:");
scanf("%s",G->vexs->introduction);
}
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
printf("请输入路径长度:\n");
for(k=0;k<G->arcnum;k++)
{
printf("第%d条边:\n",k+1);
printf("景点对(x,y):");
scanf("%s",v1);
scanf("%s",v2);
printf("路径长度:");
scanf("%d",&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
if(i>=0&&j>=0)
{
G->arcs[i][j].adj=w;
G->arcs[j][i]=G->arcs[i][j];
}
}
return G;
}
int LocateVex(MGraph *G,char* v)
{
for(i=0;i<G->vexnum;i++)
if(strcmp(v,G->vexs[i].name)==0)
{c=i;break;}
return c;
}
3、抽象数据类型的设计
本设计利用了图数据结构及图中几个重要的算法。所以抽象数据类型如下:
ADT graph{
数据对象V:具有相同特性的数据元素的集合
数据关系R:R={VR}
VR={<v,w>|v,w ∈V,<v,w>表示从v到w的弧}
基本操作P:
结构的建立:
CreatGraph(&G, V, VR): // 按定义(V, VR) 构造图
对顶点的访问操作:
LocateVex(G, u); // 若G中存在顶点u,则返回该顶点在图中“位置” ;否则返回其它信息。
GetVex(G, v); // 返回 v 的值。
PutVex(&G, v, value); // 对 v 赋值value。
FirstAdjVex(G, v); // 返回 v 的“第一个邻接点” 。若该顶点在 G 中没有邻接点,则返回“空”。
NextAdjVex(G, v, w); // 返回 v 的(相对于 w 的) “下一个邻接点”。若 w 是 v 的最后一个邻接点,则/返回“空”。
InsertVex(&G,v);//在图G中增添新顶点v。
DeleteVex(&G,v);//删除G中顶点v及其相关的弧。
InsertArc(&G,v,w);//在G中增添弧<v,w>,若G是无向的则还增添对称弧<w,v>。
DeletArc(&G,v,w);//在G中删除弧<v,w>,若G是无向的则还删除对称弧<w,v>。
}
第四章 详细设计
1、设计抽象数据类型对应的类定义。
typedef struct ArcCell { // 弧的定义
VRType adj; // VRType是顶点关系类型。对无权图,用1或0表示相邻否; // 对带权图,则为权值类型。
InfoType *info; // 该弧相关信息的指针
} ArcCell,AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];
typedef struct { // 图的定义
VertexType vexs[MAX_VERTEX_NUM]; //顶点信息
AdjMatrix arcs; // 弧的信息
int vexnum, arcnum; // 顶点数,弧数
GraphKind kind; // 图的种类标志
} MGraph;
2、设计每个成员函数;在本设计这些函数中有一个公共成员函数:
void Menu()
{
printf("\n 山东理工大学导游图\n");
printf(" ┏━━━━━━━━━━━━━━━━━━━━┓\n");
printf(" ┃ 1.浏览校园全景 ┃\n");
printf(" ┃ 2.查看所有游览路线 ┃\n");
printf(" ┃ 3.选择出发点和目的地 ┃\n");
printf(" ┃ 4.查看所选景点信息 ┃\n");
printf(" | 5.用户完善校园景点平面图 |\n");
printf(" ┃ 6.退出系统 ┃\n");
printf(" ┗━━━━━━━━━━━━━━━━━━━━┛\n");
printf("Option-:");
}
另外各模块有自己的成员函数如下
第一模块成员函数有两个如下所示:(1)初始化平面图
MGraph InitGraph(void)
{
MGraph G;
int i,j;
G.vexnum=10;
G.arcnum=14;
for(i=0;i<G.vexnum;i++)
{
G.vexs[i].num=i;
strcpy(G.vexs[0].name,"理工大南门");
strcpy(G.vexs[0].introduction,"学校正大门很气派");
strcpy(G.vexs[1].name,"鸿远楼");
strcpy(G.vexs[1].introduction,"正对学校南门的,高层领导办公之地,平时学生的快递也送达那");
strcpy(G.vexs[2].name,"信息楼");
strcpy(G.vexs[2].introduction,"多媒体教学场所,设施先进,环境良好");
strcpy(G.vexs[3].name,"图书馆");
strcpy(G.vexs[3].introduction,"藏书464.8万册,设施完备,1楼东区为电子阅览室,环境幽雅");
strcpy(G.vexs[4].name,"体育场");
strcpy(G.vexs[4].introduction,"现代化塑胶跑道,人造草坪,适宜锻炼身体的场所");
strcpy(G.vexs[5].name,"第三食堂");
strcpy(G.vexs[5].introduction,"紧邻我们的第一水房,干净卫生,饭菜可口");
strcpy(G.vexs[6].name,"大学生事务中心");
strcpy(G.vexs[6].introduction,"大学生事务中心于20##年6月30日成立,挂靠学生工作处");
strcpy(G.vexs[7].name,"地下超市");
strcpy(G.vexs[7].introduction,"学校两大超市之一,日常生活用品,电子产品等应有尽有");
strcpy(G.vexs[8].name,"国防教育学院");
strcpy(G.vexs[8].introduction,"学生半军事化管理,是学校的一道亮丽风景线");
strcpy(G.vexs[9].name,"校医院");
strcpy(G.vexs[9].introduction,"设施不是很齐全,只能看小病,服务态度挺好");
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=INFINITY;
G.arcs[0][1].adj=50;
G.arcs[0][2].adj=200;
G.arcs[0][6].adj=600;
G.arcs[1][7].adj=580;
G.arcs[2][3].adj=100;
G.arcs[3][4].adj=50;
G.arcs[3][6].adj=400;
G.arcs[4][5].adj=450;
G.arcs[4][8].adj=700;
G.arcs[5][8].adj=800;
G.arcs[6][7].adj=50;
G.arcs[6][9].adj=200;
G.arcs[7][8].adj=210;
G.arcs[8][9].adj=80;
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
G.arcs[j][i].adj=G.arcs[i][j].adj;
return G;
}
} //InitGraph end
(2)浏览函数展示校园平面全景图
void Browser(MGraph *G)
{
int v;
printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━┓\n");
printf("┃编号┃景点名称 ┃简介 ┃\n");
for(v=0;v<G->vexnum;v++)
printf("┃%-4d┃%-16s┃%-56s┃\n",G->vexs[v].num,G->vexs[v].name,G->vexs[v].introduction);
printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━┛\n");
}
第二个模块有自己的一个成员函数如下
void Search(MGraph *G)
{
int k,flag=1;
while(flag)
{
printf("请输入要查询的景点编号:");
scanf("%d",&k);
if(k<0||k>G->vexnum)
{
printf("景点编号不存在!请重新输入景点编号:");
scanf("%d",&k);
}
if(k>=0&&k<G->vexnum)
flag=0;
}
printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━┓\n");
printf("┃编号┃景点名称 ┃简介 ┃\n");
printf("┃%-4d┃%-16s┃%-56s┃\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);
printf("┗━━┻━━━━━━━━━━━━━━━━━━━━━┛\n");
}//Search end
第三个模块是用实现单元颠倒其他各点的最短路径,成员函数为:
void ShortestPath_DIJ(MGraph * G)
{
int v,w,i,min,t=0,x,flag=1,v0;
int final[20], D[20], p[20][20];
while(flag)
{
printf("请输入一个起始景点编号:");
scanf("%d",&v0);
if(v0<0||v0>G->vexnum)
{
printf("景点编号不存在!请重新输入景点编号:");
scanf("%d",&v0);
}
if(v0>=0&&v0<G->vexnum)
flag=0;
}
for(v=0;v<G->vexnum;v++)
{
final[v]=0;
D[v]=G->arcs[v0][v].adj;
for(w=0;w<G->vexnum;w++)
p[v][w]=0;
if(D[v]<INFINITY)
{
p[v][v0]=1;p[v][v]=1;
}
}
D[v0]=0;final[v0]=1;
for(i=1;i<G->vexnum;i++)
{
min=INFINITY;
for(w=0;w<G->vexnum;w++)
if(!final[w])
if(D[w]<min){v=w;min=D[w];}
final[v]=1;
for(w=0;w<G->vexnum;w++)
if(!final[w]&&(min+G->arcs[v][w].adj<D[w]))
{
D[w]=min+G->arcs[v][w].adj;
for(x=0;x<G->vexnum;x++)
p[w][x]=p[v][x];
p[w][w]=1;
}
}
for(v=0;v<G->vexnum;v++)
{
if(v0!=v)
printf("%s",G->vexs[v0].name);
for(w=0;w<G->vexnum;w++)
{
if(p[v][w]&&w!=v0)
printf("-->%s",G->vexs[w].name);
t++;
}
if(t>G->vexnum-1&&v0!=v)printf(" 总路线长%dm\n\n",D[v]);
}
}//ShortestPath_DIJ end
第四个模块实现了图中任意两个场所之间的最短路径,成员函数为:
void Floyd(MGraph *G)
{
int v,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];
for(v=0;v<G->vexnum;v++)
for(w=0;w<G->vexnum;w++)
{
D[v][w]=G->arcs[v][w].adj;
for(u=0;u<G->vexnum;u++)
p[v][w][u]=0;
if(D[v][w]<INFINITY)
{
p[v][w][v]=1;p[v][w][w]=1;
}
}
for(u=0;u<G->vexnum;u++)
for(v=0;v<G->vexnum;v++)
for(w=0;w<G->vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w])
{
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G->vexnum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}
while(flag)
{ printf("请输入出发点和目的地的编号:");
scanf("%d%d",&k,&j);
if(k<0||k>G->vexnum||j<0||j>G->vexnum)
{
printf("景点编号不存在!请重新输入出发点和目的地的编号:");
scanf("%d%d",&k,&j);
}
if(k>=0&&k<G->vexnum&&j>=0&&j<G->vexnum)
flag=0;
}
printf("%s",G->vexs[k].name);
for(u=0;u<G->vexnum;u++)
if(p[k][j][u]&&k!=u&&j!=u)
printf("-->%s",G->vexs[u].name);
printf("-->%s",G->vexs[j].name);
printf(" 总路线长%dm\n",D[k][j]);
}//Floyd end
第五模块更新校园景点平面图的成员函数如下:
int LocateVex(MGraph *G,char* v)
{
int c=-1,i;
for(i=0;i<G->vexnum;i++)
if(strcmp(v,G->vexs[i].name)==0)
{c=i;break;}
return c;
}
MGraph * CreatUDN(MGraph *G)//初始化图形,接受用户输入
{
int i,j,k,w;
char v1[20],v2[20];
printf("请输入图的顶点数,弧数:");
scanf("%d%d",&G->vexnum,&G->arcnum);
printf("请输入景点的编号:、名称、简介:\n");
for(i=0;i<G->vexnum;i++)
{
printf("景点编号:");
scanf("%d",&G->vexs->num);
printf("景点名称:");
scanf("%s",G->vexs[i].name);
printf("景点简介:");
scanf("%s",G->vexs->introduction);
}
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
printf("请输入路径长度:\n");
for(k=0;k<G->arcnum;k++)
{
printf("第%d条边:\n",k+1);
printf("景点对(x,y):");
scanf("%s",v1);
scanf("%s",v2);
printf("路径长度:");
scanf("%d",&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
if(i>=0&&j>=0)
{
G->arcs[i][j].adj=w;
G->arcs[j][i]=G->arcs[i][j];
}
}
return G;
}
void print(MGraph *G)
{
int v,w,t=0;
for(v=0;v<G->vexnum;v++)
for(w=0;w<G->vexnum;w++)
{
if(G->arcs[v][w].adj==INFINITY)
printf("∞ ");
else printf("%-7d",G->arcs[v][w].adj);
t++;
if(t%G->vexnum==0)
printf("\n");
}
}
3、设计主函数。 本函数在主函数里调用了C++语言的两个特殊命令修改控制台的颜色命令和设置控制台窗口大小的命令,还调用了一个具体实现该校园景点平面图的功能函数CMD函数。主函数如下:
void main(void)
{
system("color 1f"); //修改控制台的颜色信息,改为白字蓝底的模式
system("mode con: cols=140 lines=130"); //设置窗口大小
cmd(); //调用cmd函数
}
void cmd(void)
{
int i;
char *v;
b=InitGraph();
Menu();
scanf("%d",&i);
while(i!=6)
{
switch(i)
{
case 1:system("cls");Browser(&b);Menu();break; //先清屏,然后调用游览函数,调用选项菜单函数,跳出本层循环
case 2:system("cls");ShortestPath_DIJ(&b);Menu();break;
case 3:system("cls");Floyd(&b);Menu();break;
case 4:system("cls");Search(&b);Menu();break;
case 5:system("cls");CreatUDN(&b);LocateVex(&b,v);Menu();break;
case 6:exit(1);break;
default:break;
}
scanf("%d",&i);
}
}
第五章 运行与测试
1、在调试程序的过程中遇到什么问题,是如何解决的?
调试过程遇到了很多问题,例如在用表格输出校园平面图时,一开始不知道怎么输出整张表格,后来在试了好多次以后知道可以一点一点输出,比如可以用printf函数单独输出一条横线,这样慢慢可以组成一整张表格;还有在初始化无向图时,一开始设置数组表示景点名称和对应介绍时总是忘记用图的顶点来调用,老是报错,经过调试才记住了顶点的结构体类型,等等。
2、设计了那些测试数据?测试结果是什么?
本设计查询部分的测试数据分为以下三种:1)平面图中各景点的编号,编号范围为0到9十个数字;2)各景点编号的组合,例如2 3,2“Enter”3;3)五个选项编号,范围从1到5五个数字。
另外更新部分的测试数据为用户输入的顶点数和弧数范围。
测试结果举例如下:
Menu功能:
第一模块功能显示:
第二模块功能实现如下:
第三模块能如下:
第四模块功能如下:
第五模块功能如下:
第六章 总结与心得
从过本次课程设计对图的概念有了一个新的较全面的认识,在学习离散数学的时候总觉得图是比较抽象的东西,但是在学习了数据结构课程以后,慢慢体会到了其中的奥妙,图能够在计算机中存在,首先要捕捉它有哪些具体化数字化的信息,比如说权值、顶点个数等。这也就说明了想要把现实生活中的信息转换成计算机能识别的信息,必须用数字来完整的构成一个信息库,而图的存在又涉及到了顶点之间的关系。图分为有向图和无向图,无向图是有向图在权值双向相等下的特例。
那么如何把现实生活中的校园游览问题转换成用图来实现呢?通过老师和同学的帮助我用图的邻接矩阵存储方式完成了景点之间的路径问题。对整个程序而言,迪杰斯特拉算法和弗洛伊德算法是核心内容,实现了校园景点之间最短路径问题,其实这两个算法在实际思考中并不难,找一个景点到其他景点的最短路径,也许大家会说一步步从这个场所找最近路线并与其实际距离相比较,就可以轻易找出来,但是在计算机中实现却需要很多专业知识,为实现这两个函数功能上调试了好多次,在老师和同学帮助下终于完成这两个模块的设计。在此次设计中还学会了C++的一些特殊命令:如清屏函数system("cls"),conio.h不是C标准库中的头文件,conio是Console Input/Output(控制台输入输出)的简写,等等。另一方面,加深了对C语言的标准库函数中scanf()函数的理解,如scanf("%d%d",&k,&j);格式控制串中没有非格式字符作输入数据之间的间隔,只能用空格、Tab、回车作输入数据之间的间隔。最后,本设计的第五模块只是实现了用户可以初始化平面景点图的功能,并没有在原图基础上增加删除顶点及弧的功能,我会以此为契机刻苦学习,多实践,争取做出更好的咨询系统。
相信通过此次课程设计对数据结构图部分的理解与掌握较以前透彻了很多。
参考文献:
[1] 严蔚敏、吴伟民主编 《数据结构》(C语言版) 清华大学出版社 2002
[2] 殷人昆等著 《数据结构》(C++版) 清华大学出版社 2001
[3] 金远平著 《数据结构》(C++描述) 清华大学出版社 20##
[4] 许卓群等著 《数据结构与算法》 高等教育出版社 2004
[5] Frank M.Carrano 等著 《数据结构与C++高级教程》清华大学出版社 2004
[6] 严蔚敏、吴伟民 《数据结构习题集》(C语言版)清华大学出版社
[7] 谭浩强 《C语言程序设计》 清华大学出版社
[8] 与所用编程环境相配套的C语言或C++相关的资料