从前有个神人叫哈夫曼，发明了一种二进制编码技术，可以实现压缩存储。后来人们发现这玩意真的好用，居然到9102年了还在用它的改进型。
那么稍稍学习一下吧
这个算法是基于权值的概念，权为出现频率较高的元素赋较高的权值，并编以较短的代码，以此缩短整个数据串的占用空间。
定义哈夫曼树之前先说明几个与哈夫曼树有关的概念：
路径： 树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：路径上的分枝数目称作路径长度。
树的路径长度：从树根到每一个结点的路径长度之和。
结点的带权路径长度：在一棵树中，如果其结点上附带有一个权值，通常把该结点的路径长度与该结点上的权值之积称为该结点的带权路径长度
一般来说，用n（n>0）个带权值的叶子来构造二叉树，限定二叉树中除了这n个叶子外只能出现度为2的结点。
那么符合这样条件的二叉树往往可构造出许多颗，
其中带权路径长度最小的二叉树就称为哈夫曼树或最优二叉树
哈夫曼树的构造：
显然，权值高的元素应该尽可能接近树的根部，将较远的地方留给权值
哈弗曼树的实现代码：
/* 因为需要存储哈夫曼树和植树前的临时节点，所以在抽象定义的时候将数组长度设置为2*N会方便很多。其中0号不使用(作为哨兵)，1到N号植树，N+1到2N-1号存储节点 */ #define N 999998 #define MAX 0x3f3f3f3f //关于无穷大为啥是3f先别问，自己查 typedef struct { elemType Data; //数据域 int w; //节点权值 int parent, lchild, rchild; //这是小学英语 }HFMNode; HFMNode Ht[2*N]; void Huffman( HFMNode Ht[] , int N ) //导入数组存储的完全二叉树，N为最大许可长度 { int i, k, lmin, rmin; //左最小和右最小用来存放最小权值的标号 int min1, min2; //分别存放最小权值的值 for(i=1; i<2*N; i++) //这里令i=N+1的意思是在无亲无故节点的森林里查找 Ht[i].w = Ht[i].parent = Ht[i].lchild = Ht[i].rchild = -1; //全部初始化为-1 for(i=N+1; i<2*N; i++) //在这个循环中，将要找出权值最小的两个元素 { min1=min2=MAX; lmin=rmin= -1; //这一步是清空数值 for( k=1; k<2*N; k++) if( Ht[i].parent == -1 ) //对没有处理过的节点进行操作 { //找出两个最小的值 if( Ht[k].w<min1 ) {min2=min1; min1=Ht[k].w; lmin=rmin; lmin=k; break;} else if( Ht[k].w<min2 ) {min2=Ht[k].w; rmin=k; break;} } //权值相加，父节点和子节点归位 Ht[k].w = Ht[lmin].w + Ht[rmin].w; Ht[k].lchild = lmin; Ht[k].rchild = rmin; Ht[lmin].parent =Ht[rmin].parent = I; } }
怎么样，很简单吧？作为作业请编写一个数据压缩软件作为练习！
因为哈夫曼树也是一种二叉树，所以在遍历的时候和一般的二叉树一样，利用递归或者栈/队列即可完成。稍微有些不同之处在于哈夫曼树利用的是顺序表而不是链表！
接下来我会贴上我实现数据压缩的代码，在书上是课后题来着
警告：截止目前这段代码并没有完善并通过测试！
现在我也看不懂了
huffman.h
#pragma once #include#include #include #define N 350 #define MAXBIT 20 typedef struct { char ch; int weight; int parent; int Lchild, Rchild; }HtreeNode; typedef struct { int bit[MAXBIT]; int start; char ch; }HcodeNode; int WeightCount(char* str, HtreeNode t[]); void PlantTree(HtreeNode t[], char* str); void EnCode(HtreeNode t[], HcodeNode code[], char* str); void Print(HtreeNode t[], HcodeNode code[]);
huffman.c
#include"Huffman.h"
int WeightCount(char* str, HtreeNode t[])
/*
Scan the words and count the weight
*/
{
int len = strlen(str);
for (int i = 0; i < len; i++)
{// If existed, weight++, or create a new item
char ch = str[i];
//find if str[i] existed or current node is empty ?
for (int x = 0; x < N; x++)
if (t[x].ch == ch || t[x].weight == 0)
{
t[x].ch = ch;
t[x].weight++;
break;
}
}
int i = 0;
while (t[i].ch != 0)
i++;
return i;
}
void PlantTree(HtreeNode t[], char* str)
/*
Reorder the Nodes and create
*/
{
for (int temp = 0; temp < 2 * N; temp++)//Initialize the array
{
t[temp].ch = t[temp].weight = 0;
t[temp].Lchild = t[temp].Rchild = t[temp].parent = -1;
}
int i, j, Lmin, Rmin;
int min1, min2;
int allweight;
allweight = WeightCount(str, t);
for (i = allweight; i < 2 * N; i++) //place new nodes behind original nodes
{
min1 = min2 = INT_MAX;
Lmin = Rmin = -1;
for (j = 0; j < i+1; j++)// Reorder nodes from [0]--[allweight]
{
if (t[j].parent == -1) //Only reorder node those still in the forest
{
if (t[j].weight < min1)
{
Rmin = Lmin;
Lmin = j;
min1 = t[j].weight;
min2 = min1;
}
else if (t[j].weight < min2 && j != Lmin)
{
min2 = t[j].weight;
Rmin = j;
}
}
}
//place new node
t[Lmin].parent = t[Rmin].parent = i;
t[i].weight = t[Lmin].weight + t[Rmin].weight;
t[i].Lchild = Lmin; t[i].Rchild = Rmin;
}
}
void EnCode(HtreeNode t[], HcodeNode code[], char* str)
{
PlantTree(t, str);
for (int s = 0; s < 2 * N; s++)
if (t[s].weight == 0 && t[s].parent != -1)
t[s].parent = -1;
t[63].parent = -1;
}
void Print(HtreeNode t[], HcodeNode code[])
{
int i;
for (i = 0; i < 2 * N; i++)
if(t[i].weight)
printf(" %d '%c' P:%d W:%d L:%d R:%d \n", i, t[i].ch, t[i].parent, t[i].weight, t[i].Lchild, t[i].Rchild);
}
main.c
#include"Huffman.h"
int main()
{
HtreeNode* t = malloc(sizeof(HtreeNode) * 2*N);
if (!t)
exit("16543");
HcodeNode* code = malloc(sizeof(HcodeNode) * N);
if (!code)
exit("64541");
char* str = "I prefer my English classes to betaught in both English and Chinese, whose advantage is that it is easy for usto understand what the teacher talks about. The teacher first teaches the classin English, and then she explains those that are hard to understand to us sothat we get a better knowing of the passage. That will be good for us.However, teaching the class in twolanguages will make the English atmosphere not so strong.Some students whowish to be taught in English will be disappointed. Except for the disadvantage, I thinkit is really good to hear two languages in classes.It can make us morefamiliar with the foreign culture.";
EnCode(t, code, str);
Print(t, code, strlen(str) );
return 0;
}