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

课程设计说明书课程设计 ： 哈夫曼编码和译码课程名称 ： 数据结构班级：姓名： 学号：教师： 信息工程学院计算机系目录一、设计任务书3问题描述3基本要求3小组成员及分工3二、设计题目3三、设计目的4四、算法思想分析4建立哈夫曼树4构造哈夫曼树的过程4一个完整的编/译码系统应具有的功能5选择parent为0且权值最小的两个根结点的算法5统计字符串中字符的种类以及各类字符的个数5构造哈夫曼树5哈夫曼编码6哈夫曼编码算法6建立正文的编码文件6代码文件的译码6五、算法描述与实现7主要算法流程图7主要类型定义10功能描述10程序源代码10六、程序运行结果11七、结论11一、设计任务书问题描述 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。基本要求一个完整的系统应具有以下功能：初始化及文本的频率统计。从终端读入字符集大小n，以及n个字符和n个权值，完成文本的频率统计。建立哈夫曼树，并将它存于文件中；编码。利用已建好的哈夫曼树，从文件中读入，对正文进行编码。然后将结果存入文件“CodeFile-姓名”中；译码。利用已建好的哈夫曼树将输入的代码进行译码，将文件“CodeFile-姓名”中的代码进行译码，结果存入文件“Decoding-姓名”中；打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式显示在屏幕上。小组成员及分工二、设计题目哈夫曼编码和译码三、设计目的利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。四、算法思想分析树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表。树在计算机领域中也得到广泛应用，如在编译程序中，可以用树来表示源程序的语法结构。又如在数据库系统中，树形结构也是信息的重要组织之一。哈夫曼树能将符号按概率从大到小的顺序排列，能对对概率最小的两个符号求其概率之和，同时给两个符号分别赋予码元，能从树根到端点经过的树枝即为码字，并输出码字。树中从根到每个叶子都有一条路径，对路径上的各分支约定:指向左子树的分支表示 “0”码，指向右子树的分支表示 “1”码，取每条路径上的 “0”或“1”的序列作为和各个叶子对应的字符的编码。建立哈夫曼树 在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径 ，路径上的分支数目称做路径长度。树的路径长度是从树根到每个结点的路径长度之和。带权二叉树是指每个结点都带有一个权值的二叉树。构造哈夫曼树的过程将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。易证明，路径长度最短的二叉树一定是一棵完全二叉树。由哈夫曼树算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树;每合并一次，森林中就减少一棵树，产生一个新结点.显然要进行n-1次合并,所以,共产生n-1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n-1分支结点，其中n个叶结点是初始森林的n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们可用一个大小为2n-1的一维数组来存储哈夫曼树中的结点。 一个完整的编/译码系统应具有的功能 建立哈夫曼编码树(Create)。从键盘输入字符集中的所有字符及其对应的频率值，建立哈夫曼编码树。 输出编码表(Table)。利用已建好的哈夫曼树，列出字符集中的所有字符及其对应的哈夫曼编码。 编码(Coding)。利用已建好的哈夫曼树，对从键盘输入的正文串进行编码，并在屏幕上显示结果。 译码(Decoding)。利用已建好的哈夫曼树，对从键盘输入的0、1代码串进行译码，并在屏幕上显示结果要实现哈夫曼树算法，首先要实现在parent为0且权值最小的两个根结点的选择算法；另外，还要有一个实现统计输入电文字符串中各种字符出现的频率以及字符的种类的算法。选择parent为0且权值最小的两个根结点的算法在众多权中选择