データ構造実験33——ハフマンコンパイラ【写した】
4905 ワード
Description
ハフマン符号の符号化/復号システムを書き、伝送するメッセージを符号化および復号化することが要求される.ハフマンツリーを構築する場合,重み値の小さいものは左サブツリー,重み値の大きいものは右サブツリー,符号化時は右サブツリーは1,左サブツリーは0と符号化する.
Input
文字セットのサイズがn(n<=100)であることを示す正の整数と、n文字とn個の重み値(正の整数、値が大きいほどその文字が現れる確率が大きい)を入力します.シリアル長が100以下のターゲットメッセージを入力します.
Output
符号化されたバイナリ符号は、1行を占める.復号後のメッセージに対応し、1行を占める.最後にリターン記号を出力
文字セットのサイズがn(n<=100)であることを示す正の整数と、n文字とn個の重み値(正の整数、値が大きいほどその文字が現れる確率が大きい)を入力します.シリアル長が100以下のターゲットメッセージを入力します.
Output
符号化されたバイナリ符号は、1行を占める.復号後のメッセージに対応し、1行を占める.最後にリターン記号を出力
Sample Input
5 a b c d e 12 40 15 8 25
bbbaddeccbbbSample Output
00011111110111010110110000
#include
#include
#include
int pc = 1;
typedef struct HtNode
{
int weight;
int parent, lchild, rchild;
int flag;
}HtNode;
typedef struct HtTree
{
HtNode ht[3000];
int root;
}phtree;
void select(phtree* pht,int pos,int *x1,int *x2)
{
int m1, m2;
m1 = m2 = 10000;
for(int i = 1;i < pos;i++)
{
if(pht->ht[i].weight < m1 && pht->ht[i].parent == 0)
{
m2 = m1;
*x2 = *x1;
m1 = pht->ht[i].weight;
*x1 = i;
}
else if(pht->ht[i].weight < m2 && pht->ht[i].parent == 0 && pht->ht[i].weight > m1)
{
m2 = pht->ht[i].weight;
*x2 = i;
}
}
}
phtree *huffman(int n,int *w)
{
phtree* pht;
int i, x1, x2;
pht = (phtree* )malloc(sizeof(phtree));
pht->ht[0].flag = 2;
pht->ht[0].lchild = 0;
pht->ht[0].rchild = 0;
pht->ht[0].parent = 0;
pht->ht[0].weight = 0;
for(i = 2*n;i < 3000;i++)
{
pht->ht[i].flag = 2;
pht->ht[i].lchild = 0;
pht->ht[0].rchild = 0;
pht->ht[0].parent = 0;
pht->ht[0].weight = 0;
}
for(i = 1;i <= 2*n-1;i++)
{
pht->ht[i].lchild = 0;
pht->ht[i].rchild = 0;
pht->ht[i].parent = 0;
pht->ht[i].flag = 2;
if(i <= n)
{
pht->ht[i].weight = w[i];
}
else
{
pht->ht[i].weight = 0;
}
}
for(i = 1;i < n;i++)
{
select(pht,n+i,&x1,&x2);
pht->ht[x1].parent = n+i;
pht->ht[x1].flag = 0;
pht->ht[x2].parent = n+i;
pht->ht[x2].flag = 1;
pht->ht[n+i].weight = pht->ht[x1].weight + pht->ht[x2].weight;
pht->ht[n+i].lchild = x1;
pht->ht[n+i].rchild = x2;
pht->root = n+i;
}
return pht;
}
void traversehuffman(phtree *t,int n,int pcode[][100])
{
int i = 1;
HtNode node;
node = t->ht[pc];
while(node.parent != 0)
{
pcode[pc][i] = node.flag;
node = t->ht[node.parent];
i++;
}
pc++;
}
void output(int pcode[][100],int n,char *x)
{
int i, j, k, cnt;
int code[100][100];
for(i =0;i < 100;i++)
{
for(j = 0;j < 100;j++)
{
code[i][j] = -1;
}
}
for(i = 1;i <= n;i++)
{
for(cnt = 1;pcode[i][cnt+1] == 1 || pcode[i][cnt+1] == 0;cnt++);
k = cnt;
for(j = 1;j<= k;j++)
{
code[i][j] = pcode[i][cnt--];
}
}
char s[100], c;
scanf("%s",s);
int f = strlen(s);
for(i = 0;i <= f;i++)
{
for(j = 1;j <= n;j++)
{
if(s[i] == x[j])
{
for(k = 1;code[j][k] == 0 || code[j][k] == 1;k++)
{
printf("%d",code[j][k]);
}
}
}
}
printf("
%s
",s);
}
int main()
{
int i, n, cnt = 1;
char c;
int w[101];
char s[101];
int pcode[100][100];
for(i = 0;i < 100;i++)
{
for(int j = 0;j < 100;j++)
{
pcode[i][j] = -1;
}
}
scanf("%d",&n);
while(1)
{
scanf("%c",&c);
if(cnt == n+1)
{
break;
}
else if(c != ' ')
{
s[cnt++] = c;
}
}
for(i = 1;i <= n;i++)
{
scanf("%d",&w[i]);
}
phtree* pht;
pht = huffman(n,w);
for(i = 1;i <= n;i++)
{
traversehuffman(pht,n,pcode);
}
output(pcode,n,s);
return 0;
}