《[计算机软件及应用]赫夫曼编译码器说明书》由会员分享，可在线阅读，更多相关《[计算机软件及应用]赫夫曼编译码器说明书（34页珍藏版）》请在金锄头文库上搜索。
1、目 录摘 要1前 言2正 文31.采用类c语言定义相关的数据类型32.各模块的伪码算法33.函数的调用关系图34.调试分析35.测试结果36.源程序（带注释）3总 结4参考文献5致 谢6附件 部分源程序代码7摘 要本课程设计主要研究如何解决对于给定的叶子数目及其权值构造最优二叉树的方法。通过对问题的分析，采用哈夫曼算法的设计思想。根据给定的权值构成二叉树森林，在森林中任意选取两棵根结点权值最小的树，将这两棵树合并为新的树，为保证新树仍为二叉树，需要增加一个新的结点作为根将这两个孩子的权值之和作为新树根的权值。对新的森林重复上述步骤直到森林中只剩一棵树为止。此树即为哈夫曼树。前 言字符以某种编码
2、形式存储在计算机中，目前世界上应用最广泛的两个字符是ASCII码（美国信息交换标准码）和EBCDIC码（扩充的二进制的十进制信息码）。当采纳这两个字符集时字符在计算机内是以固定长度的比特串表示的。但事实上，在具体应用中字符集中字符的使用频率常常差别很大，为了提高存储和传输的效率，可采用不等长的编码方式。若要设计不等长编码，则要求对字符集中任一字符的编码都不是另一个字符编码的前缀，称这种编码符合前缀特性，也称前缀编码，前缀编码可以一个字符一个字符地进行译码，不需要在字符之间添加分隔符。利用哈夫曼编码可以解决上述问题。正 文1. 采用类c语言定义相关的数据类型用C语言实现 :typedef str
3、uct HaffmanTreeNode char ch, code15; /ch 代表当前字符，code 代表这个字符的编码 int weight; /当前统计的字符的个数 int parent, lchild, rchild; HTNode, *HaTree; typedef struct HTNode arrMAX_NODE; int total; HTree; Max_Node 代表数的最大结点数 Max_Weight 代表权值的最大值typedef struct /结点类型int weight; /根节点的权值int flag; /标志位,为0即没有双亲,反之则是int parent;
4、 /双亲结点 char ch; /要编码的字符,即哈夫曼树叶子int lchild; /根节点的左孩子int rchild; /根节点的右孩子HafNode;typedef struct /哈夫曼编码int bitMAX_NODE; /二进制编码位,用于存放哈夫曼树编码int start; /编码的值在数组存放的起始位置int weight; /要编码的字符出现的频率,即权值char ch; /要编码的字符Code;typedef struct /编码操作类型char bitMAX_NODE; /将字符的编码结果存入bit数组中char ch; /要编码的字符int weight; /字符出现
5、的频率Coding;typedef struct /输入字符信息 HafNode arrMAX_NODE; /数组结点信息 int total; /统计输入字符的种类个数 HTree;2. 各模块的伪码算法算法描述 : int statistic_char(char *text, HTree *t) /* 统计字符出现的频率 */ int text_len = strlen(text); t-total = 0; for (i=0; itext_len; i+) for (j=0;jtotal ; j+) if (t-arrj.ch = texti) .统计已经出现的字符的个数 if (j=t
6、-total) .记录新出现的字符 return t-total; /打印出字符和它们的出现的次数 int create_htree(HTree *t) /* 建立一棵赫夫曼树,并对数据初始化 */ for (i=0; itotal total_node) /初始森林根节点数小于合并后新树的所有结点数 min1 = min2 = Max_Weight; for (i=0; itotal; i+) .找到当前权值最小的两个结点,并把它们建立成一棵新树,其中树根的权值为这两个的权值的和 t-total +; return 0; void coding(HTree *t, int head_i, c
7、har *code) /* 对哈夫曼树进行编码 */ if ( head_i = -1) /判断是否为空，为空返回 return;.从树的根节点出发，查找左子树输出0，查找右子树输出1，直到找到该树的叶子结点，按每个叶子结点在数组中的下标依次输出 void print_htree_ldr(HTree *t, int head_i, int deep, int* path) /* 中序打印树 */ .判断是否为空树，是的话返回；不是的话，按照先输出左孩子，然后输出双亲，再输出右孩子的方法依次打印各个字符和它的权值； void code_string(char *text, HTree *t) /
8、* 对字符进行编码 */ 变量初始化： for (条件判断) 依次输出每个字符的编码 3. 函数的调用关系图4. 调试分析a、 调试中遇到的问题及对问题的解决方法调试过程中遇到的问题及解决： 我在该程序中遇到的最大问题是如何以文件形式存储赫夫曼树，以及如何从文件读取赫夫曼树，读与存都要涉及到字符串转换成整数或整数转换成字符串的问题，最后终于成功了，可是很耗时，不知道是不是我的方法太不好了。b、算法的时间复杂度和空间复杂度算法的时空分析 在此程序中，存储字符串都用了指针，先动态申请空间，然后再存，这样就有效的利用了空间，不过为了实现任意长字符串的输入，最后转存到字符指针里，这样就浪费了一些空间。
9、 而对于哈夫曼树算法本身，由于这里只是一个静态的，所以当进行网络传输时，可能会显得效率比较低。 5. 测试结果6. 源程序（带注释）#include #include #include #define MAX_NODE 100 /代表哈夫曼树最大的结点数#define MAX_VALUE 10000 /代表权值的最大值typedef struct /结点类型int weight; /根节点的权值int flag; /标志位,为0即没有双亲,反之则是int parent; /双亲结点 char ch; /要编码的字符,即哈夫曼树叶子int lchild; /根节点的左孩子int rchild;
10、/根节点的右孩子HafNode;typedef struct /哈夫曼编码int bitMAX_NODE; /二进制编码位,用于存放哈夫曼树编码int start; /编码的值在数组存放的起始位置int weight; /要编码的字符出现的频率,即权值char ch; /要编码的字符Code;typedef struct /编码操作类型char bitMAX_NODE; /将字符的编码结果存入bit数组中char ch; /要编码的字符int weight; /字符出现的频率Coding;typedef struct /输入字符信息 HafNode arrMAX_NODE; /数组结点信息 i
11、nt total; /统计输入字符的种类个数 HTree; void statistic_char(char text, HTree *t) /* 统计字符出现的频率 */ FILE *fp,*fp1; char ch,ch120;printf(请输入一批字符数据: nA:键盘输入 B:文件输入n);scanf(%c,&ch);if(ch=A)scanf( %s,text);if(ch=B)printf(请输入文件名: n);scanf( %s,ch1); if(fp=fopen(ch1,r)=NULL) puts(cant open file!); exit(0); fscanf(fp,%s
12、,text); fclose(fp); fp1=fopen(zifu_quanzhi.txt,w+);int text_len = strlen(text); t=(HTree *)malloc(sizeof(HTree); t-total = 0; int i,j; for (i=0; itext_len; i+) for (j=0;jtotal; j+) if (t-arrj.ch = texti) /要统计字符在之前已出现 t-arrj.weight+; break; if (j=t-total) /记录新出现的字符 t-total+; t-arrj.ch=texti; t-arrj.weight=1
