.. ..
1.初始化：从文件humanWeight.txt（ 程序运行时，由用户输入 ）读入字符集大小n，以
及n个字符和n个权值，建立哈夫曼树，将它存于文件hufTree.txt中。
2.编码：利用已建好的哈夫曼树（如不在存，则从文件hufTree.txt中读入）对 文件
tobebin.txt字符集中的每一个进行编码，将结果放在codefile.txt 中。
3.译码：利用已建好的哈夫曼树将 codefile.txt 中的代码进行译码，结果保存在
textfile.txt 中。
4.印代码文件。将文件 codefile.txt 以紧凑的格式显示在终端上，每行50个
代码。同时将结果保存在 codeprint.txt 中。
二.概要设计：
1.哈夫曼树的抽象数据类型定义：
ADT haffman
{ 数据对象：D={ai|ai为charnode型的结点，i=1，2，3，……n，n>0} 数据关系：R={
} ADT haffman
2.编码集结构体的抽象数据类型的定义：
ADT code
{ 数据对象：D1={ai| ai是charlink型的结点，i=1，2，……n，n>0}
D2={bi|bi是codelink型的结点，i=1，2，……n，n>0} 数据关系： R1={
R2={
} ADT code
3.程序分为四个部分：
1）读入字符集以及相应频度，建立哈夫曼树。 2）根据哈夫曼树得到每一个字符的哈夫曼编码。
3）读入要编码的字符串，根据哈夫曼树和编码集求出字符串的哈夫曼编码。 4）根据哈夫曼编码和哈夫曼树得到字符串。
三.详细设计：
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////zy //
// 赫夫曼编/译码器 // 朱勇 13011090 //
////////////////////////////////////////////////////////////////////////////////
///////////////////
#include
using namespace std;
... . .
.. ..
/////////////////////////////////////////////////////////// // 赫夫曼树和赫夫曼编码的存储表示 typedef struct { unsigned int weight; unsigned int parent , lChild , rChild;
} HTNode , *HuffmanTree; // 动态分配数组存储赫夫曼树
typedef struct { char ch; char* hufCh;
} HuffmanCode; // 动态分配数组存储赫夫曼编码表
/////////////////////////////////////////////////////////// // 权值字符结点类型 typedef struct { char ch; int wt;
} wElem; // 动态分配数组存储读入字符与权值
/////////////////////////////////////////////////////////// // 赫夫曼编码函数
void HuffmanCoding( HuffmanTree & , HuffmanCode * , wElem * , int );
/////////////////////////////////////////////////////////// // 对文件 tobebin.txt 中的正文进行编码 // 将结果存入 codefile.txt
void EnCoding( HuffmanCode * , const char* );
/////////////////////////////////////////////////////////// // 对文件 codefile.txt 里的代码进行译码 // 将结果存入 textfile.txt
void DeCoding( HuffmanTree , HuffmanCode * , const char* , const int );
/////////////////////////////////////////////////////////// // 对 codefile.txt 里的代码进行编排,显示,打印 void PrintCode( const char* , const char* );
/////////////////////////////////////////////////////////// // 选择两个最小的结点
void SelectTwoNode( HuffmanTree , int , int& , int& );
int main() { //
... . .
.. ..
// 用文件流对象 hufInPut 打开外部文件
// humanWeight.txt 储存字符集大小 n ，以及 n 个字符和 n 个权值 ifstream hufInPut( \int hufNum = 0;
hufInPut >> hufNum; // 读入字符集大小 n 到 hufNum
wElem* hufW = new wElem[ hufNum ]; // 分配 n 个字符和 n 个权值的储存空间 for( int ii = 0 ; ii < hufNum ; ii++ ) {
//
// 循环读入字符及其对应的权值
hufInPut >> hufW[ ii ].ch >> hufW[ ii ].wt; }
hufInPut.close(); // 关闭 humanWeight.txt 文件
HuffmanTree hufT; // 空树
HuffmanCode* hufC = ( HuffmanCode* ) malloc ( ( hufNum + 1 ) * sizeof( HuffmanCode ) ); // 分配n个字符编码的头指针向量 HuffmanCoding( hufT , hufC , hufW , hufNum ); // 编码中...
//
// 用文件流对象 hufTreeOutPut 把赫夫曼树 HT , HC 输出到文件 hufTree.txt 中 ofstream hufTreeOutPut( \
hufTreeOutPut << \setw( 9 )
<< \<< endl;
for( int tOut = 1 ; tOut <= 2*hufNum-1 ; tOut++ ) {
hufTreeOutPut << setw( 6 ) << tOut << setw( 8 ) << hufT[ tOut ].weight << setw( 8 ) << hufT[ tOut ].parent << setw( 8 ) << hufT[ tOut ].lChild << setw( 8 ) << hufT[ tOut ].rChild << endl; }
hufTreeOutPut << \ << \for( int cOut = 1 ; cOut <= hufNum ; cOut++ ) {
hufTreeOutPut << \hufC[ cOut ].hufCh << endl; }
hufTreeOutPut << \hufTreeOutPut.close(); // 输出完毕，关闭文件 delete [] hufW; // 释放存
EnCoding( hufC , \// 对正文编码
... . .
.. ..
DeCoding( hufT , hufC , \// 译码 PrintCode( \// 打印代码 cout << endl; return 0; }
////////////////////////////////////////////////////////////////////////////////
////////////////// //
// w 存放 n 个字符的权值（ 均大与0 ）
// 构造赫夫曼树 HT , 并求出 n 个字符的赫夫曼编码 HC //
void HuffmanCoding( HuffmanTree &HT , HuffmanCode* HC , wElem* w , int n ) { if( n <= 1 ) return; int m = 2 * n - 1; // 赫夫曼树的结点数目 HT = ( HuffmanTree ) malloc ( ( m + 1 ) * sizeof( HTNode ) ); //0 号单元未用 HuffmanTree p = HT; p++; // p 指向 HT 的第 1 号单元 int i=0 , ww=0; // ww 为 wElem* w 的下标 for( i = 1 ; i <= n ; i++ , p++ , ww++ ) { p->weight = w[ww].wt; p->parent = p->lChild = p->rChild = 0; // } // 初始化 for( ; i <= m ; ++i , ++p ) // { p->weight = p->parent = p->lChild = p->rChild = 0; } // // 建赫夫曼树 // 在 HT[ 1 .. i-1 ]选择parent 为 0 且 weight 最小的两个结点，其序号分别为
s1 和 s2 // int s1=0 , s2=0; for( i = n + 1 ; i <= m ; ++i ) { SelectTwoNode( HT , i-1 , s1 , s2 ); HT[ s1 ].parent = i; // 标记 parent HT[ s2 ].parent = i; // 标记 parent HT[ i ].lChild = s1; // 标记左孩子 HT[ i ].rChild = s2; // 标记右孩子 HT[ i ].weight = HT[ s1 ].weight + HT[ s2 ].weight; // 新结点的权值 } // // 从叶子到根逆向求每个字符的赫夫曼编码
... . .
.. ..
} // end HuffmanCoding()
////////////////////////////////////////////////////////////////////////////////
////////////////// //
// 选择两个最小的结点 , 序号分别放在 s1 和 s2 中 //
void SelectTwoNode( HuffmanTree HT , int i , int& s1 , int& s2 ) { unsigned int sm1 , sm2; // 用于权值的比较 s1 = 1; // 从序号为 1 的权值开始 s2 = 1; int m=0; // 最小权值的序号临时变量 for( m = 1 ; m <= i ; m++ ) // 第一遍中第一个 parent 为 0 的结点 { if( HT[ m ].parent != 0 ) continue; else { sm1 = HT[ m ].weight; s1=m; break; } } for( int j = m+1 ; j <= i ; j++ ) // 第一遍选第一个最小的 { if( HT[ j ].parent != 0 ) continue; else {
... . .
//
char* cd = new char[ n ]; // 分配求编码的工作空间 cd[ n - 1 ] = '\\0'; // 编码结束符 int c = 0; int f = 0;
for( i = 1 ; i <= n ; ++i ) // 逐个字符求赫夫曼编码 {
int start = n - 1; // 编码结束符位置
for( c = i , f = HT[ i ].parent ; f != 0 ; c = f , f = HT[ f ].parent ) // 从叶子到根逆向求编码 { if( HT[ f ].lChild == c ) { cd[ --start ] = '0'; } else { cd[ --start ] = '1'; } }
HC[ i ].ch = w[ i-1 ].ch ; // 复制字符
HC[ i ].hufCh = ( char* ) malloc ( ( n - start ) * sizeof( char ) ); // 为第 i 个字符编码分配空间
strcpy( HC[ i ].hufCh , &cd[ start ] ); // 从 cd 复制编码到 HC }
delete [] cd; // 释放工作空间
实习报告6_哈夫曼编码
