北郵數據結構實驗3哈夫曼編碼

數據結構實驗報告實驗名稱：實驗3——哈夫曼編碼學生姓名：班 級：班內序號：學 號：日 期：2013年11月24日1.實驗要求利用二叉樹結構實現赫夫曼編/解碼器?；疽螅?、 初始化(Init):能夠對輸入的任意長度的字符串s進行統計，統計每個字符的頻度，并建立赫夫曼樹2、 建立編碼表(CreateTable)：利用已經建好的赫夫曼樹進行編碼，并將每個字符的編碼輸出。3、 編碼(Encoding)：根據編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出。4、 譯碼(Decoding)：利用已經建好的赫夫曼樹對編碼后的字符串進行譯碼，并輸出譯碼結果。5、 打印(Print):以直觀的方式打印赫夫曼樹(選作)6、 計算輸入的字符串編碼前和編碼后的長度，并進行分析，討論赫夫曼編碼的壓縮效果。2.程序分析2.1存儲結構：structHNode{charc;//存字符內容intweight;intlchild,rchild,parent;};structHCodechardata;charcode[100];}；//字符及其編碼結構classHuffman{private:HNode*huffTree;//Huffman樹HCode*HCodeTable;//Huffman編碼表public:Huffman(void);voidCreateHTree(inta[],intn);//創(chuàng)建huffman樹voidCreateCodeTable(charb[],intn);//創(chuàng)建編碼表voidEncode(char*s,string*d);〃編碼voidDecode(char*s,char*d);//解碼voiddiffer(char*,intn);charstr2[100];//數組中不同的字符組成的串intdif;//str2[]的大小~Huffman(void);};結點結構為如下所示:三叉樹的節(jié)點結構：structHNode//哈夫曼樹結點的結構體{ intweight;//結點權值intparent;//雙親指針intlchild;//左孩子指針intrchild;//右孩子指針chardata;//字符};示意圖為：intweightintparentintlchildintrchildCharc編碼表節(jié)點結構：structHCode//編碼表結構體{chardata;//字符charcode[100];//編碼內容}；示意圖為：chardatacharcode[100]基本結構體記錄字符和出現次數:structnode{intnum;chardata;};示意圖為:intnumchardata2.關鍵算法分析(1).初始化：偽代碼：輸入需要編譯的文本內容將輸入的內容保存到數組str1中統計出現的字符數目，并且保存到變量count中統計出現的不同的字符，存到str2中，將str2的大小存到dif中時間復雜度O(n！).創(chuàng)建哈夫曼樹算法偽代碼：創(chuàng)建一個長度為2*n-1的三叉鏈表將存儲字符及其權值的鏈表中的字符逐個寫入三叉鏈表的前n個結點的data域，并將對應結點的孩子域和雙親域賦為空從三叉鏈表的第n個結點開始，3.1從存儲字符及其權值的鏈表中取出兩個權值最小的結點x,y，記錄其下標x,y。3.2將下標為x和y的哈夫曼樹的結點的雙親設置為第i個結點3.3將下標為x的結點設置為i結點的左孩子，將下標為y的結點設置為i結點的右孩子，i結點的權值為x結點的權值加上y結點的權值，i結點的雙親設置為空根據哈夫曼樹創(chuàng)建編碼表時間復雜度O(n).創(chuàng)建編碼表算法偽代碼：初始化編碼表初始化一個指針，從鏈表的頭結點開始，遍歷整個鏈表2.1將鏈表中指針當前所指的結點包含的字符寫入編碼表中2.2得到該結點對應的哈夫曼樹的葉子結點及其雙親2.3如果哈夫曼樹只有一個葉子結點，將其字符對應編碼設置為02.4如果不止一個葉子結點，從當前葉子結點開始判斷2.4.1如果當前葉子結點是其雙親的左孩子，則其對應的編碼為0，否則為12.4.2child指針指向葉子結點的雙親，parent指針指向child指針的雙親，重復2.4.1的操作2.5將已完成的編碼倒序2.6取得鏈表中的下一個字符輸出編碼表時間復雜度O(n)選擇兩個最小權值的函數算法偽代碼：從下標為i=0的開始遍歷。前兩次將x，y賦值為序號最小的兩個結點的地址序號。開始進行比較：進行如下分類對于任何不存在父節(jié)點的結點：若x權值＜=y權值且i權值＞=y權值，貝9無疑i權值最大，為輸出x、y為權值較小的兩個故而x，y值不便；其余情況皆為x、i的權值是較小的兩個，令y賦值為i，則保證x、y權值是最小的兩個。若y權值＜=x權值且i權值＞=x權值，則i權值是最大，x、y不變。其余情況皆為i、y權值最小，令x賦值為i，保證x、y序號結點的權值最小完成如上循環(huán)，直至i=k則推出循環(huán)，第k個結點在樹的位置已經確定時間復雜度O(n).將字符串倒序的函數(voidHuffmanTree::Reverse(char*pch))算法偽代碼：得到字符串的長度初始化兩個記錄下標的變量，一個為字符串開頭字符所在的下標i，另一個為字符串結尾字符所在的下標j將下標為i和j的字符交換i++,j--時間復雜度O(n).編碼函數算法偽代碼：從開頭的字符開始，逐一對a中的字符進行編碼在編碼表中查找與當前字符對應的字符如果找到了與當前字符對應的編碼表中的字符，將其編碼追加到解碼串的末尾。重復以上步驟，直到所有待編碼串中的字符都編碼完畢輸出編碼后的字符串時間復雜度O(n)(7),解碼函數(voidHuffman::Decode())算法偽代碼：得到指向哈夫曼樹的根結點的指針和指向待解碼串中的第1個字符的指針逐個讀取待解碼串中的字符，若為0,則指向哈夫曼樹當前結點的指針指向當前結點的左孩子，若為1，則指向當前結點的右孩子指向待解碼串的指針指向解碼串中的下一個字符，直到指向哈夫曼樹結點的指針的孩子結點為空如果哈夫曼樹只有一個葉子結點，直接將待解碼串中的編碼轉換為對應的字符如果指向哈夫曼樹結點的指針的孩子結點已經為空，則將葉子結點下標對應的字符追加到解碼串中。輸出解碼串時間復雜度O(n)程序運行結果1.主函數流程圖

C:\Windoww'qystem32\cmd.exe請送擇功能”輸入編詩字符呂Z喻出編袒表3輸出字符串編誦及玉縮比4解毋X底出）1請輸KIlouedataStructure.IloueComputer.IwilltrympbesttostuidpdataStpucture隋訝擇（1繼續(xù)運行聘溟出）1請遂擇功能（1輸入編譯字符呂2喻出編袒表3輸出宇符串編碼茨玉縮LL4解有S退出）nueij(htLChildRChildparentcharcade&13-1-14111111-1-1陰r-Bl1BQB22-1-12&■Q311G31-1123c011OS143-1-130I01111b2-1-12bsMU11164-1-132a09Q071-1-124b011010R2-1-1S7二R1RRfi93-1-131d11S1610C-113Gc1310111-11241011011124-1-132109S1132-1-1k7nm皿144-1-133o0310151-1-125D011160166-1-11*1?11172-1-1283Q1S1G1811-1140t19B196-1-137unee2U2-1-12UuMltdll211-1-125VI011161223-1-131y11011J?32133924271129VJ3252152136N02G42533N327431334\9ZU417ZM34\a294232435\330525435\3316922明328%12^38

main.cpp#include"huffman.h”voidmain(){HuffmanH;inti;charstr1[100]={'\0'};stringd;intcount=0;do{cout<<"請選擇功能（輸入編譯字符串2輸出編碼表3輸出字符串編碼及壓縮比4解碼5退出）"<<endl;intn;cin>>n;charch='a';cin.get(ch);switch(n){case1:{cout<<”請輸入”<<endl;cin.getline(str1,100);intm=0;while(str1[m++])count++;}break;case2:{H.differ(str1,count);H.CreateCodeTable(H.str2,H.dif);}break;case3:{H.Encode(str1,&d);}break;case4:{cout<<"請輸入解碼數據"<<endl;chars[200]=('\0'};chard[100]=('\0'};cin.getline(s,200,'\n');H.Decode(s,d);cout<<"解碼數據為："<<d<<endl;}break;case5:break;default:cout<<'請輸入正確序號”<<endl;break;}cout<<"請選擇(繼續(xù)運行0退出)"<<endl;cin>>i;}while(i);cout<<”謝謝使用”<<endl;}huffman.h#pragmaonce#include<iostream>#include<string>#include<iomanip>usingnamespacestd;structHNode{charc;//存字符內容intweight;intlchild,rchild,parent;};structHCode{chardata;charcode[100];};〃字符及其編碼結構classHuffman{private:HNode*huffTree;//Huffman樹HCode*HCodeTable;//Huffman編碼表public:Huffman(void);voidCreateHTree(inta[],intn);//創(chuàng)建huffman樹voidCreateCodeTable(charb[],intn);//創(chuàng)建編碼表voidEncode(char*s,string*d);〃編碼voidDecode(char*s,char*d);//解碼voiddiffer(char*,intn);charstr2[100];//數組中不同的字符組成的串intdif;//str2[]的大小~Huffman(void);};huffman.cpp#include"huffman.h"Huffman::Huffman(void){}voidSelect(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;j=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==-1&&hTree[i].weight<hTree[i2].weight){i2=i;}}}voidReverse(charc[]){intn=0;chartemp;while(c[n+1]!='\0')//統計字符個數{n++;}for(inti=0;i<=n/2;i++){temp=c[i];c[i]=c[n-i];c[n-i]=temp;}}〃找到只含有不同字符的數組，權重及其大小voidHuffman::differ(char*str,intn){char*temp=newchar[n];//申請動態(tài)數組存儲字符串以便之后對字符串排序for(inti=0;i<n;i++){temp[i]=*(str+i);}charctemp;for(inti=0;i<n-1;i++)//冒泡排序法,排序以后方便統計不同字符串出現的個數{for(intj=0;j<n-1-i;j++){if(temp[j]>temp[j+1]){ctemp=temp[j];temp[j]=temp[j+1];temp[j+1]=ctemp;}}}dif=1;for(inti=1;i<n;i++)//統計不同字符個數{if(temp[i]!=temp[i-1]){dif++;}int*a=newint[dif];//用a[dif]來統計權重intl=0;//統計不同字符出現的頻度intk=0;//控制哈夫曼數組下標ctemp=temp[0];//做標記for(inti=0;i<=n;i++)//因為巳經排序了{if(temp[i]==ctemp){l++;//統計同字符出現的頻度if(i==n-1)a[k]=l;}else{str2[k]=ctemp;a[k]=l;ctemp=temp[i];k++;l=1;}}delete[]temp;//釋放動態(tài)內存空間CreateHTree(a,dif);}voidHuffman::CreateHTree(inta[],intn){ 〃根據權重數組a[1到n]初始化Huffman樹huffTree=newHNode[2*n-1];for(inti=0;i<n;i++){huffTree[i].weight=a[i];huffTree[i].lchild=-1;huffTree[i].rchild=-1;huffTree[i].parent=-1;huffTree[i].c=str2[i];}intli,ri;for(inti=n;i<2*n-1;i++)〃開始建Huffman樹{ 〃從?i-1中選出兩個權值最小的結點，Select(huffTree,i,li,ri);huffTree[li].parent=huffTree[ri].parent=i;huffTree[i].weight=huffTree[li].weight+huffTree[ri].weight;huffTree[i].lchild=li;huffTree[i].rchild=ri;huffTree[i].parent=-1;huffTree[i].c='\0';}}voidHuffman::CreateCodeTable(charb[],intn){HCodeTable=newHCode[n];//申請與不同字符個數對應的動態(tài)空間，以存儲不同字符代表的編碼for(inti=0;i<n;i++){HCodeTable[i].data=huffTree[i].c;intic=i;intip=huffTree[i].parent;intk=0;while(ip!=-1){if(ic==huffTree[ip].lchild)//左孩子標"HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';〃右孩子標‘’k++;ic=ip;ip=huffTree[ic].parent;}HCodeTable[i].code[k]='\0';//字符編碼串最后添加結束符Reverse(HCodeTable[i].code);}cout<<setiosflags(ios::left)<<setw(5)<<"n"<<setw(12)<<"weight"<<setw(12)<<"LChild"<<setw(12)<<"RChild"<<setw(12)<<"parent"<<setw(12)<<"char"<<setw(12)<<"code"<<endl;for(inti=0;i<2*dif-1;i++){if(i<dif){cout<<setiosflags(ios::left)<<setw(5)<<i<<setw(12)<< huffTree[i].weight<<setw(12)<<huffTree[i].lchild<<setw(12)<< huffTree[i].rchild<<setw(12)<<huffTree[i].parent<<setw(12)<<HCodeTable[i].data<<setw(12)<<HCodeTable[i].code<<endl;}elsecout<<setiosflags(ios::left)<<setw(5)<<i<<setw(12)<< huffTree[i].weight<<setw(12)<<huffTree[i].lchild<<setw(12)<< huffTree[i].rchild<<setw(12)<<huffTree[i].parent<<setw(12)<<"\\0”<<setw