迪杰斯特拉-景点导航问题的课程设计.doc

课程设计报告

实验名称：数据结构与算法课程设计
题 目： 景点导航问题
院 系： 计算机工程学院
班 级： 软件
学 号：
学生姓名：
指导教师：
设计周数： 1周

成 绩：

日期： 2016 年 7 月 4 日
25
目录
一、 课程设计的目的与要求 2
1. 目的： 2
2. 要求： 2
二、 课程设计题目 2
三、 需求分析 2
四、 概要设计 3
五、 详细设计 4
六、 调试分析 6
1. 界面及其选择功能测试 6
2. 创建景点平面图功能的调试 7
3. 景点相关信息查询功能的调试 7
4. 景点路径信息查询功能的调试 8
七、 使用说明 9
八、 测试结果 10
九、 总结 11
1 已完成的工作 11
2 未完成的工作 11
3 需做的改进 12
附录 12
参考文献 12
景点平面图 12
源程序 13

一、 课程设计的目的与要求
1. 目的：
应用数据结构和算法来设计相应的程序，培养学生问题求解模块的框架设计和详细设计、相关程序实现和调试能力，完成创新能力和实践能力的训练。
2. 要求：
用高级程序设计语言C编码，用VC++开发平台调试。
二、 课程设计题目
景点导航问题：设计某一景点的平面图，至少包括10个以上的场所，每两个场所可以有不同的路径，并且路径长度可能不同，找出从任意场所到达另一场所的最佳路径。
三、 需求分析
本演示程序基于VC++6.0编写，完成景点布局的建立、查询，以及各个景点之间的路径查询。
1) 设计景点的平面图，在该景点选取10个左右的子景点。以图中顶点表示该景点内的各景点，存放子景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。
2) 为来访客人提供图中任意景点相关信息的查询。
3) 为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。
4) 为来访客人提供将所查询到的信息保存到指定文件中去的功能。
5) 测试数据：
A. 创建景点平面图的操作中依次输入11（景点个数）、 14（相邻景点边数）、 “枇杷园”（各个景点的名称）、“枇杷园是……”（各个景点的简介）、（1 2）（相邻景点的代号）、13（相邻景点的距离），生成一个景点平面图。
B. 查询景点相关信息操作中，输入1、23……屏幕终端分别显示1号景点、2号景点、3号景点……的名称、简介，以及其相邻的景点。
C. 查询景点路径的操作中，输入景点代号，如代号1，屏幕终端显示1号景点与其他所有景点的最短路程及所经过的路径。
四、 概要设计
1) 为了实现上述程序功能，需要定义景点平面图的抽象数据类型：
Mgraph{
数据对象：D1={vex|vex∈vexs[vnum]，i=0,1,2，…，n≥0}
D2={arc|arc∈IntegerSet，i=0,1,2，…，n≥0}
数据关系：R={（ai,ai+1）=arci| ai,ai+1 ∈D1，arci∈D2 }
基本操作：
函数原型
初始条件
操作结果
Void creatgraph(Mgraph *G,char *name[],char *intro[])
无初始条件
创建一个景点平面图的邻接矩阵和两个字符数组，存放有景点名称、简介等相关信息
Void dijkstra(Mgraph G,int v,char *name[]);
景点平面图G、景点名称数组name已经存在
查询到任意一景点代号v到其他景点的最短路程和路径
Void dijkstra_file(Mgraph G,int v,char *name[]);
景点平面图G、景点名称数组name已经存在
查询到任意一景点代号v到其他景点的最短路程和路径并保存到指定文件中
Void asked(Mgraph G,int v,char *intro[],char
*name[]);
景点平面图G、景点名称数组name、景点简介数组intro已经存在
查询到任意一景点v的名称、简介以及相邻景点
Void asked_file(Mgraph G,int v,char *intro[],char *name[]);
景点平面图G、景点名称数组name、景点简介数组intro已经存在
查询到任意一景点v的名称、简介以及相邻景点并保存到指定文件中
Void menu_one();
在屏幕终端输入1
实现任意一景点的相关查询；
在屏幕上显示操作菜单
Void menu_two();
在屏幕终端输入2、景点平面图G、景点名称数组name已经存在
在屏幕上显示操作菜单
实现景点平面图中任意一景点相关信息的查询
}
2) 本程序包含8个函数
① 主函数main()
② 创建景点平面图函数creatgraph()
③ 显示操作菜单函数一menu_one()
④ 显示操作菜单函数二menu_two()
⑤ 最短路径查询函数dijkstra()
⑥ 最短路径结果储存函数dijkstra_file()
⑦ 景点名称查询函数asked()
⑧ 景点名称结果储存函数asked_file()
各函数间关系如下

