#include"stdio.h"#include"malloc.h"#include"stdlib.h"
typedef struct{int x,y;int ord;int der;}ElemType;
typedef struct{ElemType *base;ElemType *top;int stacksize;}Sqstack;
void InitStack(Sqstack &S);void Push(Sqstack &S, ElemType e);int Pop(Sqstack &S,ElemType &e);void NextPos(int *x, int *y, int der);
void InitStack(Sqstack &S){S.base=(ElemType*)malloc(sizeof(ElemType)*INIT_SIZE);if(!S.base) exit(1);S.top=S.base;S.stacksize=INIT_SIZE;}
void Push(Sqstack &S, ElemType e){if(S.top-S.base==S.stacksize){S.base=(ElemType*)malloc(sizeof(ElemType)*(INIT_SIZE+INCREMENT));S.top=S.base+S.stacksize;S.stacksize+=INCREMENT;}*(S.top++)=e;}
int Pop(Sqstack &S,ElemType &e){if(S.top==S.base) return 0;e=*(--S.top);return 1;}
void NextPos(int *x, int *y, int der){switch(der){case 1:++(*x);break;case 2:++(*y);break;case 3:--(*x);break;case 4:--(*y);break;default:break;
}}
int main(){Sqstack S;int x,y,step;ElemType e,*P;char maze[10][10]={{'#',' ','#','#','#','#','#','#','#','#'},{'#',' ',' ','#',' ',' ',' ','#',' ','#'},{'#',' ',' ','#',' ',' ',' ','#',' ','#'},{'#',' ',' ',' ',' ','#','#',' ',' ','#'},{'#',' ','#','#','#',' ',' ',' ',' ','#'},{'#',' ',' ',' ','#',' ',' ',' ',' ','#'},{'#',' ','#',' ',' ',' ','#',' ',' ','#'},{'#',' ','#','#','#',' ','#','#',' ','#'},{'#','#',' ',' ',' ',' ',' ',' ',' ','#'},{'#','#','#','#','#','#','#','#',' ','#'},
};
printf("The needed found maze are as follows:\n\n");for(x=0;x<10;x++){for(y=0;y<10;y++)printf("%c",maze[x][y]);printf("\n");}InitStack(S);P=S.base;x=0; y=1;step=1;do{if(maze[x][y]==' '){maze[x][y]='1';e.x=x;e.y=y;e.ord=step;e.der=1;
Push(S,e);if(x==9&&y==8) break;NextPos(&x,&y,1);step++;}else{if(S.base!=S.top){Pop(S,e);while(e.der==4){maze[e.x][e.y]='@';Pop(S, e);}}
if(e.der<4){e.der++;Push(S, e);x=e.x;y=e.y;NextPos(&x, &y, e.der);}}} while(S.top!=S.base);
printf("\n找到路径: 用1表示走的路，@表走的死路，#表墙: \n\n");for(x=0;x<10;x++){ for(y=0;y<10;y++)printf("%c",maze[x][y]);printf("\n");}printf("坐标表示如下：\n\n");
while(S.base!=S.top){if(P==S.base){printf("(%d,%d)", (*S.base).x, (*S.base).y);S.base++;}else{printf(" -> (%d,%d)", (*S.base).x, (*S.base).y);S.base++;}}printf("\n");
free(P);return 0;
上面划横线的地方不是很懂么1，为什么e.di==4时能判断那是死路？
                          2，P指针起什么作用？

程序整理好

#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"

typedef struct
{
int x,y;
int ord;
int der;

}ElemType;

typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}Sqstack;

void InitStack(Sqstack &S);
void Push(Sqstack &S, ElemType e);
int Pop(Sqstack &S,ElemType &e);
void NextPos(int *x, int *y, int der);


void InitStack(Sqstack &S)
{
S.base=(ElemType*)malloc(sizeof(ElemType)*INIT_SIZE);
if(!S.base) exit(1);
S.top=S.base;
S.stacksize=INIT_SIZE;
}

void Push(Sqstack &S, ElemType e)
{
if(S.top-S.base==S.stacksize)
{
S.base=(ElemType*)malloc(sizeof(ElemType)*(INIT_SIZE+INCREMENT));
S.top=S.base+S.stacksize;
S.stacksize+=INCREMENT;
}

*(S.top++)=e;
}

