7-2 哈夫曼编码译码 (25 分) 编写一个哈夫曼编码译码程序。

Question

按词频从小到大的顺序给出各个字符（不超过30个）的词频，根据词频构造哈夫曼树，给出每个字符的哈夫曼编码，并对给出的语句进行译码。 为确保构建的哈夫曼树唯一，本题做如下限定： （1）选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。 （2）若多棵二叉树根结点权值相等，按先后次序分左右，先出现的作为左子树，后出现的作为右子树。 生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。 输入格式: 第一行输入字符个数n； 第二行到第n行输入相应的字符及其词频(可以是整数，与可以是小数）； 最后一行输入需进行译码的串。 输出格式: 首先按树的先序顺序输出所有字符的编码，每个编码占一行； 最后一行输出需译码的原文，加上original:字样。 输出中均无空格
输入样例:
3
m1
n1
c2
10110
输出样例:
c:0
m:10
n:11
original:mnc
有厉害的能用c语言吗谢谢了

Answer 1

#include <iostream>
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#include<map>
#include<math.h>
#include <algorithm>
using namespace std;

/**
 *  树结点
 */
struct TreeNode{
    double data; //权值
    char ch;//字符
    struct TreeNode *left;//左孩子,默认指向空
    struct TreeNode *right;//右孩子
} Node;
map<string,char> m;  //定义一个map

/*********定义函数***************/
bool cmp(struct TreeNode a,struct TreeNode b);
TreeNode* createTree(TreeNode *v,int n);
void printCode(struct TreeNode *root,char code[],int location);
void f_decode(char decoding[],int len);
/****************************/
int main()
{
    
    int n;
    scanf("%d",&n);
    getchar();//吸收回车字符
    //定义n个结点，使用vector存放
    TreeNode v[2*n-1];
    //输入n个结点
    for(int i=0;i<n;i++){
        scanf("%c%lf",&v[i].ch,&v[i].data);
        v[i].left=NULL;//默认指向NULL
        v[i].right=NULL;
        getchar();
    }
    //输入需进行译码的串
    char decoding[1000]; 
    scanf("%s",decoding);
    int len = strlen(decoding);//统计长度

    //根节点
    TreeNode* root=(TreeNode*)malloc(sizeof(TreeNode));
    //生成树
    root=createTree(v,n);
    //cout<<"根节点权值为："<<root->data<<endl;

    char code[60]={0};//存储字符的编码
    //先序顺序输出所有字符的编码
    printCode(root,code,0);

    //解码
    /*
    for(int i=0;i<5;i++){//打印输入的一串字符
        printf("%c",decoding[i]);
    }
    printf("\n");
    
    cout<<"输出map："<<endl; 
    for(auto  &it:m){//打印map中的数据 
        string str=it.first;
        cout<<str<<":"<<it.second<<endl;
    }
    printf("\n字符串的长度为：%d\n",len);
    */
    f_decode(decoding,len);

    system("pause");
    return 0;
}
/**
 *解码 ，码——>原文
 */
void f_decode(char decoding[],int len)
{
    string str;
    int i=0;
    printf("original:");
    for(i=0;i<len;i++)
    {
        str+=decoding[i];//拼接key
        if(m.find(str)!=m.end()){//找到了key，输出
            printf("%c",m[str]); 
            str="";//清空key，重新拼接
        }
        else
        {
            //找不到key，什么也不用做，继续拼接，这个可以去掉
        }
    }
    printf("\n");
}

/**
 * 先序顺序输出所有字符的编码
 */
void printCode(TreeNode *root,char code[],int location){
    if (root == NULL) {
        return;
    }
    if(root->ch!='-')//说明已经遍历到叶子节点，输出序列
    {   
        printf("%c:",root->ch);
        string key="";
        for(int i=0;i<location;i++){//输出记录的长度。
            printf("%d",code[i]);   
            key+=to_string(code[i]);//to_string()将参数转为string类型
        }
        printf("\n");
           //cout<<"key:"<<key<<","<<"value："<<root->ch<<endl;
        m.insert(make_pair(key, root->ch));//将值以键值对的形式插入到map中
    }
    //该节点是左孩子,路径设0        
        code[location]=0; 
        location++;//下一个位置给下一个节点用
        printCode(root->left,code,location); //递归该节点。
        location--;//该节点递归完成。取消该节点的记录。
    
    //右孩子,1
        code[location]=1;
        location++;
        printCode(root->right,code,location);
        location--;
}

/**
 * 创建树
 */
TreeNode* createTree(TreeNode *v,int n){  
    
    int i=0,index=n-1; //i为0 ，从位置0开始合成。index是生成的结点该放的地方
    while(i<2*n-1) //当i走到最后一个结点，无需再构建，也可以使用index控制
    {
        //1.先排序
        sort(v+i,v+index,cmp);  //只对范围内的排序。随两个索引变化，排序的范围也变化
        //2.合并:拿出排好序序列中的前两个结点。
        TreeNode* node1 = &v[i++];//TreeNode* node1 = &v[i];i++;
        TreeNode* node2 = &v[i++];

        //3.生成新节点，给结点赋值
        TreeNode newNode=v[index];
        newNode.data=node1->data+node2->data; //权值相加
        newNode.ch='-';//随意设置，表示其为中间结点。
        newNode.left=node1;//设置左右孩子
        newNode.right=node2;

        //4.新节点放入到序列中
        v[++index]=newNode;
    }
    return &v[index-1]; //最后一个为根节点
}

/**
 * 排序规则 
 */
bool cmp(TreeNode a, TreeNode b)
{
    return a.data < b.data; //根据权值升序排序
}