公园导游图课程设计

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课 程 设 计

题目 教学院 专业 班级 姓名 指导老师

公 园 导 游 图 计 算 机 学 院 计算机网络技术 09网络技术（1）

冯 珊 、熊敬一

2010 年 12 月 30 日

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

课程设计任务书

2009～2010学年第 1学期

学生姓名： 何雪梅 专业班级： 09网络技术 指导教师： 冯姗、熊敬一 工作部门： 计算机学院

一、课程设计题目: 公园导游图 二、课程设计内容

给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。

三、进度安排

1． 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2． 完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能；

3． 进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。

四、基本要求

1. 界面友好，函数功能要划分好 2. 总体设计应画一流程图 3. 程序要加必要的注释 4. 要提供程序测试方案

5. 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值

的。

教研室主任签名：

年 月 日

2

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

目 录

摘要

1 问题描述 ························································································································

1.1图、无向图 ··········································································································· 3

1.1.1图的存储结构 ···························································································· 3 1.1.2 图的邻接矩阵表示法 ·············································································· 3 1.2算最短路径 ·········································································································· 4 1.3无向图遍历 ··········································································································· 4 广度优先搜索 ······································································································· 4 2.系统分析 ······························································································································ 5 2.1系统流程图 ··········································································································· 5 3 系统设计 ····························································································································· 5 3.1主要数据结构 ······································································································· 6 3.2 主要函数说明 ······································································································ 6 3.3主要算法说明 ······································································································· 6

3.3.1数组表示法 ······························································································· 6 3.3.2FLOYD算法 ································································································· 6 4 心得体会 ····························································································································· 7

附录一：源程序 ····················································································································· 8 附录三：参考文献 ·············································································································· 14

3

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

摘 要

计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种 运算的算法。

1.问题描述

１.１图的存储结构

图的存储方式很多，这里用的是邻接矩阵的方式。为了适合用C语言描述，以下假定顶点序号从0开始，即图G的顶点集的一般形式是V(G)={v 0 ，v i ， ，V n-1 }。

1.1.1 图的邻接矩阵表示法

（１）用邻接矩阵表示顶点之间的相邻关系； （２）用一个顺序表来储存顶点信息

1.1.2 图的邻接矩阵(Adacency Matrix)

设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵： 若Ｇ是网络，则邻接矩阵可定义为：

4

1,若(vi,vj)或 vi,vj E(G)

A[i,j]

0，其它

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

１.２求最短路径

给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

1.2.1单源最短路径问题

Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

１.３求最小生成树

对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：

Te,W(u , v)

TE表示T的边集

w(u，v)表示边(u，v)的权。

权最小的生成树称为G的最小生成树(Minimum Spanning Tree)。最小生成树可简记为MST。

最小生成树性质：

设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。

5

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

２.系统分析

２.１系统流程

本系统主要是实现图的最短路径问题

2.2系统相关抽象数据类型

2.2.1图的邻接矩阵存储结构形式说明

#define MaxVertexNum l00 //最大顶点数，应由用户定义 typedef char VertexType; //顶点类型应由用户定义 typedef int EdgeType; //边上的权值类型应由用户定义 typedef struct{

VextexType vexs[MaxVertexNum] //顶点表 EdeType edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表

int n，e; //图中当前的顶点数和边数 }MGragh;

6

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

2.2.2建立无向网络的算法 void CreateMGraph(MGraph *G) {//建立无向网的邻接矩阵表示 int i，j，k，w;

scanf("%d%d"，&G->n，&G->e); //输入顶点数和边数 for(i=0;in;i++) //读人顶点信息，建立顶点表 G->vexs[i]=getchar(); for(i=0;in;i++) for(j=0;jn;j++)

G->edges[i][j]=0; //邻接矩阵初始化 for(k=0;ke;k++){//读入e条边，建立邻接矩阵

scanf("%d%d%d"，&i，&j，&w);//输入边(v i ,v j )上的权w G->edges[i][j]=w; G->edges[j][i]=w; }

}//CreateMGraph

3.系统设计

3.1系统功能