int Pop(Sqstack &S,ElemType &e)
{
if(S.top==S.base) return 0;
e=*(--S.top);

return 1;
}

void NextPos(int *x, int *y, int der)
{
switch(der)
{
case 1:
++(*x);
break;
case 2:
++(*y);
break;
case 3:
--(*x);
break;
case 4:
--(*y);
break;
default:
break;

}
}


int main()
{
Sqstack S;
int x,y,step;

ElemType e,*P;
char maze[10][10]=
{
{'#',' ','#','#','#','#','#','#','#','#'},
{'#',' ',' ','#',' ',' ',' ','#',' ','#'},
{'#',' ',' ','#',' ',' ',' ','#',' ','#'},
{'#',' ',' ',' ',' ','#','#',' ',' ','#'},
{'#',' ','#','#','#',' ',' ',' ',' ','#'},
{'#',' ',' ',' ','#',' ',' ',' ',' ','#'},
{'#',' ','#',' ',' ',' ','#',' ',' ','#'},
{'#',' ','#','#','#',' ','#','#',' ','#'},
{'#','#',' ',' ',' ',' ',' ',' ',' ','#'},
{'#','#','#','#','#','#','#','#',' ','#'},

};


printf("The needed found maze are as follows:\n\n");
for(x=0;x<10;x++)
{
for(y=0;y<10;y++)
printf("%c",maze[x][y]);
printf("\n");
}

InitStack(S);
P=S.base;
x=0; y=1;
step=1;
do
{
if(maze[x][y]==' ')
{
maze[x][y]='1';
e.x=x;
e.y=y;
e.ord=step;
e.der=1;

Push(S,e);
if(x==9&&y==8) break;
NextPos(&x,&y,1);
step++;

}
else
{
if(S.base!=S.top)
{
Pop(S,e);
while(e.der==4)
{
maze[e.x][e.y]='@';
Pop(S, e);
}
}


if(e.der<4)
{
e.der++;
Push(S, e);
x=e.x;
y=e.y;
NextPos(&x, &y, e.der);
}
}



} while(S.top!=S.base);

printf("\n找到路径: 用1表示走的路，@表走的死路，#表墙: \n\n");
for(x=0;x<10;x++)
{ for(y=0;y<10;y++)
printf("%c",maze[x][y]);
printf("\n");
}
printf("坐标表示如下：\n\n");

while(S.base!=S.top)
{
if(P==S.base)
{
printf("(%d,%d)", (*S.base).x, (*S.base).y);
S.base++;
}
else
{
printf(" -> (%d,%d)", (*S.base).x, (*S.base).y);
S.base++;
}

}
printf("\n");


free(P);
return 0;
}
1，为什么e.der==4时能判断那是死路？
 2，P指针起什么作用？
哈哈哈，终于看到版主了。版主，你好，小的这里有礼了。

1，der的值1234分别代表“东南西北”，从某一点出发，是按照规定依次“东->南->西->北”（e.der=1;e.der++）这样的顺序搜索的，当一个点e从栈中出来，说明其上一次搜索是不通的，而如果此时如果e.der==4，说明从e点出发的4个方向都搜索过了，那么当然e点本身也就是死路了。
2，指针p用来记录s.base也就是栈的首地址（栈底），因为s.base在后面用来做了累加变量(见s.base++)
   为了防止之后找不到栈底，所以程序的作者用了p存放。（释放栈空间的时候是要用到这个栈底地址的）

对于第一点，还是有疑问，如果e.der==2,再要用相同的方法判断，是不是也是到e.der==4就结束了呢?那这样e.der==1岂不是没有判断？

程序里每个点默认都是从e.der=1开始搜索的。

如果一个点的e.der=2的话，说明e.der=1的情况已经判断过了，der=1这个方向不通的。（也即e这个点之前已经被弹出栈过一次，然后e.der++再装入栈的。接下来从der=2这个方向开始搜索）
接下来，如果从这个点的der=2的方向出发，最终找到了通路，那么这个点就会保存到栈中，并且e.der=2保持到程序结束。
如果这个点e又被弹出来了说明der=2的方向也不通，那么der=3，再入栈，从der=3的方向重新搜索，以此类推。

如果最终在der=4的状态下又被弹出，那么从本点出发的都是死路，该点不再入栈。




[ 本帖最后由 三月的雪 于 2011-4-29 20:45 编辑 ]

明白了  感谢编程论坛，感谢三月的雪。