数据结构课程设计报告哈夫曼编码器

1、计算机工程学院 课程设计报告 课程名称：课程名称：数据结构课程设计 设计题目设计题目： 哈夫曼编码器 院院 系：系： 计算机工程学院 班班 级：级： 软件 1102 组组 别：别： 15 学生姓名学生姓名: : 吴超 学学 号号: 1101306229 起止日期起止日期: 2011 年 12 月 26 日 31 日 目目 录录 1、设计目的、设计目的.2 2、需求分析、需求分析.3 2.1 选题的意义及背景 2.2 基本要求 2.3运行环境及开发工具 3、概要设计、概要设计.4 3.1 设计思想 3.2 程序框图 3.3 方法及原理 3.4 主要数据结构 4、详细设计、详细设计.7 4.1 创

2、建哈夫曼树 4.2 编码 4.3 源程序 5、调试与操作说明、调试与操作说明.14 6、总结与体会、总结与体会.15 7、致谢、致谢.16 设计目的设计目的 1、 利用学过的数据结构知识设计一个简单的哈夫曼编/译 码器系统。 2 2、了解并掌握数据结构与算法的设计方法，具备初步的独立分 析和设计能力； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、 测试等基本方法和技能； 4、提高综合运用所学的理论知识和方法独立分析和解决问题的 能力； 5、训练用系统的观点和软件开发一般规范进行软件开发，培养 软件工作者所应具备的科学的工作方法和作风。 2 2 需求分析需求分析 2.1、选题的意义和

3、背景、选题的意义和背景 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信 息传输时间，降低传输成本。但是，这是要求在发送端通过一个编 码系统对待传数据预先编码，在接收端将传来的数据进行译码（复 原） 。对于双工信道（即可以双向传输信息的信道） ，每端都需要一 个完整的编/译码系统。 2.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

4、 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 2.3、运行环境及开发工具、运行环境及开发工具 本程序采用 visual c+6.0 编程实现。 3 概要设计概要设计 3.1 设计思想设计思想 本程序的主要功能是实现对用户输入的字符编码，然 后再把编码结果翻译成原字符。但在进行这些操作之前必 须做一项工作，就是创建 huffman 树。哈夫曼树又称最优 二叉树，是一种带权路径长度最短的二叉树。所谓树的 带权路径长度，就是树中所有的叶结点的权值乘上其到 根结点的

5、路径长度（若根结点为 0 层，叶结点到根结点 的路径长度为叶结点的层数）。树的带权路径长度记为 wpl=(w1*l1+w2*l2+w3*l3+.+wn*ln)，n 个权值 wi(i=1,2,.n)构成一棵有 n 个叶结点的二叉树，相应 的叶结点的路径长度为 li(i=1,2,.n)。可以证明哈夫 曼树的 wpl 是最小的。哈夫曼在上世纪五十年代初就提 出这种编码时，根据字符出现的概率来构造平均长度最 短的编码。它是一种变长的编码。在编码中，若各码字 长度严格按照码字所对应符号出现概率的大小的逆序排 列，则编码的平均长度是最小的 。 4 3.2 程序框图及流程图程序框图及流程图 哈夫曼编哈夫曼编

6、/译码器译码器 初始化初始化退出退出编码编码 3.33.3 方法及原理方法及原理 3.3.13.3.1创建创建 huffmanhuffman 树树 本文创建 huffman 树是在顺序链表的基础上进行的，建树原理如下： 1、根据给定的 n 个权值w1,w2,w3,wn，构造具有 n 棵二叉树的森 林 f=t1,t2,t3,tn，其中每棵二叉树 ti 只有一个带权值 wi 的根结点， 其左右子树均为空。 2、重复以下步骤，直到 f 中仅剩下一棵树为止： (1)在 f 中选取两棵根结点的权值最小的二叉树，作为左右子树构造一棵 新的二叉树。使新的二叉树的根结点的权值为其左右子树上根结点的权值之 和。

7、 (2)在 f 中删去这两棵二叉树，把新的二叉树加入 f。 最后得到的就是 huffman 树。 3.3.23.3.2 编码编码 编码操作需在建立好 huffman 树的基础上进行。二叉树的叶子结点标记 字符，由根结点沿着二叉树路径下行，左分支标记为 0，右分支标记为 1， 则每条从根结点到叶子结点的路径唯一表示了该叶结点的二进制编码。编码 的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点是其父结 点的左孩子，则编码为 0，如果是右孩子，则编码为 1，如此回溯，直到父 结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字 符的编码。如此操作，直到所有叶子结点都扫描一遍为

