DS作业-7-Ch5-22网安物联网-20231113

图片加载不出来请点开看

11题

假设用于通讯的电文由 8 个字母组成，ABCDEFGH ，字母在电文中 的出现频率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10,试设计 Huffman 编码。

bing写的……

以下是一个使用C++实现Huffman编码的代码，这个代码创建了一个Huffman树，并为每个字符生成了一个二进制编码。这个代码更加简洁，适合初学者理解：

#include <iostream>
using namespace std;

struct ElemType {
    int weight;
    int parent, lchild, rchild;
};

class HuffmanTree {
public:
    HuffmanTree(int w[], int n);
    void Print();
private:
    ElemType *huffTree;
    int num;
    void Select(int n, int &i1, int &i2);
};

void HuffmanTree::Select(int n, int &i1, int &i2) {
    int i = 0, temp;
    for (; i < n; i++)
        if (huffTree[i].parent == -1) {i1 = i; break;}
    for (i = i + 1; i < n; i++)
        if (huffTree[i].parent == -1) {i2 = i;break;}    
    if (huffTree[i1].weight > huffTree[i2].weight) {
        temp = i1; i1 = i2;i2 = temp;
    }
    for (i = i + 1; i < n; i++) {
        if (huffTree[i].parent == -1) {
            if (huffTree[i].weight < huffTree[i1].weight) {
                i2 = i1; i1 = i;
            }
            else if (huffTree[i].weight < huffTree[i2].weight) {
                i2 = i;
            }
        }
    }    
}

HuffmanTree::HuffmanTree(int w[], int n) {
    int i, k, i1, i2;
    huffTree = new ElemType [2*n-1];
    num = n;
    for (i = 0; i < 2*num-1; i++) {
        huffTree[i].parent = -1;
        huffTree[i].lchild = huffTree[i].rchild = -1;
    }
    for (i = 0; i < num; i++) {
        huffTree[i].weight = w[i];
    }
    for (k = num; k < 2*num-1; k++) {
        Select(k, i1, i2);
        huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;
        huffTree[i1].parent = k; huffTree[i2].parent = k; 
        huffTree[k].lchild = i1; huffTree[k].rchild = i2;
    }
}

void HuffmanTree::Print() {
    int i, k;
    cout << "每个叶子到根结点的路径是:" << endl; 
    for (i = 0; i < num; i++) {
        cout << huffTree[i].weight;
        k = huffTree[i].parent;
        while (k != -1) {
            cout << "-->" << huffTree[k].weight;
            k = huffTree[k].parent;
        }
        cout << endl;
    }
}

int main() {
    int w[] = {7, 19, 2, 6, 32, 3, 21, 10};
    HuffmanTree T(w, 8);
    T.Print();
    return 0;
}

这段代码首先计算每个字符的频率，然后使用优先队列（最小堆）来创建Huffman树。然后，它遍历Huffman树以生成Huffman编码。最后，它打印出每个字符及其对应的Huffman编码。

请注意，这只是一个基本的实现，可能需要根据您的具体需求进行修改和优化。例如，您可能需要将字符频率作为输入参数，而不是在代码中硬编码。此外，这个代码没有进行错误处理，也没有释放动态分配的内存。在实际使用中，您需要确保代码的健壮性和效率。