提供无向图的生成，并保证了该无向图为一个无向网，同时也提供了计算最短距离的迪杰斯特拉算法，以及图的遍历。

3.2主要函数说明

本系统用了一个类来实现程序，里面包含了4个对象，即void graph::picture()；void graph::creatp(graph &t)；void graph::floyd(graph &t,const int n)；void graph::bfs(graph t)

3.3主要算法说明

7

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

3.3.1无向网的建立

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储 区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构，但可以借助数组的数据类型表示元素之间的关系。另一方面，用多重链表表示 图是自然的事，它是一种最简单的这式映像结构，聚聚以一个由一个数据域和多个指针域存储该顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针.

3.3.2数组表示法

用两个数组分别存储数据元素的信息和数据元素这间的关系的信息。以二维数组表示有N个顶点的图时，需存放N个顶点信息和N2个弧信息的存储量。

3.3.3Floyd算法

Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。

Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单； 缺点：时间复杂度比较高，不适合计算大量数据。

4.心得体会

当今世界，C语言作为国际上广泛流行的通用程序设计语言，在计算机的研究和应用中已展现出强大的生命力。C语言兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。

而数据结构-作为C语言使用的途径学科,也是计算机学科的一门核心课程.虽然我们学C语言和数据结构已快一年了，但一直都注重理论概念，而实际上机操作却不多.很感谢这次的课程设计，它使我更加深刻地体会到多看专业书、多学习专

8

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

业知识的重要性，只有掌握了一定量的专业知识才能得心应手地解决诸多问题；另外，在课程设计过程中，我遇到了很多棘手的问题，好几次都差点放弃了，但最终还是坚持下来了，所以我懂得了，做任何事都要有耐心，不要一遇到困难就退缩；当遇到那么多的问题时，我自己能解决的并不多，大部分都是通过和小组同学讨论而解决的。所以，在学习和工作中要时刻谨记“团结”二字，它好比通向成功的铺路石，不可或缺。在编程过程中，有编得很顺利的，也有很多不顺利的，正如人生的道路是曲折的，但正是因为曲折人生才光彩夺目，在人生的路上，总遇到重重困难，但正是因为这些困难我们才变的更加坚强，才能够不断地提高自己，充实自己，最后达到我们理想的彼岸。

感谢冯老师在授课期间对我们严厉的态度和严格的管理，才造就了今天的我们。在课程设计过程中，我们几乎每个小组都遇到了不同程度的问题，但老师都细心指导，耐心地为我们讲解。老师认真负责的工作态度，对我们这次的课程设计得以顺利完成发挥了不可估量的作用。最后，再一次感谢在这次课程设计中对我给予帮助的老师和同学。通过这次课程设计，我们不光收获了知识，还收获了友谊和欢乐。

附录1 源程序

#include <iostream.h>

const int n=5; //n表示公园图中顶点个数 const int e=7; //e表示公园图中路径 bool visited[n+1]; #define max 32767

class graph {

public:

int arcs[n+1][n+1]; //领接矩阵 int a[n+1][n+1]; //距离 int path[n+1][n+1]; //景点

void floyd(graph &t,const int n);

9

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

void picture();

void creatp(graph &t); void bfs(graph t); };

void graph::picture() //公园图 {

cout<<" ******公园导游图******"<<endl; cout<<"以下是公校的景点"<<endl;

cout<<" ***************************"<<endl; cout<<" * 1.公园入口 2.水族馆 *"<<endl;

cout<<" * 3.摩天轮 4.动物园 * *"<<endl; cout<<" * 5.公园出口 *"<<endl; cout<<" ***************************"<<endl; cout<<"以下是公园的路径图 "<<endl; cout<<" 9 "<<endl; cout<<" 2 *---------*4 "<<endl; cout<<" | \\ /| "<<endl; cout<<" | 4\\ 5/ | "<<endl; cout<<" | \\ / | "<<endl; cout<<" 3 | \\/ | 2 "<<endl; cout<<" | * 3 | "<<endl; cout<<" | / \\ | "<<endl; cout<<" | /10 \\3| "<<endl; cout<<" 1 * / \\ * 5 "<<endl;

