huffman(哈夫曼)树编码译码-课程设计报告.docx

《huffman(哈夫曼)树编码译码-课程设计报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计学院：信息科学与工程学院专业：计算机科学与技术班级：计卓1601学号：学生姓名：指导教师：年月日题目名称一、实验内容哈夫曼编码译码系统【问题描述】用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【基本要求】1）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。2）编码。利用已建好的哈夫曼

2、树对输入英文进行编码，编码结果存储在数组中。3）译码。利用已建好的哈夫曼树将数组中的代码进行译码，结果存入一个字符数组。4）输出编码。将编码结果显示在终端上，每行50个代码。5）输出哈夫曼树。将哈夫曼树以直观的方式（树或凹入表形式）显示出来。【实现提示】用户界面可以设计为“菜单”方式，再加上一个“退出”功能。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“退出”为止。参考教材P240-246【选做内容】将哈夫曼树保存到文件中，编码和译码的结果也分别存放在两个文本文件中。二、数据结构设计储存结构structHNodeType{//字符结构体

3、类型intweight;//权intparent;//双亲位置intlchild;//左孩子intrchild;//右孩子charinf;//字符};structHcodeType{intbit[MaxBit];//存储编码intstart;//起始位置};三、算法设计1、在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1。求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码实际上就是在已建立的

4、哈夫曼树中，从叶子结点开始，沿结点的父节点回退到根结点，每回退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位2、初始化为从键盘接受字符集大小n，以及n个字符和n个权值。3、建立哈夫曼编码为使用2中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树，即将HuffNode数组中的各个位置的各个域都填上相关的值，并将这个结构体数组存于文件nodedata.dat中。voidCreat_Haffmantre

5、e(int&n){//建树并输出树n++;HNodeType*HaffNode=newHNodeType[2*n-1];inti,j;intm1,m2,x1,x2;for(i=0;i<2*n-1;i++){//赋初值HaffNode[i].weight=0;HaffNode[i].parent=-1;HaffNode[i].lchild=-1;HaffNode[i].rchild=-1;HaffNode[i].inf='0';}for(i=0;i>HaffNode[i].inf;

6、cout<<"请输入该字符的权值:"<>HaffNode[i].weight;}HaffNode[n-1].inf='';//最后一个为空格HaffNode[n-1].weight=120;//空格权值for(i=0;i

7、(HaffNode[j].parent==-1&&HaffNode[j].weight