递归创建带有类 C++ 的链表

Question

我正在使用 C++ 递归地创建一个六边形网格（使用多重链接列表样式）。我已将其设置为轻松创建相邻图块，但因为我是递归执行的，所以我只能为给定图块真正创建所有 6 个相邻图块。显然，这会导致创建重复的图块，我正在尝试以某种方式摆脱它们。因为我正在使用一个类，所以检查空指针似乎不起作用。它要么无法从我的 Tile 类转换为 int，要么以某种方式转换它但没有正确执行。我在创建时明确将所有指针设置为 NULL，当我检查它是否仍然是 NULL 时，它说它不是，即使我自初始化以来从未碰过它。我应该有一个具体的方法来做到这一点吗？如果没有某种 NULL，我什至无法遍历网格

这是我的一些相关代码。是的，我知道这很尴尬。

图块类头：

class Tile
{
public:
    Tile(void);
    Tile(char *Filename);
    ~Tile(void);

    void show(void);
    bool LoadGLTextures();
    void makeDisplayList();
    void BindTexture();
    void setFilename(char *newName);

    char Filename[100];
    GLuint texture[2];
    GLuint displayList;
    Tile *neighbor[6];
    float xPos, yPos,zPos;
};`

图块初始化：

Tile::Tile(void)
{
    xPos=0.0f;
    yPos=0.0f;
    zPos=0.0f;
    glEnable(GL_DEPTH_TEST);
    strcpy(Filename, strcpy(Filename, "Data/BlueTile.bmp"));
    if(!BuildTexture(Filename, texture[0]))
        MessageBox(NULL,"Texture failed to load!","Crap!",MB_OK|MB_ICONASTERISK);

    for(int x=0;x<6;x++)
    {
        neighbor[x]=NULL;
    }
}

创建相邻图块：

void MakeNeighbors(Tile *InputTile, int stacks)
{
    for(int x=0;x<6;x++)
    {
        InputTile->neighbor[x]=new Tile();
        InputTile->neighbor[x]->xPos=0.0f;
        InputTile->neighbor[x]->yPos=0.0f;
        InputTile->zPos=float(stacks);
    }
    if(stacks)
    {
        for(int x=0;x<6;x++)
            MakeNeighbors(InputTile->neighbor[x],stacks-1);
    }
}

最后，遍历网格：

void TraverseGrid(Tile *inputTile)
{
    Tile *temp;
    for(int x=0;x<6;x++)
        if(inputTile->neighbor[x])
        {
            temp=inputTile->neighbor[x];
            temp->xPos=0.0f;
            TraverseGrid(temp);
            //MessageBox(NULL,"Not Null!","SHUTDOWN ERROR",MB_OK | MB_ICONINFORMATION);
        }

}

关键行是“if(inputTile->neighbor[x])”以及我是否将其设为“if(inputTile->neighbor[ x]==NULL)" 或无论我做什么，它只是没有正确处理它。哦，我也知道我还没有完全设置列表。现在只有一个方向。

Answer 1

如果您想创建六角形网格，您应该记住，可以使用普通网格轻松模拟它！

    __    __    __
\__/2 \__/4 \__/6 \
/1 \__/3 \__/5 \__/
\__/8 \__/10\__/12\
/7 \__/9 \__/11\__/
\__/  \__/  \__/  \

这将使生活变得更加简单:)

因此，最简单的方法是

1. 设置一个临时方形网格 m*n
2. 用瓷砖填充它
3. ，遍历网格并正确连接

现在，根据上图进行连接：

A) Connect to previous and next [x-1,y], [x+1,y]
B) Connect to row above and row below [x,y-1], [x,y+1]
C) Connect to row above previous and next [x-1,y-1], [x+1,y-1]

...并且您拥有所有所需的连接（只需记住检查边界以确定图块是否不在边缘） - 如果您以其他方式握住图块，您甚至可以删除网格:)。

Answer 2

我只是猜测 MakeNeighbors() 的作用，但不要盲目地执行 InputTile->neighbor[x]=new Tile();，您可以检查一下 neighbor[x] 是否是在创建新的并初始化它之前非 NULL。例如，如果它的父级创建了它并设置了它的所有邻居信息，那么它不应该去创建它的父级。

当父级创建子级时，它还应该适当地定义子级的其他邻居（只要它知道）。因此，它应该确保 child[i] 也是 child[i-1] 和 child[i+1] 的邻居。

Answer 3

创造。递归是解决某些问题的一种简洁而优雅的方法，但它并不适合所有问题。我怀疑创建节点的纯粹递归解决方案会比 Kornel Kisielewicz 的简单迭代解决方案。这是因为 Tile 构造函数需要知道其附近所有图块的布局，以避免重新创建已经存在的节点。

遍历。节点遍历代码中的主要问题是相似的，因为每个节点最终都会“遍历”回其父节点，开始循环，因此您将陷入无限循环并破坏堆栈再次。我想您正试图访问每个图块一次，对吧？在这种情况下，TraverseGrid() 需要有一个参数告诉它我们从哪个方向进入节点，这样我们就可以避免从那个方向遍历回来。

但这还不够——你还需要更多的纪律来决定前进的方向。简单地向除我们输入的方向之外的所有方向展开仍然会陷入无限循环和堆栈溢出，因为任何三个相邻的图块都会无限循环。为了递归地执行此操作，您需要真正考虑哪些策略将最终访问每个节点一次且仅一次。

一种可能是将 TraverseGrid() 的签名更改为 TraverseGrid(Tile *inputTile, int fromDir, bool leftmost) ，然后使用以下规则：

• 如果我们从上面输入-left，仅遍历到右上方，传递 leftmost = false。
• 如果我们从左下或右上进入，则仅遍历到右下，传递 leftmost = false。
• 如果leftmost，并且左下角有一个节点，那么也遍历到该节点，传递leftmost = true。

当然，fromDir 和 leftmost 可以组合成一个参数，但这给出了总体思路。

另一种选择是在每个图块中保留一个 visited 标志，在遍历该图块之前检查该标志。那么你的遍历将是洪水填充。但同样，简单的迭代遍历可能会简单得多且更容易理解，并且具有使用恒定堆栈空间的额外好处。

Answer 4

在类声明中，有第二个构造函数 Tile(char *Filename);。也许这个构造函数用于创建主节点，但没有正确初始化 neighbor ？ （它的实现没有显示。）

在不相关的节点上，构造函数中有一个重复的 strcpy() ，它没有任何用途，可能只会导致问题：

strcpy(Filename, strcpy(Filename, "Data/BlueTile.bmp"));

Answer 5

我实际上做了同样的事情，但我的模式更像是这样的：

00   01   02   03   04

   10    11   12   13   14

      20    21   22   23   24

         30   31   32   33   34

这使得很容易找出可以达到的目标，但会强制出现奇怪的偏移模式。我刚刚摆脱了（在上面的示例中）00,01,10 和 20，使其更像是这样的十六进制模式：

            02   03   04   05   06

         11   12   13   14   15

            21   22   23   24   25

         30   31   32   33   34

因此，如果您查看上面的模式，可达性始终相同：

从 23 （调用 2 " a" 和 3 "b") 你可以得到：

NW(a-1, b), NE(a-1, b+1), W(a, b-1), E(a, b+1), SW(a+1, b-1), SE(a+1,b)

这个模式对于整个网格来说应该是正确的。

编辑：

我本来打算在评论中这样做，但它太长了。我可以看到两种方法。

1）分配节点数组（null，不分配它们）。每当您需要分配一个节点时，就这样做，但是每当您需要引用一个节点时，请使用数组地址，如果它为空，则填充它，如果它有值，则使用该值。巨大的空数组不应该占用那么多内存，但如果它们占用了...

2) 创建一个 HashSet 来保存节点，其中节点类的哈希值计算如下：(a << 32 || b).通过这种方式，您可以立即查找先前的节点是否存在。记住也要重载“equals”（只有当比较对象是相同类型并且 a 和 b 相等时，它才应该返回 true）。

在已知边界的人口最多的系统中，1 将节省内存，但如果您的系统稀疏（如您所说），则 #2 可以节省大量内存，而不会降低效率。