哈夫曼编码译码器

1、沈阳航空航天大学课程设计报告课程设计名称： 数据结构课程设计课程设计题目： 哈夫曼编码 / 译码器院（系）：计算机学院专业：计算机科学与技术班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告目录沈阳航空航天大学.I第1章 概要设计11.1题目的内容与要求11.2总体结构1第2章 算法分析22.1核心算法思想22.2算法结构定义2第3章 详细设计33.1功能流程3第4章 系统实现54.1错误分析54.2运行结果5参考文献8附录9I沈阳航空航天大学课程设计报告第 1章 概要设计1.1 题目的内容与要求内容：设计一个利用哈夫曼算法的编码和译码系统，可以接收从键盘输入的字符集大小、字符和权值信息

2、， 创建哈夫曼树生成哈夫曼编码并能对其进行解码。要求：1存储结构自定；2将生成的哈夫曼编码与等长编码进行比较，判断优劣；3给出动态演示过程（选作） 。1.2 总体结构本程序主要分为3 个模块（功能模块图见图1.1 ）：主模块，编码模块，译码模块。主模块：程序的主体部分，分别调用各个模块，实现各项功能。编码模块：对每个出现的字符进行编码。译码模块：将已有编码译成字符，使之可以直接被读出。哈夫曼编码 / 译码器主编译码码模模模块块块图 1.1 功能模块图1沈阳航空航天大学课程设计报告第2章算法分析2.1 核心算法思想哈夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有 n 棵只含有根结点的二叉树。

3、算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行 n 1 次合并，所以共产生 n 1 个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有 2n1 个结点，其中 n 个结点是初始森林的 n 个孤立结点。并且哈夫曼树中没有度数为 1 的分支结点。我们可以利用一个大小为 2n-1 的一维数组来存储哈夫曼树中的结点。哈夫曼编码是可变字长编码。编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到相等时，即取出其

4、对应的字符存入一个新串中。2.2 算法结构定义结构体存储表示typedef structint weight;int parent,lchild,rchild;Htnode,*Hfmtree;/动态分配数组存储哈夫曼树typedef char *Hfmcode;/动态分配数组存储哈弗曼编码表2沈阳航空航天大学课程设计报告第 3章 详细设计3.1 功能流程此流程图为构造哈夫曼树的过程，输入字符的次数为权值对每个结点赋值，构造哈夫曼树，如图3.1开始以读入字符次数对各结点赋初值并令i=2n-1Yi 为 0N找出根结点权值最小和次小树s1,s2两树合并成新树n+ii 减 1结束图 3.1 流程图3沈

5、阳航空航天大学课程设计报告此流程图（图 3.2）为对字符进行哈夫曼编码的过程，将字符转化为哈夫曼编码。开始第一个字符，i=1Ni<=nYN结点是否是根结点Y双亲结点的左结点是否等于该结点N将得到的编码存储Y记编码0记编码1i=i+1结束图 3.2 字符编码模块流程图4沈阳航空航天大学课程设计报告第 4章 系统实现4.1 错误分析在此程序调试过程中主要遇到以下几类问题：1、本程序运用了对文件进行操作，一定要注意在操作文件是文件的位置，我在做次程序是就是因为操作的文件位置错了导致程序无法正常运行。2、在函数内部有时需要多定义参数，注意参数的作用域， 而且注意传引用调用和传值调用的区别， 不能

6、不正确的修改实参的值， 否则会导致程序运行的错误。3、本程序用到的外部函数较多， 在调用时一定要注意传入的参数是否符合函数的定义，而且位置也不能错，这是引用函数要注意的一点。4、刚开始时清屏函数运用出错， 导致操作界面消失， 使用户无法操作， 因此，在使用一些函数是一定要注意。4.2 运行结果运行程序首先出现界面图，如图4.2 所示。图 4.1 界面图选择操作 1 后，输入相应的字符大小，字符和权值，生成哈夫曼树。系统会显示每个字符的哈夫曼编码，如图4.2 所示。5沈阳航空航天大学课程设计报告图 4.2 程序运行截图选择操作 2 后，输入字符串，系统会显示对字符串进行哈弗曼编码得到的哈弗曼编码

7、，显示以下界面（图 4.3 ）供用户选择。图 4.3 程序运行截图选择操作 3 后，系统会显示用哈夫曼编码翻译成的字符，显示以下界面（图4.4 ）供用户选择图 4.4 程序运行截图选择操作 4 后，退出系统，显示以下界面（图4.5 ）6沈阳航空航天大学课程设计报告图 4.5 程序运行截图7沈阳航空航天大学课程设计报告参考文献1 严蔚敏 . 数据结构 (C 语言版 ). 清华大学出版社， 20072 谭浩强 .C 语言程序设计教程 . 高等教育出版社， 20063 苏仕华 . 数据结构课程设计 . 机械工业出版社， 20078沈阳航空航天大学课程设计报告附录源程序如下：#include<i