cout<<" 入口 出口 "<<endl;

cout<<"下面是景点与景点之间的距离和介绍："<<endl; cout<<"1.公园入口 ->2.水族馆 距离为：3"<<endl; cout<<"1.公园入口 ->3.摩天轮 距离为：10"<<endl; cout<<"2.水族馆 ->4.动物园 距离为：9"<<endl; cout<<"2.水族馆 ->3.摩天轮 距离为：4"<<endl; cout<<"3.摩天轮 ->4.动物园 距离为：5"<<endl; cout<<"4.动物园 ->5.公园出口 距离为：2"<<endl; cout<<"3.摩天轮 ->5.公园出口 距离为：3"<<endl; }

void graph::creatp(graph &t) {

int i,j;

for(i=1;i<=n;i++) for(j=1;j<=n;j++)

if(i==j)t.arcs[i][j]=0; //景点一样则距离为0 else t.arcs[i][j]=max; //i不等于j时 t.arcs[1][2]=3;

10

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

t.arcs[2][1]=3; t.arcs[2][4]=9; t.arcs[4][2]=9; t.arcs[3][1]=8; t.arcs[1][3]=8; t.arcs[3][2]=4; t.arcs[2][3]=4; t.arcs[3][4]=5; t.arcs[4][3]=5; t.arcs[3][5]=3; t.arcs[5][3]=3; t.arcs[5][4]=2; t.arcs[4][5]=2;

} //把景点跟距离用一个二围数组存储下来 void graph::floyd(graph &t,const int n) {

for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) {

t.a[i][j]=t.arcs[i][j]; //把距离付值给a.[i][j] if((i!=j)&&(a[i][j]<max)) t.path[i][j]=i;

else t.path[i][j]=0; }

for(int k=1;k<=n;k++) {

for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)

if(t.a[i][k]+t.a[k][j]<t.a[i][j]) {

t.a[i][j]=t.a[i][k]+t.a[k][j]; t.path[i][j]=t.path[k][j]; } } }

void graph::bfs(graph t) //从顶点i出发实现广度搜索搜索n {

int j,i; //f，r分别为队列头，尾指针 char ch;

cout<<"请输入一个你想去的地方:"; cin>>i;

课程设计（论文）

11

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

while(i<=5) {

if(i==1)cout<<"这里就是你要去的地方拉!!"<<endl<<endl; else {

for(j=1;j<=n;j++) {

if(i!=j) {

cout<<"距离为"<<t.a[i][j]<<": "; int next=t.path[i][j]; cout<<j;

while(next!=i) {

cout<<"--"<<next; next=t.path[i][next]; }

cout<<"--"<<i<<endl; } }

cout<<"等我推荐一条最佳路径供你返回吧(y/n):"; }

cin>>ch; if(ch=='y') {

if(i==2) cout<<"2--3--5"<<endl; if(i==3) cout<<"3--5"<<endl; if(i==4) cout<<"4--5"<<endl;

cout<<"请问你想去游览公园全景吗(y/n)："<<endl; cin>>ch; if(ch=='y')

cout<<"请走1--2--3--4--5路线"<<endl; cout<<"你还想去别的地方吗?(y/n)"; cin>>ch; if(ch=='y')

{cout<<"请输入一个你想去的地方:"; cin>>i;} if(ch!='y') {

cout<<" *****退出程序*****"<<endl; cout<<" 欢迎下次再来"<<endl; break; }

12

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

}

else break; } }

int main() {

graph t; t.picture(); t.creatp(t); t.floyd(t,n); t.bfs(t); }

附录二：测试数据

图1—1

13

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

图1—2

参考文献

[1] 严蔚敏 吴伟民著 数据结构（C 语言版） 清华大学出版 1999年 第一版 [2] 谭浩强著 C程序设计 清华大学出版社 1999年 第二版

14

此课程设计内容是给出一张某公园的导游图,游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。里面涉及到数据结构及图的结构和图的遍历等。希望对大家有帮助。

课程设计（论文）

课程设计成绩评定表

指导教师签字：

年 月 日

15

本文来源：https://www.bwwdw.com/article/d8iq.html