《数据结构-哈夫曼编码器课程设计报告.doc》由会员分享，可在线阅读，更多相关《数据结构-哈夫曼编码器课程设计报告.doc（17页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告一. 需求分析1、 一个完整的系统应具有以下功能：（1） I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2） E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3） D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4） P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端
2、上，每行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(HuffmanCode *HC,int n)2、主
4、函数 void main() 初始化; Switch() end;3、模块之间的调用关系 三、详细设计1、树的结构体的建立 struct HTNode int weight,parent,lchild,rchild; char zifu;struct HuffmanCode char *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+) if(HTk
5、.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)return
6、; 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=s
7、2; 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) CDk=0; else CDk=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
8、;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=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
9、.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=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 *&
