我哪里出错了？生成tictactoe游戏树

Question

我正试图用链表实现生成一棵tree移动树。我在启动板时填充了三个单元格，所以树应该有(9-3)！= 720个节点，但是在运行我的程序之后，它很快就挂起了。我哪里出错了？

#include <stdlib.h>
#include <stdio.h>

struct Node {

    struct Node *next_move;
    int cell[3][3];

};

struct Node *root, *position, *temp;
void generate_tree(struct Node *, int move);

int main() {

    root = (struct Node *) malloc (sizeof (struct Node));
    root->next_move = NULL;

     root->cell[0][0] = 1;
     root->cell[0][1] = 1;
     root->cell[0][2] = 1;

     generate_tree(root, 1); // computer's next move

    return 0;
}

void generate_tree(struct Node *root, int move) {

    position = root;    // use position to move down the linked list
    print_board(root);

    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {   // for all cells in root

            if (root->cell[j][i] == 0) { // if cell is empty

                temp = root;    // copy board
                temp->cell[j][i] = move; // make move

                while(1) {  // move to end of list
                    if (position->next_move == NULL) {
                        position->next_move = temp; // link new board at end of list
                        break;
                    } else { // move down list by 1
                        position = position->next_move; 
                        }
                }

                if (move == 1) {    // if it was the computers move
                    generate_tree(position, 2); // call self, with temp as new root, and opponent's move next
                } else {
                    generate_tree(position, 1); // call self, with temp as new root, and computers's move next
                }

            }

        }

    }

}
void print_board(struct Node *node) {

    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {

            printf("%d ",node->cell[j][i]);

        }
        printf("\n");
    }
}

Answer 1

最后，你第二次撞到了这个：

while(1) {  // move to end of list
    if (position->next_move == NULL) {
        position->next_move = temp; // link new board at end of list
        break;
    } else { // move down list by 1
        position = position->next_move; 
    }
}

当您第一次点击它时，您将root->next_move替换为root，将您的列表转换为指向自身的单个节点。下一次，您在这个循环中，第一个条件永远不会满足，循环也不会终止。

看起来问题就在这里：

temp = root;    // copy board

当然，这一行应该分配一个新的空节点：

temp = (struct Node *) malloc (sizeof (struct Node));
temp->next_move = NULL;

这并不是说这将使你的程序按照你的意图工作，但它应该有助于克服你所要求的窍门。