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

1、课程设计报告一. 需求分析1、一个完整的系统应具有以下功能：(1) I :初始化(Initialization )。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。(2) E：编码(Encoding )。利用已建好的哈夫曼树(如不在内存，则从文件hfmTree中读入),对文件 ToBeTran 中的正文进行编码,然后将结果存入文件 CodeFile 中。(3) D :译码(Decoding )。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件 TextFile 中。(4) P:印代码文件(Print )。将文件 Code

2、File以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件中。(5) T：印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。2、利用哈夫曼编译码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传 输成本。3、 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运 行 Quito 。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“ Q”为止。4、 在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫

3、曼树已经在内存 了，不必再读入。每次执行中不一定执行 I命令，因为文件hfmTree可能早已建好。二、概要设计1 、部分函数1 ) 树与编码类型struct HTNode2) 选两个最小的树组成二叉树Void Select(HNode *HT,int I,int &s1,int &s2)3) 初始化哈夫曼树void Initialization(HTNode *&HT,HuffmanCode *&HC,int *&w,char *&x,int &n)4) 输出哈夫曼树void TreePrint(HTNode *HT,int n)5) 输出哈夫曼编码void CodePrint(Huffman

4、Code *HC,int n)2、主函数void main()初始化 ;Switch() end;3、模块之间的调用关系三、详细设计1、树的结构体的建立struct HTNodeint weight,parent,lchild,rchild;char zifu;struct HuffmanCodechar *code;char zifu;int size;2、部分编码void Select(HTNode *HT,int i,int &s1,int &s2) int k;for(k=1;k=i;k+)if(HTk.parent=0) s1=k; break; for(k=k+1;k=i;k+)

5、if(HTk.parent=0) s2=k; break; for(k=k+1;k=i;k+) if(HTk.parent=0) if(HTk.weightHTs1.weight) if(HTk.weightHTs2.weight) if(HTs2.weightHTs1.weight) s1=s2; s2=k; else s2=k; else s1=s2; s2=k; else if(HTk.weightHTs2.weight) s2=k;void HuffmanCoding(HTNode *&HT,HuffmanCode *&HC,char *x,int *w,int n) if(n=1)r

