2023年數(shù)據(jù)結構哈夫曼編碼實驗報告

數(shù)據(jù)結構實驗報告一一實驗五簡樸哈夫曼編/譯碼的設計與實現(xiàn)本實驗的目的是通過對簡樸哈夫曼編/譯碼系統(tǒng)的設計與實現(xiàn)來純熟掌握樹型結構在實際問題中的應用。此實驗可以作為綜合實驗，階段性實驗時可以選擇其中的幾個功能來設計和實現(xiàn)。一、【問題描述】。運用哈夫曼編碼進行通信可以大大提高信道運用率，縮短信息傳輸時間，減少傳輸成本。但是，這規(guī)定在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼,在接受端將傳來的數(shù)據(jù)進行譯碼,此實驗即設計這樣的一個簡樸編/碼系統(tǒng)。系統(tǒng)應當具有如下的幾個功能：1、接受原始數(shù)據(jù)。。從終端讀入字符集大小n,以及n個字符和n個權值，建立哈夫曼樹，并將它存于文獻nodedata.dat中。。2、編碼。運用已建好的哈夫曼樹（如不在內(nèi)存，則從文獻nodedata.dal中讀入），對文獻中的正文進行編碼，然后將結果存入文獻code.dat中。。3、譯碼。運用已建好的哈夫夏樹將文獻code.dal中的代碼進行譯碼,結果存入文獻lexlfile.dat中。4、打印編碼規(guī)則。即字符與編碼的一一相應關系。二、【數(shù)據(jù)結構設計】。1、構造哈夫曼樹時使用靜態(tài)鏈表作為哈夫曼樹的存偌。。在構造哈夫曼樹時，設計一個結構體數(shù)組HuffNode保存哈夫曼樹中各結點的信息,根據(jù)二又樹的性質可知，具有n個葉子結點的哈夫曼樹共有2n-l個結點，所以數(shù)組HuffNode的大小設立為2n-l,描述結點的數(shù)據(jù)類型為：typedefstrucI?for(j=HaffCode[i].start+l;j<n；j++)00outfilei.write((char*)&HaffCode[i].bit[j],sizeof(HaffCode[i].bit[j]))；。8。cout?HaffCode[i].bit[j];0)°}}°}cout?endl;。cout<V”編譯后的代碼串已經(jīng)存入code.dat文獻中！"<Vendl;cout<<end1;outfile1.close();delete[]HaffNode;delete[]HaffCode;1voiddecode(int&n)//解碼(inti;HNodeType*11affNode=newIINodeType[2*n-1];fstreaminfile1;oinfilel.open("E:\\nodedata.dat",ios::in|ios:：binary);//讀出哈夫曼樹oif(!infi1e1)cout<<*'nodedata.dat文獻不能打開"VVend1;gabort()；}。ofor(i=0;i<2*n—l;i++)nfile1.read((char*)&HaffNode[i],sizeof(HNodeType))；Anfilel.close();intlempcode[100];◎intnum=0;for(i=0;i<100;i++)tempoode[i]=-l;0HcodeType*Code=newHcodeType[n]；fstreaminfile2;〃讀編碼oinfile2.open("E：Wcode.dat",ios::in|ios:：binary);while(!infile2.eof())infi1e2.read((char*)&tempcode[num],sizeof(tempcode[num]));oonum++;}infile2.close();叫um—;。cou從文獻中讀出的編碼為"<<endl;for(i=0;i<num;i++)cout?tempcode[i];cout?end1;intm=2*n-2；i=0；cout<<end1;couK<"譯碼后為:"<<endl;fstreamoutfile;outfile.open("E:\\textfile.txtH,ios:：out);if(!outfi1e)(cout?"textfilc.txt文獻不能打開!"VVendl;abort();)while(i<num)//小于字符串的長度(while(HaffNode[m].1child!=_1&&HaffNode[m].rchiId!=-l)0(if(tempcodefi]==0)o{?a?m=HaffNode[m].1child;oooai++；。)。elseif(tempcode[i]==1)(o?m=HaffNode[m].rchi1d;i++;

