数据结构-哈夫曼编码器课程设计报告(共17页).doc

《数据结构-哈夫曼编码器课程设计报告(共17页).doc》由会员分享，可在线阅读，更多相关《数据结构-哈夫曼编码器课程设计报告(共17页).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）。将文件CodeF

2、ile以紧凑格式显示在终端上，每行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

4、*HC,int n)2、主函数 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

5、=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) 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)

6、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(;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;

7、 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) 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

8、; 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=0; char *a; a=(char *)malloc(10*n)*sizeof(char); for(i=0;in;i+) k=0; while(*d!=HCk.zifu) k+; j

9、=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=k; else m=HTm.lchild; b+; else if(HTHTm.rchild.lchild=0) ai=HTHTm.rchild.zifu;

10、 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,&w

11、i); fflush(stdin); HC=(HuffmanCode *)malloc(n*sizeof(HuffmanCode); 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+) p

12、rintf(%c ,HCi.zifu); puts(HCi.code); 3、主程序 void main() HTNode *HT; 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: Initiali

13、zation(HT,HC,w,x,n); goto start; case e: gets(a); fflush(stdin); y=Bianma(HC,a); puts(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、利用哈夫曼编译码进行

14、通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。2、在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。3、在译码时，由于对程序的不是很了解，把两个循环搞错，最后导致无法正确译码。五、用户手册1、本程序的运行环境为Windows操作系统，执行文件为：Untitled1.exe2、进入演示程序后，按要求键入。3、之后即显示文本方式的用户界面：4、进入“初始化命令”后，即提示输入字符的大小，字符以及权值。5、进入“印代码文件”命令后，终端显示哈夫曼编码6、进入“印哈夫曼树”命令后，终端显

15、示哈夫曼树。六、测试结果七、附录#include#includestruct HTNode int weight,parent,lchild,rchild; char zifu;struct HuffmanCode char *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.parent=0) s1=k; break; for(k=k+1;k=i;k+) if(HTk.parent=0) s2=k; break; for(k=k+1;k=i

16、;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; int m=2*n-1,i,s1,s2; HTNode *p; HT=

17、(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.weight=HTs1.weight+HTs2.weight

18、; 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;l=m;l+) HCi-1.codel=CDk; k-; HCi-1.z

19、ifu=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+; d+; asu

20、m=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

21、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(HuffmanCode)

22、; 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); void main() HTNode *HT; HuffmanCode *HC; in

23、t 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(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: ;专心-专注-专业