
No.1ベストアンサー
- 回答日時:
木の作り方によって得られる符号は微妙に違いますのでこれは参考です。
シンボルと頻度テーブルから木を作って符号一覧を表示します。
符号化だけならleftとrightは不要です(復号化のとき使う)
#include <stdio.h>
#define N 6 /* N>=2 */
char *s[N]={"a1","a2","a3","a4","a5","a6"};
float f[2*N-1]={0.35,0.15,0.15,0.20,0.10,0.05};
int size=N, parent[2*N-1], left[2*N-1], right[2*N-1];
/* ハフマン木の作成 */
void huff(void) {
int i,j,dat1,dat2;
float min;
/* 初期化 */
for (i=0;i<2+N;i++) left[i]=right[i]=parent[i]=0;
/* 最小頻度2個をまとめ続ける */
while(1) {
/* 一番小さい数を探す */
for (i=0;i <size;i++) if (f[i]>=0) break;
if (i==size) break; /* 頻度リストが空? */
dat1=i; min=f[dat1];
for (;i<size;i++) if (f[i]<min && f[i]>=0) {min=f[i]; dat1=i;}
/* 二番目に小さい数を探す */
for (i=0; i<size; i++) if ((f[i]>=0)&&(i!=dat1)) break;
if (i==size) break; /* 頻度リストが1個しかない */
dat2=i; min=f[dat2];
for (;i<size;i++) if (f[i]<min && f[i]>=0 && i!=dat1) { min=f[i]; dat2=i; }
/* 木に登録 */
left[size]=dat1; right[size]=dat2;
parent[dat1]=size; parent[dat2]= -size;
f[size]=f[dat1]+f[dat2]; f[dat1]= -1; f[dat2]= -1;
size ++;
}
}
/* ハフマン符号の出力 */
void outenc(int huf) {
if (huf== size-1) return;
if (parent[huf]<0) {
outenc(-parent[huf]); printf("1");
} else {
outenc(parent[huf]); printf("0");
}
}
/* メインルーチン */
int main(void) {
int i;
huff();
for (i=0; i<N; i++) { printf("%s ",s[i]); outenc(i); printf("\n"); }
return 0;
}
この回答へのお礼
お礼日時:2008/07/05 00:47
詳しい説明ありがとうございます。
コメントが多いのでとてもわかりやすかったです。
これを参考にいろいろ変えて試してみます。
本当にありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
c言語プログラミングについて f...
-
クリックされた地点が2点の線分...
-
openCVの画像処理について
-
C++ bmp 透過処理
-
intとlongは同じ?
-
C++デバックエラーについて詳し...
-
C++ Debug Errorについて教えて
-
再起呼び出しの回数をカウント...
-
C言語プログラミング 漸化式に...
-
「Aに対するBの割合」と「Aに対...
-
2÷3などの余りについて
-
信頼区間の1.96や1.65ってどこ...
-
Aの値からBの値を除するとは??
-
C言語での引数の省略方法
-
20'(角度)の計算がわかりま...
-
C言語のfor文です。 繰り返しの...
-
long型の定数の末尾にLを付ける...
-
マイナスからプラスへ転じた時...
-
Enterキーを押されたら次の処理...
-
ある商品のロス率を5%見込み、...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
2の補数を計算するプログラム
-
【C#】SQL文の中に変数を埋め込...
-
再起呼び出しの回数をカウント...
-
C言語のプログラムについて(...
-
C言語で%を使わない余りの出し方
-
3のつく数と3の倍数を表示 C言語
-
分数の足し算をさせるプログラ...
-
intとlongは同じ?
-
C++で表を作成したいのです ...
-
c言語プログラミングについて f...
-
再帰処理をループ処理に変換
-
argvのNULLチェック
-
コマンドプロンプトのウィンド...
-
ヌメロンのプログラム
-
条件が多い場合
-
C言語でDOS画面のプログラム(...
-
プログラミングに関して
-
ヒストグラム均等化処理プログラム
-
複数の共有メモリの作成
-
OpenGLの惑星プログラム
おすすめ情報