#include?"hfm.h"
#include<string.h>
#include<malloc.h>?//malloc()等
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<limits.h>
#include<iostream>
#define?TRUE?1
#define?FALSE?1
#define?OK?1
#define?ERROR?1
#define?INFEASIBLE?-1
typedef?int?Status;
typedef?int?Boolean；
/************************************************************************/
/*?最優二叉樹簡稱：哈夫曼樹?*/
/************************************************************************/
//哈夫曼樹結構
;?typedef?struct{
unsigned?int?weight;?//權重
unsigned?int?parent,?lchild,?rchild;?//樹的雙親節點，和左右孩子
}HTNode,?*HuffmanTree;
typedef?char**?HuffmanCode;
//返回i個節點中權值最小的樹的根節點的序號，供select()調用
int?Min(HuffmanTree?T,?int?i){
int?j,?flag;
unsigned?int?k?=?UINT_MAX;?//%d-->UINT_MAX?=?-1,%u--->非常大的數
for?(j?=?1;?j?<=?i;?j++)
if?(T[j].weight?<?k?&&?T[j].parent?==?0)
k?=?T[j].weight,?flag?=?j;?//
T[flag].parent?=?1;//將parent標誌為1避免二次查找
return?flag;//返回
}
void?Select(HuffmanTree?T,?int?i,int&?s1,int&?s2){
//在i個節點中選取2個權值最小的樹的根節點序號，s1為序號較小的那個
int?j;
s1?=?Min(T,i);
s2?=?Min(T,i);
if?(s1?>?s2){
j?=?s1;
s1?=?s2;
s2?=?j;
}
}
//HuffmanCode代表的樹解碼二進制值
void?HuffmanCoding(HuffmanTree?&HT,?HuffmanCode&HC,?int*?w,?int?n){
//w存放n個字符的權值(均>0),構造哈夫曼樹HT,並求出n個字符的哈夫曼編碼HC
int?m,?i,?s1,?s2,?start;
unsigned?c,?f;
char*?cd;
//分配存儲空間
HuffmanTree?p;
if?(n?<=1)
return;
//n個字符(葉子節點)有2n-1個樹節點，所以樹節點m
m?=?2?*?n?-?1;
HT?=?(HuffmanTree)malloc((m?+?1)*sizeof(HTNode));?//0號元素未用
//這壹步是給哈夫曼樹的葉子節點初始化
for?(p?=?HT?+?1,?i?=?1;?i?<=?n;?++i,?++p,++w)
{
(*p).weight?=?*w;
(*p).lchild?=?0;
(*p).rchild?=?0;
(*p).parent?=?0;
}
//這壹步是給哈夫曼樹的非葉子節點初始化
for?(;?i?<=?m;?++i,?++p){
(*p).parent?=?0;
}
/************************************************************************/
/*?做完準備工作後?，開始建立哈夫曼樹
/************************************************************************/
for?(i?=?n?+?1;?i?<=?m;?i++)
{
//在HT[1~i-1]中選擇parent=0且weigh最小的節點，其序號分別為s1,s2
Select(HT,?i?-?1,?s1,?s2);?//傳引用
HT[s1].parent?=?HT[s2].parent=?i;
HT[i].lchild?=?s1;
HT[i].rchild?=?s2;
HT[i].weight?=?HT[s1].weight?+?HT[s2].weight;
}
/************************************************************************/
/*?從葉子到根逆求每個葉子節點的哈夫曼編碼?*/
/************************************************************************/
//分配n個字符編碼的頭指針向量，（[0]不用）
HC?=?(HuffmanCode)malloc((n?+?1)*sizeof(char*));?
cd?=?(char*)malloc(n*sizeof(char));//分配求編碼的工作空間
cd[n?-?1]?=?'\0';?//結束符
for?(i?=?1;?i?<=?n;?i++)?//每個節點的遍歷
{
start?=?n?-?1;
for?(c?=?i,?f?=?HT[i].parent;?f?!=?0;?c?=?f,f?=?HT[f].parent){?//每個節點到根節點的遍歷
//從葉子節點到根節點的逆序編碼
if?(HT[f].lchild?==?c)
cd[--start]?=?'0';
else
cd[--start]?=?'1';
}
HC[i]?=?(char*)malloc((n?-?start)*sizeof(char));?//生成壹個塊內存存儲字符
//為第i個字符編碼分配空間
strcpy(HC[i],?&cd[start]);?//從cd賦值字符串到cd
}
free(cd);?//釋放資源
}
//函數聲明
int?Min(HuffmanTree?T,?int?i);?//求i個節點中的最小權重的序列號，並返回
void?Select(HuffmanTree?T,?int?i,?int&?s1,?int&?s2);?//從兩個最小權重中選取最小的(左邊)給s1，右邊的給s2
void?HuffmanCoding(HuffmanTree?&HT,?HuffmanCode&HC,?int*?w,?int?n);//哈夫曼編碼與解碼
int?main(){
HuffmanTree?HT;
HuffmanCode?HC;
int?*w,?n,?i;
printf("請輸入權值的個數(>1):");
scanf_s("%d",&n);
w?=?(int*)malloc(n*sizeof(int));
printf("請依次輸入%d個權值(整形):\n",n);
for?(i?=?0;?i?<=?n?-?1;i++)
{
scanf_s("%d",w+i);
}
HuffmanCoding(HT,?HC,?w,?n);
for?(i?=?1;?i?<=?n;i++)
{
puts(HC[i]);
}
return?0;
}