C:霍夫曼编码

Question

我需要编写一个函数，它是系统的一部分，以便在字符串上使用霍夫曼编码。这个函数扫描一个字符串，然后根据字符串中的字符生成一个单例霍夫曼树列表。但是，当我运行它时，这个函数什么也不做。谁能帮我找出这个函数出了什么问题？

hufflist* build_hufflist(char* s)
{
    char* letters = malloc(strlen(s));
    int x;

    int letterspos = 0;
    hufflist* output = malloc(sizeof(hufflist));
    output = NULL;

    char* scopy = strdup(s);
    make_capital(scopy);

    for(x = 0 ; x < strlen(s) ; x++) {
        if(('a' <= scopy[x]) && (scopy[x] <= 'z')) {
            scopy[x] -= 32;
        }

        if(char_in_array(letters, s[x] == 0)) {
            letters[letterspos] = scopy[x];
            letterspos++;
            hl_insert(output, huff_singleton(scopy[x], char_count(scopy, scopy[x])));
        }
    }
    return output;
}

char_in_array是返回字符是否在数组中的函数，char_count返回字符在数组中的次数。我对这两种方法都进行了测试，它们都能正常工作。

另外，下面是相关的数据定义

typedef struct leaf leaf;
typedef struct node node;
typedef struct huff huff;
typedef struct hufflist hufflist;

enum huff_tag { LEAF, NODE };

struct leaf {
    char c;
    int n;
};

struct node {
    int n;
    huff *lsub;
    huff *rsub;
};

union huff_union {
    leaf leaf;
    node node;
};

struct huff {
    enum huff_tag tag;
    union huff_union h;
};

struct hufflist {
    huff* val;
    hufflist* next;
};

Answer 1

以下是我发现的几个问题。

1)你将letters锁定，然后开始使用它，而不初始化它指向任何基本情况的数据(例如，全0，或者s的副本，等等)。相反，如果letterspos = 0用于指示letters为空，那么char_in_array()可能也需要该信息。

2)将output设置为空，然后立即将其设置为NULL并最终返回该值。

3)在scopy上调用make_capital()，然后在循环中执行类似的逻辑。

4)将布尔值(0或1)传递给char_in_array()作为其第二个参数。您可能打算将== 0放在对char_in_array()的调用之外。

4a)函数char_in_array()只接受指向letters的指针和要检查的字符。它不以letterspos为例。因此，必须将letters的"end“嵌入到数组本身中(例如，使用nul终止符(参见1))，否则您也需要传递letterspos。

hufflist* build_hufflist(char* s)
{
    char* letters = malloc(strlen(s));  // 1) maybe calloc(strlen(s), 1) or calloc(256, 1) instead?
    int x;

    int letterspos = 0;
    hufflist* output = malloc(sizeof(hufflist));
    output = NULL;  // 2) probably not what you intended

    char* scopy = strdup(s);
    make_capital(scopy);

    for(x = 0 ; x < strlen(s) ; x++) {
        if(('a' <= scopy[x]) && (scopy[x] <= 'z')) {  // 3) didn't make_capital() already do this?
            scopy[x] -= 32;
        }

        if(char_in_array(letters, s[x] == 0)) {  // 4) should the == 0 be outside the call to char_in_arrays? 4a) doesn't char_in_array need letterspos too?
            letters[letterspos] = scopy[x];
            letterspos++;
            hl_insert(output, huff_singleton(scopy[x], char_count(scopy, scopy[x])));
        }
    }
    return output;
}

编辑看起来你的代码重复地扫描整个字符串(即，你为你找到的每个新字符调用char_count() )，这并不是最优的。您可以在一次传递中获得字符串中所有字符的计数，如下所示：

unsigned int char_counts[256] = { 0 };
unsigned char *ptr = (unsigned char*) scopy;

for (; *ptr; ++ptr)
  ++char_counts[*ptr];

char_counts现在包含copy中包含的每个字符的计数，并由(无符号)字符值本身进行索引。字符串中不包含的字符的计数将为零。所以你可以这样做：

for (x = 0; x < 256; ++x)
  if (char_counts[x])
    hl_insert(output, huff_singleton(x, char_counts[x]));

我假设插入的顺序并不重要，这可能是真的，也可能不是。