哈弗曼数据结构专题实验报告

..数据结构与程序设计专题实验报告______信息45班______信息45班______信息45班实验指导李峰实验地点：西一楼一层计算机中心机房实验结束日期：12月5日实验任务：对于给定的源文档SourceDoc.txt,1>统计其中所有字符的频度〔某字符的频度等于其出现的总次数除以总字符数,字符包括字母〔区分大小写、标点符号及格式控制符〔空格、回车等。2>按频度统计结果构建哈夫曼编码表。3>基于哈夫曼编码表进行编码,生成对应的二进制码流,并输出到文件Encode.dat,完成信源的编码过程。4>根据生成的哈夫曼编码表,对二进制码流文件Encode.dat进行解码,把结果输出到文件TargetDoc.txt,完成信源的解码过程。5>判断TargetDoc.txt与SourceDoc.txt内容是否一致,以验证编解码系统的正确性。实验内容:1>线性链表的构建以及排序;2>哈夫曼树的构建;3>基于哈夫曼码进行编码;4>对二进制码进行解码;5对生成文件与原文件进行比较；程序的算法描述创建动态线性创建动态线性链表对源文件生成的动态线性链表按频数进行排序对生成的有序线性链表生成二叉树根据动态链表以及二叉树按权值生成相对应的哈夫曼树根据哈夫曼编码生成对应的哈夫曼码本并对源文件生成哈夫曼吗按二进制码存储由文件的哈夫曼码进行解码并生成目标文件判断目标文件是否与源文件一致程序运行结果：源程序代码：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>typedefstructaa{chardata;doublerate;intcount;structaa*next;structaa*pre;charhaffmancode[120];}NODE;NODE*creat<charb[]>{NODE*h,*p,*s,*death;inti;h=<NODE*>malloc<sizeof<NODE>>;p=<NODE*>malloc<sizeof<NODE>>;h->next=p;h->pre=NULL;p->pre=h;p->next=NULL;p->data=b[0];p->count=1.0;for<i=1;b[i]!='\0';i++>{s=<NODE*>malloc<sizeof<NODE>>;s->data=b[i];s->count=1.0;s->next=NULL;s->pre=p;p->next=s;p=s;}returnh;}voidfun<NODE*h,intamount>{NODE*p,*q,*death; for<p=h->next;p;p=p->next>{ for<q=p->next;q;>{ if<q->data==p->data>{ <p->count>++;if<q->next==NULL>{q->pre->next=NULL;free<q>;break;}else{q->pre->next=q->next;q->next->pre=q->pre; death=q;q=q->next; free<death>; } } elseq=q->next;}<p->rate>=1.0*<p->count>/amount;//printf<"%c:\t%d\t%f\n",p->data,p->count,p->rate>;}puts<"构建链表完成\n">;}voidoutlink<NODE*h,int*n>{//printf<"%d",amount>;NODE*p=<NODE*>malloc<sizeof<NODE>>;NODE*s=<NODE*>malloc<sizeof<NODE>>; inti; charch; doubler;for<p=h->next;p;p=p->next> { for<s=p->next;s;s=s->next> { if<s->count>p->count> { i=p->count; p->count=s->count; s->count=i; ch=p->data; p->data=s->data; s->data=ch; r=p->rate; p->rate=s->rate; s->rate=r; } } }p=h->next;while<p>{//printf<"%c:\t%d\t%f\n",p->data,p->count,p->rate>;<*n>++;p=p->next;}puts<"排序完成\n">;}typedefstruct{ NODEbody;intlchild,rchild,parent; structTreenode*next;}HTNode,*Tree;typedefchar**Huffmancode;voidselect<Tree&HT,intn,int&s1,int&s2>{inti,j;for<i=1;i<=n;i++>if<!HT[i].parent>{s1=i;break;}for<j=i+1;j<=n;j++>if<!HT[j].parent>{s2=j;break;}for<i=1;i<=n;i++>if<<HT[s1].body.rate>HT[i].body.rate>&&<!HT[i].parent>&&<s2!=i>>s1=i;for<j=1;j<=n;j++>if<<HT[s2].body.rate>HT[j].body.rate>&&<!HT[j].parent>&&<s1!=j>>s2=j;}voidHuffmancoding<Tree&HT,Huffmancode&HC,intn,NODE*head,int*wei>{HTNode*p;intm=2*n-1,i;ints1,s2;NODE*L=head->next;HT=<Tree>malloc<<m+1>*sizeof<HTNode>>;for<p=HT+1,i=1;i<=n;i++,p++>{p->body=*L; L=L->next; p->lchild=0;p->parent=0;p->rchild=0;}for<;i<=m;p++,i++>{p->body.rate=0;p->lchild=0;p->parent=0;p->rchild=0;}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].body.rate=HT[s1].body.rate+HT[s2].body.rate;}for<i=n+1;i<=m;i++>{if<HT[i].parent==0>{*wei=i;}}HC=<Huffmancode>malloc<<n+1>*sizeof<char*>>;char*temp=<char*>malloc<n*sizeof<char>>;temp[n-1]='\0';for<i=0;i<n;i++>{intstart=n-1;for<intf=HT[i].parent,h=i;f;h=f,f=HT[f].parent>{if<HT[f].lchild==h>{temp[--start]='0';}else{temp[--start]='1';}}//HC[i]=<char*>malloc<<n-start>*sizeof<char>>;strcpy<HT[i].body.haffmancode,&temp[start]>;}free<temp>;FILE*fw;fw=fopen<"Statistic.txt","wt">;for<i=1;i<n;i++>{fprintf<fw,"%c:\t%d\t%f\t%s\n",HT[i].body.data,HT[i].body.count,HT[i].body.rate,HT[i].body.haffmancode>;}puts<"哈夫曼编码完成,Statistic.txt文件生成完毕\n">;fclose<fw>;}voidputdat<NODE*h,FILE*fp,FILE*ft,FILE*fw,Tree&HT,int*wei,int*nc>{charqq[10000]={0};intt[10000]={0};inti=0,j=0,n=0,last=*nc;rewind<fp>; charpp[10000]={0}; //strcpy<pp,"\0">; NODE*L=h->next; while<L>{i=0; while<i<last>{ if<L->data==HT[i].body.data>strcpy<L->haffmancode,HT[i].body.haffmancode>; i++; } L=L->next;}charcp=fgetc<fp>; while<cp!=EOF> { L=h->next; while<cp!=L->data> L=L->next; strcat<pp,L->haffmancode>; cp=fgetc<fp>; }//printf<"%s\n\n",pp>;i=0;while<pp[i]!='\0'>{ n=0; while<n<15&&pp[i]!='\0'>{ if<pp[i]=='1'>{ t[j]=t[j]|1; } if<n!=14&&pp[i+1]!='\0'>{t[j]=t[j]<<1;} n++; i++; } if<pp[i]=='\0'>{t[j+1]=0;last=n;break;} j++;}//for<;t[n]!=0;n++>;//itoa<t[0],string,2>;printf<"string=%s\n",string>; fwrite<&t[0],sizeof<char>,j-1,fw>;i=0;j=0;while<t[j+1]!='\0'>{ n=14; while<n>=0>{ doublea=pow<2,n>; if<<t[j]&<int>a>==<int>a>{ qq[i]='1';} else{qq[i]='0';} n--; i++; } j++;}n=last-1;while<n>=0>{doublea=pow<2,n>; if<<t[j]&<int>a>==<int>a> qq[i]='1'; elseqq[i]='0'; n--;i++;}qq[i]='\0';//printf<"%s",qq>;introot=*wei; charc; i=0; while<qq[i]!='\0'> {c=qq[i]; if<qq[i]=='0'>{ root=HT[root].lchild;} else{ root=HT[root].rchild;} if<HT[root].rchild==0&&HT[root].lchild==0>{fprintf<ft,"%c",HT[root].body.data>; root=*wei;} i++; }puts<"解码完成,Target.txt文件生成\n">;}boolcompare<FILE*fp,FILE*ft>{ rewind<fp>; charch1=fgetc<fp>; charch2=fgetc<ft>; while<ch1!=EOF&&ch2!=EOF> { if<ch1!=ch2> break; ch1=fgetc<fp>; ch2=fgetc<ft>; } returnch1==ch2&&ch1==EOF?true:false;}intmain<>{FILE*fp; charch; intcnt=0; charb[10000]; if<<fp=fopen<"source.txt","rt">>==NULL> {printf<"\ncannotopenfile">; return0;} ch=fgetc<fp>; while<ch!=EOF> {ch=fgetc<fp>; b[cnt]=ch;cnt++; } FILE*fw; fw=fopen<"Encode.dat","wb">; if<!fw>{ printf<"NOSPACE%s\n">; return0; }intamount=strlen<b>;intn=0,m=2*n-1,i;NODE*head;head=creat<b>;fun<head,amount>;outlink<head,&n>;TreeHT;char**HC;floattemp;intwei;HT=<Tree>malloc<<m+1>*sizeof<HTNode>>;HC=<Huffmancode>malloc<<n>*sizeof<char*>>;Huffmancoding<HT,HC,n,head,&wei>;FILE*ft;ft=fopen<"Target.txt","wt">;if<!ft>{ printf<"NOSPACEFORTarget.txt">; return0; } putdat<head,fp,ft,fw,HT,&wei,&n>;fclose<ft>;fclose<fp>; if<!ft>{ printf<"NOSPACEFORTarget.txt">; return0; } fclose<ft>; FILE*ftnew; ftnew=fopen<"TargetDoc.txt","rt+">; boolresult=compare<fp,ftnew>; if<result==true> { puts<"目标文件与原文件一致\n">; } else puts<"