《哈夫曼编码译码器实验报告》由会员分享，可在线阅读，更多相关《哈夫曼编码译码器实验报告（27页珍藏版）》请在金锄头文库上搜索。
1、中北大学中北大学 数数 据据 结结 构构 课课 程程 设设 计计 说说 明明 书书学生姓名学生姓名:学学 号：号：10210109 学学 院院:软软件件学学院院专专 业业:软件开发与测试 题题 目目:哈夫曼编码/译码器指指导导教教 师师康珺2011 年 12 月 20 日- 1 - 目 录1 问题描述.12 需求分析.13 概要设计.131 抽象数据类型定义.132 总体框图以及功能描述.24 详细设计.241 数据类型的定义.242 主要模块的算法描述.35 测试分析.46 课程设计总结.6附录（源程序清单）.71 问题描述1.设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目
2、，直到选择退出为止。(1) 将权值数据存放在数据文件(文件名为 data.txt，位于当前目录中)；(2) 分别采用动态和静态存储结构; 初始化：键盘输入字符集大小 n、n 个字符和 n 个权值，建立哈夫曼树;(3) 编码：利用建好的哈夫曼树生成哈夫曼编码；输出编码；设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性。2 需求分析编写此软件是为了实现一个利用哈夫曼算法的编码和译码系统。比如，再利用电报进行通讯时，需要将文字转换成由二进制的字符组成的字符串。比如需传送的电文为“A B A C C D A”假设将 A,B,C,D
3、分别编码为00、01、10、11.则上述电文遍为 00010010101100，总长度为 14 位。但是在传送过程中，总希望长度能够尽可能的短，于是我们想采用长度不等的编码。但是这种编码必须遵循：任何一个字符的编码都不是另一个字符编码的前缀。对此软件的要求：能够正确的使得对于输入的字符进行编码以及译码，并且是的在译码过程中不会出错，同时能够将编码以及译码的结果正确的存入文件当中。- 1 - 3 概要设计31 抽象数据类型定义ADT BinaryTree数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：若 D 为空集，则称为空树。若 D 仅为一个数据元素，则 R 为空集
4、，否则 R=H，H 是如下的二元关系：（1）再 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱。（2）若 D-root0）。（3）对应于 D-root的划分，H-有唯一的一个划分 H1，H2，Hm（m0）。基本操作：InitTree(float weight; /结点权值int parent,lchild,rchild; /父结点，左、右孩子结点;（2）哈夫曼树类型struct hufmtree /哈弗曼树数据类型hufmtreenode *node; /结点数组（根据 n 的值动态分配）int n; /叶子结点数;（3)哈夫曼编码数据类型struct Codetype /
5、哈弗曼编码数据类型- 3 - char *bits; /编码流数组，int start;/编码实际在编码流数组里的开始位置42 主要模块的算法描述（1)主函数：void main()printf(“哈夫曼编码译码系统n“);tree=CreateHuffmanTreeFromSourceFile();/读取文件建立哈树tree=CreateHuffmanTreeByInput(); /手动输入建立哈夫曼树HuffmanCode(tree); /打印字符集的哈夫曼编码tree=Encoding(tree); /对文本文件编码Decoding(tree); /对代码文件译码（2）构造哈夫曼树huf
6、mtree* BuildHuffmanTree(hufmtree *tree)/构建叶子结点已初始化的哈夫曼树For(p=HT,i=1;i#include #include #define MAXVAL 10000.0struct hufmtreenode/哈弗曼树结点数据类型char data;double weight;/结点权值int parent,lchild,rchild;/父结点，左、右孩子结点;struct hufmtree/哈弗曼树数据类型hufmtreenode *node;/结点数组（根据 n 的值动态分配）int n;/叶子结点数;struct Codetype/哈弗曼编
7、码数据类型char *bits;/编码流数组，n 为为哈夫曼树中叶子结点的数目，编码的长度不可能超过 nint start;/编码实际在编码流数组里的开始位置- 9 - ;void SortHufmtree(hufmtree *tree)/将哈夫曼树 n 个叶子结点由大到小排序int i,j,k;hufmtreenode temp;if (tree=NULL)return;for (i=0;in;i+)k=i;for(j=i+1;jn;j+)if (tree-nodej.weighttree-nodek.weight)k=j;if (k!=i)temp=tree-nodei;tree-node
8、i=tree-nodek;tree-nodek=temp;Codetype* HuffmanCode(hufmtree *tree)/哈弗曼编码的生成int i,j,p,k;Codetype *code;if (tree=NULL)return NULL;code=(Codetype*)malloc(tree-n*sizeof(Codetype);for (i=0;in;i+)- 10 - printf(“%c “,tree-nodei.data);/打印字符信息codei.bits=(char*)malloc(tree-n*sizeof(char);codei.start=tree-n-1;
9、j=i;p=tree-nodei.parent;while(p!=-1)if (tree-nodep.lchild=j)codei.bitscodei.start=0;elsecodei.bitscodei.start=1;codei.start-;j=p;p=tree-nodep.parent;for (k=codei.start+1;kn;k+)/打印字符编码printf(“%c“,codei.bitsk);printf(“n“);return code;hufmtree* BuildHuffmanTree(hufmtree *tree)/构建叶子结点已初始化的哈夫曼树/tree 中所有叶
10、子结点已初始化int i,j,p1,p2,m;float small1,small2;m=2*(tree-n)-1;for (i=tree-n;inodei.parent=-1;- 11 - tree-nodei.lchild=-1;tree-nodei.rchild=-1;tree-nodei.weight=0.0;for (i=tree-n;inodej.parent=-1 p1=j;for (j=0;jnodej.parent=-1 p2=j;tree-nodep1.parent=tree-nodep2.parent=i;tree-nodei.weight=tree-nodep1.wei
11、ght+tree-nodep2.weight;tree-nodei.lchild=p1;- 12 - tree-nodei.rchild=p2;return tree;hufmtree* CreateHuffmanTreeFromSourceFile()/通过解析源文件建立哈夫曼树FILE *textfile,*datafile;char ch,sourcefilename100;int i,j=0,n=0;float count128; /用于统计字符在源文件中出现的次数，27 表示 26 个英文字母和 1 个空格字符hufmtree *tree;/打开一个源文件printf(“n 请输入源文件所在路径:n“);scanf(“%s“,sourcefilename);if (textfile=fopen(sourcefilename,“r“)=NULL)printf(“n 找不到文件%sn“,sourcefilename);return NUL
