Haffmanコード
2617 ワード
Haffmanコード
時間制限:1000 ms|メモリ制限:65535 KB
難易度:3
説明
ハフマンコードは皆さんおなじみでしょう(詳しくなくても大丈夫、自分で調べます...).文字列と対応する重み値を与えて、ハフマンツリーを構築して、各文字のハフマン符号化を決定します.もちろん、ここにはいくつかの小さな規定があります.
1.ハフマンツリーの左サブツリー符号化を0、右サブツリー符号化を1とする.
2.両方の文字の重み値が同じであれば、ASCIIコードの値が小さい文字は左の子供、大きい文字は右の子供である.
3.作成された新しいノードが表す文字は、その左の子供の文字と同じです.
4.すべての文字はASCIIコードテーブル上の32-96の間の文字(すなわち「」から「`」の間の文字)である.
入力
複数のデータを含む入力(100を超えない)
各グループのデータの最初の行には整数nがあり、文字の個数を表す.次にn行、各行に1文字chと整数weightがあり、文字chに対応する重み値を表し、中間をスペースで区切る.
入力データは、各テストデータの文字が重複しないことを保証します.
しゅつりょく
各テストデータのセットについて、対応する文字およびそれらのハーバーマン符号化結果を入力順に出力し、具体的なフォーマットはサンプルを参照してください.
サンプル入力
3
a 10
b 5
c 8
4
a 1
b 1
c 1
d 1
サンプル出力
a:0
b:10
c:11
a:00
b:01
c:10
d:11
ソース
オリジナル
アップロード者
TC_黄平
#include #include #include #define N 30 #define M 2*N-1 typedef struct { int weight; int parent; int lchild; int rchild; }HTnode,HTree[M+1]; typedef struct zi{ char n;//構造タイプの定義}zi;zi ch[55]; typedef char* HaCode[N+1]; void select(HTree ht,int n,int *p,int *q){ int min1=32767,min2=32767,t,i; for(i=1;i<=n;i++) if(ht[i].parent==0) { if(min1>ht[i].weight){ min1=ht[i].weight; *p=i; }}for(i=1;i<=n;i++)if(ht[i].parent=0&&i!=*p){if(min 2>ht[i].weight&&i!=*p){//select関数min 2=ht[i].weight;*q=i; } } if(ht[*p].weight==ht[*q].weight&&ch[*p].n>ch[*q].n){ t=*q; *q=*p; *p=t; }}void CrtHTree(HTree ht,int n){//ツリーint i;int s 1,s 2,m=2*n-1;for(i=1;i<=n;i+){scanf("%c%d",&ch[i].n,&ht[i].weight);ht[i].parent=ht[i].lchild=ht[i].rchild=0; } for(i=n+1;i<=m;i++) ht[i].weight=ht[i].parent=ht[i].lchild=ht[i].rchild=0; for(i=n+1;i<=m;i++) { select(ht,i-1,&s1,&s2); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i;ht[s2].parent=i; ht[i].lchild=s1;ht[i].rchild=s2; }void CrtHacode(HTree ht,HaCode hc,int n){//符号化char*cd;int start,c,i,p;cd=(char*)malloc(n*sizeof(char);cd[n-1]='0';for(i=1;i<=n;i+){start=n-1;c=i;p=ht[i]=i].parent;whiile(p!=0){start;start;if(ht[p].lchild==c)[start]==0;cd[start]==0;p]=0';else cd[start]='1';c=p;p=ht[p].parent; } hc[i]=(char*)malloc(sizeof(char)); strcpy(hc[i],&cd[start]); } free(cd); } int main(){int l,i;HaCode hc;HTree ht;while(~scanf("%d",&l)){//主関数CrtHTree(ht,l);CrtHacode(ht,hc,l);for(i=1;i<=l;i+)printf("%c:%s",ch[i].n,hc[i]); } return 0; }
//ポインタや配列の使い方が間違っているかもしれませんが、テストデータに問題はありません.