求帮忙看看程序哪出错了,迷宫求得的路径是错的

2017-05-06 02:29
#include<stdio.h>
#include<stdlib.h>
#include<Windows.h>
#include<malloc.h>

#define STACK_INITSIZE 100
#define INCREMENT 20
typedef struct{
int x;
int y;
}position;

typedef struct{
int ord;
position seat;
int di;
}selemtype;

typedef struct{
selemtype *top;
selemtype *base;
int stacksize;
}stack;
int maze[5][5] = {
{ 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 1 },
{ 1, 1, 1, 0, 0 } };
int Initstack(stack *s){
s->base = (selemtype *)malloc(STACK_INITSIZE*sizeof(selemtype));
if (!s->base) exit(-1);
s->top = s->base;
s->stacksize = STACK_INITSIZE;

return 0;
}

int push(stack *s, selemtype e){
if ((s->top) - (s->base) > s->stacksize){
s->base = (selemtype *)realloc(s->base, (STACK_INITSIZE + INCREMENT)*sizeof(selemtype));
if (!s->base) exit(-1);
s->top = s->base + s->stacksize;
}
*s->top++ = e;

return 0;
}
int pop(stack *s, selemtype *e){
if (s->top == s->base) exit(-1);
*e = *--s->top;
return 0;
}
int empty(stack s){
if (s.base == s.top)
return 1;
return 0;
}
int pass(position p){
if (maze[p.x][p.x] == 0)
return 1;
return 0;
}
int footprint(position p, int step){
maze[p.x][p.y] = step;
return 0;
}
int markprint(position p){
maze[p.x][p.y] = -1;
return 0;
}
position nextpos(position now, int direction){
position next;
int x = now.x;
int y = now.y;
switch (direction){
case 1:{
next.x = x + 1;
next.y = y;
break;
}
case 2:{
next.x = x;
next.y = y + 1;
break;
}
case 3:{
next.x = x - 1;
next.y = y;
break;
}
case 4:{
next.x = x;
next.y = y - 1;
break;
}
default:break;
}
return next;
}

int main(){
for (int i = 0; i < 5; i++){
for (int j = 0; j < 5; j++){
printf("%3d", maze[i][j]);
}
printf("\n");
}
stack s;
Initstack(&s);
position curpos,end;
int curstep = 1;
curpos.x = 0;
curpos.y = 0;
end.x = 4;
end.y = 4;
while (1){
if (pass(curpos)){
//if (maze[curpos.x][curpos.x] == 0){
footprint(curpos, curstep);
selemtype e;
e.ord = curstep;
e.seat.x = curpos.x;
e.seat.y = curpos.y;
e.di = 1;
push(&s, e);
if (curpos.x == end.x&&curpos.y == end.y)
break;
curpos = nextpos(curpos, e.di);
curstep++;
}
else{
//if (maze[curpos.x][curpos.x] == 1){
if (!empty(s)){
selemtype e;
pop(&s, &e);
curstep--;
while (e.di == 4 && !empty(s)){
markprint(e.seat);
pop(&s, &e);
curstep--;
}
if (e.di < 4){
e.di++;
curstep++;
push(&s, e);
curpos = nextpos(e.seat, e.di);
}
}
}
}
 
  
for (int i = 0; i < 5; i++){
for (int j = 0; j < 5; j++){
printf("%3d", maze[i][j]);
}
printf("\n");
}

system("pause");
return 0;
}

回复讨论(解决方案)

int pass(position p){
	if (maze[p.x][p.y] == 0)
		return 1;
	return 0;
}

写代码要稍微小心点,你这x,y大小一致所以没有引发奔溃,如果x>y。。。
给个建议,多断点调试下
int Initstack(stack *s)
{
    s->base = (selemtype *)malloc(STACK_INITSIZE * sizeof(selemtype));
    if (!s->base)
        exit(-1);
    s->top = s->base;
    s->stacksize = STACK_INITSIZE * sizeof(selemtype);

    return 0;
}

int push(stack *s, selemtype e)
{
    if ((s->top) - (s->base) > s->stacksize) {
        s->base = (selemtype *)realloc(s->base, (STACK_INITSIZE + INCREMENT) * sizeof(selemtype));
        if (!s->base)
            exit(-1);
        s->stacksize += INCREMENT * sizeof(selemtype);
        //s->top = s->base + s->stacksize;
    }
    *s->top++ = e;

    return 0;
}

注意这两个地方也是有问题的。注意栈的长度
建议你在必要位置设置断点,然后单步跟踪程序运行,看每一步变量变化情况是否与你期望的一致,很容易找到原因,别人不知你程序表示的意思,所以不好帮你找