数据结构课程设计报告（校园导游系统）附有源代码

课程论文（设计）

2011-2012 学年第2学期

课程名称：数据结构课程设计课程性质：实践课专业班级：考核方式：考查学生姓名：学 号：学 时：教师姓名： 1周

自评分：95分 评语及评分

目 录

1. 作业内容·····················································1 2. 基本思路·····················································1 2.1 本校10个景点···············································1 2.2 图的初始化··················································2 2.3 图的遍历····················································2 2.4 求最短路径··················································3 3.系统流程······················································4 3.1 系统的简单说明··············································4 3.2 系统流程图··················································5 4. 系统运行效果图···············································5 4.1 校园导游界面················································5 4.2 华农校园地图················································6 4.3 景点的相关信息查询··········································6 4.4 任意两个景点间的最短路径····································7 4.5 退出校园导游系统············································8 5.总结··························································9 6.参考文献······················································10

1. 作业内容

设计一个校园导游程序，为来访客人提供各种信息查询任务。基本要求： （1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介信息，以边表示路权，存放路径长度等相关信息。

（2）为来访客人提供图中任意景点相关信息的查询

（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

2. 基本思路

要完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。有以下设计思路：

（1）.结合本校的实际情况，选出10个景点；

（2）.人为手工为选出的10个景点赋上相关信息（名称、代号、简介信息、以及路权等等）；

（3）.根据选出来的10个景点用邻接矩阵存储校园图。 （4）.依照景点的相关信息创建校园图。

（5）.把纸质上的内容，利用C++编程语言编写查找景点相关信息的程序。 （6).根据人为赋值的路权，迪杰斯特拉算法计算任意两点之间的最短路径。 （7）.综上所诉，用一个主函数把这些板块合成，生产一个菜单界面呈现在用户面前。

为此，可把系统分为以下几个核心：图的初始化、图的遍历、求最佳路线。 2.1 选出本校10个景点

结合华南农业大学实际情况，我选出以下10个景点，从1到10编号： 编号 1 5 9

名称 校史馆 东区运动场 老校门 编号 2 6 10 名称 红满堂 树木园 黑山运动场 编号 3 7 名称 行政楼 竹园 编号 4 8 名称 西园 新校门 1

2.2 图的初始化

由于邻接矩阵特殊的存储方式，它非常便于快速的查找两个顶点之间的边上的权值。所以，图采用带权的邻接矩阵存储。

决定了图的存储方式后，以华南农业大学10个景点的游览地图作为蓝本，把校园地图抽象化成顶点与边构成的图形式，如图2.2所示，途中数字代表线的权值。

2.3 图的遍历

图的遍历是图中最基本的操作。图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。导游图需要把每条路径的信息都向游客展示，就需要读取每两个顶点间的路径信息。由于采用了带权的邻接矩阵存储结构进行存储，所以需要针对这一存储结构对路线进行遍历操作。其遍历算法如图2.3所示。

2

