实习报告6_哈夫曼编码

1、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.t

2、xt 中。二.概要设计：1.哈夫曼树的抽象数据类型定义： ADT haffman 数据对象：D=ai|ai为charnode型的结点，i=1，2，3，n，n>0 数据关系：R=<ai,ai.Lchild><ai,ai.Rchild>|ai是D上的元素 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=<ai,ai.next>|ai是D1上的元素

3、R2=<bi,bi.next>|bi是D2上的元素 ADT code3.程序分为四个部分： 1）读入字符集以及相应频度，建立哈夫曼树。 2）根据哈夫曼树得到每一个字符的哈夫曼编码。 3）读入要编码的字符串，根据哈夫曼树和编码集求出字符串的哈夫曼编码。 4）根据哈夫曼编码和哈夫曼树得到字符串。三.详细设计：/zy/ / 赫夫曼编/译码器/ 朱勇 13011090/#include <iostream>#include <fstream>#include <iomanip>#include <cstring>using namespace

4、 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( HuffmanT

5、ree & , HuffmanCode * , wElem * , int );/ 对文件 tobebin.txt 中的正文进行编码/ 将结果存入 codefile.txt void EnCoding( HuffmanCode * , const char* );/ 对文件 codefile.txt 里的代码进行译码/ 将结果存入 textfile.txtvoid DeCoding( HuffmanTree , HuffmanCode * , const char* , const int );/ 对 codefile.txt 里的代码进行编排,显示,打印void PrintCode(

6、 const char* , const char* );/ 选择两个最小的结点void SelectTwoNode( HuffmanTree , int , int& , int& ); int main() / 用文件流对象 hufInPut 打开外部文件/ humanWeight.txt 储存字符集大小 n ，以及 n 个字符和 n 个权值ifstream hufInPut( "humanWeight.txt" , ios:in );int hufNum = 0;hufInPut >> hufNum; / 读入字符集大小 n 到 hufNu

7、mwElem* 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( Hu

8、ffmanCode ) ); / 分配n个字符编码的头指针向量HuffmanCoding( hufT , hufC , hufW , hufNum ); / 编码中./ 用文件流对象 hufTreeOutPut 把赫夫曼树 HT , HC 输出到文件 hufTree.txt 中ofstream hufTreeOutPut( "hufTree.txt" , ios:out );hufTreeOutPut << "- HT - " << endl << setw( 9 ) << " weight &q

9、uot; << " parent " << " lchild " << " rchild " << endl;for( int tOut = 1 ; tOut <= 2*hufNum-1 ; tOut+ )hufTreeOutPut << setw( 6 ) << tOut << setw( 8 ) << hufT tOut .weight << setw( 8 ) << hufT tOut .parent &

10、lt;< setw( 8 ) << hufT tOut .lChild << setw( 8 ) << hufT tOut .rChild << endl;hufTreeOutPut << "- end HT - " << endl << endl << "- HC - " << endl;for( int cOut = 1 ; cOut <= hufNum ; cOut+ )hufTreeOutPut << "

11、" << hufC cOut .ch << " ->> " << hufC cOut .hufCh << endl;hufTreeOutPut << "- convert - ok - " << endl;hufTreeOutPut.close(); / 输出完毕，关闭文件delete hufW; / 释放内存EnCoding( hufC , "tobebin.txt" ); / 对正文编码DeCoding( hufT , hufC , &q

12、uot;codefile.txt" , hufNum ); / 译码PrintCode( "codefile.txt" , "codeprint.txt" ); / 打印代码cout << endl;return 0;/ w 存放 n 个字符的权值（ 均大与0 ）/ 构造赫夫曼树 HT , 并求出 n 个字符的赫夫曼编码 HC/void HuffmanCoding( HuffmanTree &HT , HuffmanCode* HC , wElem* w , int n ) if( n <= 1 ) return;in

