【数据结构】课前测试_哈夫曼编码

这两节数据结构课都遇到了一个编程题，遇到两次了一模一样。第三次，可能也有很大概率是这个，感觉上课一点时间，感觉都没怎么听懂，必须下课看看。这次必须写好这个编程题冲冲冲。

![题目截图](https://blog.fivk.cn/usr/uploads/2021/11/3046072371.png)

题目如下：

### R6-1 哈夫曼编码 (10 分)

函数Select (HuffmanTree HT,int len,int &s1,int &s2)是从1到len中找出parent为0的且权值最小的节点编号赋给s1,s2,（s1的节点编号小于s2）；

函数void CreatHuffmanTree(HuffmanTree &HT,int n)是构造哈夫曼树；

函数void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)计算哈夫曼编码。

### 函数接口定义：

```cpp
void Select(HuffmanTree HT,int len,int &s1,int &s2);
void CreatHuffmanTree(HuffmanTree &HT,int n);
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n);
```

其中 `HT` 是哈夫曼树，`HC`是哈夫曼编码，` n`是叶子结点个数。

### 裁判测试程序样例：

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

typedef struct
{    char ch;
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree HT,int len,int &s1,int &s2);
void CreatHuffmanTree(HuffmanTree &HT,int n);
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n);
void show(HuffmanTree HT,HuffmanCode HC,int n);

int main()
{
    HuffmanTree HT;
    HuffmanCode HC;
    int n;
    cin >> n;
    CreatHuffmanTree(HT,n);
    CreatHuffmanCode(HT,HC,n);
    show(HT,HC,n);
    return 0;
}
void show(HuffmanTree HT,HuffmanCode HC,int n)
{
    for(int i=1;i<=n;i++)
        printf("%c:%s\n",HT[i].ch,HC[i]);
}

/* 请在这里填写答案 */
```

### 输入样例：

第一行输入一个数n(1<n<100)，表示叶子节点的个数，接下去输入n行，每行输入一个字符和一个整数，表示每个节点表示的字符和权值。

```in
5
A 8
B 10
C 2
D 11
E 1
```

### 输出样例：

输出n行，每行输出一个字符及其编码，字符与编码中“:”分隔。

```out
A:01
B:10
C:001
D:11
E:000
```

### 我写的（不知道对不对，等明天）：

我也不知道写了多久，差不多一个小时多。。。

```cpp
void Select(HuffmanTree HT, int len, int& s1, int& s2)
{
    int i;
    for (s1 = 0, i = 1; i < len; i++)
    {
        if (HT[i].parent == 0)
            if (HT[i].weight < HT[s1].weight)
            {
                s2 = s1;
                s1 = i;
            }
            else {
                if (HT[i].weight < HT[s2].weight)
                    s2 = i;
            }
    }
}

void CreatHuffmanTree(HuffmanTree& HT, int n)
{

HT = new HTNode[2 * n + 2];
    HT[0].ch = '\0';
    HT[0].weight = 100;
    HT[0].parent = HT[0].lchild = HT[0].rchild = 0;
    for (int i = 1; i <= n; i++)
    {
        getchar();
        scanf("%c %d", &HT[i].ch, &HT[i].weight);
        HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
    }

int i, s1 = 0, s2 = 0;
    for (i = n + 1; i <= 2 * n - 1; i++)
    {
        Select(HT, i, s1, s2);
        HT[i].ch = '\0';
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        HT[i].parent = 0;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[s1].parent = HT[s2].parent = i;
    }
}

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)
{
    HC = new char*[101];
    for (int k = 0; k < 101; k++)
        HC[k] = new char[101];

int i, j, p, q;
    for (i = 1; i <= n; i++)
    {
        for (j = 0, p = i, q = HT[p].parent; q != 0; p = q, q = HT[p].parent)
        {
            if (HT[q].lchild == p)
                HC[i][j] = '0';
            else
                HC[i][j] = '1';
            j++;
            HC[i][j] = '\0';
        }
    }
}
```

最后修改：2021 年 11 月 13 日