PAGE第12頁共12頁華%%%%%%%%%%%%%%%%%%學院數據結構實驗報告2011～2012學年第二學期2011級計算機專業班級：學號：姓名：實驗三樹的應用實驗題目：樹的應用——哈夫曼編/譯碼實驗內容：利用哈夫曼編碼進行通信可以大大提高信道的利用率，縮短信息傳輸的時間，降低傳輸成本。根據哈夫曼編碼的原理，編寫一個程序，在用戶輸入字符及權值的基礎上求哈夫曼編碼。要求：從鍵盤輸入字符集（字母a～z，空格）共27個字符，以及出現的頻率，將字符出現的頻率作為結點的權值，建立哈夫曼樹，并輸出數組ht[]的初態和終態。對各個字符進行哈夫曼編碼，打印輸出字符及對應的哈夫曼編碼。編碼：從鍵盤輸入字符串，利用已建好的哈夫曼編碼，實現該字符串的編碼。（選作）譯碼：從鍵盤輸入二進制串，利用已建好的哈夫曼編碼，將二進制串還原為字符串。程序源代碼：typedefstruct{ chardata; intweight; intparent; intlchild; intrchild;}HTNode;typedefstruct{ charcd[100]; intstart;}HCode;//這里保存字母對應的編碼，我本來想用指向字符數組的指針數組，可是后來想到利用結構體更簡單。structCodes{ charch; charcodes[27];};#include<iostream.h>#include<stdio.h>#include<string.h>constintmaxsize=100;//特色，動態編碼voidtongji(charstr[],int*pinlv);voidcreateHT(HTNode*ht,intn,intpinlv[]);voidshowHT(HTNodeht[],intn);voidcreateHcode(HTNodeht[],HCode*hcd,intn);voidshowHCode(HCodehcd[],intn,intpinlv[]);//使字符與編碼對應voidmatchcodes(HCodehcd[],intpinlv[],intn,Codes*code);voidcharToCode(Codescodes[],char*str);voidcodeToChar(Codescodes[]);voidmain(){ cout<<"本例實現動態編碼：根據輸入的字符串建立編碼規則，然后按此規則對輸入的字符串進行編碼，對輸入的編碼進行譯碼操作"<<endl; //輸入 cout<<"inputastring"<<endl; charstr[maxsize]; gets(str); //統計 intpinlv[27]; intlen=0; for(inti=0;i<27;i++) pinlv[i]=0; tongji(str,pinlv); for(intk=0;k<27;k++) if(pinlv[k]!=0) len++; cout<<len<<endl; // cout<<pinlv[26]<<endl; //構造哈夫曼樹 HTNodeht[199]; createHT(ht,len,pinlv); //哈夫曼編碼 HCodehcd[27]; createHcode(ht,hcd,len); showHCode(hcd,len,pinlv); //字符與編碼對應匹配 Codescodes[27]; matchcodes(hcd,pinlv,len,codes); //chartocode charToCode(codes,str); //codetochar codeToChar(codes);}//這個函數有錯誤，已經改正voidcodeToChar(Codescodes[]){ cout<<"根據上面輸出的編碼規則，請輸入要譯碼的01編碼（相鄰編碼要以逗號分割，以“#”結束）"<<endl; charstr[100]; gets(str); cout<<str<<"的譯碼為："<<endl; chartemp[27];//保存每個字符的編碼，每次要賦0啊 inti,j; for(i=0,j=0;i<100;i++) { if(str[i]!=',') { temp[j]=str[i]; j++; } else { temp[j]='\0'; for(intk=0;k<27;k++) { if(strcmp(codes[k].codes,temp)==0) { cout<<codes[k].ch<<""; //cout.flush(); break; } } j=0;//賦0操作 } if(str[i]=='#') { break; } } cout<<endl;}voidcharToCode(Codescodes[],char*str){ charch=*str; intk=0; cout<<str<<"的編碼為："<<endl; while(ch!='\0') { for(inti=0;i<27;i++) { if(codes[i].ch==ch) cout<<codes[i].codes<<"，"; } k++; ch=*(str+k); } cout<<endl;}//已經改進過的地方voidmatchcodes(HCodehcd[],intpinlv[],intn,Codes*codes){ inti,k,m; charch='a'; intp=0; chartemp[27]; for(intz=0;z<26;z++) { temp[z]=''; } temp[26]='\0'; for(i=0;i<27;i++) { if(pinlv[i]!=0) { ch='a'; ch=char(ch+i); if(ch>='a'&&ch<='z') { codes[p].ch=ch; //測試 /* if(codes[p].ch==ch) { cout<<"succss"<<endl; }*/ } else codes[p].ch=''; m=0; for(k=hcd[p].start;k<=n;k++) { temp[m]=hcd[p].cd[k]; m++; } //字符串必須給出結束符位置，否則會輸出亂碼啊 temp[m]='\0'; //codes[p]=temp; strcpy(codes[p].codes,temp); // cout<<codes[p].ch; // cout<<codes[p].ch<<""<<codes[p].codes<<endl; p++; } }}voidshowHCode(HCodehcd[],intn,intpinlv[]){ inti,k; charch='a'; intp=0; cout<<"字符"<<""<<"對應編碼"<<endl; for(i=0;i<27;i++) { //每次必須從字符'a'開始 ch='a'; //// ch=char(ch+i); if(pinlv[i]!=0) { if(ch>='a'&&ch<='z') cout<<ch<<""; else cout<<""<<""; for(k=hcd[p].start;k<=n;k++) cout<<hcd[p].cd[k]; p++; cout<<endl; } } }voidcreateHcode(HTNodeht[],HCode*hcd,intn){ inti,f,c; HCodehc; for(i=0;i<n;i++) { //不是書上的 hc.start=n; hc.start=n-1; c=i; f=ht[i].parent; while(f!=-1) { if(ht[f].lchild==c) hc.cd[hc.start--]='0'; else hc.cd[hc.start--]='1'; c=f; f=ht[f].parent; } //最后一位必須賦值為結束符 hc.cd[n]='\0'; hc.start++; hcd[i]=hc; }}voidcreateHT(HTNode*ht,intn,intpinlv[]){ for(intm=0;m<=2*n-1;m++)//初始化節點的所有與域值 ht[m].parent=ht[m].lchild=ht[m].rchild=-1; charch='a'; intp=0; for(intz=0;z<27;z++)//循環27個字母（a-z和''），若頻數大于0，就創建節點 { if(pinlv[z]!=0) { if(ch>='a'&&'z'>=ch) { ht[p].data=ch; ht[p].weight=pinlv[ch-97]; } else { ht[p].data=''; ht[p].weight=pinlv[26]; } p++; } ch=char(ch+1); } cout<<"ht[]初態輸出"; showHT(ht,n); inti,k,lnode,rnode; intmin1,min2; for(i=n;i<2*n-1;i++) { min1=min2=32767; lnode=rnode=-1; for(k=0;k<=i-1;k++) { if(ht[k].parent==-1) { if(ht[k].weight<min1) { min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k; } elseif(ht[k].weight<min2) { min2=ht[k].weight; rnode=k; } } } ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; ht[i].data='*'; } cout<<"ht[]終態輸出"; showHT(ht,2*n-1);}voidtongji(charstr[],int*pinlv){ charch=*str; intk=1; while(ch!='\0') {if(ch>='a'&&'z'>=ch) pinlv[ch-97]+=1; else pinlv[26]+=1; ch=*(str+k); k++; }}voidshowHT(HTNodeht[],intn){cout<<"節點信息如下："<<endl; cout<<"data"<<""<<"weig"<<""<<"pare"<<""<<"lchd"<<""<<"rchd"<<endl; for(inti=0;i<n;i++) { cout<<ht[i]