データ構造の第6回オンライン試験——ハフマン符号化アルゴリズムの実現

実験目的:
(1)二叉木の定義を把握する.
(2)ハフマンツリーとハフマン符号化アルゴリズムの実現を把握する.     
実験内容:
ハフマン符号化システムを実現し、システムは以下の機能を含む.
(1)文字情報統計:符号化対象のソースファイルSourceFileを読み込む.txtは、出現する文字とその頻度を統計します.
添付:SourceFile.txtファイルの内容は

AAAAABBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCDDDDDDDDEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFGGGHHHHHHHHHHH

(2)ハフマンツリーの構築:統計結果に基づいてハフマンツリーを構築する.
(3)ハフマン符号表を作成する:得られたハフマンツリーを利用して、各文字に対応する符号表をファイルCodeに保存する.txtで.
(4)ソースファイルを符号化する:ハフマン符号表に基づいてSourceFile.txt中の文字を対応する符号化ファイルResultFileに変換する.txt.
実装のヒント:
(1)文字情報統計:ソースファイルSourceFileを想定.txtの文字は大文字と小文字の英字(同じ文字の大文字と小文字を1文字と見なす)のみであり、文字統計アルゴリズムの実現過程は、26要素を含む整形配列を定義し、各文字の出現回数を格納し、最後に出現回数が0の配列要素を排除することにまとめることができる.
(2)ハフマンツリーの構築:教材アルゴリズム5.10を参照し,関数Selectの実装を補完する.
(3)ハフマンコード表を作成する:教材アルゴリズム5.11を参照し、コンパイル表HCの内容をファイルCodeに書く.txtで.
(4)ソースファイルを符号化:順次ファイルSourceFileを読み込む.txt中の文字cは、符号化テーブルHCにおいてこの文字を見つける、文字cを符号化テーブルに格納符号化列に変換し、符号化ファイルResultFileに書き込む.txtでは、すべての文字が処理されるまで.

#include
#include
#include
#include
#include
using namespace std;
typedef struct{
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode; 
int a[24+1],b[24+1];
char c[24+1];
void Select(HuffmanTree &HT,int n,int &s1,int &s2){
	for(int i=1;i<=n;i++)
		if(HT[i].parent==0&&s1==0) {s1=i;break;} 
	for(int i=1;i<=n;i++)	
		if(HT[i].parent==0&&HT[i].weight

出力結果:
文字対応の符号表はファイルCodeに保存する.txt、結果は:

A:0001
B:10
C:1110
D:1111
E:110
F:01
G:0000
H:001

ハーフマンコード表によると、SourceFile.txt中の文字を対応する符号化ファイルResultFileに変換する.txt、結果は:

0001000100010001000110101010101010101010101010101010101010101010101010111011101110111011101110111011111111111111111111111111111111110110110110110110110110110110110110110110010101010101010101010101010101010101010101000000000000001001001001001001001001001001001