哈夫曼编码与解码（C语言实现）

NULL 博文链接：https://touch-2011.iteye.com/blog/1058800

#include
#include
#include
#include

#define MAXNUM 60

typedef struct
{
	char ch;
	int weight; //权值，这个字符出现的频率
	int parent;
	int left;
	int right;
}HuffNode;

typedef struct
{
	char code[MAXNUM];
	int start;
}HuffCode;

HuffNode ht[MAXNUM*2]; //存放哈夫曼树

HuffCode hcd[MAXNUM];  //存放ht数组中对应的字符的编码

int n;                 //字符的个数

//初始化哈夫曼树ht
void initHt（）
{
	FILE * fp;
	char ch;
	int i=0;
	//从文件document/character.txt中读出要编码的字符和权值
	if（（fp=fopen（“document/character.txt““r“））==NULL）{
		printf（“can not open the file character.txt“）;
		exit（0）;
	}
	ht[i].left=ht[i].right=ht[i].parent=-1;
	while（（ch=fgetc（fp））!=EOF）{
		if（ch==‘\n‘）{
			i++;
			ht[i].left=ht[i].right=ht[i].parent=-1;		
		}
		else if（（ch>=‘a‘ && ch<=‘z‘）||（ch>=‘A‘ && ch<=‘Z‘））
			ht[i].ch=ch;
		else if（ch>=‘0‘&&ch<=‘9‘）
			ht[i].weight=ht[i].weight*10+ch-‘0‘;
	}
	n=i+1;
	if（fclose（fp））{
		printf（“can not close the file character.txt“）;
		exit（0）;
	}
}

//构造哈夫曼树看成有n棵树，选择权值最小的两棵树合并
void createHuffTree（）
{

	int i=0k;
	int minIminJ;
	int f=0;
	minI=minJ=-1; //minI	for（k=n;k<2*n-1;k++）{
		//寻找ht中权值最小且无父结点的两个结点
		i=0;
		f=0;
    	while（ht[i].ch!=‘\0‘）{
    		if（ht[i].parent==-1）{
	    		if（f==0）{
            		minI=i;
		          	f++;
				}else if（f==1）{
					if（ht[i].weight						minJ=minI;
						minI=i;
					}else
			    		minJ=i;
					f++;
				}else{
			    	if（ht[i].weight			    		minJ=minI;
			    		minI=i;
					}else if（ht[i].weight						minJ=i;
				}
			}
    		i++;
		}
		//合并两个结点
		ht[k].ch=‘#‘;
		ht[k].left=minI;
		ht[k].right=minJ;
		ht[k].weight=ht[minI].weight+ht[minJ].weight;
		ht[k].parent=-1;
		ht[minI].parent=ht[minJ].parent=k;
	}
}

//将一个字符串反转
void reverse（char *str）
{
	int ij;
	char ch;
	for（i=0j=strlen（str）-1;i		ch=str[i];
		str[i]=str[j];
		str[j]=ch;
	}
}

//哈夫曼编码，通过父节点从下往上找
void createHuffCode（）
{
    int ijlength;
	FILE * fp;
	for（i=0;i		length=0;
		j=i;
		//给每个字符进行编码
		while（ht[j].parent!=-1）{
    		if（ht[ht[j].parent].left==j）{
		    	hcd[i].code[length++]=0+‘0‘;
			}else
		    	hcd[i].code[length++]=1+‘0‘;
			j=ht[j].parent;
		}

		hcd[i].start=hcd[i].code[length-1]-‘0‘;
		hcd[i].code[length]=‘\0‘;
		reverse（hcd[i].code）;
	}
	//把hcd字符编码写入文件document/code.txt中
	if（（fp=fopen（“document/code.txt““w“））==NULL）{
		printf（“can not open the file character.txt“）;
		exit（0）;
	}
    for（i=0;i		fputc（ht[i].chfp）;
		fputs（“    “fp）;
		fputs（hcd[i].codefp）;
		fputc（‘\n‘fp）;
	}
	if（fclose（fp））{
		printf（“can not close the file character.txt“）;
		exit（0）;
	}
}

//哈夫曼解码，每次都从根节点开始搜索
int releaseHuffCode（char *strchar* code）
{
	int root=2*n-2;
	int length=0i=0;
	while（code[i]）{
		if（code[i]==‘0‘+0）
			root=ht[root].left;
		else if（code[i]==‘0‘+1）
			root=ht[root].right;
		else
			return 0;
	

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        328  2011-05-26 07:25  源代码\document\character.txt

     文件        694  2011-05-26 07:30  源代码\document\code.txt

     文件       5049  2011-05-26 07:22  源代码\Huffman.c

     目录          0  2011-05-26 07:34  源代码\document

     目录          0  2011-05-26 07:34  源代码

----------- ---------  ---------- -----  ----

                 6071                    5