校园导游程序的设计与实现课程设计-大学论文.doc

海南大学

课程名称 数据结构（基于C语言）课程设计
题 目 校园导游程序的设计与实现
院 系 ＿ 信息科学技术学院＿＿＿＿
班 级 ＿＿通信工程B班＿

软件专题训练任务书

软件专题训练题目
校园导游程序
姓名

学号

专业班级

组别

组长

同组成员

指导教师
吴泽辉
专题训练目的
通过校园导游程序的设计与实现，熟1练掌7握图型结构在实际问题中的应用。
专题训练环境
运行环境为Visual C++ 6.0
课程设计任务和要求
设计校园导游程序，基本要求：
1．咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的场所。
2、计算并记录从校门口到各个场所的最短路径，即求单源点到其它各个场所的最短路径。
3、提供校园中任意场所的问路查询，即求任意两点之间的最短路径。
参考
文献
1、严蔚敏等. 数据结构（C语言版）. 清华大学出版社2004
2、谭浩强. C语言程序设计. 清华大学出版社. 2002
3、李春保. 数据结构教程上机实验指导. 清华大学出版社. 2005

校园导游程序
一、简介
1．设计目的：通过校园导游程序的设计与实现，熟练掌握图型结构在实际问题中的应用。
2．问题的描述：设计一个校园模拟导游程序，为新生或来访的客人通过与机器的“对话“提供最短路径的信息查询服务。 1．任意选取n个场所，构成一个无向带权图，图中顶点表示场所，边上的权值表示两点间的距离，图的存储结构可采用带权的邻接矩阵。
2．咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的场所。
3、计算并记录从校门口到各个场所的最短路径，即求单源点到其它各个场所的最短路径。
4、提供校园中任意场所的问路查询，即求任意两点之间的最短路径。
二、数据结构的设计：
由于各个场所通过校园中的道路相连，各个场所和连接它们的道路构成了整个校园的地理环境，所以使用图这种数据结构对他们去进行描述。以图中的顶点表示校园内各个场所，应包含场所名称、代号、简介等信息；以边表示连接各个场所的道路，应包含路径的长度等信息；顶点和边均使用结构体定义，整个图的数据结构采用教材中介绍的带权的邻接矩阵方法。

二、数据结构的设计：
typedef struct ArCell
{
int adj; //路径长度
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct //图中顶点表示主要景点，存放景点的序号、名称、介绍等信息，
{
char name[30];
int num;
char introduction[100];//简介
}infotype;
typedef struct
{
infotype vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
MGraph b;
void cmd(void)
{
int i;
b=InitGraph();
Menu();
scanf("%d",&i);
while(i!=4)
{
switch(i)
{
case 1:Browser(&b);Menu();break;
case 2:ShortestPath_DIJ(&b);Menu();break;
case 3:Floyd(&b);Menu();break;
case 4:exit(1);break;
default: printf("输入序号不存在,请重新输入");break;
}

scanf("%d",&i);
}
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,"3号教学楼");
strcpy(G.vexs[3].introduction,"海大学子努力学习，坚持向上的场所 ");
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,"厅内卫生整洁，环境宜人");
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=100;
G.arcs[0][2].adj=80;
G.arcs[0][6].adj=100;
G.arcs[1][7].adj=120;
G.arcs[2][3].adj=50;
G.arcs[3][6].adj=110;
G.arcs[3][4].adj=150;
G.arcs[4][5].adj=60;
G.arcs[4][9].adj=280;
G.arcs[5][9].adj=250;
G.arcs[6][7].adj=190;
G.arcs[6][9].adj=180;
G.arcs[7][8].adj=130;
G.arcs[8][9].adj=100;
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
用的是一个switch语句实现输入不同的序号操作选项，调用不同的函数进入不同的操作板块
// 迪杰斯特拉算法计,v0为始点
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");
}
}

旅客进行查询：1. 查看校园各景点2. 查看所有游览线路； 3. 选择始点和终点 4. 退出程序

三、功能（函数）设计：
一．本程序从总体上分为四个功能模块，分别为： (1)查看校园各景点，这一功能主要为来客提供要查的信息。（2） 查看所有游览线路,这一功能主要提供来客所要到达目的地的所有的线路，方便选择最短的的路线。（3）选择始点和终点 ，这一功能的实现为了找出所走线路中的最短路径（4）. 退出程序

