1 題目
樣例輸入
8
5 29 7 8 14 23 3 11
樣例輸出
0110
10
1110
1111
110
00
0111
010
2 代碼
#include
#include
#include
#include
#include
using std::swap;
using std::strcpy;
typedef char *HuffmanCode;
const int MAXN = 110;
typedef struct{
int weight;
int lchild, rchild, parent;
}HuffmanNode, *HuffmanTree;
void seletMin(HuffmanTree HT, int n, int &s1, int &s2){
int min = INT32_MAX;
for (int i = 1; i <= n; ++i) {
if(HT[i].parent == 0 && min > HT[i].weight){
min = HT[i].weight;
s1 = i;
}
}
min = INT32_MAX;
for (int j = 1; j <= n; ++j) {
if(HT[j].parent == 0 && min > HT[j].weight && j != s1){
min = HT[j].weight;
s2 = j;
}
}
if(s1 > s2){
swap(s1, s2);
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode *&HC,int w[],int n){
// w存放n個字元的權值(均>0),構造哈夫曼樹HT,并求出n個字元的哈夫曼樹編碼HC
if(n <= 1) return;
int m = 2 * n -1;
//0号單元未用
HT = new HuffmanNode[m + 1];
for (int i = 1; i <= n; ++i) {
HT[i].weight = w[i];
HT[i].lchild = HT[i].rchild = HT[i].parent = 0;
}
for (int i = n + 1; i<= m; ++i) {
HT[i].lchild = HT[i].rchild = HT[i].parent = 0;
}
for (int i = n + 1; i <= m; ++i)//建立哈夫曼樹
{
int s1, s2;
//在HT[1~i-1]中選擇parent為0且weight最小的兩個結點,其序号分别為s1,s2
seletMin(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;
}
//從葉結點到根你想求每個字元的哈夫曼編碼
HC = new HuffmanCode[n + 1];
//配置設定n個字元編碼的頭指針向量([0]不用)
char* cd = new char[n];//配置設定編碼工作空間
cd[n - 1] = '\0';//編碼結束符
for (int i = 1; i <= n; ++i)//逐個字元求哈夫曼編碼
{
int star = n - 1;//編碼結束位置
for (int c = i, f = HT[i].parent;f != 0; c = f, f = HT[f].parent)
{
//從葉結點到根逆向求編碼
if(HT[f].lchild == c){
cd[--star] = '0';
}else{
cd[--star] = '1';
}
}
//為第i個字元串編碼配置設定空間
HC[i] = new char[n - star];
//從cd複制編碼(串)到HC
strcpy(HC[i], cd + star);
}
delete []cd;//釋放工作空間
}
int main(){
HuffmanTree HT;
HuffmanCode *HC;
int n;
int data[MAXN];
while(scanf("%d", &n) != EOF){
for (int i = 1; i <= n; ++i) {
scanf("%d", &data[i]);
}
HuffmanCoding(HT, HC, data, n);
for (int j = 1; j <= n; ++j) {
//printf("%s\n", HC[j]);
std::cout << HC[j] << std::endl;
}
delete(HT);
delete(HC);
}
return 0;
}
/*
Input:
8
5 29 7 8 14 23 3 11
Output:
0110
10
1110
1111
110
00
0111
010
*/