c語言如何實現(xiàn)哈夫曼編碼與譯碼

　　在電報通訊中，電文是以二進制的0、1序列傳送的。字符集中的字符的使用頻率是不同的（比如e和t的使用較之q和z要頻繁得多），哈夫曼編碼可以使得編碼的總長最短，從而相同的位長可以傳送更多的信息。

　　本程序以下面的字符及使用頻率為例：

　　首先建立哈夫曼樹：

　　下面是哈夫曼編碼的存儲結(jié)構(gòu)：

　　程序清單如下：

　　#include《stdio.h》

　　#define n 5 //葉子數(shù)目

　　#define m （2*n-1） //結(jié)點總數(shù)

　　#define maxval 10000.0

　　#define maxsize 100 //哈夫曼編碼的最大位數(shù)

　　typedef struct

　　{

　　char ch;

　　float weight;

　　int lchild，rchild，parent;

　　}hufmtree;

　　typedef struct

　　{

　　char bits［n］; //位串

　　int start; //編碼在位串中的起始位置

　　char ch; //字符

　　}codetype;

　　void huffman（hufmtree tree［］）;//建立哈夫曼樹

　　void huffmancode（codetype code［］，hufmtree tree［］）;//根據(jù)哈夫曼樹求出哈夫曼編碼

　　void decode（hufmtree tree［］）;//依次讀入電文，根據(jù)哈夫曼樹譯碼

　　void main（）

　　{

　　printf（“ ——哈夫曼編碼——\n”）;

　　printf（“總共有%d個字符\n”，n）;

　　hufmtree tree［m］;

　　codetype code［n］;

　　int i，j;//循環(huán)變量

　　huffman（tree）;//建立哈夫曼樹

　　huffmancode（code，tree）;//根據(jù)哈夫曼樹求出哈夫曼編碼

　　printf（“【輸出每個字符的哈夫曼編碼】\n”）;

　　for（i=0;i《n;i++）

　　{

　　printf（“%c： ”，code［i］.ch）;

　　for（j=code［i］.start;j《n;j++）

　　printf（“%c ”，code［i］.bits［j］）;

　　printf（“\n”）;

　　}

　　printf（“【讀入電文，并進行譯碼】\n”）;

　　decode（tree）;//依次讀入電文，根據(jù)哈夫曼樹譯碼

　　}

　　void huffman（hufmtree tree［］）//建立哈夫曼樹

　　{

　　int i，j，p1，p2;//p1，p2分別記住每次合并時權(quán)值最小和次小的兩個根結(jié)點的下標

　　float small1，small2，f;

　　char c;

　　for（i=0;i《m;i++） //初始化

　　{

　　tree［i］.parent=0;

　　tree［i］.lchild=-1;

　　tree［i］.rchild=-1;

　　tree［i］.weight=0.0;

　　}

　　printf（“【依次讀入前%d個結(jié)點的字符及權(quán)值（中間用空格隔開）】\n”，n）;

　　for（i=0;i《n;i++） //讀入前n個結(jié)點的字符及權(quán)值

　　{

　　printf（“輸入第%d個字符為和權(quán)值”，i+1）;

　　scanf（“%c %f”，&c，&f）;

　　getchar（）;

　　tree［i］.ch=c;

　　tree［i］.weight=f;

　　}

　　for（i=n;i《m;i++） //進行n-1次合并，產(chǎn)生n-1個新結(jié)點

　　{

　　p1=0;p2=0;

　　small1=maxval;small2=maxval; //maxval是float類型的最大值

　　for（j=0;j《i;j++） //選出兩個權(quán)值最小的根結(jié)點

　　if（tree［j］.parent==0）

　　if（tree［j］.weight《small1）

　　{

　　small2=small1; //改變最小權(quán)、次小權(quán)及對應(yīng)的位置

　　small1=tree［j］.weight;

　　p2=p1;

　　p1=j;

　　}

　　else

　　if（tree［j］.weight《small2）

　　{

　　small2=tree［j］.weight; //改變次小權(quán)及位置

　　p2=j;

　　}

　　tree［p1］.parent=i;

　　tree［p2］.parent=i;

　　tree［i］.lchild=p1; //最小權(quán)根結(jié)點是新結(jié)點的左孩子

　　tree［i］.rchild=p2; //次小權(quán)根結(jié)點是新結(jié)點的右孩子

　　tree［i］.weight=tree［p1］.weight+tree［p2］.weight;

　　}

　　}//huffman

　　void huffmancode（codetype code［］，hufmtree tree［］）//根據(jù)哈夫曼樹求出哈夫曼編碼

　　//codetype code［］為求出的哈夫曼編碼

　　//hufmtree tree［］為已知的哈夫曼樹

　　{

　　int i，c，p;

　　codetype cd; //緩沖變量

　　for（i=0;i《n;i++）

　　{

　　cd.start=n;

　　cd.ch=tree［i］.ch;

　　c=i; //從葉結(jié)點出發(fā)向上回溯

　　p=tree［i］.parent; //tree［p］是tree［i］的雙親

　　while（p！=0）

　　{

　　cd.start--;

　　if（tree［p］.lchild==c）

　　cd.bits［cd.start］=‘0’; //tree［i］是左子樹，生成代碼‘0’

　　else

　　cd.bits［cd.start］=‘1’; //tree［i］是右子樹，生成代碼‘1’

　　c=p;

　　p=tree［p］.parent;

　　}

　　code［i］=cd; //第i+1個字符的編碼存入code［i］

　　}

　　}//huffmancode

　　void decode（hufmtree tree［］）//依次讀入電文，根據(jù)哈夫曼樹譯碼

　　{

　　int i，j=0;

　　char b［maxsize］;

　　char endflag=‘2’; //電文結(jié)束標志取2

　　i=m-1; //從根結(jié)點開始往下搜索

　　printf（“輸入發(fā)送的編碼（以‘2’為結(jié)束標志）：”）;

　　gets（b）;

　　printf（“譯碼后的字符為”）;

　　while（b［j］！=‘2’）

　　{

　　if（b［j］==‘0’）

　　i=tree［i］.lchild; //走向左孩子

　　else

　　i=tree［i］.rchild; //走向右孩子

　　if（tree［i］.lchild==-1） //tree［i］是葉結(jié)點

　　{

　　printf（“%c”，tree［i］.ch）;

　　i=m-1; //回到根結(jié)點

　　}

　　j++;

　　}

　　printf（“\n”）;

　　if（tree［i］.lchild！=-1&&b［j］！=‘2’） //電文讀完，但尚未到葉子結(jié)點

　　printf（“\nERROR\n”）; //輸入電文有錯

　　}//decode