哈夫曼树编解码

女爷i 2022-04-16 02:45 169阅读 0赞

问题 B: DS\_6.14 给定报文，哈弗曼编码、译码(by Yan)  
时间限制: 20 Sec 内存限制: 256 MB  
提交: 303 解决: 218  
\[提交\]\[状态\]\[讨论版\]  
题目描述  
已知某段通信报文内容，对该报文进行哈弗曼编码，并计算平均码长。  
(1)统计报文中各字符出现的频度。(字符集范围为52个英文字母，空格，英文句号。报文长度<=200)  
(2)构造一棵哈弗曼树，依次给出各字符编码结果。  
(3)给字符串进行编码。  
(4)给编码串进行译码。  
(5)计算平均码长。  
规定：  
(1)结点统计：以ASCII码的顺序依次排列，例如：空格，英文句号，大写字母，小写字母。  
(2)构建哈弗曼树时：左子树根结点权值小于等于右子树根结点权值。  
(3)选择的根节点权值相同时，前者构建为双亲的左孩子，后者为右孩子。  
(4)生成编码时：左分支标0，右分支标1。  
输入  
第一部分：报文内容，以’\#'结束。  
第二部分：待译码的编码串。  
输出  
依次输出报文编码串、译码串、平均码长，三者之间均以换行符间隔。  
平均码长，保留小数点2位。  
样例输入

**Data structure is the way of computer storage and organization data. A data structure is a collection of data elements that exist between one or more specific relationships.\#  
000111111110101111110100101010000110111100010011011000001110011110011100101011010011100001101111011001011010101011001101110010101011101011110110101000110001101001010101010001111000101001110111111101000001101010100000010111111110101110110011111101001111010111011100000011110101111000100110000111011000000111101011111101001010100001101111000100110110000011100111100111011111101110010100000100001001111000100111101011101110101010110011000000111101011111100010000100110111000111101010100111001010110111110101100010110001011110010101100110000001010000110001001111011101010111010011101010100011010111010101000001110100110111100111100011110110001111110011010000010000111110100111101011101100110110101111011111001000100**

样例输出