8、止，即编码结束。 3.43.4 主要的数据结构主要的数据结构 3.4.13.4.1 huffmanhuffman 结点结构结点结构 huffman 结点结构是本程序的基本结构，所有操作都在此上进行。其中 包括存储字符的元素 data，字符的权值 weight，以及左右孩子指针和父指 针。 typedef struct char ch;/结点值 int weight;/权值 int parent;/父结点指针 int lchild; /左孩子结点指针 int rchild;/右孩子结点指针 huffnode; 详细设计详细设计 4.14.1 创建创建 huffmanhuffman 树树 4.1.

9、14.1.1 功能描述功能描述 huffman 树是整个程序的核心部分，是编码译码操作的前提。哈 夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。根 据字符出现的概率来构造平均长度最短的编码。它是一种变长的 编码。在编码中，若各码字长度严格按照码字所对应符号出现概 率的大小的逆序排列，则编码的平均长度是最小的 。 4.1.24.1.2 算法原理算法原理 首先根据用户输入创建 n 棵子树的森林，然后对所有子树扫描， 找出权值最小的两个子树，把它们合并成一棵新的子树，同时把它 们的权值之和作为新树的权值。把这两棵子树删掉，再把新树加如 到森林中，然后再扫描出权值最小的两棵子树，接着进行同样的

10、操 作，直到只剩下一棵树即为 huffman 树。 4.1.34.1.3 算法流程算法流程 7 7 4.24.2 编码编码 4.2.14.2.1 功能描述功能描述 编码的功能就是把字符转换成二进制数来存储 4.2.24.2.2 算法原理算法原理 编码的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点 是其父结点的左孩子，则编码为 0，如果是右孩子，则编码为 1，如此回溯， 直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就 是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结 束。 4.2.34.2.3 算法流程算法流程 4.44.4 源程序源程序 #in

11、clude#include #include#include #include#include #include#include #include#include typedeftypedef structstruct /哈夫曼树的结构体哈夫曼树的结构体 charchar ch;ch; intint weight;weight; /权值权值 intint parent,lchild,rchild;parent,lchild,rchild; htnode,*hfmtree;htnode,*hfmtree; typedeftypedef charchar *hfmcode;*hfmcode; vo