五、 详细设计
为了实现概要设计中定义的所有的数据类型，对每个操作写出C语言算法；对主程序和其他模块也都需要写出C语言算法；画出系统结构图
1) 景点平面图的数据类型
typedef char Velemtype;
typedef struct
{
Velemtype vexs[vnum];
int arcs[vnum][vnum];
int vex,arc;
}Mgraph;
2) 景点平面图的基本操作如下
void creatgraph(Mgraph *G,char *name[],char *intro[]);
void dijkstra(Mgraph G,int v,char *name[]);
void dijkstra_file(Mgraph G,int v,char *name[]);
void asked(Mgraph G,int v,char *intro[],char *name[]);
void asked_file(Mgraph G,int v,char *intro[],char *name[]);
void menu_one();
void menu_two();
void main();
其说明见前。
其中Menu_two为自行设计的景点平面图，即景点平面图已初始化成功。该景点平面图有11个景点14条景点间的接边。
该景点平面图设计如下：

六、 调试分析
1. 界面及其选择功能测试
检查界面布局是否合理、正确， 选择不同功能后是否可以正确显示。
① 主菜单1(Menu_one)的界面如下：

② 主菜单2(menu_two)的界面如下：

2. 创建景点平面图功能的调试

3. 景点相关信息查询功能的调试
① Menu_one中查询功能的调试
分别为输入数据有误和无误时的情况，并可选择是否将结果储存到文件中：

② Menu_two中查询功能的调试
[1.] 输入正确时：

[2.] 输入非法数字时：

4. 景点路径信息查询功能的调试

① Menu_one中路径查询功能的调试

② Menu_two中路径查询功能的调试
[1.] 输入非法数字时：

[2.] 输入正确时

经检验，该结果与用dijkstra算法所求得的结果一致。
通过以上测试可以基本确景点导航系统是否实现了预定的功能。
七、 使用说明
程序名为 课程设计.exe，运行环境为DOS。程序执行后显示
*******************欢迎使用XXX景点导航系统********************
**********Welecome to Use the Attractions Navigation System********
******************** Menu *********************
* *
* *
Function one: 设计景点 Function two: 查询景点信息
* *
Function three 问路查询 Function zero: 退出系统
* *
请选择 [Please choose the function what you want]-----------

在select后输入数字选择实现不同的功能，该主菜单需要先自行设计一景点平面图后才能进行其他操作。
具体操作在第六部分均有图示
八、 测试结果
1) 在menu_one中的设计（创建）操作：
选择1，输入3 2建立一个三个景点，两条路径的平面图；
输入各个景点的名称和简介；
输入各个路径的终点和始点，以及路径长度。
得到景点平面图G、景点名称数组name以及景点简介数组intro。
2) 查询景点详细信息操作（以menu_two为例）：
输入2，得到：

继续输入1，则

若输入2，则返回主菜单。
输入55，提示输入错误，重新输入。
3) 查询景点相关路径操作（以menu_two为例）：
输入4，得到

继续输入1，得到

若输入2，则返回主菜单。
输入 -2，提示输入错误返回主菜单重新输入。
九、 总结
1 已完成的工作
本演示程序运行于DOS环境，基本完成了对景点平面图的设计、对其中各个景点的查找、各个景点之间路径查找的功能，用户端可能输入的各种情况考虑的比较完善，程序界面也做到较为简洁友善。而且程序还支持文件储存功能，可以将查询结果向用户端保存。
2 未完成的工作
该程序在灵活性、通用性方面还有所欠缺。其中设计（创建）景点平面图的过程比较繁琐，需大量输入各种信息，平面图若较为复杂则实用性不高。此外程序部分过程比较繁琐，时间、空间复杂度相对较大，对于大程序大平面图设计来说，会造成很多时间空间的浪费。在存储功能的方面也存在些许不足，不支持文件的追加读入功能，导致每个文件只能读入一次储存结果，若继续存储则会替换原有的存储内容。
3 需做的改进
本设计中只是完成了要求的内容，并没有考虑算法的时间和空间复杂度，然而这些也是图论所介绍过的，在大程序中就显得的非常重要了，但是本例考虑程序小为了实现方便没有予以考虑，特别是在求最短路径的算法中，又增加了以固定字符串格式输出以确保效果，时间复杂度达到了O（n*n*n*n*n*n）的程度，在以后的编程中需要注意。
附录
参考文献
[1.] 蒋长浩，吴建专，顾国华等《图论及其应用》，东南大学出版社，2002年
[2.] 徐俊明《图论及其应用》，中国科学与技术出版社，2000年
[3.] 张璇平，雷永梅等《数据结构》，机械工业出版社，2001年
[4.] 李明哲《图论及其算法》，机械工业出版社，2010年
[5.] 谭浩强《C程序设计（第四版）》，清华大学出版社，2010年
[6.] 郑玲《C语言程序设计》，中国电力出版社，2009年
[7.] 林碧英《新编数据结构及算法教程》，清华大学出版社，2012年
景点平面图

