关于#c++#的问题：请教一下各位专家,这段代码哪里有错误,为啥输出不了哈夫曼编码.(本人初学者,写的代码很烂)

Question

#include <iostream>
#include <cstring>
using namespace std;

struct treenode{
    int value;
    char element;
    treenode *left, *right;
    treenode *next;
};

struct Queue{
    treenode *front, *rear;
};

void initialQueue(Queue *queue) {
    treenode *node = new treenode;
    queue->front = queue->rear = node;
    node->next = nullptr;
}

treenode *createnode(char element, int value) {
    treenode *node = new treenode;
    node->right = node->left = nullptr;
    node->element = element;
    node->value = value;
    node->next = nullptr;
    return node;
}

void offerqueue(Queue *queue, char element, int value) {
    treenode *node = new treenode;
    node->element = element;
    node->value = value;
    node->next = nullptr;
    treenode *pre = queue->front;
    while(pre->next && pre->next->value <= value) {
        pre = pre->next;
    }
    node->next = pre->next;
    pre->next = node;

    if (node->next == nullptr) {
        queue->rear = node;
    }
}

treenode *pollQueue(Queue *queue){
    treenode *node = queue->front->next;
    queue->front->next = queue->front->next->next;
    if(queue->rear == node) queue->rear = queue->front;
    return node;
}

char *encode(treenode *root, char element) {
    if(root == nullptr) return nullptr;
    if(root->element == element) return "";
    char *str = encode(root->left, element);
    char *s = new char[10];
    if(str != nullptr) {
        s[0] = '0';
        str = strcat(s, str);
    } else {
        str = encode(root->right, element);
        if(str != nullptr) {
            s[0] = '1';
            str = strcat(s, str);
        }
    }
    return str;
}

void printencode(treenode *root, char element) {
    cout << element << ":" << encode(root, element) << " ";
}

void printQueue(Queue *queue){
    cout << "<<< ";
    treenode *node = queue->front->next;
    while (1) {
        cout << node->element << " ";
        if(node == queue->rear) break;
        else node = node->next;
    }
    cout << "<<<" << endl;
}

int main() {
    string Huffman = "The Chinese official said he viewed the Trump Presidency not as an aberration but as the product of a failing political system. This jibes with other accounts. The Chinese leadership believes that the United States, and Western democracies in general, haven’t risen to the challenge of a globalized economy, which necessitates big changes in production patterns, as well as major upgrades in education and public infrastructure. In Trump and Trumpism, the Chinese see an inevitable backlash to this failure.";
    char Arr[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
                  'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
    int *arr = new int[26]();
    for(int j = 0; j < 26; j++) {
        for(int i = 0; i < Huffman.size(); i++) {
            if(tolower(Huffman[i]) == Arr[j]) {
                arr[j]++;
            }

        }
    }
    for(int m = 0; m < 26; ++m) {
        cout << Arr[m] << ":" << arr[m] << " ";
    }
    cout << endl;

    Queue queue;
    initialQueue(&queue);
    for(int i = 0; i < 26; i++) {
        offerqueue(&queue, createnode(Arr[i], arr[i])->element, createnode(Arr[i], arr[i])->value);
    }
    printQueue(&queue);

//    构建哈夫曼树
    while(queue.front != queue.rear) {
        treenode *left = pollQueue(&queue);
        treenode *right = pollQueue(&queue);
        treenode *node = createnode(' ', left->value + right->value);
        node->left = left;
        node->right = right;
        offerqueue(&queue, node->element, node->value);
    }
    treenode *root = pollQueue(&queue);

    printencode(root, 'a');

    for(int i = 0; i < 26; i++) {
        printencode(root, Arr[i]);
    }

    delete[] arr;

    return 0;
}

请教一下各位专家,这段代码哪里有错误,为啥输出不了哈夫曼编码.(本人初学者,写的代码很烂)

Answer 1

本答案参考 多次询问 ChatGPT-3.5 后选择的最佳回答，若是满意，还请采纳，谢谢

1. 内存管理问题
   • 在offerqueue函数中，创建了一个新的node，但是没有初始化它的left和right指针。虽然在这个函数中可能不需要这两个指针的正确初始化（因为这里主要是处理队列操作），但这是一个潜在的隐患。
   • 在encode函数中，存在内存泄漏问题。每次调用strcat时，都会返回一个新的字符串地址，但没有释放之前分配的内存。例如：
     • 当str不为nullptr时，s[0] = '0'; str = strcat(s, str);这部分代码，没有释放s之前可能分配的内存（如果有的话），并且会导致str指向的原始内存泄漏。
     • 同理，当str为nullptr且在处理右子树的情况时也有同样的问题。
2. 逻辑错误
   • 在encode函数中，if(root->element == element) return "";这部分逻辑可能存在问题。在构建哈夫曼树时，内部节点的element可能是空白字符（在构建树的过程中创建了值为' '的节点），而这里直接比较可能会导致无法正确找到编码路径。
   • 在offerqueue函数中，逻辑可能存在错误。while(pre - > next&&pre - > next - > value<=value)这个循环可能不会按照预期将节点插入到正确的位置。如果有多个节点具有相同的值，可能会导致插入顺序不正确。
   • 在printencode函数中，直接调用encode函数可能会返回一个未正确处理的字符串指针。由于encode函数存在内存管理问题，这里可能会导致未定义行为。
3. 编码问题
   • 在main函数中，offerqueue(&queue, createnode(Arr[i], arr[i])->element, createnode(Arr[i], arr[i])->value);这行代码存在问题。这里创建了一个新的节点，然后使用这个新节点的element和value，但是这个新节点没有被正确地加入到队列中。应该直接将创建的节点加入队列，而不是分别取其成员的值加入。

以下是一些修改建议：

1. 在encode函数中，正确管理内存，避免内存泄漏。
2. 在offerqueue函数中，重新审视插入逻辑，确保节点按照正确的顺序插入。
3. 在printencode函数中，确保encode函数返回的指针是有效的并且正确处理内存。
4. 在main函数中，正确地将节点加入队列。