递归内存"tree"：正确释放内存

Question

刚刚结束我的第一个 CS class，我想更多地练习递归内存分配，所以我决定制作一个名为“递归地牢”的小游戏。它只是允许用户在每次玩家进入一个空的 (NULL) 房间时递归地生成一个新的“房间”，从而在无限地牢中漫游。

然后保存新房间，可以访问...

沿着进入房间时使用的完全相同的路径前进
如果你离开房间，原路返回到同一个房间

*该程序不使用循环（至少，我认为它不使用）。我不熟悉循环的概念以及如何使用它。

我运行遇到的问题是当我尝试清理所有递归分配的内存（“房间”）时，我收到 classic 错误“分段错误：核心转储”。

下面是我的结构“房间”：


    struct room
    {//begin struct

        room* backward;
        room* left;
        room* forward;
        room* right;

        string desc;
  
        room() { //begin
    
            backward = NULL;
            left = NULL;
            forward = NULL;
            right = NULL;
    
        /*End*/}
 
    /*End struct*/};

每个“房间”都有与其相连的其他房间 (left/right/forward/backward)。用户从一个空房间指针“起点”开始，并可以朝上述任何方向前进。尝试进入空 (NULL) 房间时，会随机生成一个新房间供用户进入。

一旦玩家对探索感到满意，我就会尝试在结束程序之前使用存储所有房间的数组来清理分配的内存。相反，它会导致分段错误。这是代码：

    void ClearAllocatedMemory(room* aRoom, room** roomArray, int& raIndex) {

        for(short i=0; i<raIndex; i++) {//begin for
    
            delete roomArray[i];
    
        /*End for*/}
    
        delete[] roomArray;

    /*End func*/}

这是创建我的数组并定义其第一个（第 0 个）索引的代码：


    room** roomArray;
    int raIndex = 0;

    room* startingpoint = new room();
    roomArray[0] = startingpoint;

这里是将新房间添加到 roomArray 索引的代码：


    room* GenRoom(room** roomArray, int& raIndex) {

        room* newroom = new room();
    
        newroom->desc = GenRoomDesc( rand()%12 + 1 );
    
        raIndex++;
    
        roomArray[raIndex] = newroom;

        return newroom;


    }

Answer 1

即使双删没问题，你的算法也不行。如果您有两个相互连接的房间，它们将递归地尝试相互删除，从而导致堆栈溢出。 IE。你不能用简单的递归删除循环。

您有一个设计问题 - 谁拥有每个房间？如果它是用 garbage-collected 语言编写的，您就不会在意，而且这些房间仅凭它们自己的存在就可以相互拥有。在 C++ 中，您必须关心并且设计应该反映这一点。

shared_ptr 和 std::weak_ptr 在这种情况下会很混乱。即使你可以建立一个 tree-like 层次结构并因此使用 unique_ptr，它也可能仅仅由于深树的嵌套析构函数而导致堆栈溢出。

最好和最简单的解决方案是创建一个 std::vector<Room>，它是所有房间的明确所有者。然后邻居可以使用这个向量的索引。需要注意的是，取消分配向量中心的房间会使较高的索引无效。这可以通过与最后一个元素交换并仅修复它们的连接来解决。它还会从中间删除 O(1).

如果地图真的是动态的，就像你的情况一样，我可以争论 std::list<Room> - 对邻居使用迭代器或指针 - 或者 std::vector<std::unique_ptr<Room>> - 使用原始 non-owning 指点。

这些 neighbour-only 解决方案只是一个警告 - 当玩家循环探索房间时，您没有工具来确定该房间是否已经存在。例如。向上 2 向右 2 向下向左 2 应该 return 玩家到达初始房间。您可能要考虑实际使用 2D 网格（稍后再担心 memory/performance）。

Answer 2

如果你的房间图是一棵普通的树（不回头），你的算法就会起作用。既然可以回去，请注意不要再次处理您已经处理的房间。

我将展示两种方法，一种适用于任意图，另一种仅适用于具有反向链接的树。

方法 1. 房间 class 应该有一个布尔值 visited 标志（不是玩家访问的，而是耗尽序列访问的）。初始值为 false。那么你的删除函数应该修改成这样：

ClearAllocatedMemory(room* aRoom) {
   if (aRoom == nullptr || aRoom->visited) return;
   aRoom->visited = true;
   ClearAllocatedMemory(aRoom->backward);
   ClearAllocatedMemory(aRoom->left);
   ClearAllocatedMemory(aRoom->forward);
   ClearAllocatedMemory(aRoom->right);
   delete room;
}

这实质上将删除过程变成了Depth-first search。

方法 2. 房间删除例程应该知道它从到达了哪个房间，而不是触及那个房间。

ClearAllocatedMemory(room* aRoom, room* parent) { if (aRoom == nullptr) return; if (aRoom->backward != parent) ClearAllocatedMemory(aRoom->backward, aRoom); if (aRoom->left != parent) ClearAllocatedMemory(aRoom->left, aRoom); if (aRoom->forward != parent) ClearAllocatedMemory(aRoom->forward, aRoom); if (aRoom->right != parent) ClearAllocatedMemory(aRoom->right, aRoom); delete room; }

这只是正常的 top-to-bottom 树遍历，添加了阻止向上遍历的检查。

第一种方法可能更可取，因为它是通用的，您可以使删除例程成为 析构函数，就像在 C++ 中一样。但这是另一个场合。

另请注意，此检查

if ( (aRoom->backward == NULL) && (aRoom->left == NULL)\ && (aRoom->forward == NULL) && (aRoom->right == NULL) ) {

没有多大意义。每个房间都需要删除，而不仅仅是那些没有传出路径的房间。

Answer 3

做一些更多的研究，回顾 stack 与 heap 内存，并通读这个 article- 我想我可能已经找到上面代码中的问题了。

在改变我清理内存的方式后，从使用递归到使用@Quimby 建议的数组，我实现了一个 room** 数组来容纳所有房间。我运行遇到的问题是我试图删除不应删除的房间**：房间** 是从堆栈中分配的而不是 heap 因为我没有使用关键字 new 来创建它。

因此，要修复我的代码，我只需要从我的函数中取出 delete[] roomArray;。

递归内存"tree"：正确释放内存

Recursive memory "tree": properly freeing memory

c++

memory

recursion

segmentation-fault

c++17