Huffman編碼C實現

Huffman編碼：根據Huffman樹進行編碼的，用到的數據結構是二叉樹。

C++使用優先隊列來構建huffman樹[哈夫曼樹] http://www.linuxidc.com/Linux/2012-01/52790.htm

Huffman編碼實現（詳細實現） http://www.linuxidc.com/Linux/2012-01/51730.htm

Huffman編碼與解碼的實現 http://www.linuxidc.com/Linux/2014-08/105644.htm

typedef int elemtype;
typedef struct
{
elemtype weight;
int parent,l_child,r_child;
} binarytree;

//2、構建最優二叉樹
void CreateHuffman(int leafnum, binarytree *huffmantree)
{
//leafnum個葉子，決定nodenum個結點數
int nodenum=2*leafnum-1;
huffmantree=(binarytree *)malloc(nodenum*sizeof(binarytree)); //0號單元也使用

//leafnum個葉子，決定nodenum個結點數，也決定了（nodenum-1）個bit位編碼
char *huffmancode;
huffmancode =(char *)malloc((nodenum-1)*sizeof(char));

//huffmantree的初始化:葉子結點data權值手動輸入，非葉子默認值都為0
cout<<"請輸入葉子權值：";
int i;
for(i=0;i<nodenum;i++)
{
if(i<leafnum)
{
cin>>huffmantree[i].weight;
}
else
{
huffmantree[i].weight=0;
}
huffmantree[i].parent=huffmantree[i].l_child=huffmantree[i].r_child=0;
}

int j;
//j從leafnum開始，指的是包含了新建子樹的結點編號
for(j=leafnum;j<nodenum;j++)
{
int w1=32767,w2=0; //存儲最小權值；
int p=0,q=0; //存儲最小權值的編號；

int k;
for(k=0;k<j;k++)
{
if(huffmantree[k].parent==0) //判斷結點是否使用
{
if(huffmantree[k].weight<w1)
{
w2=w1;
q=p;
w1=huffmantree[k].weight;
p=k;

}
else if(huffmantree[k].weight<w2)
{
w2=huffmantree[k].weight;
q=k;
}
}
}
//p對應左節點，編碼為‘0’；q對應左節點，編碼為‘1’；
huffmancode[p]='0';
huffmancode[q]='1';

huffmantree[j].weight =w1+w2;
huffmantree[j].l_child=p;
huffmantree[j].r_child=q;
huffmantree[p].parent=j;
huffmantree[q].parent=j;
}

//3、尋找從子節點到根節點的編碼 HuffmanCoding(int n,binarytree *HuffmanTree)
//針對每一個葉子，從葉子到根方向尋找huffmancode
//每一個葉子，對應的編碼長度codelength
const int maxsize=10;
char iscode[maxsize][maxsize];
int m;
for(m=0;m<leafnum;m++) //從第一個葉子開始找
{
int n=0;
iscode[m][n]=huffmancode[m];
int parent=huffmantree[m].parent;
while(parent !=0)
{
iscode[m][++n]=huffmancode[parent];
parent=huffmantree[parent].parent;
};

int x;
cout<<"第"<<m+1<<"個葉子的HuffmanCode————";
for(x=0;x<n;x++)
cout<<iscode[m][x];
cout<<endl;
}
}

void main()
{
binarytree *T=0;
int leafnum;
printf("輸入葉子數量n=\n");
cin>>leafnum;
CreateHuffman( leafnum, T);
while(1);
}

編譯結果如下：