javascript - C语言中的二叉树装箱算法

Question

我正在尝试做的事情:

我看到了this算法，它是用 javascript 制作的，我正在尝试在 C 中执行 Packing Blocks into a Fixed Rectangle。 在我的代码中，如下所示，我从 .txt 中读取数据。这部分没有问题，我只是制作了一个指向 struct Blocks 的指针数组，然后对它进行排序。 在那之后，我所做的与文章中的代码完全一样，同样的逻辑，这就是错误发生的地方。

我的代码:

#include "stdio.h"
#include "stdlib.h"

typedef struct Block
{
    struct Node* fit;
    int width;
    int height;
    int x;
    int y;
    int id;
} Block;

typedef struct Node {
    struct Node* down;
    struct Node* right;
    int used;   
    int width;
    int height;
    int x;
    int y;
} Node;

Node *findNode(Node *root, int w, int h);
Node *splitNode(Node **root, int w, int h);

int main()
{
    FILE *file;
    char line[80];
    Block **blocks; 
    int totalBoards, boardWidth, boardHeight, totalBlocks;
    int i = 1, j;

    Node *root = malloc(sizeof(Node));
    root->x = 0;
    root->y = 0;
    root->used = 0;
    root->id = 0;

    fopen_s(&file, "blocks.txt", "r");

    // Reading the file
    while (fgets(line, 80, file)) {
        if (i == 1) {
            sscanf_s(line, "%d\n", &totalBoards);
        } else if (i == 2) {
            sscanf_s(line, "%d\n", &boardWidth);
            root->width = boardWidth;
        } else if (i == 3) {
            sscanf_s(line, "%d\n", &boardHeight);
            root->height = boardHeight;
        } else if (i == 4) {
            sscanf_s(line, "%d\n", &totalBlocks);
            blocks = malloc(totalBlocks * sizeof(Block *));

        } else {            
            int w, h;
            blocks[i - 5] = malloc(sizeof(Block));
            sscanf_s(line, "%d %d", &w, &h);
            blocks[i - 5]->width = w;
            blocks[i - 5]->height = h;
            blocks[i - 5]->id = i - 5;
        }

        i++;
    }

    //Bubble sort
    for (i = 0; i < totalBlocks; i++) {

        for (j = 0; j < totalBlocks - i - 1; j++)

            if (blocks[j]->height < blocks[j + 1]->height) {                
                Block *b = blocks[j];
                blocks[j] = blocks[j + 1];
                blocks[j + 1] = b;
            }
    }

    // THE IMPORTANT PART
    // The logic used by the algorithm
    // fit function
    for (i = 0; i < totalBlocks; i++) {
        Block *block = blocks[i];   
        Node *node;
        if (node = findNode(root, block->width, block->height)) {
            block->fit = splitNode(&node, block->width, block->height);
        }
    }

    //Print the blocks
    for (i = 0; i < totalBlocks; i++) {
        Block *block = blocks[i];
        if (block->fit) {           
            printf("x %d y %d\n", blocks[i]->fit->x, blocks[i]->fit->y);
        }
    }

    return 0;
}

Node *findNode(Node *root, int w, int h) {
    printf("%d", root->id);
    if (root->used == 1) {
        //Error Here
        return findNode(root->down, w, h) || findNode(root->right, w, h);
    }
    else if ((w <= root->width) && (h <= root->height)) {
        return root;
    }
    else {
        return NULL;
    }
}

Node *splitNode(Node **root, int w, int h) {

    (*root)->used = 1;
    (*root)->down = malloc(sizeof(Node));
    (*root)->down->right = malloc(sizeof(Node));
    (*root)->down->down = malloc(sizeof(Node));
    (*root)->down->x = (*root)->x;
    (*root)->down->y = (*root)->y + h;
    (*root)->down->width = (*root)->width;
    (*root)->down->height = (*root)->height - h;
    (*root)->down->used = 0;
    (*root)->down->id = idCount;
    idCount++;


    (*root)->right = malloc(sizeof(Node));
    (*root)->right->right = malloc(sizeof(Node));
    (*root)->right->down = malloc(sizeof(Node));
    (*root)->right->x = (*root)->x + w;
    (*root)->right->y = (*root)->y;
    (*root)->right->width = (*root)->width - w;
    (*root)->right->height = (*root)->height;
    (*root)->right->used = 0;
    (*root)->right->id = idCount;
    idCount++;

    return *root;
}

错误:

这部分findNode返回的Node出错了

if (node = findNode(root, block->width, block->height)) {
    block->fit = splitNode(&node, block->width, block->height);
}

返回时

return findNode(root->down, w, h) || findNode(root->right, w, h);

因为当我在 splitNode 中使用变量 node 时

block->fit = splitNode(&node, block->width, block->height);

node 的所有属性都是 NULL，这会导致错误。

问题:

在这个 article 的代码中, 它返回以下内容

return this.findNode(root.right, w, h) || this.findNode(root.down, w, h);

在 C 中我回来了

return findNode(root->right, w, h) || findNode(root->down, w, h);

我认为错误就在这里。

解决方案？

我认为 返回 ___ || ___ 对两种语言的作用不同。所以我有两个问题:

1. 返回 ___ || ___ 在两种语言中做同样的事情？如果不是，有什么区别，JavaScript 中该代码的等效 C 代码是什么？
2. 我的代码有什么问题？为什么会发生该错误，而不是像在 javascript 代码中那样返回正确的节点？

Answer 1

您的假设是正确的，即 || 在 JavaScript 和 C 中具有不同的语义。

在 JavaScript 中，a || b 返回 a 如果 a 是“truthy”，b 如果 a 是 falsy 。

同时在 C 中，a || b 是一个 bool 表达式。它将始终返回 true 或 false 而不是原始表达式。

例如，5 || 0 在 JavaScript 中是 5 但在 C 中是 1。

替换 return findNode(root->right, w, h) || findNode(root->down, w, h); 和

Node *answer = findNode(root->right, w, h);
if (answer) return answer;
else return findNode(root->down, w, h);

应该可以。