二，流程图如下
（1） 程序功能介绍和操作提示模块

选项操作菜单
查看校园各景点
查看所有游览路线
选择始点和终点
退出程序

（2）查看所有游览线路
开始
用求迪杰斯特拉算法出中转最少的路径
输入v0,v
v0,v合理
v0==v
递归调用此算法
输出中转最少的路径
v0,v直接到达
结束
N
Y
Y
N
Y
N
权值小于无穷
带权最少的路径

（3） 选择始点和终点
开始
初始化path[i][j],dist[i][j]
用弗洛伊德算法
计算最小路径
输入vi,vj
vi,vj合理
输出最短路径
结束
N
Y
Y
Y

· Y
N
dist[i][k]+dist[k][j]<
dist[i][j]
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=JoinList(path[i][k],path[k][j]);调用JoinList()和Addtail()

四、界面设计：
本程序界面本着易于操作简单整洁而不失美观的理念，采用数字对应功能选项，结合详细的操作提示，使得操作方便快捷，界面清晰明朗。

函数MGraph InitGraph():初始化图。
函数void Menu()：创建菜单。
函数void Browser(MGraph *G)：浏览全景。
函数void Search(MGraph *G)：查询某点信息。
函数void Floyd(MGraph *G)：查询任意两点之间的最短路径。
函数void ShortestPath_DIJ(MGraph * G)：查询校门口到其他各点之间的最短路径
六、运行与测试：
1、测试的数据及其结果：
（1）浏览各景点选项功能

（2）选择查看校门口到各个景点的最短路径

（3）从各个景点中任意选择两景点之间的最短距离
（4）查询完毕，退出程序

2、运行与测试期间遇到的问题及其解决办法。
1. 对文件的输入、输出打开方式不够熟悉，导致输入输出信息有误，后参照教材等材料进行修改，使得程序正常进行；
2. 删除函数中循环使用不当，导致运行结果及写入文件结果错误，经修改后恢复正常；
3. 经过反复修改测试运行，程序功能基本实现，基本完成题目要求。 。
七、设计后的思考：
1.首先经过这一个星期的紧张而又充实的课程设计，是我对数据结构这一门课程的相关知识有了全面深刻的认识，尤其是对图这一数据结构的相关知识掌握的更加全面和牢固，特别是对迪杰斯特拉算法的思想和具体实现更是经历了从不知所云到熟练运用的学习过程，同时也全面而又系统的复习了C++相关知识。 2.此次课程设计最大的收获可以说是全面掌握了数据结构图的相关知识。虽说图这一章也是数据结构的终点，但是由于考试只考一些算法的思想，对具体的实现没有做要求，因此课程设计之前我对迪杰斯特拉算法可以说是一窍不通，更谈不上了解。经过几天的探索和同学的指点，终于可以运用迪杰斯特拉算法实现对无向网中各顶点间的最小路径和具体路径的求解。 3.经过此次课程设计，使我懂得任何一门计算机语言学习，都是应该理论与实际的结合，光有理论知识是不行的。在以前的学习中，我往往知识以备考为目的，只注重对教材理论知识的学习，不注重实践，平时很少主动去写一些代码，从以前的C语言到C++语言包括现在的数据结构都是这样一个情况。虽然在期末考试中往往有不错的表现，但是真正到要我自己动手去编写一个程序时，往往都是困难重重。 4.学习无止境，但不代表这门课程的学习彻底结束，因为我还没掌握的知识还有很多很多，就拿本次课程设计来说，在设计输出相关路径时，最初的设计思想是输出相关顶点的名称而不是其序号，因为这样就可以是相关的路径信息表达的更为直观明了，使用户更容易使用。但是真正到了实现的时候困难重重，最后只能退而求其次，用各顶点的序号代替其名称。这导致用户在查询相关路径信息时必须拿路径中所列出的序号同主登入界面中所列出的景点名称一一对照，加大了用户的工作量。这可谓是本系统的一大遗憾，所以我决定在寒暑假等课余时间将这些知识重新学习，达到真正对这门课程的掌握。