课程设计--哈夫曼编码和译码

《课程设计--哈夫曼编码和译码》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计说明书哈夫曼编码和译码课程设计说明书课程设计：哈夫曼编码和译码课程名称：数据结构班级：姓名：学号：教师：信息工程学院计算机系18数据结构课程设计说明书哈夫曼编码和译码目录一、设计任务书3问题描述3基本要求3小组成员及分工3二、设计题目3三、设计目的4四、算法思想分析4建立哈夫曼树4构造哈夫曼树的过程4一个完整的编/译码系统应具有的功能5选择parent为0且权值最小的两个根结点的算法5统计字符串中字符的种类以及各类字符的个数5构造哈夫曼树5哈夫曼编码6哈夫曼编码算法6建立正文的编码文件6代码文件的译码6五、算法描述与实现7主要

2、算法流程图7主要类型定义10功能描述10程序源代码10六、程序运行结果1118数据结构课程设计说明书哈夫曼编码和译码七、结论1118数据结构课程设计说明书哈夫曼编码和译码一、设计任务书问题描述利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。基本要求一个完整的系统应具有以下功能：1.初始化及

3、文本的频率统计。从终端读入字符集大小n，以及n个字符和n个权值，完成文本的频率统计。建立哈夫曼树，并将它存于文件中；2.编码。利用已建好的哈夫曼树，从文件中读入，对正文进行编码。然后将结果存入文件“CodeFile-姓名”中；3.译码。利用已建好的哈夫曼树将输入的代码进行译码，将文件“CodeFile-姓名”中的代码进行译码，结果存入文件“Decoding-姓名”中；4.打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式显示在屏幕上。小组成员及分工二、设计题目哈夫曼编码和译码三、设计目的利用哈夫曼编码进行信息通信可以大大提高信道利用率，

4、缩短信息传输时间，降低传输成本。18数据结构课程设计说明书哈夫曼编码和译码四、算法思想分析树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表。树在计算机领域中也得到广泛应用，如在编译程序中，可以用树来表示源程序的语法结构。又如在数据库系统中，树形结构也是信息的重要组织之一。哈夫曼树能将符号按概率从大到小的顺序排列，能对对概率最小的两个符号求其概率之和，同时给两个符号分别赋予码元，能从树根到端点经过的树枝即

5、为码字，并输出码字。树中从根到每个叶子都有一条路径，对路径上的各分支约定:指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码。建立哈夫曼树在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每个结点的路径长度之和。带权二叉树是指每个结点都带有一个权值的二叉树。构造哈夫曼树的过程1.将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,T

6、n}，其中每棵二叉树只有一个根结点；2.在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；3.在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；4.重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。易证明，路径长度最短的二叉树一定是一棵完全二叉树。由哈夫曼树算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树;每合并一次，

7、森林中就减少一棵树，产生一个新结点.显然要进行n-1次合并,所以,共产生n-1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n-1分支结点，其中n个叶结点是初始森林的n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们可用一个大小为2n-1的一维数组来存储哈夫曼树中的结点。一个完整的编/译码系统应具有的功能1.建立哈夫曼编码树(Create)。从键盘输入字符集中的所有字符及其对应的18数据结构课程设计说明书哈夫曼编码和译码频率值，建立哈夫曼编码树。1.输出编码表(Table)。利用已建好的哈夫曼树

8、，列出字符集中的所有字符及其对应的哈夫曼编码。2.编码(Coding)。利用已建好的哈夫曼树，对从键盘输入的正文串进行编码，并在屏幕上显示结果。3.译码(Decoding)。利用已建好的哈夫曼树，对从键盘输入的0、1代码