admin 管理员组

文章数量: 1086019


2024年3月12日发(作者：shellexecutew)

数据结构课程设计

一、目的

《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在

掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应

用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世

界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

二、要求

通过这次设计，要求在数据结构析逻辑特性和物理表示，数据结构的选择的应

用、算法的设计及其实现等方面中深对课程基本内容的理解。同时，在程序设计方

法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

三、内容

2.哈夫曼编码/译码器

【问题描述】

设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择

退出为止。

【基本要求】

(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；

(2)编码：利用建好的哈夫曼树生成哈夫曼编码；

(3)输出编码；

(4)设字符集及频度如下表：

字符 空格 A B C D E F G H I J K L M

频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20

字符 N O P Q R S T U V W X Y Z

频度 57 63 15 1 48 51 80 23 8 18 1 16 1

【选做内容】

(1)译码功能；

(2)显示哈夫曼树；

(3)界面设计的优化。

哈夫曼编写编译码

一、问题描述

利用哈夫曼编码进行通信可以大大提高信道利用率，这要求在发送端

通过一个编码系统对待传输预先编码，在接收端将传来的数据进行译码。

对于双工通道，每端都需要一个完整的编/译码系统。试为这样的信息收发

站写一个哈夫曼码的编/译码系统。

二、概要设计

1．哈夫曼树的定义：

在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优

二叉树，也称为哈夫曼树。

2．哈夫曼树的构造：

假设有N个权值，则构造出的哈夫曼树有N个叶子结点。N个权值分别设

为W1,W2,……….Wn,则哈夫曼树的构造规则为：

（1） 将W1，W2，……….Wn看成有N棵树的森林；

（2） 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的

左，右子树，且新树的根结点为其左，右子树结点权值之和；

（3） 从森林中删除选取取的两面三刀棵树，并将新树加入森林；

（4） 重复（2）（3）步，直到森林中只剩一棵树为止，该树即为我们

所求得的哈夫曼树。

在构造哈夫曼树的过程中，每次由两棵权值最小的树生成一棵新树时，

新树的左子树和右子树可以任意安排，这样将会得到具有不同结构的多个

哈夫曼树，但字们都具有相同的带权路径长度。为了歙 得到的哈夫曼树

的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的

权要小于等于右女树根结点的权。

3．构造哈夫曼树的算法实现：

假设哈夫曼树采用双亲孩子表示法存储，并增加权值域，构造哈夫曼

树的叶子结点（树木的权）有N个，合并次数为N—1次，则森林中总共有

2N—1棵树，（包含合并后删除的）。 存储结构描述为：

const int n=maxn //maxn表示叶子数目

const int m=2*n-1 //m为森林中树的棵数


本文标签： 编码 结点 系统 权值 森林

版权声明：本文标题：哈夫曼编码-数据结构-C++程序 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1710253512a564557.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。