论坛 › 萌新交流区 › 迷宫问题-栈-空指针

墨笠阳 发表于 2023-7-9 22:26:12

迷宫问题-栈-空指针

本帖最后由 墨笠阳 于 2023-7-9 22:35 编辑

需求：以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，获得出没有通路的结论。

程序设计思路：定义一个position类型的结构体来储存迷宫元素，用栈来存储迷宫maze 和通路path ，定义了两个指针p、per，分别指向在迷宫中遍历的当前位置和下一位置，通过“FindPath“函数的返回值判断，是否有通路，若有，则用for循环，将通路坐标自path栈输出，若无，则输出无通路的结论。
“FindPath“函数
操作1.依照”上、左、下、右”顺序从当前起点位置 p 开始对迷宫进行深度遍历，当下一位置per 未越边界、无障碍 且未被访问时，使 *per入通路栈path，并对其进行标记，表示已访问，再以per为新起点，进行深度遍历，直到下一位置per不满足入path栈的条件，操作2.此时判断栈顶元素是否是出口，若是，则return 1；若不是，则判断是否是入口，若是，则return 0，若不是，使path栈栈顶元素出栈，实现回退，以新栈顶元素为新起点，重复操作1，操作2问题：初始化及构建maze栈完成后，将maze栈的首地址赋给指针p,经检验，赋值后，指针p仍为空指针，与预期不符，求各位大佬不吝赐教InitStack_FindPath(path);//初始化通路栈
InitStack_maze(maze);//初始化迷宫栈
cout << "请输入行数：" ;
cin >> row;
cout << "\n请输入列数：";
cin >> col
cout << endl;
Creat_maze(maze,row,col);//创造迷宫
start = maze.base;//将迷宫入口的地址赋给指针start
end = maze.top - 1;//将迷宫出口的地址赋给指针end
p = maze.base;//将迷宫入口的地址赋给指针p
p->step = 1;

//验证指针p是否为空
if (p) {
cout << "NULL";
cout << "\tx= " << p->x << "\ty= " << p->y << "\tpos= " << p->pos << "\tstep= " << p->step << endl;
}

输入：550 1 0 1 10 0 1 1 1 1 0 1 0 11 0 0 0 1 1 0 1 0 0输出：NULL    x= 0    y= 0    pos= 0step= 0<blockquote>

墨笠阳 发表于 2023-7-9 22:49:07

//struct.h
#include<malloc.h>
#define MAX_STACK_FindPath_SIZE 1275
#define MAX_ROW 50
#define MAX_COL 50

//位置
typedef structposition {
    int x = 0;//横坐标
    int y = 0;//纵坐标
    int pos = 1;//1，有障碍      0 无障碍      
    int step = 0;//1 已访问 0 未访问，-1 回退时再次访问
}position;

typedef struct {
    position* base;
    position* top;
    int stacksize;
}Stack;

//初始化
int InitStack_FindPath(Stack& S) {
    S.base = new position;
    if (!S.base)
      return 0;
    else {
      S.top = S.base;
      S.stacksize = MAX_STACK_FindPath_SIZE;
      return 1;
    }
}

int InitStack_maze(Stack& S) {
    int max = MAX_ROW * MAX_COL;
    S.base = new position;
    if (!S.base)
      return 0;
    else {
      S.top = S.base;
      S.stacksize = max;
      return 1;
    }
}

//入栈
int Push(Stack& S, position p) {
    if (S.top - S.base == S.stacksize)//栈满
      return 0;
    else {
      *S.top = p;
      S.top++;
      return 1;
    }
}

//出栈
int Pop(Stack& S, position& p) {
    if (S.top == S.base)
      return 0;
    else {
      p = *(S.top - 1);
      S.top--;
      return 1;
    }
}

墨笠阳 发表于 2023-7-9 22:51:35

本帖最后由 墨笠阳 于 2023-7-9 22:53 编辑

#include<iostream>
#include"struct.h"
using namespace std;