cout<<HaffNode[m].inf;outfile?HaffNode[m].inf;0m=2*n-2;)cout?endl;outfi1e.c1ose();coutV<”譯碼后的結果已經(jīng)存入textfi1e.txt中!”V<end1；delete]]HaffNode;intmain()intn;cout?"*************歡迎進入編/譯碼系統(tǒng)！*火*******************"<<cnd1;?intch1;?do{0COUt?"1.建樹”0COUt?"1.建樹”vvendl;cout<<"cout<<"2:編碼,并顯示字符和相應的編碼"cout<<"2:編碼,并顯示字符和相應的編碼"V<endl；?C0ut<<"?C0ut<<"3:譯碼H?endl;cout<<"0:退出"v<endl;cout?n?C0ut<<"3:譯碼H?endl;cout<<"0:退出"v<endl;************"<vend卜cout?”請選擇(0?3):";。cin>>ch1；whi1e(!(ch1<=3&&chi>=0))〃輸入不在0到4之間無效°(。coutVV”數(shù)據(jù)輸入錯誤，請重新選擇(0?4):**;。cin?chi;00}switch(ch1)(。case1：08{。。cout<V”\t\l\l請輸入編碼個數(shù)“V<endl;//葉子結點個數(shù)。。ocin?n;Creat_Haffmantree(n);break；)。case2:HaffCode(n);break;case3:decode(n);break；}}whi1e(chi!=0)oreturn0；)五、【運營與測試】1、令葉子結點個數(shù)n為4,權值集合為{1,3,5,7},字符集合為{A,B,C,D},并有如下相應關系，A1、B3,C5,D7,調(diào)用初始化功能模塊可以對的接受這些數(shù)據(jù)。2、調(diào)用建立哈夫曼樹的功能模塊,構造靜態(tài)鏈表HuffNode的存儲。。3、調(diào)用建立哈夫曼編碼的功能模塊，在屏幕上顯示如下相應關系：A11IB110、C10、D0。4、調(diào)用譯碼的功能模塊，輸入代碼串"”后，屏幕上顯示譯碼結果：0ABCD?intweight;//結點權值intparent;?int1chiId;“ntrchild;charinf；}HNodeType;2、求哈夫曼編碼時使用一維結構數(shù)組HuffCode作為哈夫曼編碼信息的存儲。。求哈夫曼編碼，實質上就是在已建立的哈夫曼樹中，從葉子結點開始，沿結點的雙親鏈域【可退到根結點,沒回退?步,就走過了哈夫曼樹的?個分支，從而得到?位哈夫曼碼值，由于?個字符的哈夫曼編碼是從根結點到相應葉子結點所通過的途徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼位所求編碼的高位碼，所以設計如下數(shù)據(jù)類型：#defineMAXBIT10typedefstruct（ointbit[MAXBITJ;aintstart;}HcodcTypc；03、文獻nodedata.dat、code.dat和textfile.date三、【功能（函數(shù)）設計】1、初始化功能模塊。。此功能模塊的功能為從鍵盤接受字符集大小n,以及n個字符和n個權值。2、建立哈夫曼樹的功能模塊。此模塊功能為使用1中得到的數(shù)據(jù)按照教材中的構造哈夫曼樹的算法構造哈夫曼樹，即將HuffNode數(shù)組中的各個位置的各個域都添上相關的值，并將這個結構體數(shù)組存于文獻hfmtree.dat中。3、建立哈夫曼編碼的功能模塊。此模塊功能為從文獻nodedata.dat中讀入相關的字符信息進行哈夫曼編碼，然后將結果存入code.dat中,同時將字符與()、1代碼串的一一相應關系打印到屏幕上。4、譯碼的功能模塊。此模塊功能為接受需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文獻textfile,dat，同時將翻譯的結果在屏幕上打印輸出。。四、【編碼實現(xiàn)】#inc1ude<iostrearn.h>include<fstream.h>include<string.h>inc1ude<stdlib.h>defineMaxBit10defincMaxvalue100//應當大于權重之和defineMaxieaf100#defineMaxnodeMaxleaf*2—1typedefstruct(ntweight;intparent;?intIchiId;intrchiId;charinf；)HNodeType;structHcodeType{??intbil[MaxBit];。intstart;}；voidCreat_Haffmantree(int&n)(HNodeType*HaffNode=newHNodeType[2*n-l];inti,j；“ntml,m2,x1,x2;for(i=0;i<2*n—1;i++)(◎HaffNode[i].weight=0;HaffNodc[i].parcnt=—1;HaffNodefi].Ichild=-1;“HaffNode[ij.rchild=—1;ooHaffNode[i)?for(i=0;i<n;i++)oocout?"請輸入字符"?end1;oocin?HaffNode[i].inf;ocout<<”請輸入該字符的權值"?end1;cin?HaffNodefi].weight;。｝for(i=0;i<n-l；i++)//構造哈夫曼樹l=m2=Maxva1ue；xl=x2=0;gfor(j=0;j<n+i;j++)〃選取最小和次小(oif(HaffNode[j].parent==-l&&HaffNode[j].weight<ml)8(m2=m1；ox2=x1;oml=HaffNode[j].weight;8OXl=j；)geIseOd{。。if(HaffNodefjl.parent==-l&&HaffNode[j].weight<m2)0o{。。m2=HaffNode[j].weight；88X2=j；)00)0)。//將找出的最小和次小合并，發(fā)明其父母結點oHaffNode[xlj.parent=n+i;。HaffNode[x2].parent=n+i；oHaffNode[n+i].weight=HaffNode[xl].weight+HaffNode[x2].weight;HaffNode[n+i].Ichi1d=x1;。HaffNode[n+i].rchild=x2;?HaffNode[n+i].inf=NULL;0Joocout<<I顯示存儲的哈弗曼樹信息:"vvendl;cout?”權值左孩子右孩子雙親"VVend1;for(i=0;i<2*n-1;i++)(cout?HaffNode[i].weight?n”；cout?HaffNode[i].lchild<<H"；cout?HaffNode[i].rchild?""；。cout?HaffNode[i].parent?"。cout<<HaffNode[i].inf<<endl;0)?！▽懭胛墨Iofstreamoutfile1;outfi1el.open("E：\\nodedata,dat'\ios::out|ios::trunc|ios::binary);//建立進行寫入的文獻oif(!outfilei)//沒有創(chuàng)建成功則顯示相應信息{ocout<<"nodedata.dat文獻不能打開"〈〈end1;??abort();ofor(i=0;i<2*n-1；i++)//將內(nèi)存中從HaffNode[i]地址開始的sizeof(HaffNode[i])的內(nèi)容寫入文獻中outfile1.write((char*)&HaffNodeLi],sizeof(HaffNode[i]));utfile1.close()；//關閉文獻。delete[]HaffNode;}voidHaffCode(int&n)〃哈夫曼編碼(oHNodeType*HaffNode=newHNodeType[Maxnode]；oHcodeType*HaffCode=newHeodeType[Max1eaf];?HeodeTypecd;?inti,j,c,p;fstreamin("E:\\nodedata.datH,ios::in|ios::binary);in.read((char*)HaffNode,(2*n-1)*sizeof(HNodeType));in.close();?fstreamoutfile;ooutfile.open(HE:\\codedata.datn,ios:：out|ios::binary)；〃建立進行寫入的文獻ofor(i=0;i<n;i++)(8cd.start=n-1；oc=i；??p=HaffNode[c].parent;?while(p!=-l)o?if(HaffNode[pj.lchi1d==c)cd.bit[cd.start]=0；e1se。cd.bil[cd.slart]=1;。cd.start";。箋=p；。p=HaffNode[c].parent;°}oofor(j=cd.start+1;j<n；j++)?HaffCode[j]=cd.bit[j];affCode[i].start=cd.start;)for(i=0;i<n;i++)(◎ouifiIe?HaffNo