哈夫曼数据结构实验报告

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

2、：对输入的数字译码。（ 6）选择 0：结束。4测试数据输入1A BGH输出字母： A 编码： 1010 字母： 编码： 110 字母： B 编码： 100100 字母： G 编码： 100101 字母： H 编码： 0000（二）概要设计(三)详细设计#in clude#in clude#in cludetypedef structint weight;节点权值in t pare nt,lchild,rchild;/ 左右孩子的节点ht no de,*huffma ntree;typedef char * *huffma ncode;void select (huffma ntree ht,i

3、 nt n,i nt *s1, int *s2)挑选权值较小的两个节点int i,j,temp;for(i=1;i=n ;i+)if(hti.pare nt=O)*s1=i;break;for(j=i+1;j=n ;j+)if(htj.pare nt=O)*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 huffma ncodi ng(huffma ntree ht,huffm

4、a ncode hc,i nt *w,i nt 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=(huffma ntree) malloc(m+1)*sizeof(ht no de);/0号单元没用；for(i=1;i=n;i+)/ 数组初始化hti .weight=wi-1;hti.pare nt=O;hti.lchild=0;hti .rchild=0;for(;i=m;+i)hti .weight=O; hti.pare nt=O; hti.lc

5、hild=O;hti .rchild=0;for(i=n+1;i=m;i+)select(ht,i-1, &s1, &s2);hts1.pare nt=i;hts2.pare nt=i;hti .lchild=s1;h ti .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.pare nt;f!=O;c=f,f=htf.pare nt) if(ht

6、f.lchild=c) cd-start=0;else cd-start=1;hci=(char*)malloc( (n-start)*sizeof(char); strcpy(hci, &cdstart);/分配球编码的工作空间/编码结束符/逐个字符求赫夫曼编码/编码结束符位置/从叶子到根你想编码分配空间为第i个字符编码分配空间 /从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

7、,pi,hcj+1);break;prin tf(nn); return ;void yima(char str,char s,huffmancode hc) 译码 int j,t=O;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)prin tf(%c n,sj-1);break;p=m;t=0;p=m+t;m=p;prin tf(nn);return ; int main()/ 主函数int i=0,n=27,m;int *w;ch

8、ar s27,p100;huffma ntree ht;huffma ncode hc;hc=(huffma ncode)malloc (n *sizeof(huffma ncode);w=(i nt *)malloc( n*sizeof( in t);FILE *fp= fope n(a.txt,r);while(!feof(fp)fscan f(fp,%c %dn, &si, &wi);i+;huffma ncodi ng(ht,hc,w ,n);printf(输出编码为：n);for(i=0;i n;i+)printf(字母为:%c编码为:%sn,si,hci+1);while(1)pr

9、intf(编码：1n 译码：2n 结束：0n);scan f(%d, &m);getchar();gets(p);switch(m)case 1:bia nm a(p,s,hc);break;case 2:yima(p,s,hc);break;case 0:return 0;default :prin tf(errornn);break;fflush(stdi n);getchar();return 0;(四)程序使用说明及测试结果1程序使用说明 本程序的运行环境为 VC6.0。进入演示程序后即显示提示信息:C:Use r sJ e no voDe skto构 四次宴验buq1015,exer

10、F 卜 M; F MP 卜 xt Mz 卜 - 母乐岳岳岳隹乐-运世世任底宦.母母母母母圧limrrprrprfpldmrfrrnM7T:rrfFrJT l-n 打-in l-u l-u l-u l-u 十* -fl iy .nH .fl 扁启常扁扃n暫拥屈尿扁白細H例昴扁用扃启扇tltllS t00161 0000111101110011110110 tainL1L11101111000klllBlllOl 90100Q11Llld30011 1111016 tlllHCl1 111 01111 fl 103111 11118111112 测试结果 C ：U &e I5l e no voDe

11、 skto结梅带四次夹验D 亡 tuqf 015.exe% 当寺51: 7_r Ik 7r ? 翦编编编 A B G H1818110 L00100 丄迪皿0删编玛：译码：2站束：Enona 111811181 eiQ011naf:lJ舵电肌top炷屯做尿结秤第四次浜捡kDetug1CH 5.exeK -卜 匚亠 匸“匚亠 -L-I? 1? *卜 T *一 m.-TTHT _.m m m jt -帀帀帀帀弔弔币l-H l-u I-卄帀帀3、调试过程中遇到的问题是如何解决提以及对设计与实现的回顾讨论和分析；问题:本应输出数字，但是输出的是相应 ASCLL码对应的字符；运算产生的两位数会被当成 两

12、个数参加下一次计算解决：原来的数字栈是 char型，改成int型问题：输出格式没有对齐解决：运用左对齐和长度限制4.运行界面r 5EenovoD eskto 作业澈据結珂荣四次实號Deb u g1015.exeuwiwiafiffi舲陶gMffitaaaiwfwtffiigMiffitfisffiMi除 词si33iiSJsli!aGE.GE.G9E.GsE.G8.slgi.lGu3编码为:丄丄e 编怛为：1010 编码 ： 100100 编码为油0虹0 编码为：丄的迪 编谒为汕丄0 諭怛为：iilllft 编码知Mi砒 编码対油阪 编码为询1A0编怛为=11110110 編码.为汀血:LL 编码为=111111 编码为=B11 编利