指针指向的值超出范围并且指针中断[关闭]

Question

代码是这样的。这是一个 bfs，我希望它向后移动，所以我尝试使用指针在步骤之间建立连接。

sx,sy 是我们的起点。 tx,ty是我们的命运点。 act[][] 是一个布尔表，以确保我不会两次进入同一个地方。

struct trip
{
    int first;
    int second;
    trip* last;
};

void write(trip a)
{
    cout<<"\n";
    cout<< "x" << " " << a.first << "\n";
    cout<< "y" << " " << a.second << "\n";
    cout<< "x lasta" << " " << a.last->first << "\n";
    cout<< "y lasta" << " " << a.last->second << "\n";
}

queue<trip> Q;
trip P; P.first = sx; P.second = sy; P.last = nullptr; Q.push(P);
while(!Q.empty())
{
    //cout << "WOW" << "\n";
    trip temp = Q.front(); Q.pop();
    if(temp.last != nullptr)
        write(temp);

    int corx = temp.first;  int cory = temp.second;

    if(corx == tx && cory == ty)
    {
        // We found our destiny
    }

    if(act[corx][cory] == false)
    {
        act[corx][cory] = true;

        // Up
        if(cory - 1 >= 0)
        {
            trip TEMPUUS; TEMPUUS.first = corx - 1; TEMPUUS.second = cory; TEMPUUS.last = &temp; Q.push(TEMPUUS);
            cout << corx - 1 << " " << TEMPUUS.last -> first; // corx - 1 here is equal to
            //TEMPUUS.last -> first - 1 and that is what I want
        }

        // Down
        if(cory + 1 <= 2000)
        {
            trip TEMPUUS; TEMPUUS.first = corx + 1; TEMPUUS.second = cory; TEMPUUS.last = &temp; Q.push(TEMPUUS);
        }

        // Left
        if(corx - 1 >= 0)
        {
            trip TEMPUUS; TEMPUUS.first = corx; TEMPUUS.second = cory - 1; TEMPUUS.last = &temp; Q.push(TEMPUUS);
        }

        // Right
        if(corx + 1 <= 2000)
        {
            trip TEMPUUS; TEMPUUS.first = corx; TEMPUUS.second = cory + 1; TEMPUUS.last = &temp; Q.push(TEMPUUS);
        }
    }
}

那么问题出在哪里呢？问题是，当我将行程变量推入队列时，它的坐标与前一个的坐标不同。然而，当我们进入队列的下一次迭代时，临时变量超出范围，“最后一个”指针现在指向它自己。

如果您读过本文，我想让您知道，我对自己的沟通技巧感到非常抱歉，我希望这没有我想象的那么痛苦。

有代码示例：

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

struct trip
{
    int first;
    int second;
    trip* last;
};

void write(trip a)
{
    cout << "\n";
    cout <<  "x" << " " << a.first << "\n";
    cout <<  "y" << " " << a.second << "\n";
    cout <<  "x lasta" << " " << a.last->first << "\n";
    cout <<  "y lasta" << " " << a.last->second << "\n";
}

void bfs(int sx, int sy, int tx, int ty)
{
    queue<trip> Q;
    trip P; P.first = sx; P.second = sy; P.last = nullptr; Q.push(P);
    int test = 0;
    while(!Q.empty())
    {
        trip temp = Q.front(); Q.pop();
        if(temp.last != nullptr)
            write(temp);
        int corx = temp.first;
        int cory = temp.second;

        if(act[corx][cory] == false)
        {
            act[corx][cory] = true;

            // Up
            if(cory - 1 >= 0)
            {
                trip TEMPUUS; TEMPUUS.first = corx - 1; TEMPUUS.second = cory; TEMPUUS.last = &temp; Q.push(TEMPUUS);
                cout << corx - 1 << " " << TEMPUUS.last -> first;
            }
        }
        test++;
        if(test > 5)
            return;
    }
}

int main()
{
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    sx += 1000; sy += 1000; tx += 1000; ty += 1000;
    bfs(sx, sy, tx, ty);
    return 0;
}

Answer 1

temp

结构在堆栈上分配，当定义它的块退出时，该内存将再次释放。这意味着排队的

trip

现在具有无效的

last

引用。

相同的内存在循环的下一次迭代中被重用，使得上面提到的

last

引用再次有效。但现在对

temp.first

的赋值会影响 that 内存。简而言之，所有非空

last

成员都引用 相同 内存位置。

要解决此问题，请使用堆分配的内存（使用

new

、

class

、...等）。

您还应该注意释放已使用的内存。在您的情况下，与

last

的链接形成一棵树，这可能是一个很大的负担。我建议将内存管理留给共享智能指针。

不是你的问题，而是：

• 您的代码中有一个明显的错误。虽然注释和

  if

  条件指示“向上”移动，但您可以使用减小的 x 坐标而不是减小的 y 坐标进行

  Trip

  。
• 为什么

  using namespace std;

  被认为是不好的做法
• 不要将多个语句放在同一行；当然不是当它需要向右滚动时（多语句行之一的长度超过 110 个字符）。幸运的是，使用构造函数消除了其中一些的“需要”。

这是

struct trip

和

write

函数的替换：

class Trip
{
public:
    int first;
    int second;
    std::shared_ptr<Trip> last;

    Trip(int first, int second, std::shared_ptr<Trip> last) : 
            first(first), second(second), last(last)
    {
    }

    void write()
    {
        std::cout<<"\n";
        std::cout<< "x" << " " << this->first << "\n";
        std::cout<< "y" << " " << this->second << "\n";
        if (this->last) {
            std::cout<< "x lasta" << " " << this->last->first << "\n";
            std::cout<< "y lasta" << " " << this->last->second << "\n";
        }
    }
};

现在您的

bfs

函数可以如下所示：

void bfs(int sx, int sy, int tx, int ty)
{
    std::queue<std::shared_ptr<Trip>> Q;
    std::shared_ptr<Trip> start(new Trip(sx, sy, nullptr));
    Q.push(start);
    while (!Q.empty())
    {
        std::shared_ptr<Trip> current = Q.front();
        Q.pop();
        current->write();
        int corx = current->first;
        int cory = current->second;
        if (!act[corx][cory])
        {
            act[corx][cory] = true;
            //up
            if (cory - 1 >= 0)
            {
                std::shared_ptr<Trip> neighbor(new Trip(corx, cory - 1, current));
                Q.push(neighbor);
            }
        }
    }
}