《实习报告6_哈夫曼编码》由会员分享，可在线阅读，更多相关《实习报告6_哈夫曼编码（12页珍藏版）》请在金锄头文库上搜索。
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，n0 数据关系：R=|ai是D上的元素 ADT haffman 2.编码集结构体的抽象数据类型的定义： ADT code 数据对象：D1=ai| ai是charlink型的结点，i=1，2，n，n0 D2=bi|bi是codelink型的结点，i=1，2，n，n0 数据关系： R1=|ai是D1上的元素 R2=|bi是D2上的元素 ADT code3.程序分为四个部分： 1）读入字符集以及相应频度，建立哈夫曼树。 2）根据哈夫曼树得到每一个字
3、符的哈夫曼编码。 3）读入要编码的字符串，根据哈夫曼树和编码集求出字符串的哈夫曼编码。 4）根据哈夫曼编码和哈夫曼树得到字符串。三.详细设计：/zy/ / 赫夫曼编/译码器/ 朱勇 13011090/#include #include #include #include using namespace std;/ 赫夫曼树和赫夫曼编码的存储表示typedef struct unsigned int weight;unsigned int parent , lChild , rChild; HTNode , *HuffmanTree; / 动态分配数组存储赫夫曼树typedef struct c
4、har 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.tx
5、t 里的代码进行译码/ 将结果存入 textfile.txtvoid 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 储存字符集
6、大小 n ，以及 n 个字符和 n 个权值ifstream hufInPut( humanWeight.txt , ios:in );int hufNum = 0;hufInPut hufNum; / 读入字符集大小 n 到 hufNumwElem* hufW = new wElem hufNum ; / 分配 n 个字符和 n 个权值的储存空间for( int ii = 0 ; ii hufW ii .ch hufW ii .wt;hufInPut.close(); / 关闭 humanWeight.txt 文件HuffmanTree hufT; / 空树HuffmanCode* hufC
7、= ( HuffmanCode* ) malloc ( ( hufNum + 1 ) * sizeof( HuffmanCode ) ); / 分配n个字符编码的头指针向量HuffmanCoding( hufT , hufC , hufW , hufNum ); / 编码中./ 用文件流对象 hufTreeOutPut 把赫夫曼树 HT , HC 输出到文件 hufTree.txt 中ofstream hufTreeOutPut( hufTree.txt , ios:out );hufTreeOutPut - HT - endl setw( 9 ) weight parent lchild r
8、child 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 - end HT - endl endl - HC - endl;for( int cOut = 1 ; cOut = hufNum ; cOut+ )hufTre
9、eOutPut hufC cOut .ch hufC cOut .hufCh endl;hufTreeOutPut - convert - ok - endl;hufTreeOutPut.close(); / 输出完毕，关闭文件delete hufW; / 释放内存EnCoding( hufC , tobebin.txt ); / 对正文编码DeCoding( hufT , hufC , codefile.txt , hufNum ); / 译码PrintCode( codefile.txt , codeprint.txt ); / 打印代码cout endl;return 0;/ w 存放
10、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 weight = www.wt;p-parent = p-lChild = p-
