哈弗曼數(shù)據(jù)結(jié)構(gòu)專題實(shí)驗報告

..數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計專題實(shí)驗報告______信息45班______信息45班______信息45班實(shí)驗指導(dǎo)李峰實(shí)驗地點(diǎn)：西一樓一層計算機(jī)中心機(jī)房實(shí)驗結(jié)束日期：12月5日實(shí)驗任務(wù)：對于給定的源文檔SourceDoc.txt,1>統(tǒng)計其中所有字符的頻度〔某字符的頻度等于其出現(xiàn)的總次數(shù)除以總字符數(shù),字符包括字母〔區(qū)分大小寫、標(biāo)點(diǎn)符號及格式控制符〔空格、回車等。2>按頻度統(tǒng)計結(jié)果構(gòu)建哈夫曼編碼表。3>基于哈夫曼編碼表進(jìn)行編碼,生成對應(yīng)的二進(jìn)制碼流,并輸出到文件Encode.dat,完成信源的編碼過程。4>根據(jù)生成的哈夫曼編碼表,對二進(jìn)制碼流文件Encode.dat進(jìn)行解碼,把結(jié)果輸出到文件TargetDoc.txt,完成信源的解碼過程。5>判斷TargetDoc.txt與SourceDoc.txt內(nèi)容是否一致,以驗證編解碼系統(tǒng)的正確性。實(shí)驗內(nèi)容:1>線性鏈表的構(gòu)建以及排序;2>哈夫曼樹的構(gòu)建;3>基于哈夫曼碼進(jìn)行編碼;4>對二進(jìn)制碼進(jìn)行解碼;5對生成文件與原文件進(jìn)行比較；程序的算法描述創(chuàng)建動態(tài)線性創(chuàng)建動態(tài)線性鏈表對源文件生成的動態(tài)線性鏈表按頻數(shù)進(jìn)行排序?qū)ι傻挠行蚓€性鏈表生成二叉樹根據(jù)動態(tài)鏈表以及二叉樹按權(quán)值生成相對應(yīng)的哈夫曼樹根據(jù)哈夫曼編碼生成對應(yīng)的哈夫曼碼本并對源文件生成哈夫曼嗎按二進(jìn)制碼存儲由文件的哈夫曼碼進(jìn)行解碼并生成目標(biāo)文件判斷目標(biāo)文件是否與源文件一致程序運(yùn)行結(jié)果：源程序代碼：#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<"構(gòu)建鏈表完成\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<"目標(biāo)文件與原文件一致\n">; } else puts<"