校园导航系统 农夫过河问题 图的遍历演示 数据结构课程设计（实验报告）

广东技术师范学院天河学院

数据结构与算法 课程设计报告

题 目: 校园导航系统

农夫过河问题 图的遍历演示

学 号: 23 27____28 32 ___ __ 班 级: 移动121____ ____ _ __

小组成员:_李俊、刘锦浩、刘钦锐、潘文伟_ 指导教师: 蔡柳萍 所属系部: 计算机科学与技术系

目录

题目一：农夫过河 .............................................................................................. 3

一、问题描述 ............................................................................................... 3 二、基本要求 ............................................................................................... 2 三、算法思想 ............................................................................................... 2 四、数据结构 ............................................................................................... 2 五、模块划分 ............................................................................................... 3 六、源程序 ................................................................................................... 6 七、测试数据 ............................................................................................... 7

1）运行测试 ........................................................ 错误！未定义书签。

题目二：校园导航 .............................................................................................. 7

一、问题描述 ............................................................................................... 8 二、基本要求 ............................................................................................... 8 三、算法思想 ............................................................................................... 8 四、模块划分 ............................................................................................... 8 五、源程序 ................................................................................................. 10 六、运行及测试情况 ................................................................................. 17 题目二：图的遍历演示 ...................................................................................... 6

一、问题描述 ............................................................................................... 6 二、基本要求 ............................................................................................... 6 三、算法思想 ............................................................................................... 6 四、模块划分 ............................................................................................... 6 五、源程序 ................................................................................................... 9 六、运行及测试情况 ................................................................................. 27

1、主界面 ............................................................................................ 27 2、输入信息运行测试（部分数据） ................................................ 29 3、运行测试 ........................................................................................ 30

课程设计总结 .................................................................................................... 33

1

题目一：农夫过河

一、问题描述

有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？

二、基本要求

1）编程实现农夫过河的过程；

2）执行结果中要体现过河的先后顺序

界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。

存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构

三、算法思想

求解这个问题的简单的方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。例如整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。 现在问题变成：从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫，要求在序列中不出现重复的状态。

四、数据结构

实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索， 另一种是深度优先(depth_first) 搜索。本书只介绍在广度优先搜索方法中采用的数据结构设计。 广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。要实现广度优先搜索，可以使用队列。把下一步所有可能的状态都列举出来，放在队列中，再顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里??。由于队列的操作遵循先进

2

先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。这样，具体算法中就需要用一个整数队列moveTo，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态（二进制0000 －1111）一共16种，所以可以构造一个包含16个元素的整数顺序表来实现。顺序表的第i个元素记录状态i是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，把这个顺序表叫做route。route的每个分量初始值均为-1。route的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最后可以利用route顺序表元素的值建立起正确的状态路径。于是得到农夫过河问题的广度优先算法。在具体应用时，采用链队和顺序队均可，为叙述的方便，不妨设为使用顺序队。

五、模块划分

1、void BA() //农夫从B岸到A岸 2、void xu() //初始化三样东西的位置 3、void f() //判断农夫的位置 4、int g() //判断羊的位置 5、void huan () //农夫返回

6、void AB() //农夫从A岸到B岸

六、源程序

#include int s[100],t=0;

