哈夫曼树编码选择函数代码c++

以下是C++实现的哈夫曼树编码选择函数代码：

void select(HuffmanTree HT, int n, int &s1, int &s2) {
    int i;
    int min1, min2;
    min1 = min2 = MAXVALUE;
    for (i = 1; i <= n; i++) {
        if (HT[i].parent == 0) {
            if (HT[i].weight < min1) {
                min2 = min1;
                s2 = s1;
                min1 = HT[i].weight;
                s1 = i;
            } else if (HT[i].weight < min2) {
                min2 = HT[i].weight;
                s2 = i;
            }
        }
    }
}

该函数的作用是在哈夫曼树中选择权值最小的两个节点。其中，HT是哈夫曼树，n是叶子节点的个数，s1和s2是指向权值最小的两个节点的指针。该函数的实现过程是遍历哈夫曼树中所有未被标记的节点，找到其中权值最小的两个节点，并将它们的下标分别赋值给s1和s2。

相关问题

构造哈夫曼树并编码代码c++

构造哈夫曼树是一种经典的树形编码方法，主要用于数据压缩和编码领域。构造哈夫曼树的过程主要分为以下几个步骤：

1. 统计字符出现频率：首先需要统计待编码文本中每个字符出现的频率，可以通过遍历文本字符来实现。将字符频率存储于一个数组或者字典中。

2. 构建哈夫曼树：基于字符频率，可以选择合适的数据结构来存储和构建哈夫曼树。在构建过程中，首先将每个字符频率作为一个独立的叶子节点，然后再通过合并最小频率的节点来构造树。

3. 分配编码：根据构建好的哈夫曼树，给每个字符分配一个唯一的编码。从根节点开始，标记左子树为0，右子树为1，遍历哈夫曼树至叶子节点，即可得到每个字符的编码。为了方便查找和使用编码，可以使用数组或者字典来存储字符和其编码的对应关系。

4. 编写编码代码：根据步骤3中得到的字符和编码的对应关系，编写编码函数来实现文本编码。编码函数接受待编码的文本作为输入，然后将文本中的每个字符替换为其对应的编码。

下面是一个简单的C代码示例来演示哈夫曼树的构建和编码过程：

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

typedef struct Node {
    char character;
    int frequency;
    struct Node* left;
    struct Node* right;
} Node;

// 构建哈夫曼树
Node* buildHuffmanTree(char* characters, int* frequencies, int n) {
    Node** nodes = (Node**)malloc(sizeof(Node*) * n);
    
    for(int i = 0; i < n; i++) {
        nodes[i] = (Node*)malloc(sizeof(Node));
        nodes[i]->character = characters[i];
        nodes[i]->frequency = frequencies[i];
        nodes[i]->left = NULL;
        nodes[i]->right = NULL;
    }
    
    // 构建哈夫曼树
    while(n > 1) {
        Node* min1 = nodes[0];
        int min1Index = 0;
        
        for(int i = 1; i < n; i++) {
            if(nodes[i]->frequency < min1->frequency) {
                min1 = nodes[i];
                min1Index = i;
            }
        }
        
        Node* min2 = nodes[0 == min1Index ? 1 : 0];
        int min2Index = 0 == min1Index ? 1 : 0;
        
        for(int i = 0; i < n; i++) {
            if(i != min1Index && nodes[i]->frequency < min2->frequency) {
                min2 = nodes[i];
                min2Index = i;
            }
        }
        
        Node* parent = (Node*)malloc(sizeof(Node));
        parent->character = '\0';
        parent->frequency = min1->frequency + min2->frequency;
        parent->left = min1;
        parent->right = min2;
        
        nodes[min1Index] = parent;
        
        for(int i = min2Index; i < n - 2; i++) {
            nodes[i] = nodes[i + 1];
        }
        
        nodes[n - 2] = parent;
        
        n--;
    }
    
    return nodes[0];
}

// 分配编码
void assignCode(Node* tree, char** codes, char* code, int depth) {
    if(tree->left == NULL && tree->right == NULL) {
        codes[tree->character] = code;
        return;
    }
    
    code[depth] = '0';
    code[depth + 1] = '\0';
    assignCode(tree->left, codes, code, depth + 1);
    
    code[depth] = '1';
    code[depth + 1] = '\0';
    assignCode(tree->right, codes, code, depth + 1);
}