景点简介：
枇杷园：到枇杷园游玩，如同其它风景名胜古迹，春、夏、秋、冬景色各有魅力，只有身临其境才能欣赏到山水如画的美。
夕照廊：斜阳落照，塔起金轮，湖上黄昏暮景中无有堪与之相匹者，坐落在湖上的夕照廊，给你诗一般的感受。
山色亭：山色亭，妙在借景，把园内的山和园外的水通过复廊互相引借，使山、水、建筑构成整体，游于其中，给人以无尽的遐想和舒适。
多累台：多累台内有四季长青的雪松，龙柏，有迎春怒放的碧桃，牡丹，有夏日争艳的月季，石榴，还有八月飘香的桂花和寒冬傲雪的腊梅等，各种花木参差错落，宛若人间仙境。
沉心堂：沉心堂中有诸多字画、古玩，朴实典雅，散发悠远气息，是游客放松身心、修养品性的绝佳之地。
正门：正门位于该景点的北面，与银锄湖、夕照廊和沉心堂相连，门由红木雕刻，朴实而典雅。
银锄湖：银锄湖，波光粼粼，宛若银龙，微风拂过，泛起的淡淡涟漪银光闪闪，湖水清澈见底，湖内有各种鱼虾，是游客清凉避暑的好去处。
沁芳榭：沁芳榭中生长着各种各样的花草，无论春夏秋冬，整个园内都散发着芬芳，花盛开之时，万紫千红之境，使游客无法不驻足流连。
松陵酒家：游客若是观赏劳累，想小憩一会，松陵酒家便是不二选择。这充满古色古香气息的酒家，总是可以让游客放松下来，与朋友饮酒畅谈。
偏门：偏门位于该景点的南面，与正门相呼应，可直达引静桥、松陵酒家。
引静桥：引静桥坐落在该景点南面的一湖上，通体都是由大理石打造的引静桥，远远望去，就像是一位朴实安祥的老者，游客登上桥面，也会感觉内心平静而安。

源程序
#include
#include
#include
#include
#include

#define vnum 20

typedef char Velemtype;

typedef struct
{
Velemtype vexs[vnum];
int arcs[vnum][vnum];
int vex,arc;
}Mgraph;

void creatgraph(Mgraph *G,char *name[],char *intro[]);
void dijkstra(Mgraph G,int v,char *name[]);
void dijkstra_file(Mgraph G,int v,char *name[]);
void asked(Mgraph G,int v,char *intro[],char *name[]);
void asked_file(Mgraph G,int v,char *intro[],char *name[]);
void menu_one();
void menu_two();

void main()
{
int n;
scanf("%d",&n);
if(n==1)
{
system("cls");
menu_one();
}
else if(n==2)
{
system("cls");
menu_two();
}
else
return;
}

void menu_one()
{
Mgraph G;
char *name[vnum];
char *intro[vnum];
int n,m;
int i,j,l;
printf("******************** 欢迎使用XXX景点导航系统 ********************\n");
printf("**********Welecome to Use the Attractions Navigation System**\n");
printf("********************\t\tMenu\t\t*********************\n");
printf("* *\n");
printf("* *\n");
printf("Function one:\t设计景点\tFunction two:查询景点信息\t\n");
printf("* *\n");
printf("Function three:\t问路查询\tFunction zero:\t退出系统\t\n");
printf("* *\n");
printf("请选择 [Please choose the function what you want]-----------\n");
printf("* *\n");
while(n)
{
printf("Please input a number:\t");
scanf("%d",&n);
if(n==1)
{
printf("请按照以下操作提示进行---------\n");
printf("按任意键继续------\n");
getch();
creatgraph(&G,name,intro);
printf("*******您已设计完成~~请继续选择~~********\n");
}
if(n==2)
{
printf("请选择您当前所在的位置代号或您想查询的景点位置代号--------\n");
scanf("%d",&i);
if(i>G.vex||!i||!G.vex)
{
printf("该位置代号输入有误!!!无法查询!!!\n");
printf("请重新选择您要实现的功能:\n");
}
else
{
asked(G,i,intro,name);
printf("您可以继续选择~\n");
printf("将结果保存到文件中?\n是-----------------1\n否-----------------2\n");
scanf("%d",&l);
if(l==1)
asked_file(G,i,intro,name);
}
}
if(n==3)
{
printf("请选择您所在的位置代号或您想查询的景点位置代号--------\n");
scanf("%d",&j);
if(j>G.vex||!j||!G.vex)
{
printf("该位置代号输入有误!!!无法查询!\n");
printf("请重新选择您要实现的功能:\n");
}
else
{
dijkstra(G,j,name);
printf("您可以继续选择~\n");
printf("将结果保存到文件中?\n是-----------------1\n否-----------------2\n");
scanf("%d",&m);
if(m==1)
dijkstra_file(G,j,name);
}
}
if(n>3||n<0)
printf("您输入的数字有误!!请重新输入!\n");
}
}

