1、 数据结构课程设计 哈夫曼编码 学 院：计算机科学与技术学院 专 业：计算机科学与技术 学 生： 学 号： 指导教师： 2013 年 4 月 16 日 第 0 页 共 21 页 目录目录 一、一、课程设计的目的、功能及要求课程设计的目的、功能及要求-1 1 二、二、主要功能模块流程图主要功能模块流程图-2 2 三、三、算法的基本思想算法的基本思想-3 3 四、四、系统测试系统测试-6 6 五、五、结论结论-7 7 六、六、源程序源程序-8 8 第 1 页 共 21 页 一、课程设计的目的、功能及要求 目的： 1. 解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2. 件开发过
2、程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3. .合运用所学的理论知识和方法独立分析和解决问题的能力； 4. 用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应 具备的科学的工作方法和作风。 功能： 1 首先读入待压缩源文件； 2 然后建立并分析字母表，对每种字符的出现频度进行统计，以频度作为 建立 Huffman 树的权值； 3 频度表建好后，就可以根据算法建立 Huffman 树，对出现的每种字符进 行 Huffman 编码； 4 此时，再次读入源文件，逐字节编码，将得到的编码流写入到磁盘文件， 并且计算压缩率。 要求： 1、核心数据结构用到的结构体要采用动态内
3、存分配和链表结构。 2 、不同的功能使用不同的函数实现（模块化） ，对每个函数的功能和调用 接口要注释清楚。对程序其它部分也进行必要的注释。 3 、对系统进行功能模块分析、画出总流程图和各模块流程图。 4 、用户界面要求使用方便、简洁明了、美观大方、格式统一。 5 所有程序需调试通过。 二、主要功能模块流程图 第 2 页 共 21 页 三、三、算法的基本思想 （1）构造 Hufffman 树的方法Hufffman 算法 构造 Huffman 树步骤： I. 根据给定的 n 个权值w1,w2,wn，构造 n 棵只有根结点的二叉树， 令起权值为 wj。 II. 在森林中选取两棵根结点权值最小的树作
4、左右子树，构造一棵新的二叉 树，置新二叉树根结点权值为其左右子树根结点权值之和 III. 在森林中删除这两棵树，同时将新得到的二叉树加入森林中。 开始 编码信息 输入并存入文档 统计频率 生成哈夫曼 编码文件 译码信息 译码文件 结束 读取文档 计算压缩率 第 3 页 共 21 页 IV. 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。 （2）Huffman 编码：数据通信用的二进制编码 思想：根据字符出现频率编码，使电文总长最短 编码：根据字符出现频率构造 Huffman 树，然后将树中结点引向其左孩子的 分支标“0” ，引向其右孩子的分支标“1” ；每个字符的编码即为从根到每个 叶子
5、的路径上得到的 0、1 序列。 流程图： 部分程序： （1） 构造哈夫曼树 void HaffmanTree(HNodeType HuffNodeMAXNODE) int i,j,m1,m2,x1,x2; for(i=0;inext=NULL; p1=new LNode; 第 5 页 共 21 页 p2=q; while(p) for(i=0;idata=codei.data) j=0; while(codei.bitj!=0) p1-data=codei.bitj; j+; p2-next=p1; p2=p1; p1=new LNode; p=p-next ; p2-next=NULL; return q; SeqStack Init() SeqStack s; s=new StackNode; s-top=-1; return s; v
