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

计算机工程学院课程设计报告课程名称：课程名称：数据结构课程设计设计题目设计题目： 哈夫曼编码器 院院 系：系： 计算机工程学院 班班 级：级： 软件 1102 组组 别：别： 15 学生姓名学生姓名: : 吴超 学学 号号: 1101306229 起止日期起止日期: 2011 年 12 月 26 日 31 日 目目 录录 1、设计目的、设计目的.22、需求分析、需求分析.32.1 选题的意义及背景2.2 基本要求 2.3运行环境及开发工具3、概要设计、概要设计.43.1 设计思想3.2 程序框图 3.3 方法及原理3.4 主要数据结构4、详细设计、详细设计.74.1 创建哈夫曼树 4.2 编码4.3 源程序5、调试与操作说明、调试与操作说明.146、总结与体会、总结与体会.157、致谢、致谢.16 设计目的设计目的1、 利用学过的数据结构知识设计一个简单的哈夫曼编/译码器系统。2 2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2 2需求分析需求分析2.1、选题的意义和背景、选题的意义和背景利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这是要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原） 。对于双工信道（即可以双向传输信息的信道） ，每端都需要一个完整的编/译码系统。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 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 12.3、运行环境及开发工具、运行环境及开发工具本程序采用 Visual C+6.0 编程实现。 3概要设计概要设计3.1 设计思想设计思想本程序的主要功能是实现对用户输入的字符编码，然后再把编码结果翻译成原字符。但在进行这些操作之前必须做一项工作，就是创建 Huffman 树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为 0 层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N 个权值Wi(i=1,2,.n)构成一棵有 N 个叶结点的二叉树，相应的叶结点的路径长度为 Li(i=1,2,.n)。可以证明哈夫曼树的 WPL 是最小的。哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的 。 43.2 程序框图及流程图程序框图及流程图哈夫曼编哈夫曼编/译码器译码器初始化初始化退出退出编码编码 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 中选取两棵根结点的权值最小的二叉树，作为左右子树构造一棵新的二叉树。使新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 (2)在 F 中删去这两棵二叉树，把新的二叉树加入 F。最后得到的就是 Huffman 树。3.3.23.3.2 编码编码 编码操作需在建立好 Huffman 树的基础上进行。二叉树的叶子结点标记字符，由根结点沿着二叉树路径下行，左分支标记为 0，右分支标记为 1，则每条从根结点到叶子结点的路径唯一表示了该叶结点的二进制编码。编码的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点是其父结点的左孩子，则编码为 0，如果是右孩子，则编码为 1，如此回溯，直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。 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.14.1.1 功能描述功能描述 Huffman 树是整个程序的核心部分，是编码译码操作的前提。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的 。4.1.24.1.2 算法原理算法原理首先根据用户输入创建 n 棵子树的森林，然后对所有子树扫描，找出权值最小的两个子树，把它们合并成一棵新的子树，同时把它们的权值之和作为新树的权值。把这两棵子树删掉，再把新树加如到森林中，然后再扫描出权值最小的两棵子树，接着进行同样的操作，直到只剩下一棵树即为 Huffman 树。 4.1.34.1.3 算法流程算法流程 7 74.24.2 编码编码 4.2.14.2.1 功能描述功能描述 编码的功能就是把字符转换成二进制数来存储 4.2.24.2.2 算法原理算法原理编码的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点是其父结点的左孩子，则编码为 0，如果是右孩子，则编码为 1，如此回溯，直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。 4.2.34.2.3 算法流程算法流程 4.44.4 源程序源程序#include#include#include#include#include#include#include#include#include#includetypedeftypedef structstruct /哈夫曼树的结构体哈夫曼树的结构体charchar ch;ch;intint weight;weight; /权值权值intint parent,lchild,rchild;parent,lchild,rchild;htnode,*hfmtree;htnode,*hfmtree;typedeftypedef charchar *hfmcode;*hfmcode;voidvoid Select(hfmtreeSelect(hfmtree &HT,int&HT,int a,inta,int *p1,int*p1,int *p2)*p2) /Select/Select函数，选出函数，选出 HTHT 树到树到 a a 为止，权值最小且为止，权值最小且 parentparent 为为 0 0 的的 2 2 个节点个节点 intint i,j,x,y;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.weight&HTi.parent=0)if(HTi.weightHTx.weight&HTi.parent=0)x=i;x=i; /选出最小的节点选出最小的节点 for(j=1;j=a;+j)for(j=1;j=a;+j) if(HTj.parent=0&x!=j)if(HTj.parent=0&x!=j) y=j;y=j;break;break; for(i=j+1;i=a;+i)for(i=j+1;i=a;+i) if(HTi.weightHTy.weight&HTi.parent=0&x!=i)if(HTi.weighty)if(xy)*p1=y;*p1=y;*p2=x;*p2=x; elseelse *p1=x;*p1=x;*p2=y;*p2=y; voidvoid hfmcoding(hfmtreehfmcoding(hfmtree &HT,hfmcode&HT,hfmcode &HC,int&HC,int n)n) /构建哈夫构建哈夫曼树曼树 HTHT，并求出，并求出 n n 个字符的哈夫曼编码个字符的哈夫曼编码 HCHC intint i,start,c,f,m,w;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)*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,&z,&w);scanf(%c%d,&z,&w);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=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,&p1,&p2);Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=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(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)*sizeof(char);HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);strcpy(HCi,&cdstart); 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,str100;choice,str100;hfmtreehfmtree HT;HT;hfmcodehfmcode HC;HC;coutn;coutn;coutcout 软件软件 11021102 班班 11013062291101306229 吴超吴超n;n;while(choice!=Q&choice!=q)while(choice!=Q&choice!=q) /当当choicechoice 的值不为的值不为 q q 且不为且不为 Q Q 时循环时循环 coutcout *哈夫曼编码器哈夫曼编码器*n;*n;coutcout I.InitI.Init E.EncodingE.Encoding Q.Exitn;Q.Exitn;coutcoutchoice;cinchoice;if(choice=I|choice=i)if(choice=I|choice=i) /初始化哈夫曼初始化哈夫曼树树 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+)for(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，码值放入，码值放入 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();output_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_fileHCj;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;coutcout编码码值为：编码码值为：codeendl;codeendl;input_file.close();input_file.close(); elseelse /如果选了选项之外的就让用户重新选择如果选了选项之外的就让用户重新选择 coutcout您没有输入正确的步骤，请重新输入！您没有输入正确的步骤，请重新输入！endl;endl; coutendl;coutendl; returnreturn 0;0; 1414调试与操作说明调试与操作说明在运行程序时，需先输入需要编码的字符串，然后根据输入的字符的权重创建 Huffman 树，接着再进行编码操作，最后再把所得的编，各步操作之间存在先后关系，因此在运行程序时必须注意所选择的操作的先后顺序。 15总结与体会总结与体会在当今的信息化时代，先进的技术成为了科技的主流。哈夫曼是一种应用广泛且非常有效的数据压缩技术。这次课程设计我做的是哈夫曼编码和译码器。由于自身对数据结构的掌握有限，我只能做哈夫曼树的建立，编码和译码这部分内容。但是通过这次课程设计，我看到了自身的不足，让我有机会进一步学习了数据结构的知识。平时的学习中，我们不能单单地只学习理论知识，而应当把理论知识与实践结合起来。不然如果只有理论知识，而不能把理论运用到实际中，那也没多大用。总之，这次课程设计让我受益匪浅！ 致谢致谢感谢所有在这次课程设计中给我提出建议和提供指导的老感谢所有在这次课程设计中给我提出建议和提供指导的老师们，感谢帮助我解决很多问题的同学们。师们，感谢帮助我解决很多问题的同学们。 16指导教师评语指导教师评语： 指导教师签名： 年 月 日项项 目目权重权重成绩成绩1、设计过程中出勤、学习态度等方面0.22、课程设计（实践周）质量与答辩0.5成成绩绩评评定定3、设计报告书写及图纸规范程度0.3 总 成 绩