赫夫曼树的构造与存储以及赫夫曼编码与解码算法运行结果

83 阅读 0 评论 55 点赞

我是靠谱客的博主兴奋美女，最近开发中收集的这篇文章主要介绍赫夫曼树的构造与存储以及赫夫曼编码与解码算法运行结果，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

程序要求

构建一个赫夫曼树编/译码器。根据提供的字符集和统计结果，按赫夫曼算法构造赫夫曼树，根据赫夫曼树得到每个赫夫曼编码并输出结果，能够将一个字符串转化为对应的赫夫曼编码串，能够将赫夫曼编码字符串译码。

数据结构题集（C语言版）清华大学出版社 p149 5.2

程序代码

#include <stdio.h>
#include <malloc.h>
#include <string.h>
typedef int Status ;
typedef char TElemType;
#define ERROR 0
#define OK 1
#define N 4
typedef  struct {
  unsigned int  weight;
  unsigned int  parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树,Huffmantree是指针->HTNode
typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表


void select(HuffmanTree HT, int k, int &s1, int &s2)//select函数，从一组数中选出两个最小者
{
	//假设s1对应的权值总是<=s2对应的权值
	int tmp = 10000, tmpi = 0,i;
	for(i = 1; i <= k; i++){
		if(!HT[i].parent){//parent必须为0
			if(tmp > HT[i].weight){
				tmp = HT[i].weight;//tmp最后为最小的weight
				tmpi = i;
			}
		}
	}
	s1 = tmpi;

	tmp = 10000;
	tmpi = 0;
	for(i = 1; i <= k; i++){
		if((!HT[i].parent) && i!=s1){//parent为0
			if(tmp > HT[i].weight){
				tmp = HT[i].weight;
				tmpi = i;
			}
		}
	}
	s2 = tmpi;
}
//void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
//w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的哈夫曼编码HC.
    int m,i,s1,s2,start,c,f;
    char *cd;
    HuffmanTree p;
   if(n<=1) return;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	//0号单元未用
	p=HT,p++;
    for(i=1;i<=n;++i,++p,++w)
    {
        p->weight=*w;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
    }
    for(;i<=m;++i,++p)
    {
        p->weight=0;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
    }
    for(i=n+1;i<=m;++i)//建哈夫曼树
    {
   //在HT[1..i-1]选择parent为0且weight最小的两个结点,其序号分别为s1和s2.
       select(HT,i-1,s1,s2);
       HT[s1].parent=i;HT[s2].parent=i;
       HT[i].lchild=s1;HT[i].rchild=s2;
       HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
//-----从叶子到根逆向求每个字符的哈夫曼编码-----
   HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量
            //↑
//typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表
   cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间
   cd[n-1]='';	                            //编码结束符.
   for(i=1;i<=n;++i){		//逐个字符求赫夫曼编码
      start=n-1;			//编码结束符位置
      for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
                                                      //从叶子至根逆向求编码
       if(HT[f].lchild==c) cd[--start]='0';
       //else if(HT[f].rchild==c) cd[--start]="1";
       else cd[--start]='1';
       HC[i]=(char *)malloc((n-start)*sizeof(char));
                                                  //为第i个字符编码分配空间
       strcpy(HC[i],&cd[start]);  //从cd复制编码(串)到HC
    }
    free(cd);	 //释放工作空间
}//HuffanCoding
void printfTree(HuffmanTree HT,int n)//打印哈夫曼树，参数为HT以及输入字符串中不同字符的个数
{
    int i;
    printf("The HuffmanTree:n");
    printf("weight  parent  lchild  rchildn");
    for(i=1;i<=2*n-1;i++)
    {
        printf("%5d %5d %5d %5d n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
        //依次输出节点的权值，根节点与左右节点
    }
}

void printHuffmanCoding(HuffmanCode HC,char *sysch, int *w,int n)
//打印每个字符对应的哈夫曼编码，参数为HC，字符串，权值数组以及sysch，以及字符串中不同字符的个数
{
	printf("The corresponding Huffmancode:n");
	int i;
	for(i=1;i<=n;i++){
		printf("%3d %3c %3d %sn",i,sysch[i-1],w[i-1],HC[i]);
		//依次输出字符编号（第几个字符），字符，字符的权值以及字符的哈夫曼编码
	}
	printf("n");
}
void EnCode(char *input,char *&codestring,HuffmanCode HC,char *sysch,int n)
//求哈夫曼编码函数，与“HuffmanCoding”求每个字符的哈夫曼编码不同，此处所求为整个字符串的哈夫曼编码
//参数为给定的字符串，codestring（存储哈夫曼编码的数组），HC，sysch，以及字符串中不同字符的个数
{
    codestring=(char *)malloc(200*sizeof(char));  //这里的初始化也跟HuffmanCode类似
    int i=0,j;
    codestring[0]='';//初始时默认最后一位为字符串结束标志‘’
    for(i=0;i<strlen(input);i++)
    {
        for(j=0;j<n;j++)
        {
            if(sysch[j]==input[i])//若input中下标为[i]的元素，与sysch中下标为[j]的元素相等
                {
                    strcat(codestring,HC[j+1]);//将sysch中下标为[j]的元素对应的哈夫曼编码复制到codestring中
                }
        }
        //随着i的增长，codestring也不断在增长，最终得到input字符串所对应的哈夫曼编码
    }
    printf("n");

}
void UnCode(char *input,char *&chs,HuffmanTree HT,char *sysch,int n)
//哈夫曼解码函数，将EnCode中得到的哈夫曼编码解码得到字符串，
//input:010101000...huffmancode,chs:ABCDEFFF...the string,sysch:{A,B,C,D,E,F,G,H}
{
    int p,pre;// HT下标1..2n-1,pre是p的双亲
    //printf("EnCode:%sn",input);//输出哈夫曼编码（调试用）
    //printf("EnCode is length is:%dn",strlen(input));//求哈夫曼编码的长度（调试用）
    int i=0;// input下标
    int k=0;// chs下标
    chs=(char *)malloc(200*sizeof(char));  //初始化也跟codestring类似
    while(input[i]!='')
    {
        p=2*n-1;pre=0;
        while(p!=NULL&&input[i]!=''){// 识别出一个符号
            if(input[i]=='1'){pre=p;p=HT[p].rchild;}//左0右1
            else if(input[i]=='0'){pre=p;p=HT[p].lchild;}
            i++;
        }// 此循环结束时,p=0,需要p的双亲的信息，所以设置pre

        if(p==NULL){  //最后一个符号，p未走到空，pre=p也没执行，需特殊处理
            i--;
            chs[k++]=sysch[pre-1]; // sysch下标从0开始，p值从1开始
            }
    }
    pre=p;chs[k++]=sysch[pre-1]; //最后一个符号，p未走到空
    chs[k]='';// 最后的结束符号
    //printf("%n");
}
int main(){
	HuffmanTree HT;
	HuffmanCode HC;
	char s[]={"ABCDEFGHABCDABCDDCBAFGEHHEA"};
	char *codestring;
	char *decodestring;
	char *chs;
	int weight[8]={5,29,7,8,14,23,3,11};//给定的权值
	char sysch[8]={'A','B','C','D','E','F','G','H'};//对应的字符
    HuffmanCoding(HT,HC,weight,8);//构建哈夫曼树
    printfTree(HT,8);
    printf("n");
    printHuffmanCoding(HC,sysch,weight,8);
    printf("Please input the String(combined with capital letter A-H):n");
    //scanf("%s",s);
    printf("%s",s);
    EnCode(s,codestring,HC,sysch,8);
    printf("The Huffmancode of the String is:n");
    printf("%sn",codestring);
    UnCode(codestring,chs,HT,sysch,8);
    printf("The result of Huffmancode uncoding:n");
    printf("%s",chs);

}