这里有一个动态哈夫曼的算法：
该方法的最大特点是不需预先对原始数据进行一遍扫描以建立哈夫曼树，而改为以动态变化的哈夫曼树对数据编码。
－、说明
计算机中普遍使用的ASCII码采用7位二进制数来表示字符，它是一种定长编码。在实际应用中，经常使用的字符比较集中，每个字符使用的频率相差很大，如果根据字符使用频率的高低不同，采用不同长度的二进制位表示字符，即采用变长编码方法，使用频率高的字符编码短一些，而使用频率低的字符编码长一些，这样就可以明显地减少数据存储和通信时的开销，同时对数据也能起到保密的作用。
哈夫曼编码技术是一种比较常用的变长编码方法，最早由David Huffman提出。它采用的是一种优化静态编码方法，由该算法产生的二叉树具有最小的加权路长之和∑WjLj，其中Wj是哈夫曼树中第j个叶结点的重量，Lj为该叶结点到树根的距离。假设原始数据中含有k个各不相同的字符a〔，1〕，a〔，2〕……a〔，k〕，其编码方式就是为这k个各不相同的字符都静态地分配一个Lj位的“0”“1”编码序列（因而称为静态哈夫曼编码），该序列指明由根结点到第j个叶结点的路径，“0”表示向左，“1”表示向右，并用该序列替换原始数据中的对应字符。
静态哈夫曼方法的最大缺点就是它需要对原始数据进行两遍扫描：第一遍统计原始数据中各字符出现的频率，利用得到的频率值创建哈夫曼树并将树的有关信息保存起来，便于解压时使用；第二遍则根据前面得到的哈夫曼树对原始数据进行编码，并将编码信息存储起来。这样如果用于网络通信中，将会引起较大的延时；对于文件压缩这样的应用场合，额外的磁盘访问将会降低该算法的数据压缩速度。
为此Faller等人提出了动态哈夫曼编码方法，它对数据编码的依据是动态变化的哈夫曼树，也就是说，对第t＋1个字符编码是根据原始数据中前t个字符得到的哈夫曼树来进行的。压缩和解压子程序具有相同的初始化树，每处理完一个字符，压缩和解压方使用相同的算法修改哈夫曼树，因而该方法不需要为解压而保存树的有关信息。压缩和解压一个字符所需的时间与该字符的编码长度成正比，因而该过程可以实时进行。
二、动态哈夫曼编码
为了便于说明，我们先进行一些定义。
原始数据：需要被压缩的数据
压缩数据：被压缩过的数据
n：字母表的长度
a〔，j〕：字母表中第j个字符
t：已处理的原始数据中字符的总个数
k：已处理数据中各不相同字符的个数
显然1�j，k�n
在压缩开始前，需要引进一个空叶结点，它的重量值始终为0。在以后的压缩和解压过程中，如果k＜n，我们用它来表示n－k个字母表中还未出现的字符。初始化的哈夫曼树中只有一个根结点和空叶结点。
压缩子程序读进一个字符后，它将该字符加到根结点的右分枝上，而空叶结点仍留在左分枝上，然后将该字符以ASCII码方式输出。解压子程序对其哈夫曼树作同样的调整。
以后每读进一个字符a〔，it〕，压缩子程序都执行以下的步骤：首先它检查a〔，it〕是否出现在编码树中，如果是，压缩子程序就以静态哈夫曼编码中相同的方式对a〔，it〕进行编码；如果a〔，it〕不在编码树中，压缩子程序首先对空叶结点进行编码，然后将a〔，it〕以ASCII码方式输出，最后在编码树中增加两个结点：在空叶结点的右分枝上加入一个新结点，并将a〔，it〕放在里面，然后在其左分枝上加入一个新的空叶结点。
解压子程序对解压树也做同样的调整，因为它和压缩子程序具有相同的哈夫曼树。当它遍历到空叶结点时，解压子程序就从压缩数据中取出一个ASCII字符，然后对解压树做与压缩子程序相同的调整。
每处理一个字符，压缩和解压程序都需要修改各自的哈夫曼树，为了修改的方便，树中每个结点都具有一个序号，它是根据结点的重量由大到小排列而确定的一个递减序列。
对于图1中的例子，现在已处理了32个字符，即t＝32，a〔，it＋1〕＝“b”，此时并不是简单地将叶结点a〔，it＋1〕和它的祖先结点的重量加1，因为这样做之后，该树就不再是哈夫曼树，且各结点的序号也不再是按结点重量由大到小排列而确定的递减序列，结点4和结点6的重量为6，而结点5的重量为5。
动态哈夫曼编码技术的关键就是如何将前t个字符的哈夫曼树调整成一棵前t＋1个字符的哈夫曼树。为了解决上述问题，我们分两步来进行。第一步我们把前t个字符的哈夫曼树转换成它的另一种形式，在该树中只需在第二步中简单地把由根到叶结点a〔，it＋1〕路径上的所有结点重量加1，就可以变成前t＋1个字符的哈夫曼树。其过程就是以叶结点a〔，it＋1〕为初始的当前结点，重复地将当前结点与具有同样重量的序号最大的结点进行交换，并使得后者的父结点成为新的当前结点，直到遇到根结点为止。
算法是：
void UpDate(struct Node *Temp) /* 修改相应的重量 */
{
struct Node *Tempa,*Tempc,*Pointer;
struct LeafNode *p,*q,*b;
unsigned char Letter;
while(Temp !=Root)
{
if(Temp->Weight)
{
p=Weight;
while(p->Next->CharNode->Weight !=Temp->Weight)
p=p->Next;
if(Temp->Front!=NULL) /* 找到序号最大的结点 */
{
Tempa=Temp;
while(Temp->Front!=NULL)
Temp=Temp->Front;
pointer=Temp->LeftChild; /* 结点交换 */
if(Pointer!=NULL)
Pointer->Parent=Tempa;
Temp->LeftChild=Tempa->LeftChild;
if(Temp->LeftChild!=NULL)
Temp->LeftChild->Parent=Temp;
Tempa->LeftChild=Pointer;
Pointer=Temp->RightChild;
if(Pointer!=NULL)
Pointer->Parent=Tempa;
Temp->RightChild=Tempa->RightChild;
if(Temp->RightChild!=NULL)
Temp->RightChild->Parent=Temp;
Tempa->RightChild=Pointer;
Letter=Temp->Letter;
Temp->Letter=Tempa->Letter;
Tempa->Letter=Letter;
if((Tempa->LeftChild==NULL) &&(Tempa->LeftChild==NULL))
{
b=Leaf;
while(b!=NULL)
if(b->CharNode==Temp)
{
b->CharNode=Tempa;
break;
}
else b=b->Next;
}
if((Temp->LeftChild==NULL)&&(Temp->RightChild==NULL))
{
b=Leaf;
while(b!=NULL)
if(b->CharNode==Tempa)
{
b->CharNode=Temp;
break;
}
else b=b->Next;
}
}
p->Next->CharNode=Temp->After; /* 取下该结点 */
if(Temp->After==NULL) /* 该链为空时 */
{
q=p->Next;
p->Next=q->Next;
free(q);
}
else Temp->After->Front=NULL;
}
Temp->Weight++; /* 重量加1 */
Temp->After=Temp->Front=NULL;
InsertWeight(Temp);
Temp=Temp->Parent;
}
}
另：
下面还有一个是用java做的，希望大家能够从中得到一点启示吧。地址是：
http://colinwj.blogchina.com/3914313.html参考资料：http://colinwj.blogchina.com/3914313.html