數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)四 -哈夫曼數(shù)與哈弗曼編碼

第2頁共7頁實(shí)驗(yàn)四哈夫曼樹及其的應(yīng)用一、實(shí)驗(yàn)?zāi)康?、在二叉樹基本操作的基礎(chǔ)上，掌握對(duì)二叉樹的一些其它操作的具體實(shí)現(xiàn)方法。2、掌握構(gòu)造哈夫曼樹以及哈夫曼編碼的方法。3、熟練掌握哈夫曼樹特征及其應(yīng)用二、實(shí)驗(yàn)內(nèi)容題目哈夫曼樹和哈夫曼編碼：從終端輸入若干個(gè)字符，統(tǒng)計(jì)（或指定）字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為結(jié)點(diǎn)的權(quán)值，建立哈夫曼樹，然后對(duì)各字符進(jìn)行哈夫曼編碼。最后打印哈夫曼樹和對(duì)應(yīng)的哈夫曼編碼。三、實(shí)驗(yàn)步驟（一）、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述本實(shí)驗(yàn)在二叉樹基本操作的基礎(chǔ)上著重對(duì)其應(yīng)用，哈弗曼樹及哈弗曼編碼均采用動(dòng)態(tài)數(shù)組存儲(chǔ)，關(guān)鍵在于哈弗曼樹的構(gòu)造和哈弗曼編碼，此外對(duì)終端字符的統(tǒng)計(jì)也比較重要。以下是頭文件中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和相關(guān)函數(shù)的聲明：#defineDataTypechar#include<iostream.h>#include<malloc.h>#include<string.h>#include<iomanip.h>typedefstruct{DataTypech;intweight;//權(quán)值及頻率intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;int*TongjiChar(int*text);/*統(tǒng)計(jì)字符出現(xiàn)的頻率*/voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn);//該函數(shù)包含哈弗曼數(shù)的構(gòu)造及哈弗曼編碼voidSelect(HuffmanTreeHT,inti,int&s1,int&s2);voidTranslate(HuffmanTree&HT,HuffmanCode&HC,int&n);（二）、函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)externintn;//n為節(jié)點(diǎn)的個(gè)數(shù)voidmain(){ HuffmanTreeHT; HuffmanCodeHC;int*text,*count;count=TongjiChar(text);HuffmanCoding(HT,HC,count,n); Translate(HT,HC,n);}（三）、程序運(yùn)行結(jié)果分析：（四）、實(shí)驗(yàn)總結(jié)由于有二叉樹的基本操作的經(jīng)驗(yàn)，在本實(shí)驗(yàn)中哈弗曼樹的構(gòu)造及哈弗曼編碼相對(duì)就較容易實(shí)現(xiàn)，但是本實(shí)驗(yàn)的關(guān)鍵仍在于哈弗曼樹的構(gòu)造和哈弗曼編碼，本實(shí)驗(yàn)的一個(gè)特點(diǎn)是在實(shí)驗(yàn)基本要求的基礎(chǔ)上增加了翻譯功能。盡管實(shí)驗(yàn)過程中不同模塊遇到了不同程度的困難，但是經(jīng)過詳細(xì)的設(shè)計(jì)和反復(fù)的測(cè)試、調(diào)試，實(shí)驗(yàn)最終結(jié)果達(dá)到了實(shí)驗(yàn)的預(yù)期結(jié)果。四、主要算法流程圖及程序清單1、主要算法流程圖：終端輸入字符終端輸入字符統(tǒng)計(jì)字符的頻率構(gòu)造哈弗曼和哈弗曼編碼翻譯結(jié)束2、程序清單統(tǒng)計(jì)字符的頻率模塊：intn=0;int*TongjiChar(int*text){ charch; inti; charstr[100]; intcount[100]; for(i=0;i<100;i++) count[i]=1; inttotal=0; intlength=0; cout<<"請(qǐng)輸入一串字符(以#結(jié)尾)："; do {loop:cin>>ch;length++; total++; if(ch!='#') { str[length-1]=ch; for(i=0;i<length;i++) { if(length!=1) { for(intj=0;j<length-1;j++) { if(str[j]==ch) {count[j]++;length--; gotoloop; } } } } } }while(ch!='#'); length--;//去掉最后一個(gè)#號(hào) total--; cout<<"所有字符的個(gè)數(shù)為(不含#):"<<total<<endl; cout<<"不同字符的個(gè)數(shù)為:"<<length<<endl; text=count;for(i=0;i<length;i++) cout<<str[i]<<""<<"頻率："<<count[i]<<""<<endl;n=length; returntext;}構(gòu)造哈弗曼數(shù)和哈弗曼編碼模塊：voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){intm,i,s1,s2,start,c,f;intdata[30];charstr;HuffmanTreep;if(n<=1) return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));cout<<"請(qǐng)依次輸入各個(gè)結(jié)點(diǎn)的數(shù)值(可以是字符)：\例如：afhkr8680ds\n"; for(i=1;i<=n;i++){cin>>str; data[i]=str; } data[i+1]='\0';for(p=HT+1,i=1;i<=n;++i) { p->weight=*w; str=data[i]; p->ch=str; cout<<"第"<<i<<"個(gè)接點(diǎn)的數(shù)值為："<<p->ch<<'\n'; p->parent=0; p->lchild=0; p->rchild=0; p++; w++;}for(;i<=m;++i,++p) { p->weight=0;p->parent=0; p->lchild=0; p->rchild=0;}cout<<endl<<"建立哈夫曼樹:";for(i=n+1;i<=m;++i){ Select(HT,i-1,s1,s2); //選擇各元素中權(quán)值最小的兩個(gè)HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;cout<<endl<<setw(6)<<"HT["<<s1<<"]和HT["<<s2<<"]"<<setw(5)<<"生成";cout<<setw(5)<<"HT["<<i<<"],且權(quán)值="<<HT[i].weight<<"的接點(diǎn)。";}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//哈夫曼編碼char*cd;cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';cout<<endl<<"哈夫曼編碼如下:"<<endl;for(i=1;i<=n;++i){ start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0';//--后的值作為表達(dá)式的值。如果是左支,記為0;右支,記為1; else cd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]); cout<<"HT["<<i<<"]"<<"的哈夫曼編碼為："<<HC[i]<<endl;}free(cd);}//HuffmanCoding()end選澤模塊：voidSelect(HuffmanTreeHT,inti,int&s1,int&s2){ intj,k=1;//j為循環(huán)變量while(HT[k].parent!=0)k++;s1=k;for(j=1;j<=i;j++)if(HT[j].parent==0&&HT[j].weight<HT[s1].weight) s1=j;//s1為權(quán)值最小的元素k=1;while((HT[k].parent!=0||k==s1))k++;s2=k;for(j=1;j<=i;++j)if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1) s2=j;}//Select()end翻譯模塊：voidTranslate(HuffmanTree&HT,HuffmanCode&HC,int&n){inti,k,j=0;HuffmanTreep;char*data;data=newchar[n+1];for(p=HT+1,i=1;i<=n;i++,p++)data[i]=p->ch;cout<<"各結(jié)點(diǎn)數(shù)值依次是：";for(i=1;i<=n;i++) cout<<data[i]<<"";cout<<endl;char*str;str=newchar[n];cout<<"(提示：請(qǐng)您輸入需要譯碼的0和1的個(gè)數(shù)以及序列!例如：6010111)"<<endl;cin>>k;char*ch;ch=newchar[k+1];for(intm=0;m<k;m++) cin>>ch[m];ch[k]='\0';cout<<"翻譯后的字符序列是"; while(ch[j]!='\0') { for(i=1;i<=n;i++) { str[i-1]=ch[j];