7-2 哈夫曼编码译码分数 25_C

编写一个哈夫曼编码译码程序。

按词频从小到大的顺序给出各个字符（不超过30个）的词频，根据词频构造哈夫曼树，给出每个字符的哈夫曼编码，并对给出的语句进行译码。

为确保构建的哈夫曼树唯一，本题做如下限定：

（1）选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。

（2）若多棵二叉树根结点权值相等，按先后次序分左右，先出现的作为左子树，后出现的作为右子树。

生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。

输入格式:

第一行输入字符个数n；

第二行到第n行输入相应的字符及其词频(可以是整数，与可以是小数）；

最后一行输入需进行译码的串。

输出格式:

首先按树的先序顺序输出所有字符的编码，每个编码占一行；

最后一行输出需译码的原文，加上original:字样。

输出中均无空格

输入样例:

输出样例:

c:0
m:10
n:11
original:mnc

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int N;//字符个数
const int maxn = 1050000;
struct HuffmTree{//哈弗曼树结构体
    char ch;//字符
    double value;//词频
    HuffmTree *left;//左子树
    HuffmTree *right;//柚子树
}tree[maxn];//tree是结构体数组
mapm;//映射m
//自定义比较函数，按词频升序排序
bool Compare(HuffmTree x,HuffmTree y){
        return x.value < y.value;
}
//创建哈弗曼树
HuffmTree* BuildingTree(int N){
    int i = 0,index = N - 1;//i = 0，表示从位置0开始合成，index是生成的节点放置的地方
    while(i < 2*N-1){//while当i没走到最后一个节点就不会停止
        sort(tree+i,tree+index+1,Compare);//排序，找出词频小的两棵子树
        HuffmTree *Node = &tree[i++];//拿出词频最小的两棵子树Node,Node2
        HuffmTree *Node2 = &tree[i++];
        HuffmTree NewNode = tree[index];//定义新生成的中间节点
        NewNode.value = Node->value + Node2->value;//中间节点的权值等于左右节点的权值相加
        NewNode.ch = '.';//设置中间节点的标记
        NewNode.left = Node;//最小的两棵子树被当为左右子树
        NewNode.right = Node2;
        tree[++index] = NewNode;//把新生成的节点加入到结构体数组中
    }
    return &tree[index-1];//返回根节点
}
//先序递归，打印各字符的编码
void PrintCoding(HuffmTree *root,char coding[],int index){
    if(!root) return;//如果是空树，则返回
    if(root->ch != '.'){//如果是叶子节点
        printf("%c:",root->ch);//打印字符
        string str = "";
        for(int i = 0;i < index;i++){//for循环打印出该字符的编码
            printf("%d",coding[i]);
            str += to_string(coding[i]);//转化为string类型
        }
        printf("\n");
        m[str] = root->ch;//插入到map中
    }
    coding[index] = 0;//左子树设置为0
    index++;//下一个节点
    PrintCoding(root->left,coding,index);//递归访问该节点
    index--;//该节点递归完成，取消该节点的记录
    
    coding[index] = 1;//右子树设置为1
    index++;//下一个节点
    PrintCoding(root->right,coding,index);//递归访问该节点
    index--;//该节点递归完成，取消该节点的记录
}
//打印译码后的字符串
void PrintDecode(string decoding){
    string str;
    printf("original:");
    for(int i = 0;i < decoding.length();i++){
        str+=decoding[i];//拼接字符对应的编码
        if(m.find(str) != m.end()){//找到了该字符对应的编码
            printf("%c",m[str]);//打印该字符
            str = "";
        }
    }
    printf("\n");
}
//主函数
int main()
{
    scanf("%d",&N); getchar();//输入字符个数
    for(int i = 0;i < N;i++){//输入字符和相应的词频
        scanf("%c%lf",&tree[i].ch,&tree[i].value);
        tree[i].left = NULL;//左右子树为空子树
        tree[i].right = NULL;
        getchar();//缓冲换行
    }
    string decoding;//输入需进行译码的串
    cin>>decoding;
    HuffmTree *root = (HuffmTree*)malloc(sizeof(HuffmTree));//动态分配根节点
    root = BuildingTree(N);//建树
    char coding[1050] = {};//编码字符串，初始化为0
    PrintCoding(root,coding,0);//打印各字符的编码
    PrintDecode(decoding);//打印译码后的字符串
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/798556.html

7-2 哈夫曼编码译码分数 25

发表评论

评论列表（0条）

7-2 哈夫曼编码译码 分数 25

发表评论

评论列表（0条）

7-2 哈夫曼编码译码分数 25