ハフマンコーディング
1626 ワード
ハフマン符号の符号化/復号システムを書き、伝送するメッセージを符号化および復号化することが要求される.ハフマンツリーを構築する場合、重み値の小さいものは左サブツリー、重み値の大きいものは右サブツリー、符号化時に右サブツリーは1、左サブツリーは0と符号化する.
文字セットのサイズがn(n<=100)であることを示す正の整数と、n文字とn個の重み値(正の整数、値が大きいほどその文字が現れる確率が大きい)を入力します.シリアル長が100以下のターゲットメッセージを入力します.
符号化されたバイナリ符号は、1行を占める.復号後のメッセージに対応し、1行を占める.最後にリターン記号を出力
5 a b c d e 12 40 15 8 25bbbaddeccbbb
00011111110111010110110000bbbaddeccbbb
文字セットのサイズがn(n<=100)であることを示す正の整数と、n文字とn個の重み値(正の整数、値が大きいほどその文字が現れる確率が大きい)を入力します.シリアル長が100以下のターゲットメッセージを入力します.
符号化されたバイナリ符号は、1行を占める.復号後のメッセージに対応し、1行を占める.最後にリターン記号を出力
5 a b c d e 12 40 15 8 25bbbaddeccbbb
00011111110111010110110000bbbaddeccbbb
#include
#include
#include
#include
#define MAXBIT 100
#define MAXNODE 1000
#define MAXNUM 100000
#define MAXWEIGHT 1000
using namespace std;
//
typedef struct
{
int bit[MAXBIT];
int start;
}HCodeType;
//
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
char value;
}HNodeType;
void HuffmanTree(HNodeType HuffNode[],int n)
{
int i,j;
//
for(i=0;i<2*n-1;i++)
{
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
HuffNode[i].value=-1;
}
//
for(i=0;i>HuffNode[i].value;
for(i=0;i>HuffNode[i].weight;
for(i=0;i