**000111111110101111110100101010000110111100010011011000001110011110011100101011010011100001101111011001011010101011001101110010101011101011110110101000110001101001010101010001111000101001110111111101000001101010100000010111111110101110110011111101001111010111011100000011110101111000100110000111011000000111101011111101001010100001101111000100110110000011100111100111011111101110010100000100001001111000100111101011101110101010110011000000111101011111100010000100110111000111101010100111001010110111110101100010110001011110010101100110000001010000110001001111011101010111010011101010100011010111010101000001110100110111100111100011110110001111110011010000010000111110100111101011101100110110101111011111001000100  
Data structure is the way of computer storage and organization data. A data structure is a collection of data elements that exist between one or more specific relationships.  
4.11**

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define LettersNum 6
    #define TextCharTypeNum 54
    typedef struct{//三叉链表的结点结构体定义
    	int weight;
    	int Parent;
    	int Lchild;
    	int Rchild;
    }HFTreeNode;
    void SelectTwoMinimumWeightNodes(HFTreeNode Tree[],int Range,int *Node1,int *Node2)//在哈夫曼树数组从第一个元素到第Range元素找出两个不重复的权值最小的树结点
    {
        int cmp = 998,i;
        for(i=1;i<=Range;i++)
        {
            if(Tree[i].weight<cmp&&Tree[i].Parent==0)
            {
                cmp = Tree[i].weight;
                *Node1 = i;
            }
        }
        cmp = 998;
        for(i=1;i<=Range;i++)
        {
            if((Tree[i].weight<cmp)&&Tree[i].Parent==0&&i!=*Node1)
            {
                cmp = Tree[i].weight;
                *Node2 = i;
            }
        }
        return;
    }
    
    void CreateHuffmanTree(HFTreeNode *Tree,int weights[],int LeafsNum)//由于大小固定哈夫曼树的存储采用静态三叉链表自底而顶构建
    {
        int NodesNum = 2*LeafsNum-1;//整棵树结点数
        int i;
        int Node1,Node2;
    
        for(i=1;i<=LeafsNum;i++){Tree[i].weight = weights[i-1];Tree[i].Parent=Tree[i].Lchild=Tree[i].Rchild=0;}//初始前n个元素作为根基
        for(i=LeafsNum+1;i<=NodesNum;i++){Tree[i].weight = Tree[i].Parent = Tree[i].Lchild = Tree[i].Rchild = 0;}
        for(i=LeafsNum+1;i<=NodesNum;i++)
        {
            SelectTwoMinimumWeightNodes(Tree,i-1,&Node1,&Node2);
            Tree[i].weight = Tree[Node1].weight+Tree[Node2].weight;//子母结点的连接
            Tree[i].Lchild = Node1;
            Tree[i].Rchild = Node2;
            Tree[Node1].Parent = i;
            Tree[Node2].Parent = i;
        }
        return;
    }
    void PrintTreeContent(HFTreeNode *Tree,int LeafsNum)
    {
        int i;
        for(i = 1;i<=2*LeafsNum-1;i++)
        {
            printf("%d %d %d %d\n",Tree[i].weight,Tree[i].Parent,Tree[i].Lchild,Tree[i].Rchild);
    
        }
        return;
    }
    void SetBinaryCode(HFTreeNode *Tree,int WhichLetter,char **Aim)
    {
        int Codelength = 0,i=WhichLetter,j;
        while(Tree[i].Parent!=0)
        {
            i = Tree[i].Parent;
            Codelength++;
        }
        *Aim = (char*)malloc((Codelength+1)*sizeof(char));
    
        i = WhichLetter;
        for(j=Codelength-1;j>=0;j--)
        {
            if(Tree[Tree[i].Parent].Lchild==i)
            {
                (*Aim)[j] = '0';
                i = Tree[i].Parent;
    
            }
            else if(Tree[Tree[i].Parent].Rchild==i)
            {
                (*Aim)[j] = '1';
                i = Tree[i].Parent;
            }
    
        }
        (*Aim)[Codelength]='\0';
        return;
    }
    void PrintLetterCorrespondingCodes(char *Codes[],int CodesSize,char ValidLetters[])
    {
        int i;
        for(i=0;i<CodesSize;i++)
        {
            printf("%c:%s\n",ValidLetters[i],Codes[i]);
        }
        return;
    }
    void Encode(char *Aim,char *Codes[],int CodesSize,char ValidLetters[])//字母转为01串
    {
        int i,j;
        for(i=0;i<strlen(Aim);i++)
        {
            for(j=0;j<CodesSize;j++)
            {
                if(Aim[i]==ValidLetters[j]){printf("%s",Codes[j]);break;}
            }
        }
        return;
    }
    void Decode(char *Aim,char *Codes[],int CodesSize,char ValidLetters[])//01串转为字母
    {//0010000100111101测试数据
        int i,j,k,maxCodeLength=0,maxcmp,check,flag,AimLen;
        for(i=0;i<CodesSize;i++)if(strlen(Codes[i])>maxCodeLength)maxCodeLength = strlen(Codes[i]);
        //printf("最长码长度%d\n",maxCodeLength);
        AimLen = strlen(Aim);
        //printf("二进制串长度%d\n",AimLen);
        i=0;
        while(i<AimLen)
        {
    
            flag = 0;
            maxcmp = 0;
            for(k=0;k<CodesSize;k++)
            {
                j = 0;
                for(check=i;check<i+maxCodeLength&&check<AimLen;check++)
                {
                    if(Aim[check]!=Codes[k][check-i])break;
                    else j++;
                }
                if(j>maxcmp)
                {
                    maxcmp = j;
                    flag = k;
    
                }
            }
            printf("%c",ValidLetters[flag]);
            i+=strlen(Codes[flag]);
            //printf("此段译码长度%d\n",strlen(Codes[flag]));
        }
        return;
    }
    void CountTextCharNums(int *TextCharWeights,char Text[])
    {
        int i;
        for(i=0;i<TextCharTypeNum;i++)
        {
            TextCharWeights[i]=0;
        }
        for(i=0;i<strlen(Text);i++)
        {
            if(Text[i]==' ')TextCharWeights[TextCharTypeNum-2]++;
            else if(Text[i]=='.')TextCharWeights[TextCharTypeNum-1]++;
            else if(Text[i]>='A'&&Text[i]<='Z')TextCharWeights[Text[i]-'A']++;
            else if(Text[i]>='a'&&Text[i]<='z')TextCharWeights[Text[i]-'a'+(TextCharTypeNum-2)/2]++;
    
        }
        return;
    }
    float ComputeAverageBinStrLength(char *Codes[],int CodesSize)
    {
        unsigned i;
        float result,Sum=0;
        for(i=0;i<CodesSize;i++)
        {
            Sum += strlen(Codes[i]);
        }
        result = Sum/(float)CodesSize;
        return result;
    }
    int GetValidWeightsNum(int weights[])
    {
        int i,Num=0;
        for(i=0;i<TextCharTypeNum;i++)
        {
            if(weights[i]>0)Num++;
        }
        return Num;
    }
    void CopytoNewWeightsArr(int *NewWeights,int OldWeights[],char *ValidLetters,int ValidWeights,char TextChar[])
    {
        int i,k=0;
        for(i=0;i<ValidWeights;i++)
        {
            NewWeights[i] = 0;
        }
        for(i=0;i<TextCharTypeNum;i++)
        {
            if(OldWeights[i]>0&&k<ValidWeights)
            {
                NewWeights[k] = OldWeights[i];
                ValidLetters[k] =  TextChar[i];
                k++;
            }
    
        }
        return;
    }
    int main()
    {
        int i;
    	char TextChar[TextCharTypeNum];
    	for(i=0;i<TextCharTypeNum;i++)
        {
            if(i<(TextCharTypeNum-2)/2)TextChar[i]='A'+i;
            else if(i<TextCharTypeNum-2)TextChar[i]='a'+i-(TextCharTypeNum-2)/2;
            else if(i==TextCharTypeNum-2)TextChar[i]=' ';
            else if(i==TextCharTypeNum-1)TextChar[i]='.';
    
            //printf("%c",TextChar[i]);
        }
    	char Text[200],buf;
    	for(i=0;i<200;i++)Text[i]='\0';
    	i=0;
    	while(i<200)//给Text赋值
        {
            buf = getchar();
            if(buf=='\n')continue;
            else if(buf=='#')break;
            else Text[i++]=buf;
        }
    
    	int TextCharWeights[TextCharTypeNum];//未缩减前的weights数组
    	int ValidWeights;//weight不为零的字符数量
    
    
    	CountTextCharNums(TextCharWeights,Text);//统计Text里所有字符数量
    	ValidWeights = GetValidWeightsNum(TextCharWeights);
    	int Weights[ValidWeights];//仅有非零weight的weights数组
        char ValidLetters[ValidWeights];
    	char *Codes[ValidWeights];
        CopytoNewWeightsArr(Weights,TextCharWeights,ValidLetters,ValidWeights,TextChar);
    
        HFTreeNode HFTree[ValidWeights*2];
        CreateHuffmanTree(HFTree,Weights,ValidWeights);
        //PrintTreeContent(HFTree,TextCharTypeNum);
        for(i=0;i<ValidWeights;i++)SetBinaryCode(HFTree,i+1,&Codes[i]);
        PrintLetterCorrespondingCodes(Codes,ValidWeights,ValidLetters);
        Encode(Text,Codes,ValidWeights,ValidLetters);
        printf("\n");
        char BinStr[3000];
        i=0;
        getchar();
        while(i<3000)
        {
            buf = getchar();
            if(buf=='1'||buf=='0')BinStr[i++]=buf;
            else {BinStr[i++]='\0';break;}
        }
        //printf("\n%s\n",BinStr);
        Decode(BinStr,Codes,ValidWeights,ValidLetters);
        printf("\n%.2f\n",ComputeAverageBinStrLength(Codes,ValidWeights));
    	return 0;
    }