数据结构课程设计报告-迷宫求解

------迷宫问题求解 学号：1315925375 姓名：刘晓龙 班级：13移动1班 指点先生：钱鸽

目次

一.需求剖析1 二.数据构造 2

1. 数据构造设计斟酌 2 2. 逻辑构造存储构造 3 三.算法设计 3 四.调试剖析 8

五.程序实现及测试 8 六.领会及缺少之处 9 七.参考文献 9 八.源代码10

一.需求剖析

本课程设计是解决迷宫求解的问题,从进口动身,顺某一偏向向前摸索,若能走通,则持续往前走;不然沿原路退回,换一个偏向再持

续摸索,直至所有可能的通路都摸索到为止.为了包管在任何地位上都能沿原路退回,显然须要用一个落后先出的构造来保管从进口到当前地位的路径.是以,在求迷宫通路的算法中要运用“栈”的思惟假设“当前地位”指的是“在搜刮进程中的某一时刻地点图中某个方块地位”,则求迷宫中一条路径的算法的根本思惟是：若当前地位“可通”,则纳入“当前路径”,并持续朝“下一地位”摸索,即切换“下一地位”为“当前地位”,如斯反复直至到达出口;若当前地位“不成通”,则应顺着“来向”退回到“前一通道块”,然后朝着除“来向”之外的其他偏向持续摸索;若该通道块的周围4个方块均“不成通”,则应从“当前路径”上删除该通道块.所谓“下一地位”指的是当前地位周围4个偏向（上.下.左.右）上相邻的方块.假设以栈记载“当前路径”,则栈顶中存放的是“当前路径上最后一个通道块”.由此,“纳入路径”的操纵即为“当前地位入栈”;“从当前路径上删除前一通道块”的操纵即为“出栈”.

二.数据构造

1. 数据构造设计斟酌

1) 树立一个二维数组暗示迷宫的路径（0暗示通道,1暗示墙壁）;

2) 创建一个栈,用来存储“当前路径”,即“在搜刮进程中某

一时刻地点图中某个方块地位”. 2. 逻辑构造存储构造

1) 创建一个Int类型的二维数组int maze[n1][n2],用来存放0和1 （0暗示通道,1暗示墙壁）;

2) 创建一个构造体用来储存数组信息构造体： typedef struct//迷宫内部设置 {

int shu[16][16]; int row; int col; }Maze;

创造一个链栈 struct node {

int row; int col;

struct node *next; };

三.算法设计

起首,创建数组的大小,此数组大小请求用户本身输入.具体算

法：

