北郵信通院數據結構實驗報告三哈夫曼編碼器北郵信通院數據結構實驗報告三哈夫曼編碼器20/20北郵信通院數據結構實驗報告三哈夫曼編碼器北京郵電大學電信工程學院數據結構實驗報告實驗名稱：實驗三樹——哈夫曼編/解碼器學生姓名：班級：班內序號：學號：日期：2014年12月11日1．實驗要求利用二叉樹結構實現赫夫曼編/解碼器。基本要求：1、初始化(Init)：能夠對輸入的隨意長度的字符串s進行統計，統計每個字符的頻度，并成立赫夫曼樹2、成立編碼表(CreateTable)：利用已經建好的赫夫曼樹進行編碼，并將每個字符的編碼輸出。3、編碼(Encoding)：依據編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出。4、譯碼(Decoding)：利用已經建好的赫夫曼樹對編碼后的字符串進行譯碼，并輸出譯碼結果。5、打印(Print)：以直觀的方式打印赫夫曼樹（選作）6、計算輸入的字符串編碼前和編碼后的長度，并進行解析，談論赫夫曼編碼的壓縮見效。測試數據：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提示：1、用戶界面能夠設計為“菜單”方式：能夠進行交互。2、依據輸入的字符串中每個字符出現的次數統計頻度，對沒有出現的字符一律不用編碼。1頁-程序解析2.1存儲結構Huffman樹給定一組擁有確立權值的葉子結點，能夠結構出不一樣樣樣的二叉樹，此中帶權路徑長度最小的二叉樹稱為Huffman樹，也叫做最優二叉樹。weightlchildrchildparent2-2-1-1-15-1-1-16-1-1-17-1-1-19-1-1-1weightlchildrchildparent2-1-155-1-156-1-167-1-169-1-1770173-13238165482967-12.2重點算法解析1）計算出現字符的權值利用ASCII碼統計出現字符的次數，再將未出現的字符進行優選，將出現的字符及頻數存儲在數組a[]中。voidHuffman::Init(){intnNum[256]={0};//記錄每一個字符出現的次數intch=cin.get();inti=0;while((ch!='\r')&&(ch!='\n')){nNum[ch]++;//統計字符出現的次數str[i++]=ch;//記錄原始字符串ch=cin.get();//讀取下一個字符}str[i]='\0';n=0;4-for(i=0;i<256;i++){if(nNum[i]>0)//若nNum[i]==0，字符未出現{l[n]=(char)i;a[n]=nNum[i];n++;}}}時間復雜度為O（1）；2）創立哈夫曼樹：算法過程：Huffman樹采納次序存儲數組；數組的前n個結點存儲葉子結點，今后是分支結點，最后是根結點；第一初始化葉子結點元素—循環實現；以循環結構，實現分支結點的合成，合成規則依據huffman樹組成規則進行。重點點：選擇最小和次小結點合成。voidHuffman::CreateHTree(){HTree=newHNode[2*n-1];//依據權重數組a[0..n-1]初始化Huffman樹for(intj=0;j<n;j++)5-{HTree[j].weight=a[j];HTree[j].LChild=HTree[j].RChild=HTree[j].parent=-1;}intx,y;for(inti=n;i<2*n-1;i++)//開始建Huffman樹{SelectMin(HTree,i,x,y);//從1~i中選出兩個權值最小的結點HTree[x].parent=HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight;HTree[i].LChild=x;HTree[i].RChild=y;HTree[i].parent=-1;}}2時間復雜度為O(n)voidHuffman::SelectMin(HNode*hTree,intn,int&i1,int&i2){inti;找一個比較值的初步值for(i=0;i<n;i++)//找i1{if(hTree[i].parent==-1)6-{i1=i;break;}}i++;for(;i<n;i++)//找i2{if(hTree[i].parent==-1){i2=i;break;}}if(hTree[i1].weight>hTree[i2].weight)//i1指向最小的{intj=i2;i2=i1;i1=j;}開始找最小的兩個i++;for(;i<n;i++){if(hTree[i].parent==-1&&hTree[i].weight<hTree[i1].weight){i2=i1;i1=i;}elseif(hTree[i].parent==-1hTree[i].weight<hTree[i2].weight){i2=i;}}}時間復雜度為O(n)創立編碼表7-算法過程：從葉子到根自底向上第必然義碼表存儲空間；循環對n個葉子結點自底向上回溯到根，記下門路的左右關系，形成編碼的逆序串；將各個葉子結點對應的逆序串反序即可。voidHuffman::CreateCodeTable(){HCodeTable=newHCode[n];//生成編碼表for(inti=0;i<n;i++){HCodeTable[i].data=l[i];intchild=i;//孩子結點編號intparent=HTree[i].parent;//目前結點的父結點編號intk=0;while(parent!=-1){if(child==HTree[parent].LChild)//左孩子標‘0’HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';//右孩子標‘1’k++;child=parent;//迭代parent=HTree[child].parent;8-}HCodeTable[i].code[k]='\0';Reverse(HCodeTable[i].code);//將編碼字符逆置}}時間復雜度為O(n)生成編碼串將輸入的字符串的每一個字符與編碼表比較voidHuffman::Encode(char*d)//編碼，d為編碼后的字符串{char*s=str;while(*s!='\0'){for(inti=0;i<n;i++)if(*s==HCodeTable[i].data){strcat(d,HCodeTable[i].code);break;}s++;}9-}時間復雜度為O(n)（5）解碼:算法過程：從根到葉子自頂向下鑒于huffman樹存儲數組，從根結點開始，依據輸入待解碼串s中碼字0或1，分別向左或右追蹤至葉子結點，葉子結點對應的字符（見碼表），即為解碼獲得的字符；只需s串為結束，重復上述過程voidHuffman::Decode(char*s,char*d)//解碼，s為編碼串，d為解碼后的字符串{while(*s!='\0'){intparent=2*n-2;//根結點在HTree中的下標while(HTree[parent].LChild!=-1)//假如不是葉子結點{if(*s=='0')parent=HTree[parent].LChild;elseparent=HTree[parent].RChild;s++;}*d=HCodeTable[parent].data;d++;10-}}時間復雜度為O（n）2.3其余（1）哈夫曼樹的輸出是以凹入表示法來實現的，詳細算法以下：voidHuffman::Print(inti,intm){if(HTree[i].LChild==-1)cout<<setfill('')<<setw(m+1)<<l[i]<<setfill('-')<<setw(10-m)<<'\n';else{cout<<setfill('')<<setw(m+1)<<HTree[i].weight<<setfill('-')<<setw(10-m)<<'\n';Print(HTree[i].LChild,m+1);Print(HTree[i].RChild,m+1);}}（2）統計字符頻數時，利用字符的ASCII碼進行計數統計，調用了cin.get()函數程序運轉程序框圖：開始輸入要編碼的字符串統計字符頻數生成哈夫曼樹11-創立編碼表生成編碼串解碼結束程序源代碼：#include<iostream>#include<iomanip>usingnamespacestd;structHNode{intweight;//結點權值intparent;//雙親指針intLChild;//左孩子指針intRChild;//右孩子指針};structHCode{chardata;charcode[100];};classHuffman{private:HNode*HTree;//Huffman樹HCode*HCodeTable;//Huffman編碼表charstr[1024];//輸入的原始字符串charl[256];//葉子節點對應的字符inta[256];//記錄每個出現的字符的個數public:intn;//葉子節點數12-voidInit();//初始化voidCreateHTree();//創立huffman樹voidCreateCodeTable();//創立編碼表voidPrintTable();voidEncode(char*d);//編碼voidDecode(char*s,char*d);//解碼voidPrint(inti,intm);//打印Huffman樹voidSelectMin(HNode*hTree,intn,int&i1,int&i2);//找出最小的兩個權值voidReverse(char*s);//逆序voidCompare(char*d);//比較壓縮大小~Huffman();//析構};voidHuffman::Init(){intnNum[256]={0};//記錄每一個字符出現的次數intch=cin.get();inti=0;while((ch!='\r')&&(ch!='\n')){nNum[ch]++;//統計字符出現的次數str[i++]=ch;//記錄原始字符串ch=cin.get();//讀取下一個字符}str[i]='\0';n=0;for(i=0;i<256;i++){if(nNum[i]>0)//若nNum[i]==0，字符未出現{l[n]=(char)i;a[n]=nNum[i];n++;}}}voidHuffman::CreateHTree(){HTree=newHNode[2*n-1];//依據權重數組a[0..n-1]初始化Huffman樹for(intj=0;j<n;j++){13-HTree[j].weight=a[j];HTree[j].LChild=HTree[j].RChild=HTree[j].parent=-1;}intx,y;for(inti=n;i<2*n-1;i++)//開始建Huffman樹{SelectMin(HTree,i,x,y);//從1~i中選出兩個權值最小的結點HTree[x].parent=HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight;HTree[i].LChild=x;HTree[i].RChild=y;HTree[i].parent=-1;}}voidHuffman::SelectMin(HNode*hTree,intn,int&i1,int&i2){inti;//找一個比較值的初步值for(i=0;i<n;i++)//找i1{if(hTree[i].parent==-1){i1=i;break;}}i++;for(;i<n;i++)//找i2{if(hTree[i].parent==-1){i2=i;break;}}if(hTree[i1].weight>hTree[i2].weight)//i1指向最小的{intj=i2;i2=i1;i1=j;}//開始找最小的兩個i++;for(;i<n;i++){if(hTree[i].parent==-1hTree[i].weight<hTree[i1].weight){i2=i1;i1=i;}elseif(hTree[i].parent==-1hTree[i].weight<hTree[i2].weight){i2=i;}}}voidHuffman::Print(inti,intm){if(HTree[i].LChild==-1)14-cout<<setfill('')<<setw(m+1)<<l[i]<<setfill('-')<<setw(10-m)<<'\n';else{cout<<setfill('')<<setw(m+1)<<HTree[i].weight<<setfill('-')<<setw(10-m)<<'\n';Print(HTree[i].LChild,m+1);Print(HTree[i].RChild,m+1);}}voidHuffman::CreateCodeTable(){HCodeTable=newHCode[n];//生成編碼表for(inti=0;i<n;i++){HCodeTable[i].data=l[i];intchild=i;//孩子結點編號intparent=HTree[i].parent;//目前結點的父結點編號intk=0;while(parent!=-1){if(child==HTree[parent].LChild)//左孩子標‘0’HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';//右孩子標‘1’k++;child=parent;//迭代parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';Reverse(HCodeTable[i].code);//將編碼字符逆置}}voidHuffman::PrintTable(){for(inti=0;i<n;i++)cout<<HCodeTable[i].data<<'\t'<<HCodeTable[i].code<<endl;}voidHuffman::Encode(char*d)//編碼，d為編碼后的字符串{char*s=str;while(*s!='\0'){for(inti=0;i<n;i++)15-if(*s==HCodeTable[i].data){strcat(d,HCodeTable[i].code);break;}s++;}}voidHuffman::Decode(char*s,char*d)//解碼，s為編碼串，d為解碼后的字符串{while(*s!='\0'){intparent=2*n-2;//根結點在HTree中的下標while(HTree[parent].LChild!=-1)//假如不是葉子結點{if(*s=='0')parent=HTree[parent].LChild;elseparent=HTree[parent].RChild;s++;}*d=HCodeTable[parent].data;d++;}}voidHuffman::Reverse(char*s)//換序{charch;intlen=strlen(s);for(inti=0;i<len/2;i++){ch=s[i];s[i]=s[len-i-1];s[len-i-1]=ch;}}voidHuffman::Compare(char*d)//比較壓縮大小{cout<<"編碼前："<<strlen(str)*8<<"bit"<<endl;cout<<"編碼后："<<strlen(d)<<"bit"<<endl;16-}Huffman::~Huffman()//析構函數{delete[]HTree;delete[]HCodeTable;}voidmain(){HuffmanHFCode;chard[1024]={0};chars[1024]={0};cout<<"請輸入要編碼的字符串：";HFCode.Init();HFCode.CreateHTree();HFCode.CreateCodeTable();HFCode.Encode(d);HFCode.Decode(d,s);intm;cout<<