#include<stdio.h>
#include<stdlib.h>
#define MAXVALUE 32767
int n;
typedef struct{ //哈夫曼樹結構體
int weight; //權值
int parent,lc,rc; //雙親節點，左孩子，右孩子
}HNode;
typedef struct{ //哈夫曼編碼結構體
int bit[10]; //存放當前結點的哈夫曼編碼
int start; //存放哈夫曼編碼
}HCode;
HNode HN[10];
HCode HC[10];
void createHNTree(){
int i,j;
int a,b;
int x1,x2;
printf("請輸入節點的個數：\n");
scanf("%d",&n);
for(i=1;i<2*n;i++){ //初始化哈夫曼樹
HN[i].weight = 0; //權值
HN[i].lc = -1;
HN[i].rc = -1;
HN[i].parent = -1;
}
//輸入 n 個葉子結點的權值
for(i=1;i<=n;i++){
printf("請輸入第%d個葉結點的權值：\n",i);
scanf("%d",&HN[i].weight );
}
for(i=1;i<n;i++){ //構造哈夫曼樹
a = b = MAXVALUE;
x1 = x2 = 0;
for(j=0;j<=n+i;j++){
if(HN[j].weight <a && HN[j].parent == -1){
b = a;
x2 = x1;
a = HN[j].weight ;
x1=j;
}
else if(HN[j].weight <b && HN[j].parent == -1){
b = HN[j].weight ;
x2=j;
}
}
HN[x1].parent =n+i;
HN[x2].parent =n+i;
HN[n+i].weight = HN[x1].weight + HN[x2].weight;
HN[n+i].lc = x1;
HN[n+i].rc = x2;
}
}
void createHC(){
HCode hc;
int i,j,p,c;
for(i=1;i<=n;i++){
hc.start = n;
c=i;
p=HN[c].parent ;
while(p != -1)
{
if(HN[p].lc == c)
hc.bit[hc.start] = 0;
else
hc.bit[hc.start] = 1;
hc.start--;
c = p;
p = HN[c].parent;
}
for(j=hc.start+1;j<=n;j++)
HC[i].bit[j]=hc.bit[j];
HC[i].start=hc.start;
}
}
void printHC(){
int i,j;
for(i=1;i<=n;i++){
for(j=HC[i].start+1;j<=n;j++)
printf("%d",HC[i].bit[j]);
printf("\n");
}
}
int main(void){
createHNTree();
createHC();
printHC();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/87610.html
標籤：疑難問題
上一篇：sql陳述句