printf(\"输出神宫的外形!\\n\"); scanf(\"%d%d\ Maze m;

CreatInit(&m,x,y); 函数：

void CreatInit(Maze *m,int x,int y)//创建迷宫 {

printf(\"please input number:\\n\"); int i,j;

for(i=0;i<=x;i++) {

for(j=0;j<=y;j++) m->shu[i][j] = 2; }

for(i=1;i<=x;i++) for(j=1;j<=y;j++)

scanf(\"%d\ m->row = x; m->col = y; }

个中的0和1分离是暗示通路和障碍,界说的数组其实就是迷宫的

设计图

其次,产生迷宫,算法：

for(i=1;i<=x;i++) {

for(j=1;j<=y;j++)

printf(\"%d\\ printf(\"\\n\"); }

最后,迷宫寻路,在寻路的时刻,我们应从输入的进口地位进出神宫,当迷宫的进口处有障碍或者出口被堵,再或者没有通路时全部程序停止,并输出迷宫无解的提醒.假如迷宫求解进程中没有消失无解情形,那么在求解的进程中,会输出迷宫的通路路径,并且输出坐标值,让运用者更清晰路径的走法.在寻路的进程中,每走过一个格,谁人格得知就会被赋值为-1,用来标识表记标帜此处已走过,免除了来往返回的重走,以免消失逝世轮回,如许程序就能从进口进入到迷宫当中.假如在迷宫当中没有通路的话,可以停止轮回输出“迷宫无解！”,则当迷宫假如消失有解时,就会输出路径.如许就简略的实现了,有解无解的输出.从而实现了请求的程序！代码如下：

while((x1 >= 1 && x1 <= x) || (y1 >= 1 && y1 <= y)) {

if(x1 == x2 && y1 == y2)

{ break; }

if(m.shu[x1][y1+1] == 0 ) {

y1=y1+1; push(x1,y1);

m.shu[x1][y1] = -1; continue; }

if(m.shu[x1-1][y1]==0 ) {

x1=x1-1; push(x1,y1);

m.shu[x1][y1] = -1; continue; }

if(m.shu[x1][y1-1]==0 ) {

y1=y1-1; push(x1,y1);

m.shu[x1][y1]= -1;

continue; }

if(m.shu[x1+1][y1]==0 ) {

x1=x1+1; push(x1,y1);

m.shu[x1][y1]= -1; continue; } pop();

if(p->next==NULL) break; x1=p->row; y1=p->col; }

if(x1 == x2 && y1 == y2) {

while(p->next != NULL) {

printf(\"%d %d\\n\ pop(); }

} else

printf(\"No Answer !!!\");

个中要追求所有的通路,在这里则运用了一个while轮回,如许可以找到所有的通路. 图解剖析： 整体流程图：

迷宫内部操纵流程图：

四.调试剖析

第一个问题,在刚开端的调试进程中,我们碰到了,无法断定走过的旅程,从而消失了逝世轮回,导致程序不克不及正常进行,但是经由我们的评论辩论,我们想出用标识表记标帜的办法来解决,也就是让走过的旅程全给标示了,如许就不会再走反复的路.

第二个问题,就是性用菜单来实现操纵,那样程序的操纵性就会更强,所以我们就要把所有的办法,给写成一个个的函数来挪用,如许就碰到了参量传递的问题,但是经由我们的参考以及从书本上的实例,我们慢慢地更深的懂得到了参量传递的运用,那么这个问题也就水到渠成了.从此我们实现了菜单操纵！

五.程序实现及测试 运行界面：

开端界面

六.领会及缺少之处

经由过程此次课程设计,是我对于数据构造有了更深的懂得,更新的熟悉.数据构造是一门主要的课程,只稀有据构造学得扎实了,才干对于盘算机有更深的运用,所以学好数据构造是很主要的.经由两周的上机设计,我实现了简略的迷宫求解,可以或许简略的实现求解进程.但是还消失着缺少之处,本程序不克不及轮回履行,只能履行一次.有待改良！

七.参考文献

1.《 数据构造(c说话版) 》严蔚敏 清华大学出版社

2.《 数据构造试验教程 》李业丽.郑良斌 《 数据构造 》高教出版社

3.《 数据构造习题 》李春保 清华大学出版社 4.《 数据构造习题 》严蔚敏 清华大学出版社

5.《 C说话与数据构造 》王立柱 清华大学出版社

6.《 数据构造(C说话篇)习题与解析》 李春保 清华大学出版社.

八.源代码

#include #include

typedef struct//迷宫内部设置 {

int shu[16][16]; int row; int col; }Maze; struct node {

int row; int col;

struct node *next; };

struct node *p;

void push(int x1,int y1) {

struct node *a;

a=(struct node *)malloc(sizeof(struct node)); a->row=x1;

a->col=y1; a->next=p; p=a; }

void pop(void) {

struct node *q; q=p;

p=p->next; free(q); }

void CreatInit(Maze *m,int x,int y)//创建迷宫 {

printf(\"please input number:\\n\"); int i,j;

for(i=0;i<=x;i++) {

for(j=0;j<=y;j++) m->shu[i][j] = 2; }

for(i=1;i<=x;i++) for(j=1;j<=y;j++)

scanf(\"%d\ m->row = x; m->col = y; }

void menu() {

printf(\"\\n*************************\\n\"); printf(\"迎接进出神宫\\n\"); printf(\"1.进出神宫\\n\"); printf(\"2.退出\\n\"); }

int main(void) { int t; int x,y; int x1,y1; int x2,y2; int i,j; while(1) {

menu();

printf(\"请选择:\");

scanf(\"%d\ if(t == 2) break;

printf(\"输出神宫的外形!\\n\"); scanf(\"%d%d\ Maze m;

CreatInit(&m,x,y); for(i=1;i<=x;i++) {

for(j=1;j<=y;j++)

printf(\"%d\\ printf(\"\\n\"); }

printf(\"输入进口地位:\"); scanf(\"%d%d\ printf(\"输入出口的地位:\"); scanf(\"%d%d\

p=(struct node *)malloc(sizeof(struct node)); p->row=0; p->col=0; p->next=NULL; push(x1,y1);

while((x1 >= 1 && x1 <= x) || (y1 >= 1 && y1 <= y)) {

if(x1 == x2 && y1 == y2) { break; }

if(m.shu[x1][y1+1] == 0 ) {

y1=y1+1; push(x1,y1);

m.shu[x1][y1] = -1; continue; }

if(m.shu[x1-1][y1]==0 ) {

x1=x1-1; push(x1,y1);

m.shu[x1][y1] = -1; continue; }

if(m.shu[x1][y1-1]==0 ) {

y1=y1-1; push(x1,y1);

m.shu[x1][y1]= -1; continue; }

if(m.shu[x1+1][y1]==0 ) {

x1=x1+1; push(x1,y1);

m.shu[x1][y1]= -1; continue; } pop();

if(p->next==NULL) break; x1=p->row; y1=p->col; }

if(x1 == x2 && y1 == y2) {

while(p->next != NULL) {

printf(\"%d %d\\n\ pop(); } } else

printf(\"No Answer !!!\");}

return 0; }