实验题3:构造哈夫曼树和生成哈夫曼编码 （一）实验目的：领会哈夫曼的构造过程以及哈夫曼编码的生成过程。 （二）实验内容：编写一个程序exp3-3.cpp，构造一棵哈夫曼树，输出对应的哈夫曼编码和平均查找长度。并对如表1所示的数据进行验证。 表1 单词及出现的频度 单词 The of a to and in that he is at on for His are Be 出现频度 1192 677 541 518 462 450 242 195 190 181 174 157 138 124 123 设计相关算法，其中包含如下函数。 CreateHT(HTNode ht[],int n)：由含有n个叶子结点的ht构造完整的哈夫曼树。 CreateHCode(HTNode ht[],HCode hcd[],int n)：由哈夫曼树ht构造哈夫曼编码hcd。 DispHCode(HTNode ht[],HCode hcd[],int n)：输出哈夫曼树ht和哈夫曼编码hcd中n个叶子结点的哈夫曼编码。

以下是基于C++的实现代码，包含CreateHT、CreateHCode、DispHCode三个函数的实现。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1005;
const int MAXM = MAXN * 2 - 1;

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

struct HCode {
    char code[MAXN];
    int start;
};

void CreateHT(HTNode ht[], int n) {
    int m = 2 * n - 1;
    for (int i = 0; i < n; i++) {
        cin >> ht[i].weight;
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
    }
    for (int i = n; i < m; i++) {
        int min1 = -1, min2 = -1;
        for (int j = 0; j < i; j++) {
            if (ht[j].parent == -1) {
                if (min1 == -1) {
                    min1 = j;
                } else if (min2 == -1) {
                    min2 = j;
                } else if (ht[j].weight < ht[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (ht[j].weight < ht[min2].weight) {
                    min2 = j;
                }
            }
        }
        ht[i].weight = ht[min1].weight + ht[min2].weight;
        ht[min1].parent = i;
        ht[min2].parent = i;
        ht[i].lchild = min1;
        ht[i].rchild = min2;
    }
}

void CreateHCode(HTNode ht[], HCode hcd[], int n) {
    for (int i = 0; i < n; i++) {
        int c = i, f = ht[c].parent;
        while (f != -1) {
            if (ht[f].lchild == c) {
                hcd[i].code[hcd[i].start++] = '0';
            } else {
                hcd[i].code[hcd[i].start++] = '1';
            }
            c = f;
            f = ht[c].parent;
        }
        reverse(hcd[i].code, hcd[i].code + hcd[i].start);
    }
}

void DispHCode(HTNode ht[], HCode hcd[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cout << i << " " << hcd[i].code << endl;
        sum += ht[i].weight * hcd[i].start;
    }
    cout << "Average Length: " << (double)sum / n << endl;
}

int main() {
    int n;
    cin >> n;
    HTNode ht[MAXM];
    HCode hcd[MAXN];
    CreateHT(ht, n);
    CreateHCode(ht, hcd, n);
    DispHCode(ht, hcd, n);
    return 0;
}

在该实现中，我们首先定义了两个结构体，HTNode表示哈夫曼树的节点，HCode表示哈夫曼编码的结构体。其中，HCode中的code数组表示哈夫曼编码，start表示该编码的起始位置（即最高位的位置）。接着，我们实现了三个函数，分别为：

- CreateHT：由含有n个叶子结点的ht构造完整的哈夫曼树。
- CreateHCode：由哈夫曼树ht构造哈夫曼编码hcd。
- DispHCode：输出哈夫曼树ht和哈夫曼编码hcd中n个叶子结点的哈夫曼编码。

在主函数中，我们读入叶子节点的权值，并调用CreateHT、CreateHCode和DispHCode三个函数，输出哈夫曼编码和平均查找长度。

需要注意的是，在CreateHCode函数中，我们采用了反向存储哈夫曼编码的方式，即先存储最低位的编码，最后再将整个编码翻转过来，这样可以方便地输出哈夫曼编码。