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

Question

刚上完第一堂CS课，我想更多地练习递归内存分配，所以我决定制作一款名为"递归地牢"它只是允许用户通过递归地生成一个新的"；房间"；每次玩家进入空(NULL)房间时。

然后保存新房间，并可以通过…访问

1. 沿着与进入房间时完全相同的路径
2. 如果你离开房间，沿着你的脚步回到同一个房间

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

我遇到的问题是，当我试图清理所有递归分配的内存("房间")时，我会收到典型的错误；分段错误：核心转储"；。

下面是我的结构"；房间"：

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*/};

每个"；房间"；有其他房间连接到它(左/右/前/后)。用户从空房间指针"0"开始；起始点"；，并且可以在上述任何方向上行进。在尝试进入一个空(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

即使可以进行两次删除，您的算法也不会工作。如果有两个房间相互连接，它们会递归地尝试删除对方，导致堆栈溢出。也就是说，你不能用简单的递归来删除循环。

你有一个设计问题——谁拥有每个房间？如果这是用垃圾收集的语言写的，你就不会在乎了，房间会因为自己的存在而拥有彼此。在C++中，您必须小心，并且设计应该反映这一点。

在这种情况下CCD_ 2和CCD_。即使您可以建立一个类似树的层次结构，从而使用unique_ptr，它也可能导致堆栈溢出，这仅仅是因为深层树的嵌套析构函数。

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

如果映射真的是动态的，就像你的情况一样，我可以为std::list<Room>——使用迭代器或邻居的指针——或者std::vector<std::unique_ptr<Room>>——使用原始的非拥有的指针。

这些仅限邻居的解决方案只是一个警告——当玩家在循环中探索房间时，你没有工具来确定该房间是否已经存在。例如，向上2次，向右2次，向下2次，向左2次应该会将玩家返回到初始房间。您可能需要考虑实际使用2D网格(稍后还要担心内存/性能)。

Answer 2

如果你的房间图中有一棵普通树(没有回头路)，你的算法就会起作用。既然你可以回去，你需要注意不要再处理你已经在处理的房间。

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

---

方法1。房间类应该有一个布尔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;
}

这实质上将删除过程转变为深度优先搜索。

---

方法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;
}

这只是普通的从上到下的树遍历，添加了防止上升的检查。

---

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

还应注意，此检查

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

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

Answer 3

做更多的研究，回忆stack与heap的内存，并通读这篇文章-我想我可能已经在上面的代码中发现了问题。

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

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