Рекурсивно созданные связанные списки с классом C++

Question

Рекурсивно созданные связанные списки с классом C++

Я использую C++ для рекурсивного создания гексагональной сетки (используя многосвязный стиль списка). Я настроил его так, чтобы легко создавать соседние листы, но поскольку я делаю это рекурсивно, я действительно могу создать только все 6 соседей для данной плитки. Очевидно, это вызывает создание дублирующих плиток, и я пытаюсь каким-то образом избавиться от них. Поскольку я использую класс, проверка на нулевые указатели, похоже, не работает. Он либо не может конвертировать из моего класса Tile в int и int, либо каким-то образом конвертирует его, но делает это неправильно. Я явно устанавливаю все указатели на 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->neighbour[x])", и делаю ли я это "if(inputTile->neighbour[x]==NULL)" или что бы я ни делал, он просто не обрабатывает это должным образом. О, и я также знаю, что я не создал список полностью. Это только одно направление сейчас.

2

c++ linked-list hextiles

Источник

user349474 25 май '10 в 01:04

5 ответов

Другие вопросы по тегам c++ linked-list hextiles

user233522 25 май '10 в 01:09 2010-05-25 01:09 · Answer 1 · 2010-05-25 01:09

Если вы хотите создать гексагональную сетку, вы должны помнить, что ее легко смоделировать с помощью обычной сетки!

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

Это сделает жизнь НАМНОГО проще:)

Следовательно, самый простой способ будет

установить временную квадратную сетку m*n
заполнить его плиткой
пройти через сетку и правильно подключиться

Теперь соединения, основанные на диаграмме выше:

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]

... и у вас есть все нужные соединения (просто не забудьте проверить границы, чтобы решить, находится ли плитка не по краю) - если вы держите плитки по-другому, вы можете даже удалить сетку:).

user47984 25 май '10 в 01:52 2010-05-25 01:52 · Answer 2 · 2010-05-25 01:52

Создание. Рекурсия - это аккуратный и элегантный способ решения некоторых проблем, но он не идеален для каждой проблемы. Я подозреваю, что чисто рекурсивное решение для создания узлов будет гораздо более сложным (то есть менее элегантным), чем прямое итеративное решение Корнела Киселевича. Это потому что Tile Конструктор должен знать расположение всех плиток в его непосредственной близости, чтобы избежать воссоздания уже существующих узлов.

Traversal. Основная проблема в вашем коде обхода узла аналогична в том, что вы получите бесконечный цикл и перевернете стек, потому что каждый узел в конечном итоге "обратится" к своему родителю, начиная цикл снова. Я полагаю, вы пытаетесь посетить каждую плитку ровно один раз, верно? В таком случае TraverseGrid() должен иметь параметр, сообщающий, в каком направлении мы входим в узел, чтобы избежать обратного пути в этом направлении.

Но этого недостаточно - вам также нужно больше дисциплины, чтобы решить, в каком направлении идти. Простое растяжение во всех направлениях, кроме направления, из которого мы ввели, все равно будет замыкаться в бесконечном цикле и переполняться стеками, поскольку любые три соседние плитки будут циклически бесконечными. Чтобы сделать это рекурсивно, вам нужно по-настоящему подумать о том, какие стратегии будут посещать каждый узел один и только один раз.

Одной из возможностей будет изменение подписи TraverseGrid() в TraverseGrid(Tile *inputTile, int fromDir, bool leftmost) а затем с помощью следующих правил:

Если мы вошли сверху-слева, проходите только сверху-справа, минуя leftmost = false,
Если мы вошли снизу-слева или сверху-справа, пройдите только вниз-вправо, минуя leftmost = false,
Если leftmostи есть узел в нашем нижнем левом углу, а затем также перейти к этому узлу, передавая leftmost = true,

Конечно fromDir а также leftmost может быть объединен в один параметр, но это дает общее представление.

Другой альтернативой будет сохранение visited флаг в каждой ячейке, которая проверяется перед переходом к этой ячейке. Тогда ваш обход будет заполнен наводнением. Но опять же, простой итеративный обход, вероятно, будет намного проще и понятнее, и имеет дополнительное преимущество использования постоянного пространства стека.

user65845 25 май '10 в 01:18 2010-05-25 01:18 · Answer 3 · 2010-05-25 01:18

Я только догадываюсь о том, что делает MakeNeighbors(), но вместо того, чтобы делать вслепую InputTile->neighbor[x]=new Tile();Вы можете проверить, не является ли сосед [x] ненулевым, прежде чем создавать новый и инициализировать его. Например, если его родитель создает его и устанавливает всю информацию о соседе, то он не должен идти и создавать своего родителя.

Когда родитель создает детей, он также должен соответствующим образом определить других соседей детей, насколько он их знает. Таким образом, следует убедиться, что child[i] также является соседями с child[i-1] и child[i+1].

user12943 25 май '10 в 01:25 2010-05-25 01:25 · Answer 4 · 2010-05-25 01:25

Я на самом деле сделал то же самое, но мой шаблон был похож на это:

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) Выделите массив узлов (ноль, не выделяйте их). Всякий раз, когда вам нужно выделить узел, просто делайте это, но используйте адрес массива всякий раз, когда вам нужно сослаться на узел, если он заполнен нулем, если он имеет значение, используйте это значение. Огромные пустые массивы не должны занимать так много памяти, но если они делают...

2) Создайте HashSet для хранения ваших узлов, где значение Hash класса узла вычисляется следующим образом: (a << 32 || b). Таким образом, вы можете мгновенно посмотреть, существует ли предыдущий узел или нет. Не забудьте также перегрузить "равно" (оно должно возвращать true, только если сравниваемый объект имеет одинаковый тип, а a и b равны).

В большинстве населенных пунктов, где известны границы, 1 экономит память, но, если ваша система разрежена (как вы утверждаете), тогда № 2 может сэкономить МНОГО памяти без затрат на эффективность.

user56338 25 май '10 в 01:25 2010-05-25 01:25 · Answer 5 · 2010-05-25 01:25

В объявлении класса есть второй конструктор Tile(char *Filename);, Может быть, этот конструктор используется для создания главного узла, но не инициализирует neighbor должным образом? (Его реализация не показана.)

И на неродственном узле у вас есть дубликат strcpy() в конструкторе, который не служит какой-либо цели и может привести только к проблемам:

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