开始 选择图片控件 For循环语句 N （i=0；i<顶点数；i++） Y For循环语句 N (j=0;j

2.4 求最短路径

基于本程序中图的存储是邻接矩阵结构存储的图结构，因而采用适合该存储结构的迪杰斯特拉算法用于解决求最短路径的问题。

迪杰斯特拉提出了一个按路径长度递增的持续产生最短路径的算法，其基本思想是：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对于vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v，?，vk，就将vk加入集合S中，并将路径v，?，vk，vi，与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。如图2.4所示。

图2.3 遍历算法示意图

3

集合S Vk Vi 集合V-S V

图2.4 图的遍历算法执行效果示意图

辅助数组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中的元素个数

2.1 在dist[n]中求最小值，其下标为k（则vk为正在生成的终点）； 2.2 输出dist[j]和path[j]； 2.3 修改数组dist和path; 2.4 将顶点vk添加到数组s中；

3.系统流程

3.1 系统的简单说明

1.创建校园图：

（1）先手工画好华农的10个景点的草图，再用C++语言输出抽象化的校园地图。

（2）再用C++语言定义节点个数N，编写函数name( )为景点赋值各类信息

4

项，函数information( )，输入各个景点的简介。

（3）读入道路的起始点，为邻接矩阵的边赋相应的值。 2．利用函数travgraph来查找景点信息。

3．创建一个校园图creat(Matrix_Graph *G)，然后为相应的边赋上现实意义上的权值。

4．用path( )函数来求任意两景点之间的最短路径。 5.如果不查询则调用exit( )函数退出。 5．用main函数来输出导游界面。 3.2 系统流程图 开始 输入1 输出华农地图 Main 函数 输入2 调用查询景点函数travgraph( ) 界面菜单 输入3 YES 是否再次查询？ NO 输入4 调用函数YES 调用查询最短距离函 exit( ) 数path( ) 是否再次查询？ NO 结束 4.系统运行效果图

4.1 校园导游界面

程序运行，后台对图结构进行初始化，运行结果如图4.1。

5

返 回 界 面 菜 单

图4.1 校园导游节目图

4.2 华农校园地图

校园地图的查看是通过抽象化10个景点来用printf( )函数输出地图，在输入选择1之后弹出的界面，运行结果如图4.2。

图4.2 抽象化的华南农业大学校园导游地图

4.3 景点的相关信息查询

景点的相关信息查询是通过information( )函数来调用输出的，在主菜单那输入2之后，拿第2个景点红满堂和第7个景点竹园来当例子，第运行结果如图4.3.1和图4.3.2。

6

图4.3.1 景点2红满堂信息查询

图4.3.2 景点7竹园信息查询

4.4 任意两个景点间的最短路径

根据用户的需求，在用户输入了起点和终点后计算出最短路径是哪一条路径。以下举两个例子。第一个例子的起点是5东区运动场，终点是1校史馆。第二个例子的起点是2红满堂，终点是10黑山运动场。运行结果如图4.4.1和图4.4.2所示。

图4.4.1 从东区运动场到校史馆的最短路径

7

图4.4.2 从红满堂到黑山运动场的最短路径

根据截图可知，在现实生活中的最短路径也是如此。证明了程序的正确性。 4.5 退出校园导游系统

用户满足了需求之后，只要在界面菜单处输入4便可退出此次校园导游系统。运行结果如图4.5。

图4.5 退出校园导游系统

8

5.总结

由于设计者水平有限，本导游图系统的功能还比较简单，还有一些好的设想没有实现：比如添加管理模式，使得公园管理人员能够同样方便的更改导游图，因此更改这一导游图还必须在程序员的帮助下进行。另外，本导游图系统还有一定的局限性，如果存在只有一条通路的景点，导游图将无法求得最佳旅游路径。公园的导游图系统的这些不足请老师多多谅解。通过这次的课程设计左右，让我对数据结构中定义无向图和创建无向图的理解更加深刻，不断提升认识，提高编程技巧，借以不断地提高程序设计水平，了解数据结构在编写比较复杂的程序的重要作用；理解了迪杰斯特拉算法的原理，但对于其算法的程序编写还是不太明白；学会了在编写几百行程序时如何查找错误，如何改错误等等。

总而言之，这次的课程设计很好地锻炼自己实际操作能力！

9

参 考 文 献

[1]严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.1997.

[2]李春葆，尹为民，李蓉蓉.数据结构教程（第3版）上机实验指导.清华大学出版社.2009.

[3]滕国文.数据结构课程设计.清华大学出版社.2010.218-223. [4]蒋盛益.数据结构学习指导与训练.中国水利水电出版社.2003.

10

//程序名称：校园导游系统 //程序员：

//编写时间：2012年6月

#define N 10 #define MAX 25 #define MAXedg 30 #include #include #include #include

void clrscr() {

system(\}

typedef int AdjMatrix[MAX][MAX];

typedef struct {

int vexs[MAX]; AdjMatrix arcs; }Matrix_Graph;

typedef struct {

char name[10];

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 {

11

int lengh; int ivex, jvex; struct Edge *next; } EdgeType;

typedef struct {

int num; char name[10]; } vertex;

typedef struct {

vertex vexs[MAX]; int edges[MAX][MAX]; }adjmax;

void Name(int i) {

switch(i) {

case 1:

printf(\校史馆\\n\\n\ case 2:

printf(\红满堂 \\n\\n\ case 3:

printf(\行政楼\\n\\n\ case 4:

printf(\西园\\n\\n\ case 5:

printf(\东区运动场\\n\\n\ case 6:

printf(\树木园\\n\\n\ case 7:

printf(\竹园\\n\\n\ case 8:

printf(\新校门\\n\\n\ case 9:

printf(\老校门\\n\\n\ case 10:

printf(\黑山运动场\\n\\n\ default:

printf(\景点编号输入错误！请输入1-10的数字编号！\\n\\n\break;

12

} }

void Information(int i)/*景点介绍*/ {

switch(i) {

case 1:

printf(\校史馆:华农校史档案保存的地方。为原来华南农学院地址，建筑中西结合，每届毕业班照相处。\\n\\n\ case 2:

printf(\红满堂为白色圆顶建筑，外观华美。日常重要报告召开地。\\n\\n\ case 3:

printf(\行政楼：为学校日常事务办公点，外观壮丽，是华农的标志性建筑。 \\n\\n\ case 4:

printf(\西园：坐落华山学生区。分为三层，第一层和第二层为学生餐厅，第三层为自助餐。\\n\\n\ case 5:

printf(\东区运动场：是华农全校最大设施最先进齐全的运动场，平时各类体育比赛都在这里进行。\\n\\n\ case 6:

printf(\树木园：面积宽广，里面有众多珍贵树种。\\n\\n\ case 7:

printf(\竹园：校内高档宾馆，为外校嘉宾专设住宿。\\n\\n\ case 8:

printf(\新校门：华农百年校庆时建立，牌坊建筑。。\\n\\n\ case 9:

printf(\老校门：在地铁口附件，是华农重要标志之一。\\n\\n\\n\ case 10:

printf(\黑山运动场：面积不大，为研究生和老师而设立的运动场。\\n\\n\ default:

printf(\景点编号输入错误！请输入1->10的数字编号！\\n\\n\break; } }

void travgraph(vexnode g[],int n,adjmax adj) //查找指定景点信息 {

int i = 1,flag = 1,len; char ch;

printf(\请输入您要查询的景点序号:、\\n\\n\

printf(\校史馆 2.红满堂 3.行政楼 4.西园 5.东区运动场

13

\\n\

printf(\树木园 7.竹园 8.新校门 9.老校门 10.黑山运动场\\n\

printf(\你的选择是\ scanf(\ getchar();

printf(\此景点的名称是:\ Name(len);

printf(\此景点的介绍是:\ Information(len); do{

printf(\是否继续? Y/N \\n\ printf(\你的选择是：\ scanf(\ getchar();

if(ch == 'Y' || ch == 'y') {

clrscr(); flag = 1; i = 1;

printf(\请再次输入您要查询的景点序号:\\n\\n\

printf(\校史馆 2.红满堂 3.行政楼 4.西园 5.东区运动场\\n\

printf(\树木园 7.竹园 8.新校门 9.老校门 10.黑山运动场\\n\

printf(\你的选择是\ scanf(\ getchar();

printf(\此景点的名称是:\ Name(len);

printf(\此景点的介绍是:\ Information(len); continue ; } else

{ flag = 0;

printf(\请再次按回车键或者任意键加回车键返回至主菜单\

}

break; }while(1); }

void creat(Matrix_Graph *G)

14

{

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]=1; G->arcs[1][9]=7;

G->arcs[2][1]=1; G->arcs[2][3]=2; G->arcs[2][4]=9; G->arcs[2][9]=6;

G->arcs[3][2]=2; G->arcs[3][4]=7; G->arcs[3][7]=3; G->arcs[3][9]=4; G->arcs[3][10]=15; G->arcs[4][2]=9; G->arcs[4][3]=7;

G->arcs[4][6]=25; G->arcs[4][10]=22; G->arcs[5][6]=6; G->arcs[5][7]=18; G->arcs[5][8]=10; G->arcs[6][4]=25; G->arcs[6][5]=6; G->arcs[6][7]=2; G->arcs[6][10]=9;

G->arcs[7][6]=2; G->arcs[7][3]=3; G->arcs[7][5]=18; G->arcs[7][8]=5; G->arcs[7][10]=10; G->arcs[8][5]=10; G->arcs[8][7]=5; G->arcs[8][9]=9; G->arcs[9][1]=7; G->arcs[9][2]=6; G->arcs[9][3]=4; G->arcs[9][8]=9;

G->arcs[10][3]=15; G->arcs[10][4]=22; G->arcs[10][6]=9; G->arcs[10][7]=10; 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) {

15

t=MAX;

for(i=1;i<=N;i++)

if(flag[i]&&G->arcs[s][i]

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=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(%d)\ j=1;

while(r[e][j]!=0) {

printf(\ printf(\}

int main() {

int i,j;

Matrix_Graph G; creat(&G); int n = 0;

vexnode g[MAX]; EdgeType e[MAXedg]; adjmax adj;

char choice = 'x'; while(1)

16

{

clrscr();

printf(\校-园-导-游***\

printf(\ printf(\华农校园地图:\\n\\n\ printf(\华农景点信息:\\n\\n\

printf(\查找两点间最短路径:\\n\\n\ printf(\退出\\n\\n\

printf(\ printf(\华南农业大学校训：修德 博学 求实 创新\\n\

printf(\ printf(\请输入你的选择(0-3): \ choice = getchar();

switch(choice) {

case '1': clrscr();

printf(\华-----农-----地-----图-----\\n\\n\

printf(\西园> . . . . . . . . . . <10.黑山运动场>\\n\

printf(\. . \\n\

printf(\. . \\n\

printf(\ . \\n\

printf(\ . \\n\

printf(\. . \\n\

printf(\校史馆>...<2.红满堂>..<3.行政楼> . . \\n\

printf(\<6.树木园> \\n\

printf(\. . \\n\

17

printf(\ . \\n\

printf(\竹园> . . . . .. . . . \\n\

printf(\<5.东区运动场> \\n \

printf(\ . \\n\

printf(\ .\\n \

printf(\ . \\n\

printf(\老校

门> . . . . \\n \

printf(\新校门>\\n\\n\ printf(\输入任意键返回菜单\ getchar(); getchar(); break; case '2': clrscr();

travgraph(g,n,adj); getchar(); break; case '3': clrscr();

printf(\华-----农-----地-----图-----\\n\\n\

printf(\西园> . . . . . . . . . . <10.黑山运动场>\\n\

printf(\. . \\n\

printf(\. . \\n\

printf(\ . \\n\

18

printf(\ . \\n\

printf(\. . \\n\

printf(\校史馆>...<2.红满堂>..<3.行政楼> . . \\n\

printf(\<6.树木园> \\n\

printf(\. . \\n\

printf(\ . \\n\

printf(\竹园> . . . . .. . . . \\n\

printf(\<5.东区运动场> \\n \

printf(\ . \\n\

printf(\ .\\n \

printf(\ . \\n\

printf(\老校

门> . . . . \\n \

printf(\新校门>\\n\\n\

printf(\你现在的位置是（请输入1-10）：\\n\

printf(\校史馆 2.红满堂 3.行政楼 4.西园 5.东区运动场\\n\

printf(\树木园 7.竹园 8.新校门 9.老校门 10.黑山运动场\\n\

printf(\你的输入是：\ scanf(\ getchar();

printf(\你想要去的地方是（请输入1-10）：\\n\

19

printf(\校史馆 2.红满堂 3.行政楼 4.西园 5.东区运动场\\n\

printf(\树木园 7.竹园 8.新校门 9.老校门 10.黑山运动场\\n\

printf(\你的输入是：\ scanf(\ getchar(); path(&G,i,j); getchar(); creat(&G); do{

printf(\是否继续查询啊? Y/N\ char ch; int flag=1;

scanf(\ getchar();

if(ch == 'Y' || ch == 'y') {

flag = 1; i = 1;

printf(\你现在的位置是（请输入1-10）：\\n\ scanf(\ getchar();

printf(\你想要去的地方是（请输入1-10）：\\n\ scanf(\ getchar(); path(&G,i,j); getchar(); creat(&G); continue ; } else

flag = 0; break; }while(1); break; case '0': clrscr();

printf(\按任意键退出!--------\\n\\n\ printf(\谢谢您的使用!--------\\n\ getchar(); exit(0); break; default:

20

}

printf(\输入错误,请重新输入0-3之间的数字:\\n\ getchar(); break; } }

getchar();

21

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