1、動態(tài)哈夫曼編碼的改進 您正在瀏覽的計算機論文是動態(tài)哈夫曼編碼的改進 計算機世界月刊1994年7月號所登載的動態(tài)哈夫曼編碼的數(shù)據(jù)壓縮方法一文給出了一種實時性較強的數(shù)據(jù)壓縮方法，該方法的最大特點是不需預(yù)先對原始數(shù)據(jù)進行一遍掃描以建立哈夫曼樹，而改為以動態(tài)變化的哈夫曼樹對數(shù)據(jù)編碼。該文所附的動態(tài)哈夫曼編碼數(shù)據(jù)壓縮與解壓源程序中的UpDate函數(shù)是動態(tài)修改哈夫曼樹的關(guān)鍵部分，該函數(shù)對動態(tài)哈夫曼樹的一種可能情況無法正確修改，針對這一點，本文附上對該函數(shù)的一個修正定義，以使該壓縮與解壓程序更加完善。以下就舉例說明原UpDate函數(shù)無法正確修改的一種哈夫曼樹。例如若要壓縮“TThhis”字符串，則在壓縮完“

2、TTh”之后的動態(tài)哈夫曼樹為圖所示(設(shè)根結(jié)點序號為1000)：04A07700.GIF;圖 壓縮完“TTh”之后的動態(tài)哈夫曼樹此時若再將字符h進行壓縮編碼，則在輸出h的編碼“01”后需調(diào)整哈夫曼樹，以997號葉結(jié)點為當(dāng)前結(jié)點，則與當(dāng)前結(jié)點具有同樣重量的且序號最大的結(jié)點為998號結(jié)點，而該結(jié)點是997號結(jié)點的父結(jié)點，對二者按原文所提供的UpDate函數(shù)進行交換，則將導(dǎo)致998號結(jié)點變成葉結(jié)點，996號結(jié)點變成997號結(jié)點的左孩子，997號結(jié)點則既為自己的父結(jié)點又是自己的右孩子，這樣在對后繼字符i進行壓縮編碼時，首先就無法輸出996號空結(jié)點的編碼了，此時壓縮程序陷入死循環(huán)。顯然這時可以簡單地將99

3、8和997號結(jié)點的重量加1，然后以998號結(jié)點的父結(jié)點為當(dāng)前結(jié)點進行調(diào)整，根據(jù)這種思想對原文提供的UpDate函數(shù)進行修正所得新的UpDate函數(shù)附后。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!=

4、NULL)Tempa=Temp;while(Temp-Front !=NULL)Temp=Temp-Front;if(Temp=Tempa-Parent)Tempa-Weight+;Tempa-After=Tempa-Front=NULL;Temp-After=NULL;InsertWeight(Tempa);elsePointer=Temp-LeftChild;if(Pointer !=NULL)Pointer-Parent=Tempa;Temp-LeftChild=Tempa-LeftChild;if(Temp-LeftChild !=NULL)Temp-LeftChild-Parent=

5、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-

6、RightChild=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