在 C++ 中使用 STL 时解决边界错误

Question

我正在编写程序来寻找通过定义矩阵的路径。

#include<iostream>
#include<list>

using namespace std;

class maze{
    int inst[10][10];
    int m,n,initr,initc,finalr,finalc;
public:
    maze(int c){
        if(c==1) return;
        cout<<"\n Enter rows and colums: ";
        cin>>m>>n;
        cout<<endl<<"\n ENter initial configuration (1 for block, 0 for open):";
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin>>inst[i][j];
            }
        }
        cout<<endl<<"Enter initial state in row column:";
        cin>>initr>>initc;
        cout<<endl<<"Enter final state in row column:";
        cin>>finalr>>finalc;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==1) inst[i][j]=(-1);
            }
        }
        inst[initr][initc]=1;
    }
    bool up(int curr){
        int x,y;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==curr) {
                    x=i;
                    y=j;
                    break;
                }
            }
        }
        if(x==0) return false;
        if(inst[x-1][y]==0){
            //cout<<"\n up "<<x-1<<y; 
            inst[x-1][y]=curr+1;
            return true;
        }else return false;

    }
    bool down(int curr){
        int x,y;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==curr) {
                    x=i;
                    y=j;
                    break;
                }
            }
        }
        if(x==m-1) return false;
        if(inst[x+1][y]==0){
            //cout<<"\n down "<<x+1<<y;
            inst[x+1][y]=curr+1;
            return true;
        }else return false;

    }
    bool left(int curr){
        int x,y;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==curr) {
                    x=i;
                    y=j;
                    break;
                }
            }
        }
        if(y==0) return false;
        if(inst[x][y-1]==0){
            //cout<<"\n left "<<x<<y-1;
            inst[x][y-1]=curr+1;
            return true;
        }else return false;

    }
    bool right(int curr){
        int x,y;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==curr) {
                    x=i;
                    y=j;
                    break;
                }
            }
        }

        if(y==n-1) return false;
        if(inst[x][y+1]==0){
            //cout<<"\n right "<<x<<y+1;
            inst[x][y+1]=curr+1;
            return true;
        }else return false;

    }
    bool check(int curr){
        int x,y;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==curr) {
                    x=i;
                    y=j;
                    break;
                }
            }
        }
        if(x==finalr && y==finalc) return true;
        else return false;
    }   
    void print_maze(){
        cout<<endl<<endl;
        for(int i=0;i<m;i++){
            cout<<endl;
            for(int j=0;j<n;j++){
                cout<<"\t"<<inst[i][j];
            }
        }
    }

};

bool state_search(){
    int curr=1;
    maze start(0),temp(1);
    list<maze> queue;

    queue.push_back(start);
    while(!queue.empty()){
        start = queue.front();
        queue.pop_front();
        if(start.check(curr)){
            start.print_maze();
            return true;
        }
        //start.print_maze();

        temp=start;
        if(temp.up(curr)) queue.push_back(temp);

        temp=start;
        if(temp.down(curr)) queue.push_back(temp);

        temp=start;
        if(temp.left(curr)) queue.push_back(temp);

        temp=start;
        if(temp.right(curr)) queue.push_back(temp);

        curr++;
    }
    cout<<"\n No answer found";
}


int main(){
    state_search();
}

该程序适用于大多数输入。但是给出了以下输入的地址边界错误

Enter rows and colums: 4 4

ENter initial configuration (1 for block, 0 for open):0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0

Enter initial state in row column:1 0

Enter final state in row column:3 3 fish: “./a.out” terminated by signal SIGSEGV (Address boundary error)

请提出此错误的可能原因以及更正方法

Answer 1

问题是您没有在向上、向下、向左和向右函数中初始化 x 和 y 值。然后，如果您没有找到 curr 的索引，则可以在随机索引处访问 inst 数组。

在 right 函数中，您应该像这样声明 x 和 y：

int x = 0,y = 0;

在左:

int x = m - 1,y = 0;

在右和左中做同样的事情。

Answer 2

您在方法 maze::up:

中使用了未初始化的变量 x 和 y

bool up(int curr){
    int x,y; // !!!
    ...

因此，当在后续循环中我们没有进入 if 语句时，这些变量仍然包含来自未初始化分配内存的垃圾。

    ...
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(inst[i][j]==curr) {
                x=i;
                y=j;
                break;
            }
        }
    }
    ...

