【数据结构】生成一颗哈夫曼树，并求Huffman编码_od438. 生成哈夫曼树

前言

使用书籍：数据结构（严蔚敏老师版本）
使用软件：Dev-Cpp
项目地址：https://wws.lanzous.com/b01bwk6ja			或者下面代码自己添加进项目
提取密码：9999
求点赞收藏（厚颜无耻，诶嘿~）
1
2
3
4
5

正文

题目

  从键盘接收任意一个字符串，以回车作为结尾。以字符串中某字符出现的次数，作为该字符的权值。利用得到的权值构建huffman树、并输出每个字符对应的huffman编码。

解题思路

1.处理输入的字符串

char kind[1000],p[10000];						//p用于存放输入的待处理数据，kind用于存放处理后的数据 
	int i,w[1000]={0},n,sum=0,mid;					//w用于存放权重，sum表示字符种类 
	
	HuffmanTree HT;				
	HuffmanCode HC;
	scanf("%s",p);
	for(i=0;p[i]!='\0';i++){
		int zz=Is(p[i],kind,sum);
		
		//zz=-1 是代表新种类 
		if(zz==-1){
			sum++;
			kind[sum-1]=p[i];
			w[sum-1]++;	
		}
		//反之，返回序号。 
		else{
			w[zz]++;
		}
	}

//判断是否字符是否已经存在，不存在返回-1，存在返回在kind数组中的序号 
int Is(char x,char kind[],int sum){
	int i=0;
	for(;i<sum;i++){
		if(x==kind[i])
			return i; 
	}
	return -1;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2.构造最小二叉树
&
3.从二叉树输液逆向求Huffman编码
（其实就是书上的，自己加了注释，小声逼逼）

/***********************************************
* 参数列表：HT——存储Huffman树 （顺序存储结构）     
*           HC——存储Huffman编码 （char**） 
*			w ——带编码字符的权重数组
*			n ——待编码字符的种类 
* 函数功能：生成Huffman树，求Huffman编码 
************************************************/ 

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
	if(n<=1)return;
	
	HuffmanTree p;
	int m=2*n-1,i,s1,s2;									//m为Huffman树上所需的节点数，顺序存储 
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	
	//初始化huffman树的数组	
	for(p=HT+1,i=1;i<=n;++i,++p,++w)
		*p={*w,0,0,0};										//1~n个 
	for(;i<=m;i++,p++)	
		*p={0,0,0,0};										//n+1~m个 
	
	for(i=n+1;i<=m;i++){
		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; 
	}
	
	//从叶子到根逆向求每个字符的Huffman编码
	HC=(HuffmanCode)malloc((n+1)*sizeof(char *));			//分配n个字符的编码空间，多出来的[0]不用 
	char* cd=(char*)malloc(n*sizeof(char));					//求huffman码的工作空间（最长就是n-1位）
	cd[n-1]='\0';											//末尾补'\0'，以字符串形式存在 
	
	for(i=1;i<=n;i++){							
		int c,f,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';
		}
		HC[i]=(char*)malloc((n-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);							//学到了！数组新用法 
	} 
	free(cd);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

补一张Huffman树顺序结构的图，帮助理解严老师的算法。

运行截图

结尾

没有结尾。