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

课程设计报告一.需求分析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：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。2、利用哈夫曼编译码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。3、用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quito。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。4、在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。二、概要设计1、部分函数1）树与编码类型structHTNode2）选两个最小的树组成二叉树VoidSelect(HNode*HT,intI,int&s1,int&s2)3)初始化哈夫曼树voidInitialization(HTNode*&HT,HuffmanCode*&HC,int*&w,char*&x,int&n)4)输出哈夫曼树voidTreePrint(HTNode*HT,intn)5)输出哈夫曼编码voidCodePrint(HuffmanCode*HC,intn)2、主函数voidmain(){初始化;Switch(){}end;}3、模块之间的调用关系三、详细设计1、树的结构体的建立structHTNode{intweight,parent,lchild,rchild;charzifu;};structHuffmanCode{char*code;charzifu;intsize;};2、部分编码voidSelect(HTNode*HT,inti,int&s1,int&s2){intk;for(k=1;k=i;k++){if(HT[k].parent==0){s1=k;break;}}for(k=k+1;k=i;k++){if(HT[k].parent==0){s2=k;break;}}for(k=k+1;k=i;k++){if(HT[k].parent==0){if(HT[k].weightHT[s1].weight){if(HT[k].weightHT[s2].weight){if(HT[s2].weightHT[s1].weight){s1=s2;s2=k;}else{s2=k;}}else{s1=s2;s2=k;}}elseif(HT[k].weightHT[s2].weight){s2=k;}}}}voidHuffmanCoding(HTNode*&HT,HuffmanCode*&HC,char*x,int*w,intn){if(n=1)return;intm=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);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}char*CD;intk,j;CD=(char*)malloc(n*sizeof(char));for(i=1;i=n;i++){j=i;k=0;while(HT[j].parent!=0){if(HT[HT[j].parent].lchild==j)CD[k]='0';elseCD[k]='1';k++;j=HT[j].parent;}HC[i-1].code=(char*)malloc((k+1)*sizeof(char));HC[i-1].code[k]='\0';k--;intm=k;HC[i-1].size=m;for(intl=0;l=m;l++){HC[i-1].code[l]=CD[k];k--;}HC[i-1].zifu=HT[i].zifu;}free(CD);}intStrsize(char*d){inti=0;while(*d!='\0'){d++;i++;}returni;}char*Bianma(HuffmanCode*&HC,char*d){//哈夫曼树编码intn=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!=HC[k].zifu){k++;}j=0;while(HC[k].code[j]!='\0'){a[sum]=HC[k].code[j];j++;sum++;}d++;}a[sum]='\0';returna;}voidYima(HTNode*HT,char*&a,char*b,intn){intk=2*n-1,i=0;intm=k;while(*b!='\0'){if(*b=='0'){if(HT[HT[m].lchild].lchild==0){a[i]=HT[HT[m].lchild].zifu;i++;b++;m=k;}else{m=HT[m].lchild;b++;}}else{if(HT[HT[m].rchild].lchild==0){a[i]=HT[HT[m].rchild].zifu;i++;b++;m=k;}else{m=HT[m].rchild;b++;}}}a[i]='\0';}voidInitialization(HTNode*&HT,HuffmanCode*&HC,int*&w,char*&x,int&n){//初始化哈夫曼树printf(输入字符集大小n\n);scanf(%d,&n);fflush(stdin);w=(int*)malloc(n*sizeof(int));x=(char*)malloc(n*sizeof(char));for(inti=0;in;i++){printf(输入第%d个字符和权值:\n,i+1);scanf(%c%d,&x[i],&w[i]);fflush(stdin);}HC=(HuffmanCode*)malloc(n*sizeof(HuffmanCode));HuffmanCoding(HT,HC,x,w,n);}voidTreePrint(HTNode*HT,intn){//输出哈夫曼树for(inti=1;i(2*n);i++)printf(%c%d%d%d%d\n,HT[i].zifu,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);}voidCodePrint(HuffmanCode*HC,intn){//输出哈夫曼编码for(inti=0;in;i++){printf(%c,HC[i].zifu);puts(HC[i].code);}}3、主程序voidmain(){HTNode*HT;HuffmanCode*HC;intn,*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);gotostart;}case'e':{gets(a);fflush(stdin);y=Bianma(HC,a);puts(y);gotostart;}case'd':{gets(b);fflush(stdin);Yima(HT,a,b,n);puts(a);gotostart;}case'p':{CodePrint(HC,n);gotostart;}case't':{TreePrint(HT,n);gotostart;}case'q':gotoend;}end:;}4、函数的调用关系图四、设计和调试分析1、利用哈夫曼编译码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。2、在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。3、在译码时，由于对程序的不是很了解，把两个循环搞错，最后导致无法正确译码。五、用户手册1、本程序的运行环境为Windows操作系统，执行文件为：Untitled1.exe2、进入演示程序后，按要求键入。3、之后即显示文本方式的用户界面：4、进入“初始化命令”后，即提示输入字符的大小，字符以及权值。5、进入“印代码文件”命令后，终端显示哈夫曼编码6、进入“印哈夫曼树”命令后，终端显示哈夫曼树。六、测试结果七、附录#includestdio.h#includestdlib.hstructHTNode{intweight,parent,lchild,rchild;charzifu;};structHuffmanCode{char*code;charzifu;intsize;};voidSelect(HTNode*HT,inti,int&s1,int&s2){intk;for(k=1;k=i;k++){if(HT[k].parent==0){s1=k;break;}}for(k=k+1;k=i;k++){if(HT[k].parent==0){s2=k;break;}}for(k=k+1;k=i;k++){if(HT[k].parent==0){if(HT[k].weightHT[s1].weight){if(HT[k].weightHT[s2].weight){if(HT[s2].weightHT[s1].weight){s1=s2;s2=k;}else{s2=k;}}else{s1=s2;s2=k;}}elseif(HT[k].weightHT[s2].weight){s2=k;}}}}voidHuffmanCoding(HTNode*&HT,HuffmanCode*&HC,char*x,int*w,intn){if(n=1)return;intm=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