huffman.h

各种算法的c语言程序

#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include"LinkList.h"

#define    INFINITY         100000

//赫夫曼树和赫夫曼编码的存储表示
typedef struct{
	unsigned int weight;
      	    char data;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;           //动态分配数组储存赫夫曼树
typedef char **HuffmanCode;     //动态分配数组存储赫夫曼编码表



void Select(HuffmanTree HT,int i,int &s1,int &s2){
	//在HT[1…i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2
    int n;
	unsigned int w;
	w=INFINITY;
	for(n=1;n<=i;++n){
		if(HT[n].parent==0&&w>HT[n].weight) {
			s1=n;w=HT[n].weight;}
	}
	w=INFINITY;
   for(n=1;n<=i;++n){
		if(HT[n].parent==0&&w>HT[n].weight&&n!=s1) {
			s2=n;w=HT[n].weight;}
	}
}




void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,LinkList L,int n){
	//w存放n个字符的权值(均>0),构造赫夫曼树HT,并求n个字符的赫夫曼编码HC
	int m,i,s1,s2,start;
	HuffmanTree p;
	LinkList Lp;
	Lp=L->next;
	unsigned int f,c;
	char *cd;
	if(n<=1) return;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));     //0号单元未用
	for(p=HT+1,i=1;i<=n;++i,++p,Lp=Lp->next){
		p->weight=Lp->weight;p->data=Lp->data;p->rchild=0;p->lchild=0;p->parent=0;}    //赋值
	for(;i<=m;++i,++p){
		p->weight=0;p->data='0';p->rchild=0;p->lchild=0;p->parent=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个字符编码的头指针向量
	cd=(char*)malloc(n*sizeof(char));         //分配求编码的工作空间
	cd[n-1]='\0';                   //编码结束符号
	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 cd[--start]='1';
		  cd[--start]=HT[i].data;
		  HC[i]=(char*)malloc((n-start)*sizeof(char));  //为第i个字符编码分配空间
		  strcpy(HC[i],&cd[start]);               //从cd复制编码串到HC
	 }
	free(cd);             //释放工作空间
}//HuffmanCoding;


void Display_HT(HuffmanTree HT,int n){
	int i;
	for(i=1;i<=(2*n-1);i++){
		cout<<i<<"   "<<HT[i].weight<<"  "<<HT[i].parent<<"   "<<HT[i].lchild<<"  "<<HT[i].rchild<<"  "<<HT[i].data<<endl;}
}

void Display_HC(HuffmanCode HC,int n){
	int i;
	for(i=1;i<=n;i++)
		printf("%s\n",HC[i]);
}


void CreatHuffmanCode(HuffmanCode HC,char *&cs,int n){
	//键盘输入字符串，选择字符进行编码，并用cs指向码元流
    char c,*s;
	int i;
	cout<<"请输入字符串，以回车表示结束："<<endl;
    fflush(stdin);
	c=getchar();
	while(c!=10){
	for(i=1;i<=n;i++)
		if(c==HC[i][0]) {
			s=HC[i]+1;
			cs=(char*)realloc(cs,(strlen(HC[i])+strlen(cs))*sizeof(char));
			strcat(cs,s);
		} //for
		c=getchar();
	}//while
}//CteatHuffmanCode


void HuffmanDeCoding(HuffmanTree HT,char *cs,char *&s,int &j){
	// 根据赫夫曼树HT，确定一个给定编码流cs对应的原始符号s
	int i=1,root;
	unsigned int pos;
	pos=0;j=0;

	//首先确定根结点
   while(HT[i].parent!=0) i++;
   root=i;
   //依次处理码元流
   for(pos=0;pos<(strlen(cs));){
	     s[j]='\0'; //第j个符号位初始化
	    //每个符号的编码从根结点开始，从根结点开始符号编码过程

        //一个符号的得到
     i=root;
     while((HT[i].lchild!=0)&&(HT[i].rchild!=0)){
	 //对于分支结点，根据码元cs[pos]确定路径
        if(cs[pos]=='0')
		  i=HT[i].lchild;
	    else
		  i=HT[i].rchild;
		pos++;
	 }
	 //一个码元处理完毕
    //-到达叶子结点，表示得到一个符号码
   s[j]=HT[i].data;//叶子结点i对应的符号位译码结果
	j++;
   }//for
   //得到一个符号，回到根处理下一个码元
}