?? huffmanhead.h
字號(hào):
#include "huffmanDlg.h"
#define MaxN 1000
#define MaxBit 100
#define MaxValue 10000
typedef struct
{
int weight;
int flag;
int parent;
int leftchild;
int rightchild;
}HaffNode;
typedef struct
{
int bit[MaxN];
int start;
int weight;
}Code;
void Haffman(int weight[],int n,HaffNode haffTree[])
{
int i,j,m1,m2,x1,x2;
/*哈弗曼樹haffTree初始化。n個(gè)葉節(jié)點(diǎn)的二叉樹共有2n-1個(gè)結(jié)點(diǎn)*/
for(i=0;i<2*n-1;i++)
{
if(i<n)
haffTree[i].weight=weight[i];
else
haffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;
haffTree[i].leftchild=-1;
haffTree[i].rightchild=-1;
}
/**構(gòu)造哈弗曼樹haffTree的n-1個(gè)非葉節(jié)點(diǎn)*/
for(i=0;i<n-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(haffTree[j].weight<m1&&haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;//記錄權(quán)值最小的結(jié)點(diǎn),作為左孩子結(jié)點(diǎn)
}
else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
{
m2=haffTree[j].weight;
x2=j;//記錄權(quán)值次小的結(jié)點(diǎn),作為右孩子結(jié)點(diǎn)
}
}
haffTree[x1].parent=n+i;//記錄父節(jié)點(diǎn)下標(biāo)
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;//標(biāo)記已經(jīng)進(jìn)入哈弗曼樹
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;//合并最小的兩個(gè)結(jié)點(diǎn)
haffTree[n+i].leftchild=x1;
haffTree[n+i].rightchild=x2;
}
}
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode [])
//由n個(gè)結(jié)點(diǎn)的哈弗曼樹haffTree構(gòu)造哈弗曼編碼haffCode
{
Code *cd=(Code *)malloc(sizeof(Code));
int i,j,child,parent;
for(i=0;i<n;i++)
{
cd->start=n-1;//初始化
cd->weight=haffTree[i].weight;
child=i;
parent=haffTree[child].parent;
while(parent!=-1)
{//循環(huán)賦值
if(haffTree[parent].leftchild==child)
cd->bit[cd->start]=0;//若為左節(jié)點(diǎn),則賦值為0
else
cd->bit[cd->start]=1;//若為右節(jié)點(diǎn),則賦值為1
cd->start--;
child=parent;
parent=haffTree[child].parent;//交換父節(jié)點(diǎn)信息,
}
for(j=cd->start+1;j<n;j++)
haffCode[i].bit[j]=cd->bit[j];//保存每個(gè)葉節(jié)點(diǎn)的編碼
haffCode[i].start=cd->start+1;//保存葉節(jié)點(diǎn)的起始位
haffCode[i].weight=cd->weight;//保存編碼對(duì)應(yīng)的權(quán)值
}
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -