(哈夫曼编码译码器)(课程设计报告)

《(哈夫曼编码译码器)(课程设计报告)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程设计哈夫曼编码_译码器一、目的利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。本课程设计的目的就是为这样的信息收发站编写一个哈夫曼编/译码系统。二、需求分析1．系统结构与功能需求系统结构上，哈夫曼编码是以二叉树的形式进行存储，故要使用到数据结构中的树。功能上，本系统要求构造完整的哈夫曼编/译码系统，要求系统要对哈夫曼提供支持，能对特定的字符进行哈夫曼编码，并支

2、持将字符串进行哈夫曼转码和对二进制编码串进行解码。2、系统交互层需求根据系统设计要求，本系统要与用户进行良好的交互，并能将相关的编码解码操作进行文件读取与储存，进行信息记录。三、概要设计1．数据结构设计建立合理的数据结构，存储待编码字符集，该结构易于找出最小值，易于构造haffman树，相关功能模块存储于“haffman.h”文件中，其中minHeap类及相关结构与函数使用了小顶堆的结构提供了查询最小值的方式，其中binTree类及相关结构域函数使用了二叉树提供了哈夫曼结构的存储。2．功能模块设计核心功能主要分为，编码、解码和打印haffman树，相关功能模块存储于“codi

3、ng_decode.h”文件下，其中的coding函数提供编码功能、decode函数提供解码功能、其中的print函数提供了打印haffman数。15中南民族大学计算机科学学院软件工程专业《数据结构》课程设计3．用户交互设计本系统使用控制台菜单以及文件的读写方式与用户进行交互，文件均存储于运行程序目录下，相关输入输出代码在“main.cpp”中。四、详细设计1．类与数据结构设计定义编码字符的结构体code，用来存储待编码字符及其权值。classcode//存值{public:charkeymark;//编码字符intkey;//权值};定义树的节点element作为树的基本节

4、点。classelement//点{friendclassbinTree;//element可以访问binTree->友元关系public:element():leftchild(NULL),rightchild(NULL),parent(NULL),mark(0){};codedata;//保存本结点的使用频度和其它数据。intmark;//用于扫描判断,在coding_decode里面,作用:标记变量,mark等于0说明当前//结点的左子树的叶子还没有扫描完，继续扫描element*leftchild,*rightchild,*parent;};定义二叉树结构，用于构造哈

5、弗曼树以及小顶堆时使用。classbinTree//单个元素的二叉树数{public:binTree(){root=newelement;}binTree(binTree&bt1,binTree&bt2)//{15中南民族大学计算机科学学院软件工程专业《数据结构》课程设计root=newelement;root->leftchild=bt1.root;root->rightchild=bt2.root;root->data.key=bt1.root->data.key+bt2.root->data.key;bt1.root->parent=bt2.root->parent=r

6、oot;}element*root;};haffman树是基于二叉树结构的，构造haffman树时要求可以快速的找出最小值，故使用小顶堆结构，小顶堆又称为排序二叉树，使用堆结构对数据进行存储，每次扫描找出最小值，进行haffman树的构造。小顶堆的具体功能如下：能够构造堆结构；minHeap(){heap=NULL;};minHeap(intmaxsize);将新的元素插入到堆中；intinsert(binTreex);输出并删除堆顶最小元素；intremoveMin(binTree&x);判断堆是否为空；intisEmpty(){returncurrentsize==0;}

7、;判断堆是否已满；intisFull(){returncurrentsize==maxheapsize;};自顶向下进行调整为最小堆；voidfilterDown(intstart,intend);自底向上进行调整为最小堆。voidfilterUp(intend);haffman树的具体功能如下：通过小顶堆得到的点来构造haffman树，主要依赖binTree类。2．功能模块设计编码功能，huffcode*coding(binTree*tree,intL)，建立好haffman树后，对haffman树进