数据结构课程设计实验报告(赫夫曼编码)

《数据结构课程设计实验报告(赫夫曼编码) 》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计哈夫曼编码学院：计算机科学与技术学院专业：计算机科学与技术学生：学号：指导教师：2013年4月16日目录一、课程设计的目的、功能及要求--------------1二、主要功能模块流程图----------------------2三、算法的基本思想--------------------------3四、系统测试--------------------------------6五、结论------------------------------------7六、源程序----------------------------------8第0页共21页一

2、、课程设计的目的、功能及要求目的：1.解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3..合运用所学的理论知识和方法独立分析和解决问题的能力；4.用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。功能：1首先读入待压缩源文件； 2然后建立并分析字母表，对每种字符的出现频度进行统计，以频度作为建立Huffman树的权值； 3频度表建好后，就可以根据算法建立Huffman树，对出现的每种字符进行Huffman编码； 4此时，再次读入源文件，逐字节编码

3、，将得到的编码流写入到磁盘文件，并且计算压缩率。要求：1、核心数据结构用到的结构体要采用动态内存分配和链表结构。 2、不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 3、对系统进行功能模块分析、画出总流程图和各模块流程图。 第18页共21页4、用户界面要求使用方便、简洁明了、美观大方、格式统一。 5．所有程序需调试通过。 二、主要功能模块流程图开始编码信息读取文档输入并存入文档计算压缩率统计频率生成哈夫曼编码编码文件译码信息结束译码文件第18页共21页三、算法的基本思想（1）构造Hufffman树的方法—H

4、ufffman算法构造Huffman树步骤：I.根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令起权值为wj。II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和III.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。IV.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。（2）Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”

5、；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。流程图：开始读入各字符的权重寻找权值最小的字符将两个字符分别作为左右孩子节点建立Huffman树计算从根节点到每个叶子节点的路径得出编码输出Huffman编码结束第18页共21页部分程序：（1）构造哈夫曼树voidHaffmanTree(HNodeTypeHuffNode[MAXNODE]){inti,j,m1,m2,x1,x2;for(i=0;i

6、r(i=0;i

7、HuffNode[num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[num+i].lchild=x1;HuffNode[num+i].rchild=x2;}}（2）哈夫曼编码第18页共21页LinkListBianma(LinkListl,Codecode[MAXNODE])//写编码文件{LinkListp,q,p1,p2;inti,j;p=l->next;q=newLNode;q->next=NULL;p1=newLNode;p2=q;while(p){for