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

题目截图

题目如下:

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)计算哈夫曼编码。

函数接口定义:

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是叶子结点个数。

裁判测试程序样例:

#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行,每行输入一个字符和一个整数,表示每个节点表示的字符和权值。

5
A 8
B 10
C 2
D 11
E 1

输出样例:

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

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

我写的(不知道对不对,等明天):

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

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 日
如果觉得我的文章对你有用,请随意赞赏