我哪里做错了?生成游戏树

Question

我正在尝试使用链表实现生成一字棋移动树。我一开始在棋盘上填了三个单元格，所以树应该有(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;

这并不是说这将使您的程序按照您所期望的方式工作，但它应该有助于克服您所询问的问题。