尝试将长度为 N 的字符串放入 NxN 矩阵时出现无限循环 — C 语言的 Word Soup 程序

Question

我一直在尝试用 C 语言制作一个单词汤程序来完成作业：该程序接受用户输入的单词并将它们放置在

NxN

板上，其中每个单元格都是一个字符。

但是，我遇到了一个问题：每当我尝试将长度恰好为

N

（矩阵的宽度或高度）的单词放置时，程序无法按预期将其正确地放入单行或单列中。

完整代码如下：

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

int input_lower_upper_limit(int inf, int sup, const char *message);
void initial_fill(int N, char board[N][N]);
void input_words(int K, int N, char words[K][N]);
void to_uppercase(char *p, int N);
void insert_into_board(int K, int N, char board[N][N], char words[K][N]);

int main()
{
    srand(time(0)); // Will be used later to replace the '.' chars once the words are fitted in
    int i, j;

    // Initial memory allocation for the board and array of words:
    int N = input_lower_upper_limit(10, 35, "Enter the size of the matrix: ");
    char (*board)[N] = malloc(N * N * sizeof(char));
    if (board == NULL)
    {
        printf("ERROR: Could not allocate memory for the board.\n");
        exit(EXIT_FAILURE);
    }

    int K = input_lower_upper_limit(N/2, 2*N, "Enter the number of words you want to input: ");
    char (*words)[N] = malloc(K * N * sizeof(char));
    if (words == NULL)
    {
        printf("ERROR: Could not allocate memory for the words.\n");
        free(board);
        exit(EXIT_FAILURE);
    }

    // Main functionality of the program:
    initial_fill(N, board);
    input_words(K, N, words);
    insert_into_board(K, N, board, words);

    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }

    // Free all allocated memory:
    free(words);
    free(board);
    return 0;
}

int input_lower_upper_limit(const int inf, const int sup, const char *message) {
    int n;
    do
    {
        printf("%s", message);
        scanf("%d", &n);
        fflush(stdin);

        if (n < inf || n > sup) printf("ERROR: The number entered must be between %d and %d.\n", inf, sup);
    }
    while (n < inf || n > sup);

    return n;
}

void initial_fill(const int N, char board[N][N])
{
    int i, j;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            board[i][j] = '.';
//          board[i][j] = rand()%26 + 65;
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }
}

void input_words(const int K, const int N, char words[K][N])
{
    int i;
    for (i = 0; i < K; i++)
    {
        printf("Enter word %d: ", i + 1);
        fgets(words[i], N+2, stdin);
        to_uppercase(words[i], N);
        words[i][strcspn(words[i], "\n")] = '\0';
        printf("words[%d] = %s\n", i, words[i]);
    }
}

void to_uppercase(char *p, const int N)
{
    int i;
    for (i = 0; i < N; i++)
    {
        if (p[i] >= 'a' && p[i] <= 'z')
        {
            p[i] -= 32;
        }
    }   
}

int check_space(int N, int x, int y, int dir, char board[N][N], char *word)
{
    int i, len = strlen(word);
    for (i = 0; i < len; i++)
    {
        int nx = x, ny = y;
        if (dir == 0) nx += i;       // LR
        else if (dir == 1) nx -= i;  // RL
        else if (dir == 2) ny += i;  // UD
        else if (dir == 3) ny -= i;  // DU

        if (nx < 0 || nx >= N || ny < 0 || ny >= N || board[nx][ny] != '.')
            return 0;  // No space or overlap
    }
    return 1;  // Space is free
}

void insert_into_board(const int K, const int N, char board[N][N], char words[K][N])
{
    int i, j, h, dir, len;
    int x_initial, y_initial;
    for (i = 0; i < K; i++) // Iterate over each word
    {
        len = strlen(words[i]);
        int placed = 0;
        while (!placed)  // Try until placement is successful
        {
            for (h = 0; h < K; h++)
            {
                if (strlen(words[h]) > N/2)
                {
                    if (rand()%2) dir = rand()%2;
                    else          dir = rand()%2 + 2;
                }
                else dir = rand()%4; // 0: LR - 1: RL - 2: UD - 3: DU
            }

            // Generate valid random starting positions
            x_initial = (dir == 0 || dir == 1) ? rand() % (N - len + 1) : rand() % N;
            y_initial = (dir == 2 || dir == 3) ? rand() % (N - len + 1) : rand() % N;

            printf("Printing before check_space()\n"); // Infinite loop happens here.
            if (check_space(N, x_initial, y_initial, dir, board, words[i]))
            {
                
                // Place the word if space is valid
                for (j = 0; j < len; j++)
                {
                    int x = x_initial, y = y_initial;
                    if (dir == 0) x += j;       // LR
                    else if (dir == 1) x -= j;  // RL
                    else if (dir == 2) y += j;  // UD
                    else if (dir == 3) y -= j;  // DU

                    board[x][y] = words[i][j];
                }
                placed = 1;  // Placement successful
            }
        }
    }
}

例如，对于

N = 10

、

K = 5

，输入像“cavaliers”这样的 9 个字母的单词将按预期工作，并产生如下所示的结果：

C A V A L I E R S .
. C A V A L I E R S
. . . . . . . . . .
. . . . . . . . . .
C A V A L I E R S .
. . . . . . . . . .
C A V A L I E R S .
. . . . . . . . . .
. . . . . . . . . .
. C A V A L I E R S

但是，当单词长度恰好等于

N

时，就会发生无限循环。例如，当输入像“tablespoon”这样的10个字母的单词时，就会发生错误，并且程序将永远不会停止打印“

Printing before check_space()

”行，这就是我认为我的代码失败的地方。

（一）预期结果：

T A B L E S P O O N
N O O P S E L B A T
. . . . . . . . . .
. . . . . . . . . .
T A B L E S P O O N
N O O P S E L B A T
. . . . . . . . . .
T A B L E S P O O N
. . . . . . . . . .
. . . . . . . . . .

实际结果： 程序进入无限循环。

我已经尝试调整起始位置计算数字并通过检查验证空间可用性，但我仍然缺少一些东西。任何有关我如何修复程序以正确适应最大尺寸的见解都将受到赞赏。

Answer 1

你遇到的问题是你填写黑板的方式。您分配了一个足够大的字符方形数组，可以容纳

N

行字母长，但您希望每行都是

check_space()

中以 null 结尾的 C 字符串。这就是

strlen()

所期望的。如果你的单词有 10 个字母长，则在

check_space()

word

中似乎指向它的五个副本（至少 - 你很幸运，末尾后面有一个空值）。

您需要使单词数组的行

N+1

长，并确保有一个

\0

终止每个单词。