哈夫曼数据结构实验报告

1、数据结构实验报告班级: 姓 名: 学 号: e-mail: 日 期:实验题目: p149 5.2 哈夫曼编/译码器 完成huffman 编码的译码过程。即输入一个码串，请翻译成相应的字符串。要求有编码过程和解码过程。(一) 需求分析1.本程序中，输入是字符串，包括+，-，*，/，（，），以及09，在输入的末尾需要加上#作为标记。2演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据，若正确则输出正确结果，若运算无解，则输入error。3程序执行的命令包括：（1）从文件读取字符和权值。（2）构建哈夫曼树。（3）输出构建的哈夫曼树。（4）选择1：对

2、输入的字符串编码。（5）选择2：对输入的数字译码。（6）选择0：结束。4测试数据输入1a bgh输出字母：a 编码：1010字母： 编码：110字母：b 编码：100100字母：g 编码：100101字母：h 编码：0000 (二) 概要设计(三) 详细设计#include#include#includetypedef structint weight; /节点权值int parent,lchild,rchild; /左右孩子的节点htnode,*huffmantree;typedef char * *huffmancode;void select (huffmantree ht,int n,

3、int *s1,int *s2) /挑选权值较小的两个节点int i,j,temp;for(i=1;i=n;i+)if(hti.parent=0)*s1=i;break;for(j=i+1;j=n;j+)if(htj.parent=0)*s2=j;break;for(i=1;ihti.weight)if(*s2!=i)*s1=i;for(j=1;jhtj.weight)if(*s1!=j)*s2=j;if(*s1*s2)temp=*s1;*s1=*s2;*s2=temp;/求哈夫曼书的算法void huffmancoding(huffmantree ht,huffmancode hc,int

4、*w,int n)int i,m;int start,c,f;int s1,s2;char *cd; if(n=1) /n小于2无需构造赫夫曼树return ;m=2*n-1; /一共有m=2n-1个节点ht=(huffmantree) malloc(m+1)*sizeof(htnode);/0 号单元没用；for(i=1;i=n;i+) /数组初始化hti.weight=wi-1;hti.parent=0;hti.lchild=0;hti.rchild=0;for(;i=m;+i)hti.weight=0;hti.parent=0;hti.lchild=0;hti.rchild=0;for(

5、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;/从叶子到根节点的逆向求每个字符的赫夫曼编码cd=(char*)malloc(n*sizeof(char); /分配球编码的工作空间cdn-1=0; /编码结束符for(i=1;i=n;i+) /逐个字符求赫夫曼编码start=n-1; /编码结束符位置for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) /

6、从叶子到根你想编码分配空间if(htf.lchild=c) cd-start=0;else cd-start=1;hci=(char*)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间strcpy(hci,&cdstart); /从cd复制编码（字符串）到hcvoid bianma(char p,char s,huffmancode hc)/编码int i,j;for (i=0;pi!=0;i+)for (j=0;j27;j+)if (pi=sj)printf(字母：%c编码：%sn,pi,hcj+1);break;printf(nn);return ;v

7、oid yima(char str,char s,huffmancode hc)/译码int j,t=0;char *p,*r,*m;p=str;m=str;for (;*p=0;)for (t=0,j=1;j=27;j+)r=hcj;while (*p=*r & *p!=0)p+,r+,t+;if (*r=0)printf(%cn,sj-1);break;p=m;t=0;p=m+t;m=p;printf(nn);return ;int main()/主函数int i=0,n=27,m;int *w;char s27,p100;huffmantree ht;huffmancode hc;hc=

8、(huffmancode)malloc(n*sizeof(huffmancode);w=(int *)malloc(n*sizeof(int);file *fp= fopen(a.txt,r);while(!feof(fp) fscanf(fp,%c %dn,&si,&wi);i+;huffmancoding(ht,hc,w,n);printf(输出编码为：n);for(i=0;in;i+)printf(字母为:%c 编码为:%s n,si,hci+1);while(1)printf(编码：1n译码：2n结束：0n);scanf(%d,&m);getchar();gets(p);switch(

9、m)case 1:bianma(p,s,hc);break;case 2:yima(p,s,hc);break;case 0:return 0;default :printf(errornn);break;fflush(stdin);getchar();return 0; (四) 程序使用说明及测试结果1程序使用说明（1）本程序的运行环境为vc6.0。（2）进入演示程序后即显示提示信息：2测试结果3、调试过程中遇到的问题是如何解决提以及对设计与实现的回顾讨论和分析；问题:本应输出数字，但是输出的是相应ascll码对应的字符；运算产生的两位数会被当成两个数参加下一次计算解决：原来的数字栈是char型，改成int 型问题：输出格式没有对齐解决：运用左对齐和长度限制4运行界面（五）、实验总