能不能帮忙写个哈夫曼编码的应用?

问题要求:找一篇英文文章,统计出每个字符出现的次数,然后以他们为权值,对每个字符进行编码,编码完成后对其编码进行译码。
要求:
a) 输入一篇英文文章,根据字符出现的次数给出哈夫曼编码方式。
b) 对英文文章进行编码;
c) 对编码进行译码核对正确性
d) 采用哈夫曼编码的思想,实现该文件的压缩和恢复功能,并提供压缩前后的占用空间之比。

请先 登录 后评论

1 个回答

好问星星
给你一段代码参考,可自行修改
//HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC,int n){
    *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
    char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符数组
    cd[n-1] = '\0';//字符串结束符
  
    for(int i=1; i<=n; i++){
        //从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
        int start = n-1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while(j != 0){
            // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
            if(HT[j].left == c)
                cd[--start] = '0';
            else
                cd[--start] = '1';
            //以父结点为孩子结点,继续朝树根的方向遍历
            c = j;
            j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i], &cd[start]);
    }
    //使用malloc申请的cd动态数组需要手动释放
    free(cd);
}
请先 登录 后评论
  • 1 关注
  • 0 收藏,82 浏览
  • 提出于 2022-09-12 09:04

相似问题