自己写的链栈实现的迷宫算法，发帖纪念下...

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

int m,n;
int **maze = NULL; //表示迷宫

struct Element{            //这里就是定义节点 
int i;
int j;
int di;
};

typedef struct LinkStack {        //这里就是定义链栈...
struct Element element;
struct LinkStack * next;
struct LinkStack * prior;
}LinkStack;


LinkStack *top = NULL; //栈顶指针,因为是链栈，所以栈顶指针要是一个指针变量
LinkStack *head = NULL; //链栈的头指针

int count=1;        //路径计数


void printMaze(int ** maze)      //输出迷宫
{
int i,j;
printf("您确定的迷宫图如下所示:\n");
for(i=0; i<m+2; i++) {
for(j=0; j<n+2; j++) {
printf("%4d",maze[i][j]);
}
printf("\n");
}
}

void addWall(int ** maze) //给迷宫加墙
{
int i,j;
for(i=0; i<m+2; i++)
{
for(j=0; j<n+2; j++) {
if(i==0){
maze[i][j] = 1;
}
if(i>0 && i<(m+2-1)) {
maze[i][0]=1;
maze[i][n+2-1]=1;
break;
}
if(i==m+2-1) {
maze[i][j]=1;       
}
}
}
}

int ** initMaze() { //对迷宫进行初始化的函数
int i,j;
int flag = 0;
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
//是在给maze分配内存的时候有点点问题
maze = (int **)malloc(sizeof(int *) * (m+2));  //开辟迷宫的存储空间
for(i=0; i<n+2; i++)
{
*(maze+i) = (int *)malloc(sizeof(int)*(n+2));     
}

addWall(maze); //给迷宫加墙

printf("\n请输入迷宫的各行各列(注意:最后一个数需要是0):\n用空格隔开,0代表路,1代表墙\n"); //保证出口是路，所以最后一个数要是0
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++) {
scanf("%d",&maze[i][j]);
}
}
printf("你输完了\n");

printMaze(maze);                   //输出迷宫图

return maze;
}

void mazePath() {
if(top == head && head != NULL)   //终止递归的条件
{
return;
}
int k = 0;
int find = 0;
int i = 0,j=0;
int di = -1;
if(top != NULL)di=top->element.di; //di一开始就保存当前栈顶指针所指的节点的方向

LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack));  //每一次递归都首先开辟节点(因为要查找元素，所以要先开辟节点）
node->element.di = di;
if(top == NULL)
{

head = (LinkStack *) malloc(sizeof(LinkStack)); //链表的头指针
head->element.i = 1;
head->element.j = 0;
head->element.di = 1;
head->prior = NULL;
top = head;
node->element.i = 1;
node->element.j = 1;
node->element.di = -1;
}
top->next = node;
node->next = NULL;
node->prior = top;

top = node;
di = top->element.di;//取得当前栈顶指针所指的元素的方向
while(di<4 && find == 0)
{
di++;
switch(di)
{
case 0: i = top->prior->element.i - 1;j = top->prior->element.j;break;
case 1: i = top->prior->element.i;j = top->prior->element.j + 1;break;
case 2: i = top->prior->element.i + 1;j = top->prior->element.j;break;
case 3: i = top->prior->element.i;j = top->prior->element.j - 1;break;

}
if(maze[i][j] == 0)find = 1;
}
if(i == m && j == n) 
{
top->element.i = m;
top->element.j = n;
top->prior->element.di = di;
printf("%4d:",count++);
LinkStack * n = head->next;
while(n != NULL)
{
printf("(%d,%d)  ",n->element.i,n->element.j);      //找到出口，输出路径
if((k + 1)%5 == 0)
{
printf("\n\t");
}
k++;
n = n->next;
}
printf("\n");
maze[top->element.i][top->element.j] = 0;
top = top->prior; //退栈
free(node);
mazePath();
}else {
if(find == 1)
{
top->prior->element.di = di;//退栈时，当找到下一个可走的节点后必须对当前节点的方向进行了更新
top->element.i = i;
top->element.j = j;  
top->element.di = -1;
maze[i][j] = -1;   //避免重复走到该点
mazePath();
}
else
{
maze[top->prior->element.i][top->prior->element.j] = 0;//让它成为下条路径的可走路径
top = top->prior->prior;         //退栈  
free(node);
mazePath();
}
}
}

void main() {
int i,j;
initMaze();
printf("您确定的迷宫图如下所示:\n");
printf("迷宫所有路径如下:\n");
mazePath(); 
if(maze != NULL)         //释放开辟的所有内存空间
{
for(i=0;i<m+2;i++) //因为maze是二级指针，所以在释放maze所指的内存空间时，要先释放maze上的一级指针
{
free(maze[i]);
}
free(maze);
}
if(head != NULL)        //释放内存
{
free(head);
}
return;
}

评论

1 楼 yuxingfirst 2010-10-01  

补充：上面程序中的“//是在给maze分配内存的时候有点点问题”这个注释是多余的，因为在
发帖是LZ已经修正了所有的错误！！！