8、ostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedef struct/赫夫曼树的结构体char ch;int weight;/ 权值int parent,lchild,rchild;Htnode,*Hfmtree;/动态分配数组存储赫夫曼树typedef char *Hfmcode;/动态分配数组存储赫夫曼编码表void Select(Hfmtree &HT,int a,int *s1,int *s2) /Se

9、lect 函数，选出 HT 树到 a 为止，权值最小且 parent为 0 的 2 个节点int i,j,x,y;for(j=1;j<=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTx.weight&&HTi.parent=0)x=i;/选出最小的节点9沈阳航空航天大学课程设计报告for(j=1;j<=a;+j) if(HTj.parent=0&&x!=j)y=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HT

10、y.weight&&HTi.parent=0&&x!=i)y=i;/选出次小的节点if(x>y)*s1=y;*s2=x;else*s1=x;*s2=y;void Hfmcoding(Hfmtree &HT,Hfmcode &HC,int n) /构建赫夫曼树HT，并求出 n10沈阳航空航天大学课程设计报告个字符的赫夫曼编码HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n<=1)return;m=2*n-1;HT=(Hfmtree)malloc(m+1)*sizeof(Htnode);for

11、(i=1;i<=n;+i)/初始化 n 个叶子结点printf(" 请输入第 %d 字符信息和权值： ",i);scanf("%c%d",&z,&w);while(getchar()!='n')continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i<=m;+i)/ 初始化其余的结点HTi.ch='0'11沈阳航空航天大学课程设计报告HTi.weight=0;HTi.parent=0;HTi.lchi

12、ld=0;HTi.rchild=0;for(i=n+1;i<=m;+i)/建立赫夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(Hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1='0'/- 从叶子到根逆向给出每个字符的哈夫曼编码-for(i=1;i<=n;+i)s

13、tart=n-1;/编码起始符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c)cd-start='0'12沈阳航空航天大学课程设计报告elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);/为地 i 个字符编码分配空间strcpy(HCi,&cdstart);free(cd);void main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_

14、file;/文件输入输出流ofstream output_file;char choice,str100;Hfmtree HT;Hfmcode HC;while(choice!='4')/ 当 choice 的值 4 时循环printf("n");13沈阳航空航天大学课程设计报告printf("*赫夫曼编码/译码器*n");printf("*1创建哈夫曼树*n");printf("*2编 码*n");printf("*3译 码*n");printf("*4退 出*n&q

15、uot;);printf("n");printf(" 请输入您要操作的步骤 ");cin>>choice;if(choice='1')/初始化赫夫曼树cout<<"请输入字符个数： "cin>>n;Hfmcoding(HT,HC,n);for(i=1;i<=n;+i)cout<<HTi.ch<<":"<<HCi<<endl;output_file.open("hfmTree.txt");if

16、(!output_file)cout<<"can't oen file!"<<endl;14沈阳航空航天大学课程设计报告for(i=1;i<=n;i+)output_file<<"("<<HTi.ch<<HCi<<")"output_file.close();printf(" 赫夫曼树已经创建完毕，并且已经放入 hfmTree.txt 文件中 !n");else if(choice='2')/进行编码，并将字符放入

17、A.txt ，码值放入 B.txt 中printf(" 请输入字符： ");gets(str);output_file.open("A.txt");if(!output_file)cout<<"can't oen file!"<<endl;output_file<<str<<endl;output_file.close();output_file.open("B.txt");if(!output_file)cout<<"can't

18、 oen file!"<<endl;for(i=0;i<strlen(str);i+)for(j=0;j<=n;+j)if(HTj.ch=stri)15沈阳航空航天大学课程设计报告output_file<<HCj;break;output_file.close();cout<<"n"printf(" 编码完毕，并且已经存入B.txt 文件！ n");input_file.open("B.txt");/ 从 B.txt 中读入编码，输出在终端if(!input_file)cout

19、<<"can't oen file!"<<endl;input_file>>code;cout<<"编码码值为： "<<code<<endl;input_file.close();else if(choice='3') /读入 B.txt 中的编码进行译码，将译出来的字符放入 Textfile.txt 中input_file.open("B.txt");if(!input_file)cout<<"can't o

20、en file!"<<endl;input_file>>h;input_file.close();output_file.open("Textfile.txt");if(!output_file)16沈阳航空航天大学课程设计报告cout<<"can't oen file!"<<endl;k=0;while(hk!='0')/先用编码中的前几个和字符的编码相比较，然后往后移for(i=1;i<=n;i+)l=k;for(j=0;j<strlen(HCi);j+,l

21、+)hlj=hl;hlj='0'if(strcmp(HCi,hl)=0)output_file<<HTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.open("Textfile.txt");if(!input_file)cout<<"can't oen file!"<<endl;input_file>>h;cout<<h<<endl;17沈阳航空航天大学课程设计报告input_file.close();printf(" 译码结束，字符已经存入