
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言語
-
c言語の問題
-
C言語で簡単なパックマンゲーム...
-
2次関数プログラムを描写する...
-
異なるn個の整数からr個の整数...
-
intとlongは同じ?
-
Aの値からBの値を除するとは??
-
「Aに対するBの割合」と「Aに対...
-
信頼区間の1.96や1.65ってどこ...
-
プログラミング python
-
EXCEL AVEREGE関数について
-
C言語の問題です。 標準入力 (...
-
入力された数字を大きい順に並...
-
画面上をクリックするとクリッ...
-
プログラム作成教えてください...
-
Excelで1つしかない値だけを抽...
-
プロセシングの質問です。
-
Excelセルに入力された文字の色...
-
このプログラミングの問題の2つ...
-
C言語の課題です
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
2の補数を計算するプログラム
-
【C#】SQL文の中に変数を埋め込...
-
再起呼び出しの回数をカウント...
-
C言語のプログラムについて(...
-
C言語で%を使わない余りの出し方
-
3のつく数と3の倍数を表示 C言語
-
分数の足し算をさせるプログラ...
-
intとlongは同じ?
-
C++で表を作成したいのです ...
-
c言語プログラミングについて f...
-
再帰処理をループ処理に変換
-
argvのNULLチェック
-
コマンドプロンプトのウィンド...
-
ヌメロンのプログラム
-
条件が多い場合
-
C言語でDOS画面のプログラム(...
-
プログラミングに関して
-
ヒストグラム均等化処理プログラム
-
複数の共有メモリの作成
-
OpenGLの惑星プログラム
おすすめ情報