void BA(int a[4],int b[4]); void xu(int a[4]) { int i,j,k; for(i=0;i<3;i++) for(j=i+1;j<4;j++)if(a[i]

int f(int a[4],int x) { int i,j=0,b[4]; for(i=0;a[i];i++) { if(i==x)continue; b[j]=a[i]; if(j&&b[j]==b[j-1]-1)return 1; return 0;} int g()

a[j]=k;

j++; }

3

{ int i,r; for(i=t-1;i>=t/2;i-=2) { for(r=0;r

if(r==t-i)break; }

if(i

void huan(int a[4],int b[4],int x) { int i; for(i=0;a[i]!=x;i++); a[i]=0; b[3]=x; xu(a); xu(b);}

void AB(int a[4],int b[4]) { int i; for(i=0;a[i-1]||i==0;i++) { if(f(a,i)) continue;

s[t]=a[i]; if(g()) continue;

huan(a,b,s[t]); t++; if(a[0]==0) break; BA(a,b); if(a[0]==0) break;

t--; huan(b,a,s[t]); } }

void BA(int a[4],int b[4]) { int i; for(i=0;b[i-1]||i==0;i++) { if(f(b,i)) continue; s[t]=b[i]; if(g()) continue;

huan(b,a,s[t]); t++; AB(a,b); if(a[0]==0) break;

t--; huan(a,b,s[t]); }}

4

for(j=1;j<=Num;j++) { shortest[i][j]=edge[i][j]; path[i][j]=0;

}

}

for(k=1;k<=Num;k++) { for(i=1;i<=Num;i++) { for(j=1;j<=Num;j++) { if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) { shortest[i][j]=(shortest[i][k]+shortest[k][j]); path[i][j]=path[j][i]=k;

}

}

}

}

}

void way(int i,int j)/*最短路径的输出*/ { int k=0,a=i,b=j;

if(shortest[i][j]!=Maxedge) { printf(\从%s到%s的最短路径为:\\n\ printf(\ while(path[i][j]!=0) {

k=path[i][j];

15

}

}

}

while(path[i][k]!=0) { }

printf(\到-%s\i=k;

k=path[i][k];

printf(\到-%s;\\n\

printf(\最短距离为：%d米。\\n\

printf(\数据均为测试数据，与实际有误差，敬请谅解.\\n\\n\

else

printf(\你的输入有误，请输入数字为0-13，中间用空格隔开！\

void shortestpath()/*寻找最短路径*/ {

int i=0,j=0; while(1) {

printf(\请输入要查询的两点的编号（范围为0-13，中间用空格间隔）\\n否则需要重启本系统：\ }

int main()/*主函数*/

16

}

scanf(\if(i<=Num&&i>0&&j<=Num&&j>0) { }

floyd(); way(i,j); return ;

{ char i;

printf(\欢迎使用广东技术师范学院天河学院导航系统(个人版）\\n\\n\ init();

map();/*输出地图，提示使用者*/ while (1) { i=menu(); switch(i) { case 's':shortestpath();break;

case 'i':information();break;

case 'e':printf(\谢谢使用!\\n\\n\\t 么建议可以发送邮箱到：827655592@qq.com\ default :printf(\输入错误！\\n\

}

}

}六、运行及测试情况 1、主菜单界面

对本系统有什17

18

地图通过文本保存，运行时再调用 2、运行测试

1）信息查询测试：

19

printf(\请输入%d个顶点的信息:\注意输入的时候空格隔开每个顶点之间 for(i=0;iv;i++) {

scanf(\读入顶点信息*/ s->adjlist[i].firstarc=NULL; /*边表置为空表*/ }

for(i=0;ia;i++) {

printf(\输入第%d条边(起点序号，终点序 号):\ scanf(\输入无序对 顶点编号0开始 p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=n;

p->nextarc=s->adjlist[m].firstarc; s->adjlist[m].firstarc=p;

p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=m;

p->nextarc=s->adjlist[n].firstarc; s->adjlist[n].firstarc=p; } }

void print(algraph s)//输出邻接表的和结构 {

ArcNode *p; int i;

for(i=0;i

printf(\

printf(\p=s.adjlist[i].firstarc; while(p) {

printf(\p=p->nextarc; }

printf(\} }

int visited[MAX];//用来表示是否访问过

25

void dfs(algraph s,int i)/*以vi为出发点对邻接表表示的图g进行深度优先遍历*/ {

ArcNode *p;

printf(\访问顶点 : %c \\n\访问顶点i*/ visited[i]=1;

p=s.adjlist[i].firstarc;

while (p) /*从p的邻接点出发进行深度优先搜索*/ { if (!visited[p->adjvex]) dfs(s,p->adjvex);

p=p->nextarc;//找指向下一条弧的指针 } }

void dfstraverse(algraph s) { int i;

for (i=0;i

visited[i]=0; /*初始化标志数组*/ for (i=0;i

if (!visited[i]) /*vi未访问过*/ dfs(s,i);//函数的递归的使用 }

int visit[MAX];//用来表示是否访问过 void bfs(algraph s)//广度优先遍历函数 {

int i,k; Queue q; ArcNode *p;

for(i=0;i

InitQueue(&q); for(i=0;i

printf(\访问顶点:%c \\n\visit[i]=1;

Enqueue(&q,i);

while (!emptyQueue(&q)) {

26

DEQueue(&q,&k); p=s.adjlist[k].firstarc; while (p) {

if (!visited[p->adjvex]) {

printf(\访问顶点:%c \\n\visited[p->adjvex]=1; Enqueue(&q,p->adjvex); }

p=p->nextarc; } } } }

void main() {

algraph s;

Buildalgraph(&s); print(s);

printf(\深度优先遍历:\\n\dfstraverse(s);

printf(\广度优先遍历:\\n\bfs(s); }

六、测试数据

1）主界面：

27

28

2、输入信息运行测试（部分数据）

29

3、运行测试

30

31

课程设计总结

首先，虽然我们是一个4人的小组完成的，但是我们的分工很明确，各司其职。 通过为期一周的课程设计，我对《数据结构》这门课程有了更深一步的了解。虽然是应用C语言来编写程序，但却深刻的体现了数据结构对编程的重要性。

这次课程设计运用C语言与数据结构知识，编写一个运动会分数统计系统。其中遇到了不少问题，平时自己在编写一些普通常见的程序时只是运用单一的知识而课程设计却需要将各个方面的内容联系结合，例如文件与程序的结合，输入、输出、统计、查找的综合应用等，因此真正的程序设计必须先有一个正确的算法思想，运用正确的数据结构和编程语言，灵活的运用并联系几个方面的内容。通过课设也使我认识到，要学好编程，仅学习书本上的知识是不够的，还要有较强的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。

32

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