huffman.txt

建立完整的赫夫曼树

#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define MAXSIZE 100  //所能编译字符最大个数
#define NULL 0
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define OK 1
#define INFINITY  1000000 //最大权值

typedef char TElemType;
typedef int  Status;
typedef char** HuffmanCode;//动态分配数组存储赫夫曼编码表
typedef char* huffmanCode;



struct Data{
 TElemType  data;
 int w;//权值
};





typedef struct {
 TElemType data ;//储存信息字符类型
 unsigned int weight;//权值
 unsigned int parent, lchild, rchild;//左右孩子及双亲储存位置
} HTNode, *HuffmanTree;//动态分配数组存储赫夫曼树


void    InitData(struct Data *m,int n){
 m=(struct Data*)malloc((n+1)*sizeof(Data));
 for( int i=1;i<=n;++i){
  m[i].w=0;
   m[i].data=NULL;
 }
}


//定义 Select函数
void Select(HuffmanTree HT,int n,int &s1,int &s2){

	int i;
	int k1=INFINITY ;//始终记录较小的权值
	for( i=n;i>=1;--i){
		if(!HT[i].parent){
			if(HT[i].weight<=k1) {
				s1=i;
				k1=HT[i].weight;
				//printf("%d",s1);
			}//if
		}//if
	}//for

	//printf("\n");


    int k2=INFINITY ;//始终记录较小的权值
	for(int j=1;j<=n;++j){
		if(!HT[j].parent&&j!=s1){
			if(HT[j].weight<=k2) {
				k2=HT[j].weight;
				s2=j;
				//printf("%d",s2);
			}
		}
	}
}




Status Huffmacoding( HuffmanTree &HT,HuffmanCode &HC,struct Data  w[],  int n ){
 //w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的编码HC
	int m,i,s1,s2;
    HuffmanTree  p;
    if (n<=1) return ERROR;
    m=2*n-1; //需2*n-1个节点储存结点信息及结点之间的关系
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用 
    for (p=HT+1, i=1; i<=n; ++i,++p){//初始化贮存n个字符的结点
		p->data = w[i].data;
	    p->weight=w[i].w;
		p->parent=0;
	    p->lchild=0;
		p->rchild=0;
	}
    for (; i<=m;++i,++p){ //初始化其余的储存节点关系的n-1个结点
		p->data = NULL;
		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);
 //printf("%d,%d",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;
    } //for 
 //从叶子到根逆向求每个字符的赫夫曼编码
 HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量
    char*  cd;
	int    f;
    cd = (char*)malloc(n*sizeof(char));//分配求编码的工作空间
    cd[n-1]='\0';   //编码结束符            
    for (i=1; i<=n; i++)  {               //逐个字符求编码
 int start = n-1 ;//编码结束符位置，最深的一个叶子结点需n-1个编码
 int c=i; 
 while (f=HT[c].parent) {
     if (HT[f].lchild==c) cd[--start]='0';
     else cd[--start] = '1';
     c=f; 
 } //while
 HC[i] = (char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配 空间
 strcpy(HC[i],&cd[start]);  //从cd复制编码到HC
    } 
    free(cd);   //释放工作空间  
} //HuffmanCoding


//译码函数 
Status hfDecoding( HuffmanTree HT,char * cd,char *ccd,int n){
 int i=0;
 int m=2*n-1;//根节点位置
 int k=0;//记录ccd中位置
 int p=m;
 ccd=(char*)malloc(256*sizeof(char));//为译码申请存储空间
 int temp=TRUE;//结束循环标志
 while(temp){
	 if(!HT[p].lchild && !HT[p].rchild ) {
		 ccd[k++]=HT[p].data;  // 将译出码保存到ccd
		 p=m;//使其又从根结点寻找]
		 if(cd[i]=='\0') temp=FALSE;//跳出循环
	 }//if
	 else {	if(cd[i]=='\0') {
		 printf("给出译码错误！");
		 return ERROR;
	 }//当字符串为空或者当最后的数据串不能组成一个字母
	   if(((cd[i]=='0') && !HT[p].lchild)||((cd[i]=='1') && !HT[p].rchild)) {
		 printf("给出译码错误！");
		 return ERROR; 
	   }//给出的码串不正确，不能译码。
				if (cd[i]=='0') p=HT[p].lchild ;
				else p=HT[p].rchild;
				i++;
	 }//else
 }//while
	 ccd[k]='\0';//
	 printf("译码为：%s",ccd);
	  return OK;	 }




//定义main函数
void main(){
 int n;// 储存字符个数
  printf("用户需编译的字符个数为:");
  scanf("%d",&n);
  printf("请逐个输入字符及权值，并以逗号隔开 ");
     struct Data M[MAXSIZE];
     InitData(M,n);	
	 printf("\n");
  for(int i=1;i<=n;i++){
	 
   printf("输入第%d个数据:",i) ;
   fflush(stdin);//清除缓冲区数据
 
   scanf("%c,%d",&M[i].data,&M[i].w);

  }
  HuffmanTree HT;
  HuffmanCode HC;
  Huffmacoding(HT,HC,M,n);
  printf("sign------weight------parent------lchild------rchild");
  printf("\n");
  for(int j=1;j<=2*n-1;++j){
  printf("%-12c%-13d%-13d%-13d%-13d",HT[j].data,HT[j].weight,
	  HT[j].parent,HT[j].lchild,HT[j].rchild);
      printf("\n");
  }
  printf("\n");
  printf("各个字符赫夫曼编码为:\n");
  for(j=1;j<=n;++j){
	  printf("%c:  %s\n",HT[j].data,HC[j]);
}
printf("请用户输入需译码的数据串：");
  char cd[100];
  char *p;
  p=cd;
  scanf("%s",p);
  char *ccd;//储存译码
hfDecoding(HT,p,ccd,n);

 

//  scanf("%s",&cd);
//  hfDecoding(HT,cd,ccd,n);
}