12、idvoid select(hfmtreeselect(hfmtree i,j,x,y; for(j=1;j=a;+j)for(j=1;j=a;+j) if(htj.parent=0)if(htj.parent=0) x=j;x=j; break;break; for(i=j+1;i=a;+i)for(i=j+1;i=a;+i) if(hti.weighthtx.weightx=i; /选出最小的节点选出最小的节点 for(j=1;j=a;+j)for(j=1;j=a;+j) if(htj.parent=0y=j; break;break; for(i=j+1;i=a;+i)for(i=j+1

13、;i=a;+i) if(hti.weighthty.weight*p1=y; *p2=x;*p2=x; elseelse *p1=x;*p1=x; *p2=y;*p2=y; voidvoid hfmcoding(hfmtreehfmcoding(hfmtree i,start,c,f,m,w; intint p1,p2;p1,p2; charchar *cd,z;*cd,z; if(n=1)if(n=1) return;return; m=2*n-1;m=2*n-1; ht=(hfmtree)malloc(m+1)*sizeof(htnode);ht=(hfmtree)malloc(m+1)*

14、sizeof(htnode); for(i=1;i=n;+i)for(i=1;i=n;+i) /初始化初始化 n n 个叶子结点个叶子结点 printf(printf(请输入第请输入第%d%d 字符信息和权值：字符信息和权值：,i);,i); scanf(%c%d,scanf(%c%d, while(getchar()!=n)while(getchar()!=n) continue;continue; hti.ch=z;hti.ch=z; hti.weight=w;hti.weight=w; hti.parent=0;hti.parent=0; hti.lchild=0;hti.lchild=

15、0; hti.rchild=0;hti.rchild=0; for(;i=m;+i)for(;i=m;+i) /初始化其余的结点初始化其余的结点 hti.ch=0;hti.ch=0; hti.weight=0;hti.weight=0; hti.parent=0;hti.parent=0; hti.lchild=0;hti.lchild=0; hti.rchild=0;hti.rchild=0; for(i=n+1;i=m;+i)for(i=n+1;i=m;+i) /建立哈夫曼树建立哈夫曼树 select(ht,i-1,select(ht,i-1, htp1.parent=i;htp2.par

16、ent=i;htp1.parent=i;htp2.parent=i; hti.lchild=p1;hti.rchild=p2;hti.lchild=p1;hti.rchild=p2; hti.weight=htp1.weight+htp2.weight;hti.weight=htp1.weight+htp2.weight; hc=(hfmcode)malloc(n+1)*sizeof(charhc=(hfmcode)malloc(n+1)*sizeof(char *);*); cd=(charcd=(char *)malloc(n*sizeof(char);*)malloc(n*sizeof(

17、char); cdn-1=0;cdn-1=0; for(i=1;i=n;+i)for(i=1;i=n;+i) /给给 n n 个字符编码个字符编码 start=n-1;start=n-1; for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) if(htf.lchild=c)if(htf.lchild=c) cd-start=0;cd-start=0; elseelse cd-start=1;cd-start=1; hci=(char*)malloc(n-start)*siz

18、eof(char);hci=(char*)malloc(n-start)*sizeof(char); strcpy(hci,strcpy(hci, free(cd);free(cd); intint main()main() charchar code100,h100,hl100;code100,h100,hl100; intint n,i,j,k,l;n,i,j,k,l; ifstreamifstream input_file;input_file; /文件输入输出文件输入输出 ofstreamofstream output_file;output_file; charchar choice

19、,str100;choice,str100; hfmtreehfmtree ht;ht; hfmcodehfmcode hc;hc; coutn;coutn; coutcout 软件软件 11021102 班班 11013062291101306229 吴超吴超n;n; while(choice!=q*n; coutcout i.initi.init e.encodinge.encoding q.exitn;q.exitn; coutcoutchoice;cinchoice; if(choice=i|choice=i)if(choice=i|choice=i) /初始化哈夫曼初始化哈夫曼 树树

20、 coutcoutn;cinn; hfmcoding(ht,hc,n);hfmcoding(ht,hc,n); for(i=1;i=n;+i)for(i=1;i=n;+i) couthti.ch:hciendl;couthti.ch:hciendl; output_file.open(hfmtree.txt);output_file.open(hfmtree.txt); if(!output_file)if(!output_file) coutcantcoutcant oenoen file!endl;file!endl; returnreturn 1;1; for(i=1;i=n;i+)fo

21、r(i=1;i=n;i+) output_file(hti.chhci);output_file(hti.chhci); output_file.close();output_file.close(); coutcout哈夫曼树已经创建完毕，并且已经放入哈夫曼树已经创建完毕，并且已经放入 hfmtree.txthfmtree.txt 文文 件中件中!endl;!endl; elseelse if(choice=e|choice=e)if(choice=e|choice=e) /进行编码，进行编码， 并将字符放入并将字符放入 tobetran.txttobetran.txt，码值放入，码值放入

22、codefile.txtcodefile.txt 中中 printf(printf(请输入字符：请输入字符：);); gets(str);gets(str); output_file.open(tobetran.txt);output_file.open(tobetran.txt); if(!output_file)if(!output_file) coutcantcoutcant oenoen file!endl;file!endl; returnreturn 1;1; output_filestrendl;output_filestrendl; output_file.close();ou

23、tput_file.close(); output_file.open(codefile.txt);output_file.open(codefile.txt); if(!output_file)if(!output_file) coutcantcoutcant openopen file!endl;file!endl; returnreturn 1;1; for(i=0;istrlen(str);i+)for(i=0;istrlen(str);i+) for(j=0;j=n;+j)for(j=0;j=n;+j) if(htj.ch=stri)if(htj.ch=stri) output_fi

24、lehcj;output_filehcj; break;break; output_file.close();output_file.close(); coutn;coutn; coutcout编码完毕，并且已经存入编码完毕，并且已经存入 codefile.txtcodefile.txt 文件！文件！n;n; input_file.open(codefile.txt);input_file.open(codefile.txt); /从从 codefile.txtcodefile.txt 中读入编码，输出在终端中读入编码，输出在终端 if(!input_file)if(!input_file) coutcantcoutcant oenoen file!endl;file!code;input_filecode; coutc