并且 x 不在 [0, 10] 范围内的可能性很高。

    ...
    if(x==0) return false;
    if(inst[x-1][y]==0){
    ...

然后我们立即尝试在内存中很远的地方 (inst[x-1][y]) 获取值，并因分段错误而终止。

Fix: 最好用有意义的值初始化所有变量。假设对于您的代码这是正确的解决方案：

bool up(int curr){
    int x = 0, y = 0;
    ...

您可以告诉编译器在您保留未初始化变量时通知您。

如果您使用 GCC 编译器，您可以使用编译标志：

g++ -O2 -Wuninitialized prog.cpp

而且你会在你的代码中看到很多类似的地方。另外你可以使用标志-Wall，你会发现bool state_search()函数到达结束没有返回任何值。

Answer 3

我意识到错误在哪里了。我没有在函数 maze::up()、maze::down()、maze::right() 和 maze::left() 中初始化 x 和 y，因为它总是应该被初始化遍历矩阵时的函数。错误在算法本身。 state_search() 中的变量 curr 应该表示 BFS 树的深度。但是由于它为找到的每个节点递增，所以它表示错误的深度，只要有 2 条可能的路径就会导致错误。

为了解决这个问题，我从 state_search() 中删除了 curr 变量并将其添加到 class 定义中，将其初始化为 1 并在函数 maze::up()、maze::down()、maze::right() 和 maze::left() 被调用。

这里是完整的工作代码

#include<iostream>
    #include<list>

    using namespace std;

    class maze{
        int inst[10][10];
        int m,n,initr,initc,finalr,finalc,curr;
    public:
        maze(int c){
            if(c==1) return;
            cout<<"\n Enter rows and colums: ";
            cin>>m>>n;
            cout<<endl<<"\n ENter initial configuration (1 for block, 0 for open):";
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    cin>>inst[i][j];
                }
            }
            cout<<endl<<"Enter initial state in row column:";
            cin>>initr>>initc;
            cout<<endl<<"Enter final state in row column:";
            cin>>finalr>>finalc;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==1) inst[i][j]=(-1);
                }
            }
            inst[initr][initc]=1;
            curr=1;
        }
        bool up(){
            int x=0,y=0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==curr) {
                        x=i;
                        y=j;
                        break;
                    }
                }
            }
            if(x==0) return false;
            if(inst[x-1][y]==0){
                inst[x-1][y]=curr+1;
                curr++;
                return true;
            }else return false;

        }
        bool down(){
            int x=m-1,y=0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==curr) {
                        x=i;
                        y=j;
                        break;
                    }
                }
            }
            if(x==m-1) return false;
            if(inst[x+1][y]==0){
                inst[x+1][y]=curr+1;
                curr++;
                return true;
            }else return false;

        }
        bool left(){
            int x,y=0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==curr) {
                        x=i;
                        y=j;
                        break;
                    }
                }
            }
            if(y==0) return false;
            if(inst[x][y-1]==0){
                inst[x][y-1]=curr+1;
                curr++;
                return true;
            }else return false;

        }
        bool right(){
            int x,y=n-1;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==curr) {
                        x=i;
                        y=j;
                        break;
                    }
                }
            }

            if(y==n-1) return false;
            if(inst[x][y+1]==0){
                inst[x][y+1]=curr+1;
                curr++;
                return true;
            }else return false;

        }
        bool check(){
            int x,y;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==curr) {
                        x=i;
                        y=j;
                        break;
                    }
                }
            }
            if(x==finalr && y==finalc) return true;
            else return false;
        }   
        void print_maze(){
            cout<<endl<<endl;
            for(int i=0;i<m;i++){
                cout<<endl;
                for(int j=0;j<n;j++){
                    cout<<"\t"<<inst[i][j];
                }
            }
        }

    };

    bool state_search(){

        maze start(0),temp(1);
        list<maze> queue;

        queue.push_back(start);
        while(!queue.empty()){
            start = queue.front();
            queue.pop_front();
            if(start.check()){
                start.print_maze();
                return true;
            }

            temp=start;
            if(temp.up()) queue.push_back(temp);

            temp=start;
            if(temp.down()) queue.push_back(temp);

            temp=start;
            if(temp.left()) queue.push_back(temp);

            temp=start;
            if(temp.right()) queue.push_back(temp);
        }
        cout<<"\n No answer found";
        return false;
    }


    int main(){
        state_search();
    }

在 C++ 中使用 STL 时解决边界错误

Address boundry error while using STL in C++

c++

list

runtime-error

breadth-first-search

state-space