13、t 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 = www.wt;p->parent = p->lChild = p->rChild = 0; / / 初始化for( ;

14、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; / 标记 pare

15、nt HT i .lChild = s1; / 标记左孩子HT i .rChild = s2; / 标记右孩子HT i .weight = HT s1 .weight + HT s2 .weight; / 新结点的权值 / 从叶子到根逆向求每个字符的赫夫曼编码/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 ,

16、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

17、 复制编码到 HCdelete cd; / 释放工作空间 / 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

18、 .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;elseif( sm1 > HT j .weight ) sm1 = HT j .weight;s1 = j;for( m = 1 ; m <= i ; m+ ) / 第二遍中第一个 parent 为 0 的结点if( HT m .parent != 0 ) continue;else sm2 = HT

19、m .weight;s2=m;if( s2 = s1 ) continue;else break;for( int k = m+1 ; k <= i ; k+ ) / 第二遍选第二个最小的if( HT k .parent != 0 ) continue;elseif( (HT k .weight < sm2) && ( k != s1 ) ) / 保证sm1 != sm2sm2 = HT k .weight;s2 = k; / end SelectTwoNode()/ 要编码的正文存放在 iFile 里/ 通过 fIn 的成员函数 get( inBuf ) 从 iF

20、ile 里读入每一个字符 ，其中 char inBuf 为字符缓冲区 _/ / 编码后的结果通过 fOut( oftream 的对象 ) 输出到文件 codefile.txt/void EnCoding( HuffmanCode* HC , const char* iFile )ifstream fIn( iFile , ios:in ); char inBuf = '#'ofstream fOut( "codefile.txt" , ios:out );int sub = 0; / HC 的下标while( fIn.get( inBuf ) ) / 读入字

21、符，直至文件结束符if( inBuf = ' ' ) sub = 1; / HC 1 .hufCh = ' 'fOut << HC sub .hufCh;else if( inBuf = 'n' )continue;else / 下标换算/ 因为 'A' 的 ASCII码为 65 ，又'A' 在 HC 里的下标为 2/ 即 HC 2 .hufCh = 'A'. 以下的字符雷同sub = inBuf - 63; fOut << HC sub .hufCh; /fIn.close

22、(); / 显式关闭文件fOut.close(); / / end EnCoding()/ / 本应该把赫夫曼编码放进 map( , ) 里的，但本程序没有这样做，显得效率有点低/ 在求子串相应的字符时，用的方法为在 HC 里进行逐字扫描比较 &/ 文件流的使用同 EeCoding() 里的一样/ 参数 n 为字符个数，p = 2*n-1 就为 HT 的结点数目. HTp就为 HT 的根./void DeCoding( HuffmanTree HT , HuffmanCode * HC , const char* iFile , const int n )ifstream fIn( i

23、File , ios:in );char inBuf = '1'ofstream fOut( "textfile.txt" , ios:out );char* cd = new char n ; / 储存字串的工作空间int start = 0; / 译码开始标记int p = 2 * n - 1; / 根下标int iHC = 1; / 用于扫描 HC 的循环变量while( fIn.get( inBuf ) ) / 循环读入 '0' 或 '1' 或 'n'if( inBuf = '0' )i

24、f( HT p .lChild != 0 ) / 不是叶子cd start+ = inBuf; / 压 inBuf 进 cd*p = HT p .lChild; / 进入左子树continue;else / 左叶子cd start = '0' / 子串结束符for( iHC = 1 ; iHC <= n ; iHC+ ) / 寻找与子串匹配的字符if( strcmp( HC iHC .hufCh , cd ) = 0 )fOut << HC iHC .ch;break; / 找到，跳出 forelse continue;start = 0; /cd start

25、+ = inBuf; / 为读下一子串做准备p = HT 2*n - 1 .lChild; / 注意，这时 p 已指向 root 的 left childelse if( inBuf = '1' )if( HT p .rChild != 0 ) / 不是叶子cd start+ = inBuf; / 压 inBuf 进 cd*p = HT p .rChild; / 进入左子树continue;else / 右叶子cd start = '0' / 子串结束符for( iHC = 1 ; iHC <= n ; iHC+ ) / 寻找与子串匹配的字符if( str

26、cmp( HC iHC .hufCh , cd ) = 0 )fOut << HC iHC .ch;break; / 找到，跳出 forelse continue;start = 0; /cd start+ = '1' / 为读下一子串做准备p = HT 2*n - 1 .rChild; / 注意，这时 p 已指向 root 的 right childelse if( inBuf = 'n' ) / 有必要的话，加了个回车符，哈哈continue;/*cd start = '0' / 子串结束符for( iHC = 1 ; iHC &

27、lt;= n ; iHC+ ) / 寻找与子串匹配的字符if( strcmp( HC iHC .hufCh , cd ) = 0 )fOut << HC iHC .ch;break; / 找到，跳出 forelse continue;fOut << endl;start = 0; / p = 2*n - 1; / p 指向 root*/ else/ 不要忘了最后一个字符。cd start = '0'for( iHC = 1 ; iHC <= n ; iHC+ ) / 寻找与子串匹配的字符if( strcmp( HC iHC .hufCh , cd ) = 0 )fOut << HC iHC .ch;break; / 找到，跳出 forelse continue;delete cd; / 释放工作空间fIn.close(); / 关闭文件fOut.close(); / 关闭文件 / end DeCoding()/ / 对 codefile.txt 里的代码进行编排/ 以每行 50 个代码的格式显示在终端上，同时存入文件 codeprint.txt 里/ void PrintCode( const char* iFile , con