nyoj 801 Haffman符号化

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

分析:
万悪のハフマン、全く理解していません.私はいつそれを明らかにすることができますか.では、変数、そんなに多くの変化があります.
データ構造がどうしてこんなに難しいのか分からない.
写したコードですが、保存しておきますので、後でしっかり検討できるように001. #include<stdio.h> 002. #include<string.h> 003. #include<algorithm> 004. #define INF 99999999; 005. using   namespace   std; 006. struct   f 007. { 008. char   ch,*str; 009. int   w,p,l,r; 010. } num[200]; 011. int   main() 012. { 013. int   m,n,min1,min2,s1,s2,i,j,s,c,q; 014. char   *cd; 015. while ( scanf ( "%d" ,&n)!=EOF) 016. { 017. for (i=1; i<=n; i++) 018. { 019. getchar (); 020. scanf ( "%c%d" ,&num[i].ch,&num[i].w); 021. num[i].p=num[i].l=num[i].r=0; 022. } 023. m=2*n; 024. for (i=n+1; i<m; i++) 025. num[i].w=num[i].p=num[i].l=num[i].r=0; 026. // 027. for (i=n+1; i<m; i++) 028. { 029. min1=min2=INF; 030. s1=s2=0; 031. for (j=1; j<=i-1; j++) 032. { 033.
  034. if (num[j].p!=0) 035. continue ; 036. if (min1>num[j].w) 037. { 038. min2=min1; 039. min1=num[j].w; 040. s2=s1; 041. s1=j; 042. } 043. else   if (min1==num[j].w&&num[s1].ch>num[j].ch) 044. { 045. min2=min1; 046. min1=num[j].w; 047. s2=s1; 048. s1=j; 049. } 050. else   if (min2>num[j].w) 051. { 052. min2=num[j].w; 053. s2=j; 054. } 055. else   if (min2==num[j].w&&num[s2].ch>num[j].ch) 056. { 057. min2=num[j].w; 058. s2=j; 059. } 060. } 061. num[i].w=num[s1].w+num[s2].w; 062. num[s1].p=i; 063. num[s2].p=i; 064. if (num[s1].w==num[s2].w) 065. { 066. if (num[s1].ch>num[s2].ch) 067. { 068. num[i].ch=num[s2].ch; 069. num[i].l=s2; 070. num[i].r=s1; 071. } 072. if (num[s1].ch<num[s2].ch) 073. { 074. num[i].ch=num[s1].ch; 075. num[i].l=s1; 076. num[i].r=s2; 077. } 078. } 079. else 080. { 081. num[i].ch=num[s1].ch; 082. num[i].l=s1; 083. num[i].r=s2; 084. } 085. } 086. cd=( char   *) malloc (n* sizeof ( char )); 087. cd[n-1]= '\0' ; 088. for (i=1; i<=n; i++) 089. { 090. s=n-1; 091. c=i; 092. q=num[i].p; 093. while (q!=0) 094. { 095. --s; 096. if (num[q].l==c) 097. cd[s]= '0' ; 098. else 099. cd[s]= '1' ; 100. c=q; 101. q=num[q].p; 102. } 103. num[i].str=( char   *) malloc ((n-s)* sizeof ( char )); 104. strcpy (num[i].str,&cd[s]); 105. } 106. free (cd); 107. for (i=1; i<=n; i++) 108. printf ( "%c:%s
" ,num[i].ch,num[i].str); 109. } 110. return   0; 111. }