Question

用栈操作算法实现探索迷宫过程

尽量代码短一点，= =

Answer 1

1，设计堆栈抽象数据类型定义：
ADT栈{

数据对象：D = {AI | AI∈的CharSet，I = 1,2 ...，n}的

数据关系：R1 = { | AI-1，AI∈D，I = 1,2，...，n}的

基本操作：（这里只是用来操作这个称号）

科瑞（）

结果：建立一个空栈。

推（）

结果：将堆栈中的一个新元素。

流行（）

结果：栈顶元素弹出。 。是

空（）

判断栈空

} ADT栈

2本程序由三个模块组成

1）主要模块：

无效主要（）

{

输入开始和结束;

处理命令;

输出;

2）堆栈模块-----实现栈的抽象数据类型

3）模块-----迷宫中寻找路径的迷宫

3解决路径迷宫伪代码

默认设置当前位置为入口位置：

做{

如果当前位置可以通过，

在{插入当前位置的堆栈; / /进入

路径如果位置输出，输出迷宫结束; / /获取存储在堆栈否则切换东块的当前位置到新的当前位置;

否则，如果堆栈不为空，并有其他方向堆栈中的位置未开发的，

新的当前位置设置以顺时针方向旋转，以寻找下一个堆栈位置相邻块;

如果栈不为空，但周围的堆栈位置的顶部是不可通约的，

然后{删除堆栈中的位置; / /退后一步，从路径中删除通道

如果堆栈不为空，则重新测试新的堆栈位置，

直到它找到一个相邻块或通过堆叠栈空;

}而（堆栈不为空）

（堆栈为空说明路径不存在）

2。详细设计

协调立场迷宫型

typedef结构迷宫{

诠释一个;

整数b;

诠释目录;

结构迷宫*未来;

} mazestack;的堆栈实现

1）堆栈初始化

mazestack *科瑞（）{

mazestack * P基本操作;

P =（mazestack *）malloc的（的sizeof（mazestack））; / /打开坐标空间

返回NULL（对！）; / /打开失败，则返回null

P->接下来= NULL;

回报磷; / /返回堆栈指针

}

2）的压栈操作

mazestack *推（mazestack * P，INT I，诠释J，诠释K）/ / p是堆栈指针

I，J的坐标参数，k是下一个路径的方向代码

{

mazestack * p1的;

P1 =（mazestack *）malloc的（的sizeof（mazestack））; / /打开坐标空间

返回NULL（P1！）;

P1-> A = 1;

P1-> B = j的;

P1-> DIR = K; / /导入参数坐标空间

P1->下一个= P; / /新的开放空间到堆栈

P = P1; / /将堆栈指针到新的堆栈

回报磷; / /返回堆栈指针}

3）弹出操作

mazestack *弹出（mazestack * P，诠释*我，诠释*，诠释* K）/ / p是堆栈指针， I，J的坐标参数，k为路径上的下方向代码

{

mazestack * p1的;

P1 = P;

* I = P1-> A;

* J = P1-> B; / /的空间坐标和派生

P = P->接下来的方向代码;;

* K = P1->输入dir / /将被移动到新的堆栈指针堆栈中的位置

免费（P1）; / /释放旧的堆栈空间

回报磷;

4）判断栈空

整数空（mazestack * P）/ / p是一个指针来进行判断

{

如果（对 - >下一个== NULL）{

返回1; / /堆栈为空，则返回1

} 否则返回0; /堆栈不为空，则返回0

}

改变路径前进方向

整数nextpos（INT *我，诠释*，诠释二）/ / I，J迷宫坐标，二路径在方向 {

开关（二）{

案例1：* I = * I; * J = *+1;打破; / / DI = 1，旁边的东

案例2：* I * = I +1; * J = *焦耳;打破; / / DI = 2，旁边的南

案例3：* I = * I; * J = * J-1;打破; / / DI = 3，旁边的西

案例4：* I * = I-1; * J = *焦耳;打破; / / DI = 4，旁边的北

}

返回1;

寻找迷宫路径算法

mazestack *迷宫（INT I1，J1整型，整型I2，诠释J2）/ / I1，J1坐标的入口处，I2，J2出口坐标 BR /> {

的int a [10] [10] = {0,0,0,0,0,0,0，0,0,0，

0,1,1,0， 1,1,1,0,1,0，

0,1,1,0,1,1,1,0，1,0，

0,1,1,1,1， 0,0,1,1,0，

0,1,0,0,0,1,1,1,1，0，

0,1,1,1,0,1， 1,1,1,0，

0,1,0,1,1,1,0,1,1,0，

0,1,0,0,0,1,0， 0,1,0，

0,0,1,1,1,1,1,1,1,0， 0,0,0,0,0,0,0,0， 0,0}; / /混凝土迷宫形式

INT I = I1，J = J1;

整数K表; mazestack * P;

P =科瑞（）; / /建立堆叠

做{

如果（A [I] [J] == 1）{/ /判断路径是否已经

A [I] [J] = 5; / /有没有，那么明显

P =推（P，I，J，A [I] [j]的）的坐标; / /该点的入堆栈

坐标倘（i == I2 &&== J2）{/ /确定终点坐标是否推

就（i = 0; I <10; i + +）{

为（J = 0;<10; J + +）{

如果（A [I] [J]> 1）{

一[I] [ J] = 5;

的printf（“％d个”，一个由[i] [j]的）;

其他的printf（“％d个”，一个由[i] [j]的）;

的printf（“\ n \ n已”）;

} / /结束点的坐标被压入迷宫图的输出，其中路径是5

回报磷; / /返回堆栈指针

}

nextpos（＆I＆J，1）; / /压入坐标不是终点，将坐标点东移一步

} 其他{/ /路径已经

如果{

P =流行（P，＆我，＆J＆K）（空（P））！; / /退后一步

一个由[i] [j]的= K; （！一个由[i] [j]的== 4 &&空（P））

同时/ /判断是否有途径围绕

该坐标{

一个由[i] [j]的= 1;

P =流行（P，＆I，＆J＆K）;

A [I] [J] = K; / /没有路径，重新设置它的坐标是没有办法穿过去，返回到上一步

}

如果（一个由[i] [j]的<4）{

一[I] [J] + +;

P =推（P，I，J，A [I] [J]）;

nextpos（＆I＆J，A [I] [J]）;

} / /路径存在，那么接下来的方向

否则，如果（A [I] [J]> 4）{

A [I] [J] = 2;

P =推（P，I，J，A [I] [J]）;

nextpos（＆I＆J，A [I] [J]）;

} / /只有时间的流逝之后，下一步去南方

}

}

}而（空（P）！）;

返回NULL;

主函数算法

的main（）

{

整数I1，I2，J1，J2;

整数M，N，L;

整型数= 0;

mazestack *马;

printf（“请输入起始点\ N”的）;

的scanf（“％d个，为％d”，＆I1，J1＆）; / /输入起点

printf（“请输入终点的\ n”）;

的scanf（“％d个，为％d”，＆I2，＆J2）; / /输入端

MA =迷宫（I1，J1，I2，J2）; / /求解迷宫

如果（马== NULL）{

printf（“请没有办法”）;

} / /空栈，这表明没有路径

其他{

同时（empty!（MA））{

MA =流行（MA，＆M，＆N ，＆L）;

printf（“请（％1，％D）”，M，N）;

数+ +;

} / /输出路径的结果和步

printf（“请步骤为％d”，NUM）;

这应该是能够读取它喽根据自己的需要，你可以改变某些部分

追问

明显复制的，而且说是要简单的，这个是报告，不是代码

Answer 2

//请叫我雷锋！

#include <stdio.h>
#include <stdlib.h>

#define m 6 //迷宫行数
#define n 8 //迷宫列数

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT //存储空间分配增量

typedef struct{
int x,y,d;
}SElemType;

typedef struct {
SElemType stack[STACK_INIT_SIZE];
int top;
}SqStack;

typedef struct {
int x,y;
}Item;

SElemType XX = {-1,-1,-1};
int maze[m + 2][n + 2] = {
// 0 1 2 3 4 5 6 7 8 9
/*0*/ {1,1,1,1,1,1,1,1,1,1,},
/*1*/ {1,0,1,1,1,1,0,1,1,1,},
/*2*/ {1,1,0,1,0,1,1,1,1,1,},
/*3*/ {1,0,1,0,0,0,0,0,1,1,},
/*4*/ {1,0,1,1,1,0,1,1,1,1,},
/*5*/ {1,1,0,0,1,1,0,0,0,1,},
/*6*/ {1,0,1,1,0,0,1,1,0,1,},
/*7*/ {1,1,1,1,1,1,1,1,1,1,},
};

Item moves[8] = {{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}};

int Empty_SqStack(SqStack *s){
//判断栈是否为空。
if (s->top == -1) {
return 1;
} else {
return 0;
}
}

SElemType Gettop_SqStack(SqStack *s){
//取栈顶元素。栈空时不能出栈，返回特殊值XX；否则返回栈顶元素
if (s->top == -1) {
return XX;
} else {
return s->stack[s->top];
}
}

SElemType Pop_SqStack(SqStack *s){
if (Empty_SqStack(s)) {
printf("\n栈为空！");
exit(0);
} else {
s->top --;
return s->stack[s->top + 1];
}
}

void Push_SqStack(SqStack *s, SElemType x){
//将元素x压入栈s中。要求：栈满时，提示栈满信息，完成入栈操作则返回。
if (s->top == STACK_INIT_SIZE - 1) {
printf("\n栈满！");
} else {
s->top++;
s->stack[s->top] = x;
}
}

//探索一条路径，成功时返回1。探索成功时，将搜索路径上的顶点放进栈S中。
int * OnePath(int maze[m + 2][n + 2], Item move[8], SqStack *s){
int x,y,d,i,j,dd;
SElemType temp;
temp.x = 1;
temp.y = 1;
temp.d = -1;
Push_SqStack(s, temp);

maze[temp.x][temp.y] = -1;
dd = 0;

while (!Empty_SqStack(s)) {
temp = Gettop_SqStack(s);
x = temp.x;
y = temp.y;
d = dd;
while (d < 8) {
i = x + move[d].x;
j = y + move[d].y;
if (maze[i][j] == 0) {//试探到活路
//把活路的位置、进入方向压入栈
temp.x = i;
temp.y = j;
temp.d = d;
Push_SqStack(s, temp);
dd = 0;//搜索方向初始化为第一个方向
maze[i][j] = -1;

if (i == m && j == n) {
return 0;
}

break;

} else {
d = d + 1;
}
}
if (d == 8) {
temp = Pop_SqStack(s);
dd = temp.d + 1;//再沿上一步的下一个方向搜索。
}
}
return 0;
}

int main(int argc, const char * argv[]) {
SElemType temp;
SqStack *s;
s = (SqStack *)malloc(sizeof(SqStack));
if (!s) {
exit(0);
} else {
s->top = -1;//初始化栈
}
OnePath(maze, moves, s);//探索一条路径
if (s->top == -1) {
printf("此迷宫无路径！");
} else {
printf("迷宫路径为：\n");
while (!Empty_SqStack(s)) {//栈非空，将栈中的元素出栈并输出。
temp =Pop_SqStack(s);
printf("%d ",temp.d);
// if (s->top == -1) {
// printf("(%d,%d)\n",temp.x,temp.y);
// }
// else{
// printf("(%d,%d)-",temp.x,temp.y);
// }
}
printf("迷宫已走出\n");
printf("请输入0来退出程序\n");
while (getchar() != '0') {
getchar();
}
}
return 0;
}