C语言中的二叉树装箱算法 [英] Binary Tree Bin Packing Algorithm in C

问题描述

我看到了此算法，它是用javascript制作的，我正在尝试在C语言中将将块打包成固定矩形。
在我的代码如下所示，我从 .txt 中读取数据。这部分没有问题，我只是对 struct块进行了一系列指针处理，然后对其进行了排序。
之后，我的工作和文章中的代码完全一样，逻辑相同，这就是发生错误的地方。

I saw this Algorithm, it's made with javascript and I'm trying to do Packing Blocks into a Fixed Rectangle in C. In my code, shown below, I read data from a .txt. This part have no problem, I'm just making a array of pointers to struct Blocks and after I sort it. After that I'm doing exactly like the code in the article, same logic, and that is where the errors are happening.

#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);

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

because when I use the varible node in splitNode

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

节点的所有属性均为NULL，

all atributes of the node are NULL and it's causing a error.

在此文章，它返回了以下内容

In the code of this article, it's returned the following

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);

我认为错误在这里。

我认为返回___ || ___ 两种语言的效果都不相同。所以我有两个问题：

I think that return ___ || ___ is not doing the same for both languages. So I have two questions:

1. 返回___ || ___ 在两种语言中都使用相同的ins吗？如果不是，则有什么区别，以及javascript中该代码的C代码等效项是什么？


2. 我的代码有什么问题？为什么会发生该错误，而不像javascript代码那样返回正确的节点？

1. return ___ || ___ is doing the same ins both languages? If not, what is the difference and what is the C code equivalent for that code in javascript?
2. What is wrong with my code? Why is that error happening and not returning the correct node like in the javascript code?

推荐答案

您认为 || 在JavaScript和C中具有不同的语义是正确的。

You are correct in your assumption that || has different semantics in JavaScript and C.

在JavaScript中， a || b 如果 a 是真且 b返回 a 如果 a 是虚假。

In JavaScript, a || b returns a if a is "truthy" and b if a is falsy.

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

Meanwhile in C, a || b is a boolean expression. It will always return true or false instead of the original expressions.

例如， 5 || 0 在JavaScript中为 5 ，而在C语言中为 1 。

For example, 5 || 0 is 5 in JavaScript but 1 in C.

替换返回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);

应该可以。

这篇关于C语言中的二叉树装箱算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！