数据结构-哈夫曼编码器课程设计报告(共17页).doc
精选优质文档-倾情为你奉上课程设计报告一. 需求分析1、 一个完整的系统应具有以下功能：（1） I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2） E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3） D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4） P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件中。（5） T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。2、 利用哈夫曼编译码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。3、 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quito。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。4、 在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行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、主函数 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.parent=0) s2=k; break; for(k=k+1;k<=i;k+) if(HTk.parent=0) if(HTk.weight<HTs1.weight) if(HTk.weight<HTs2.weight) if(HTs2.weight<HTs1.weight) s1=s2; s2=k; else s2=k; else s1=s2; s2=k; else if(HTk.weight<HTs2.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;i<=n;i+,p+,w+,x+) p->weight=*w,p->parent=0,p->lchild=0,p->rchild=0,p->zifu=*x; for(;i<=m;i+,p+) p->weight=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) 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.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;i<n;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=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;i<n;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)/输出哈夫曼树 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;i<n;i+) printf("%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': 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: ;4、函数的调用关系图四、设计和调试分析1、利用哈夫曼编译码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。2、在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。3、在译码时，由于对程序的不是很了解，把两个循环搞错，最后导致无法正确译码。五、用户手册1、本程序的运行环境为Windows操作系统，执行文件为：Untitled1.exe2、进入演示程序后，按要求键入。3、之后即显示文本方式的用户界面：4、进入“初始化命令”后，即提示输入字符的大小，字符以及权值。5、进入“印代码文件”命令后，终端显示哈夫曼编码6、进入“印哈夫曼树”命令后，终端显示哈夫曼树。六、测试结果七、附录#include<stdio.h>#include<stdlib.h>struct 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;k+) if(HTk.parent=0) if(HTk.weight<HTs1.weight) if(HTk.weight<HTs2.weight) if(HTs2.weight<HTs1.weight) s1=s2; s2=k; else s2=k; else s1=s2; s2=k; else if(HTk.weight<HTs2.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;i<=n;i+,p+,w+,x+) p->weight=*w,p->parent=0,p->lchild=0,p->rchild=0,p->zifu=*x; for(;i<=m;i+,p+) p->weight=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) 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.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;i<n;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=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;i<n;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) 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;i<n;i+) printf("%c ",HCi.zifu); puts(HCi.code); 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': 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: ;专心-专注-专业
