C實現哈夫曼樹和哈夫曼編碼

C實現哈夫曼樹和哈夫曼編碼

typedef struct HaffTree{
int parent,lchild,rchild;
int data;
int weight;
}HaffTree,*Htree;

typedef char* *Ch;

//得到每個葉子結點的haffman編碼值
void get_haff_code(Htree T,Ch *ch,int n){
int c,f;
char * chpoint=(char*)malloc(n*sizeof(char)); //分配一串字符空間
chpoint[start]='/0'; //最後一個字符設置為空格，便於在控制台輸出更清晰。
for(int i=1;i<=n;i++){ //從第一個葉子結點開始循環讀取haff編碼
int start=n-1;
for(c=1,f=T[c].parent;f!=0;c=f;f=T[f].parent) //
{ if(T[f].lchild==c)
chpoint[--start]='0'; //若為左孩子則設置為0
else
chpoint[--start]='1'; //否則設置為1
}
ch[i]=(char*)malloc((n-start)sizeof(char)); //分配得到的編碼的長度的字符空間。
strcopy(ch[i],&chpoint[start]); //復制。
}
free(chpoint); //最後釋放空間。
}


//創建一個Haffmantree,傳遞的參數為:T 樹的首地址，s1為左孩子的序號，s2為右孩子序號，n為葉子結點數
void create_haff_tree(Htree T,int n,int &s1,int&s2){
for(int i=n+1;i<2*n-1;i++){
select_max_node(T,i-1,&s1,&s2);
T[s1].parent=i;
T[s2].parent=i;
T[i].lchild=s1;
T[i].rchild=s2;
T[i].weight=T[s1].weight+T[s2].weight;
}
}

Ch* init_tree(Htree T,Data *v,int n)
{
Ch *ch;
int m= 2*n-1;
T=(Htree)malloc((m+1)*sizeof(HaffTree));//分配m+1個結點的HaffTree,從1開始計數
ch=(Ch)malloc((m+1)sizeof(Ch)); //分配m+1個字符串指針數組，每個指針值指向一串字符編碼

//***************初始化葉子結點值
for(int i=1;i<=m;i++)
{
T[i]->parent=0;
T[i]->lchild=0;
T[i]->rchild=0;
T[i]->data=v.data;
T[i]->weight=v.weight;
}
//*****************初始化父節點的值
for(int i=n+1;i<=2*n-1;i++)
{
T[i].parent=0;
T[i].lchild=0;
T[i].rchild=0;
T[i].weight=0;
}
return ch;
}