void menu_two()
{
int a[14][2]={{1,2},{2,3},{3,4},{4,5},{5,6},{2,5},{2,6},{6,7},{7,8},{7,9},{5,9},{9,10},{10,11},{4,11}};
int b[vnum]={16,59,22,27,46,9,14,18,11,45,31,33,8,16};
char *name[]={"枇杷园","夕照廊","山色亭",
"多累台","沉心堂","正门",
"银锄湖","沁芳榭","松陵酒家",
"偏门","引静桥"};
char *intro[]=
{
"到枇杷园游玩，如同其它风景名胜古迹，春、夏、秋、冬景色各有魅力，只有身临其境才能欣赏到山水如画的美。",
"斜阳落照，塔起金轮，湖上黄昏暮景中无有堪与之相匹者，坐落在湖上的夕照廊，给你诗一般的感受。",
"山色亭，妙在借景，把园内的山和园外的水通过复廊互相引借，使山、水、建筑构成整体，游于其中，给人以无尽的遐想和舒适。",
"多累台内有四季长青的雪松，龙柏，有迎春怒放的碧桃，牡丹，有夏日争艳的月季，石榴，还有八月飘香的桂花和寒冬傲雪的腊梅等，各种花木参差错落，宛若人间仙境。",
"沉心堂中有诸多字画古玩，朴实典雅，散发悠远气息，是游客放松身心、修养品性的绝佳之地。",
"正门位于该景点的北面，与银锄湖、夕照廊和沉心堂相连，门由红木雕刻，朴实而典雅。",
"银锄湖，波光粼粼，宛若银龙，微风拂过，泛起的淡淡涟漪银光闪闪，湖水清澈见底，湖内有各种鱼虾，是游客清凉避暑的好去处。",
"沁芳榭中生长着各种各样的花草，无论春夏秋冬，整个园内都散发着芬芳，花盛开之时，万紫千红之境，使游客无法不驻足流连。",
"游客若是观赏劳累，想小憩一会，松陵酒家便是不二选择。这充满古色古香气息的酒家，总是可以让游客放松下来，与朋友饮酒畅谈。",
"偏门位于该景点的南面，与正门相呼应，可直达引静桥、松陵酒家。",
"引静桥坐落在该景点南面的一湖上，通体都是由大理石打造的引静桥，远远望去，就像是一位朴实安祥的老者，游客登上桥面，也会感觉内心平静而安逸"
};
Mgraph G;
int n,j,k,m,l;
G.vex=11;
G.arc=14;
for(int i=1;i[i]=0;
}
else
G.arcs [i][j]=10000;
}
for(i=0;iions Navigation System**********\n");
printf("* *\n");
printf("* *\n");
printf("* *尊敬的游客您好~欢迎来到XXX景区，我是景区的导航系统--小航 O(∩_∩)O\n");
printf("* *下面是该景区的主要景点以及代号~~\n");
for(i=1;i<=G.vex;i++)
{
printf("[ %d ]-%s\t",i,name[i-1]);
if(i%3==0)
printf("\n");
}
printf("\n");
printf(" *\n");
printf("小航有什么可以帮到您的呢?\n");
printf("* *\n");
printf("One:\t我想要看看某个景点的信息~~\n");
printf("Two:\t我想知道这个地方的路怎么走~~\n");
printf("* *\n");
printf("请选择 [Please choose the function what you want]---------\n");
printf("* *\n");
while(n)
{
printf("Please input a number:\t");
scanf("%d",&n);
if(n==1)
{
printf("请按照以下操作提示进行---------\n");
printf("按任意键继续------\n");
getch();
printf("请选择您所在的位置代号或您想查询的景点位置代号--------\n");
scanf("%d",&j);
if(j>G.vex||!j)
{
printf("您输入的代号可能有误哦~小航无法帮您查询到(；′⌒`)\n");
printf("请重新选择一下您要实现的功能吧~\n");
}
else
{
asked(G,j,intro,name);
printf("您可以继续选择~\n");
printf("将结果保存到文件中?\n是-----------------1\n否-----------------2\n");
scanf("%d",&l);
if(l=1)
asked_file(G,j,intro,name);
}
}
if(n==2)
{
printf("请选择您所在的位置代号或您想查询的景点位置代号--------\n");
scanf("%d",&k);

if(k>G.vex||!k||!G.vex)
{
printf("您输入的代号可能有误哦~小航无法帮您查询到(；′⌒`)\n");
printf("请重新选择一下您要实现的功能吧~\n");
}
else
{
dijkstra(G,k,name);
printf("您可以继续选择~\n");
printf("将结果保存到文件中?\n是-----------------1\n否-----------------2\n");
scanf("%d",&m);
if(m==1)
dijkstra_file(G,k,name);
}

}
if(n>=3||n<0)
{
printf("您输入的数字可能有误哦~超过了小航的能力范围呢(；′⌒`)\n");
printf("请重新输入~\n");
}
}
}

void creatgraph(Mgraph *G,char *name[],char *intro[])
{
int n,j;
printf("请输入总景点数和可直达的两景点数目:\t");
scanf("%d%d",&G->vex,&G->arc);
for(int i=1;i<=G>vex;i++)
G->vexs[i-1]=i;
for(i=1;i<=G->vex;i++)
{
printf("请输入 %d 编号的景点的名称:\t",i);
name[i-1]=(char *)malloc(sizeof(char)*10);
scanf("%s",name[i-1]);
printf("请输入该景点的简介:\n");
intro[i-1]=(char *)malloc(sizeof(char)*100);
scanf("%s",intro[i-1]);
}
for(i=0;ivex;i++)
for(int j=0;jvex;j++)
G->arcs[i][j]=0;
for(int k=0;karc;k++)
{
printf("请输入可以直达的两景点代号： \t");
scanf("%d%d",&i,&j);
printf("请输入两景点的距离：\t");
scanf("%d",&n);
G->arcs[i-1][j-1]=n;
G->arcs[j-1][i-1]=n;
}
for(i=0;ivex;i++)
for(j=0;jvex;j++)
{
if(G->arcs[i][j]==0&&i!=j)
{
G->arcs[i][j]=10000;
G->arcs[j][i]=10000;
}
}
}

void dijkstra(Mgraph G,int v,char *name[])
{
int dist[vnum];
int path[vnum][vnum];
int flag,k,min,m,n;
for(int i=0;i {
dist[i]=G.arcs[v-1][i];
if(dist[i]!=0&&dist[i]!=10000)
{
path[i][0]=v;
path[i][1]=i+1;
}
}
n=0;
flag=1;
while(flag)
{
k=0;
min=10000;
for(int j=0;j从%s出发，到",name[v-1],name[k],min,name[v-1]);
j=2;
while(path[k][j]!=-1&&jist[k]+G.arcs[k][j]dist[j]<10000)
flag=1;
}
}

void dijkstra_file(Mgraph G,int v,char *name[])
{
int dist[vnum];
int path[vnum][vnum];
int flag,k,min,m,n;
char infile[20];
FILE *fp;
for(int i=0;ics[v-1][i];
if(dist[i]!=0&&dist[i]!=10000)
{
path[i][0]=v;
path[i][1]=i+1;
}
}
printf("* *请输入您要保存的文件名-----\n");
scanf("%s",infile);
if((fp=fopen(infile,"w+"))==NULL)
{
printf("不好意思，小航无法帮您写入到文件里(；′⌒`)\n");
return;
}
n=0;
flag=1;
while(flag)
{
k=0;
min=10000;
for(int j=0;j])-1]);
j++;
}
fprintf(fp,"%s 结束).\n",name[path[k][j-1]-1]);
if(!fprintf(fp,"%s 结束).\n",name[path[k][j-1]-1]))
{
printf("抱歉，文件写入失败\n");
return;
}
//更新path和dist
for(j=0;jst[k]+G.arcs[k][j];
for(m=0;m件中~\n");
fclose(fp);
}

void asked(Mgraph G,int v,char *intro[],char *name[])
{
printf("%d号景点：%s\n",v,name[v-1]);
printf("景点简介\n");
printf(" %s\n",intro[v-1]);
printf("* *\n");
printf("该景点临近的景点有~:");
for(int k=0;k0&&G.arcs [v-1][k]<10000)