6、eturn;int m=2*n-1,i,s1,s2;HTNode *p;HT=(HTNode *)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;iweight=*w,p-parent=0,p-lchild=0,p-rchild=0,p-zifu=*x;for(;iweight=0,p-parent=0,p-lchild=0,p-rchild=0,p-zifu=N;for(i=n+1;i=m;i+)Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.

7、weight=HTs1.weight+HTs2.weight;char *CD;int k,j;CD=(char *)malloc(n*sizeof(char);for(i=1;i=n;i+)j=i;k=0;while(HTj.parent!=0)if(HTHTj.parent.lchild=j)CDk=0;elseCDk=1;k+;j=HTj.parent;HCi-1.code=(char *)malloc(k+1)*sizeof(char);HCi-1.codek=0;k-;int m=k;HCi-1.size=m;for(int l=0;l=m;l+)HCi-1.codel=CDk; k

8、-;HCi-1.zifu=HTi.zifu;free(CD);int Strsize(char *d) int i=0; while(*d!=0)d+; i+; return i;char* Bianma(HuffmanCode *&HC,char *d) / 哈夫曼树编码int n=Strsize(d),i,k,j,sum=0; char *a;a=(char *)malloc(10*n)*sizeof(char); for(i=0;in;i+)k=0;while(*d!=HCk.zifu) k+;j=0; while(HCk.codej!=0) asum=HCk.codej; j+;sum

9、+; d+; asum=0; return a;void Yima(HTNode *HT,char *&a,char *b,int n)int k=2*n-1,i=0;int m=k; while(*b!=0)if(*b=0) if(HTHTm.lchild.lchild=0) ai=HTHTm.lchild.zifu;i+; b+; m=k;else m=HTm.lchild; b+;else if(HTHTm.rchild.lchild=0) ai=HTHTm.rchild.zifu;i+;b+;m=k;else m=HTm.rchild; b+; ai=0;void Initializa

10、tion(HTNode *&HT,HuffmanCode *&HC,int *&w,char *&x,int &n) / 初始化哈夫曼树printf( 输入字符集大小 nn);scanf(%d,&n);fflush(stdin);w=(int *)malloc(n*sizeof(int);x=(char *)malloc(n*sizeof(char);for(int i=0;in;i+)printf( 输入第 %d 个字符和权值 :n,i+1);scanf(%c %d,&xi,&wi); fflush(stdin);HC=(HuffmanCode *)malloc(n*sizeof(Huffm

11、anCode); HuffmanCoding(HT,HC,x,w,n);void TreePrint(HTNode *HT,int n)/ 输出哈夫曼树for(int i=1;i(2*n);i+)printf(%c %d %d %d %dn,HTi.zifu,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);void CodePrint(HuffmanCode *HC,int n)/ 输出哈夫曼编码for(int i=0;in;i+)printf(%c ,HCi.zifu);puts(HCi.code);3、主程序void main()HTNode *H

12、T;HuffmanCode *HC;int n,*w;char *x,*y,Z;char *a,*b;a=(char *)malloc(100*sizeof(char);b=(char *)malloc(100*sizeof(char);start:printf(”初始化i，编码e,译码d,印哈夫曼码 p,印哈夫曼树t，退出q。n); scanf(%c,&Z);fflush(stdin);switch(Z)case i:Initialization(HT,HC,w,x,n);goto start;case e:gets(a);fflush(stdin); y=Bianma(HC,a);puts

13、(y);goto start;case d:gets(b);fflush(stdin); Yima(HT,a,b,n);puts(a);goto start;case p:CodePrint(HC,n); goto start;case t:TreePrint(HT,n);goto start;case q:goto end; end:4、函数的调用关系图四、设计和调试分析1、禾U用哈夫曼编译码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传 输成本。2、 在程序的一次执行过程中，第一次执行I, D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hf

14、mTree可能早已建好。3、在译码时，由于对程序的不是很了解，把两个循环搞错，最后导致无法正确译码。五、用户手册1、 本程序的运行环境为Windows操作系统，执行文件为：Untitled1.exe2、进入演示程序后，按要求键入。3、之后即显示文本方式的用户界面：4、进入“初始化命令”后，即提示输入字符的大小，字符以及权值。5、进入“印代码文件”命令后，终端显示哈夫曼编码6、进入“印哈夫曼树”命令后，终端显示哈夫曼树。六、测试结果七、附录#in clude#in cludestruct HTNodeint weight,pare nt,lchild,rchild;char zifu;；stru

15、ct Huffma nCodechar *code;char zifu;int size;void Select(HTNode *HT,int i,int &s1,int &s2) int k;for(k=1;k=i;k+)if(HTk.pare nt=O) s1=k; break; for(k=k+1;k=i;k+)if(HTk.parent=0)s2=k;break; for(k=k+1;k=i;k+)if(HTk.parent=0)if(HTk.weightHTs1.weight) if(HTk.weightHTs2.weight) if(HTs2.weightHTs1.weight)s

16、1=s2;s2=k;elses2=k;elses1=s2;s2=k;else if(HTk.weightHTs2.weight)s2=k;void HuffmanCoding(HTNode *&HT,HuffmanCode *&HC,char *x,int *w,int n)if(n=1)return;int m=2*n-1,i,s1,s2;HTNode *p;HT=(HTNode *)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;iweight=*w,p-parent=0,p-lchild=0,p-rchild=0,p-zifu=*x; for(;iw

17、eight=0,p-parent=0,p-lchild=0,p-rchild=0,p-zifu=N; for(i=n+1;i=m;i+)Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;char *CD;int k,j;CD=(char *)malloc(n*sizeof(char);for(i=1;i=n;i+)j=i;k=0;while(HTj.parent!=0)if(HTHTj.parent.lchild=j)CD

18、k=0;elseCDk=1;k+;j=HTj.parent;HCi-1.code=(char *)malloc(k+1)*sizeof(char);HCi-1.codek=0;k-;int m=k;HCi-1.size=m;for(int l=0;l=m;l+)HCi-1.codel=CDk; k-;HCi-1.zifu=HTi.zifu; free(CD);int Strsize(char *d)int i=0;while(*d!=0)d+;i+;return i;char* Bianma(HuffmanCode *&HC,char *d)int n=Strsize(d),i,k,j,sum

19、=0;char *a;a=(char *)malloc(10*n)*sizeof(char);for(i=0;in;i+)k=0;while(*d!=HCk.zifu)k+;j=0;while(HCk.codej!=0)asum=HCk.codej;j+;sum+;d+;asum=0;return a;void Yima(HTNode *HT,char *&a,char *b,int n)int k=2*n-1,i=0;int m=k; while(*b!=0) if(*b=0) if(HTHTm.lchild.lchild=0) ai=HTHTm.lchild.zifu; i+; b+; m

20、=k;else m=HTm.lchild; b+;else if(HTHTm.rchild.lchild=0) ai=HTHTm.rchild.zifu;i+;b+;m=k;else m=HTm.rchild; b+; ai=0;void Initialization(HTNode *&HT,HuffmanCode *&HC,int *&w,char *&x,int &n) printf( 输入字符集大小 nn); scanf(%d,&n);fflush(stdin);w=(int *)malloc(n*sizeof(int);x=(char *)malloc(n*sizeof(char);for(int i=0;in;i+)printf( 输入第 %d 个字符和权值 :n,i+1);scanf(%c %d,&xi,&wi); fflush(stdin);HC=(HuffmanCode *)malloc(n*sizeof(HuffmanCode); HuffmanCoding(HT,HC,x,w,n);void TreePrint(HTNode *HT,int n)