void Creat_maze(Stack& maze, int row,int col);
int FindPath(Stack& maze, Stack& path, position* p, position* start,position* end,int row,int col);
int main() {
        Stack maze;
        Stack path;
        position* p;
        position* start, * end;
        int row, col;
        InitStack_FindPath(path);
        InitStack_maze(maze);
        cout << "请输入行数：" ;
        cin >> row;
        cout << "\n请输入列数：";
        cin >> col;
        cout << endl;
        Creat_maze(maze,row,col);
        start = maze.base;
        end = maze.top - 1;
        p = maze.base;

        if (p) {
                cout << "NULL";
                cout << "\tx= " << p->x << "\ty= " << p->y << "\tpos= " << p->pos << "\tstep= " << p->step << endl;
        }

        p->step = 1;
        if (FindPath(maze, path, p, start,end,row, col)) {
                p = path.base;
                while (p!=path.top) {                       
                        cout << "(" << p->x << "," << p->y << ")" << endl;
                        p++;
                }
                return 1;
        }
        else {
                cout << "此迷宫无通路！" << endl;               
                return 0;
        }
}
void Creat_maze(Stack& maze, int row, int col) {
        int i, j;
        position p;
        for (i = 0; i < row; i++) {
                p.x = i;
                for (j = 0; j < col; j++) {
                        p.y = j;
                        cin >> p.pos;
                        Push(maze, p);
                }
        }
}
int FindPath(Stack& maze, Stack& path, position* p,position* start, position* end, int row, int col) {
        position* per;
       {
                //向上
                {
                        per = p - col;
                       
                        /* // 验证per是否空
                        if (per) {
                                cout << "NULL";
                                cout << "\tx= " << per->x << "\ty= " << per->y << "\tpos= " << per->pos << "\tstep= " << per->step<<endl;
                        }/**/
                        /**
                        if (p) {
                                cout << "NULL";
                                cout << "\tx= " << per->x << "\ty= " << per->y << "\tpos= " << per->pos << "\tstep= " << per->step << endl;
                        }/**/
                        if (!per && per->pos == 0 && per->step == 0) {
                                //!per 未越上边界
                                //per->pos == 0 无障碍
                                //per->step == 0 未被访问
                                Push(path, *per);
                                per->step = 1;
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                                }
                                else {
                                        return 0;
                                }
                        }
                }
                //向左
                {
                        per = p - 1;
                        /*
                        if (per) {
                                cout << "NULL";
                                cout << "\tx= " << per->x << "\ty= " << per->y << "\tpos= " << per->pos << "\tstep= " << per->step << endl;
                        }/**/
                        if (!per && p->x == per->x && per->pos == 0 && per->step == 0) {
                                //!per && p->x == per->x 未越界
                                Push(path, *per);
                                per->step = 1;
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                                }
                                else {
                                        return 0;
                                }
                        }
                       
                }
                //向下
                {
                        per = p + col;
                        if (!(per->x == 0 && per->y == 0 && per->pos == 1) && per->pos == 0 && per->step == 0) {
                                //per->x == 0 && per->y == 0 && per->pos == 1 是position类型元素的默认值，表示maze栈外元素
                                Push(path, *per);
                                per->step = 1;
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                                }
                                else {
                                        return 0;
                                }
                        }
                }
                //向右
                {
                        per = p + 1;
                        if (p->x == per->x && !(per->x == 0 && per->y == 0 && per->pos == 1) && per->pos == 0 && per->step == 0) {
                                Push(path, *per);
                                per->step = 1;
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                                }
                                else {
                                        return 0;
                                }
                        }
                }

                //判断，是出口,return 1
                if (p == end) {
                        return 1;
                }
                       
                //不是出口
                else{
                        //判断，是入口，return 0
                        if (p == start) {
                                return 0;
                        }
                        //不是入口，回退，
                        else {
                                position tem;
                                Pop(path, tem);
                                //以栈顶元素为新起点再遍历
                                per = (maze.base + (path.top - 1)->x * col + (path.top - 1)->y);
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                                }
                                else {
                                        return 0;
                                }
                        }
                }

        }

}

isdkz 发表于 2023-7-9 22:33:01

我理解您正在使用一个栈结构和深度优先搜索算法来寻找一个迷宫的路径。在您提供的代码片段中，我看到您使用了一个栈类型的结构体来存储迷宫和路径，并定义了两个指针p和per来分别指向在迷宫中遍历的当前位置和下一个位置。您的问题似乎是在初始化迷宫栈并赋值给p指针后，发现p指针仍为空。

首先，对于问题的解决，这可能涉及到对栈的初始化和赋值的实现方式。你可能需要检查InitStack_maze(maze) ，Creat_maze(maze,row,col) ，以及maze.base的实现，以确保他们都在正确的位置初始化和分配内存，并确保maze.base正确地指向了栈底部的内存地址。

然后，你也需要注意的是，你的输出表示p是NULL，但是后面的字段显示x，y，pos，step有具体的值。这有可能是if(p)的逻辑判断有问题。如果p为空，那么if(p)的结果应该是false，所以应该不会执行下面的cout语句，这就产生了矛盾。你应该检查你的if条件判断的正确性，以确保它的逻辑是正确的。

最后，可以使用一些调试技巧，比如在创建迷宫后打印栈的情况，检查栈是否已经正确初始化和填充。同时，你也可以打印maze.base和maze.top的值，看看他们是否正确地指向了栈的底部和顶部。

如果你可以提供更多关于InitStack_maze(maze) ，Creat_maze(maze,row,col) ，以及maze.base的实现细节，我可能可以提供更具体的建议。

墨笠阳 发表于 2023-7-9 22:45:31

本帖最后由 墨笠阳 于 2023-7-9 23:22 编辑

isdkz 发表于 2023-7-9 22:33
我理解您正在使用一个栈结构和深度优先搜索算法来寻找一个迷宫的路径。在您提供的代码片段中，我看到您使用 ...

谢谢您的回复，问题已解决，确实是if(p)的逻辑判断出了问题

sfqxx 发表于 2023-7-9 22:50:52

墨笠阳 发表于 2023-7-9 22:49


怎么了？

墨笠阳 发表于 2023-7-9 22:57:05

sfqxx 发表于 2023-7-9 22:50
怎么了？

报错了{:10_266:}

墨笠阳 发表于 2023-7-9 23:19:08

调试过后发现确实是if(p) 的逻辑判断出问题了，
//越边界时，per为空，if(per)==if(false)；未越界时,if(per)==if(true)，
问题已解决，谢谢大家

查看完整版本: 迷宫问题-栈-空指针