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で質問しましょう!
似たような質問が見つかりました
- 数学 ハフマン符号の符号化についてです。 確率が(A,0.25)( B,0.25)( C,0.2)( D, 1 2022/07/06 13:56
- 数学 ハフマン符号化にかんしての問題です。 出現確率が次の通りであるような記号AからFがある。 このとき、 1 2023/01/26 12:16
- その他(教育・科学・学問) 【 情報 ハフマン木 】 ハフマン符号化では、なぜハフマン木を用いるのですか? 例えばテキストデータ 1 2022/10/11 22:41
- その他(プログラミング・Web制作) プログラムの勉強のおすすめは 7 2022/12/09 20:09
- C言語・C++・C# C言語 3 2022/10/04 15:07
- その他(プログラミング・Web制作) 詳しい方誰か教えてください 1 2022/04/28 16:32
- その他(プログラミング・Web制作) 【プログラミングScratch】で音楽を演奏するプログラムを短時間でつくる方法 2 2023/07/02 07:50
- C言語・C++・C# [C言語] コメント文字列を無視して、数値データを読み込むプログラム部分について 5 2022/10/05 11:03
- C言語・C++・C# 至急お願いします。C言語で.imgのファイルを読み込んで1バイトづつ出力するプログラムを作りたいので 3 2023/01/16 22:49
- C言語・C++・C# c言語 コマンドライン引数 4 2023/02/09 18:47
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
分数の足し算をさせるプログラ...
-
再起呼び出しの回数をカウント...
-
迷路を脱出する経路探索プログ...
-
放射状ブラー C言語で書いたの...
-
OpenCVによる4値化について
-
argvのNULLチェック
-
関数とビット列
-
C言語で%を使わない余りの出し方
-
rand()の乱数は何故良くないの?
-
C言語の問題
-
intとlongは同じ?
-
opencvとmbedのシリアル通信で...
-
c++ TCHARで文字化け
-
returnの使い方
-
再帰処理をループ処理に変換
-
C++で表を作成したいのです ...
-
C言語
-
迷路の解を見つけるアルゴリズム
-
C言語のプログラムについて(...
-
強連結判定を行うプログラムに...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
2の補数を計算するプログラム
-
intとlongは同じ?
-
再起呼び出しの回数をカウント...
-
C言語で%を使わない余りの出し方
-
迷路を脱出する経路探索プログ...
-
画像の拡大・縮小
-
分数の足し算をさせるプログラ...
-
C言語で簡単なパックマンゲーム...
-
C++で表を作成したいのです ...
-
条件が多い場合
-
複数の共有メモリの作成
-
ヒストグラム均等化処理プログラム
-
3のつく数と3の倍数を表示 C言語
-
argvのNULLチェック
-
乱数で交互に偶数、奇数が、、、。
-
プログラミングに関して
-
OpenCVによる4値化について
-
再帰処理をループ処理に変換
-
16bitで乱数を生成する方法
-
C++ Debug Errorについて教えて
おすすめ情報