// 编码函数
char* encodeText(char* text, char** codes) {
    int textSize = strlen(text);
    int totalCodeLength = 0;
    char* encodedText = (char*)malloc(sizeof(char) * (textSize * 8 + 1));
    
    for(int i = 0; i < textSize; i++) {
        char* code = codes[text[i]];
        int codeLength = strlen(code);
        
        for(int j = 0; j < codeLength; j++) {
            encodedText[totalCodeLength] = code[j];
            totalCodeLength++;
        }
    }
    
    encodedText[totalCodeLength] = '\0';
    
    return encodedText;
}

int main() {
    // 示例数据
    char characters[] = {'A', 'B', 'C', 'D', 'E'};
    int frequencies[] = {2, 3, 4, 6, 8};
    int n = sizeof(characters) / sizeof(char);
    
    // 构建哈夫曼树
    Node* huffmanTree = buildHuffmanTree(characters, frequencies, n);
    
    // 分配编码
    char* codes[256];
    char* code = (char*)malloc(sizeof(char) * 256);
    assignCode(huffmanTree, codes, code, 0);
    
    // 编码文本
    char* text = "ABCDAEBD";
    char* encodedText = encodeText(text, codes);
    
    printf("原始文本：%s\n", text);
    printf("编码后的文本：%s\n", encodedText);
    
    return 0;
}

注意，这只是一个简单的示例代码，实际应用中可能还需要考虑更多的边界条件和错误处理。

哈夫曼树的设计源代码 C++

以下是哈夫曼树的设计源代码，使用了C++语言：

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

// 定义哈夫曼树节点结构体
struct HuffmanNode {
    int weight; // 权值
    HuffmanNode *leftChild; // 左子节点指针
    HuffmanNode *rightChild; // 右子节点指针

    // 构造函数
    HuffmanNode(int w) {
        weight = w;
        leftChild = rightChild = nullptr;
    }
};

// 定义哈夫曼树类
class HuffmanTree {
private:
    HuffmanNode *root; // 根节点指针

    // 比较函数对象，用于优先队列排序
    struct cmp {
        bool operator()(HuffmanNode *a, HuffmanNode *b) {
            return a->weight > b->weight;
        }
    };

public:
    // 构造函数
    HuffmanTree(int weights[], int n) {
        // 创建优先队列
        priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;

        // 将每个权值转换为节点，并加入优先队列
        for (int i = 0; i < n; i++) {
            pq.push(new HuffmanNode(weights[i]));
        }

        // 不断取出两个最小的节点，合并为一个新节点，直到队列中只剩一个节点，即为根节点
        while (pq.size() > 1) {
            HuffmanNode *left = pq.top();
            pq.pop();
            HuffmanNode *right = pq.top();
            pq.pop();

            HuffmanNode *newNode = new HuffmanNode(left->weight + right->weight);
            newNode->leftChild = left;
            newNode->rightChild = right;
            pq.push(newNode);
        }

        root = pq.top();
    }

    // 析构函数
    ~HuffmanTree() {
        destroy(root);
    }

    // 销毁哈夫曼树
    void destroy(HuffmanNode *node) {
        if (node != nullptr) {
            destroy(node->leftChild);
            destroy(node->rightChild);
            delete node;
        }
    }

    // 获取哈夫曼编码
    void getHuffmanCode(HuffmanNode *node, string code, string codes[]) {
        if (node->leftChild == nullptr && node->rightChild == nullptr) {
            codes[node->weight] = code;
            return;
        }

        getHuffmanCode(node->leftChild, code + "0", codes);
        getHuffmanCode(node->rightChild, code + "1", codes);
    }

    // 输出哈夫曼编码表
    void printHuffmanCode(string codes[], int n) {
        for (int i = 0; i < n; i++) {
            cout << "字符 " << char(i) << " 的哈夫曼编码为：" << codes[i] << endl;
        }
    }
};

int main() {
    const int n = 6;
    int weights[n] = {2, 3, 7, 10, 4, 2};
    string codes[n];

    HuffmanTree tree(weights, n);
    tree.getHuffmanCode(tree.root, "", codes);
    tree.printHuffmanCode(codes, n);

    return 0;
}

这个代码实现了哈夫曼树的创建、销毁、获取哈夫曼编码以及输出哈夫曼编码表的功能。