北郵信通院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告三哈夫曼編碼器

1、.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)三 樹哈夫曼編/解碼器學(xué)生姓名： 班 級(jí)： 班內(nèi)序號(hào)： 學(xué) 號(hào)： 日 期： 2014年12月11日1實(shí)驗(yàn)要求利用二叉樹結(jié)構(gòu)實(shí)現(xiàn)赫夫曼編/解碼器?；疽螅?、 初始化(Init)：能夠?qū)斎氲娜我忾L(zhǎng)度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立赫夫曼樹2、 建立編碼表(CreateTable)：利用已經(jīng)建好的赫夫曼樹進(jìn)行編碼，并將每個(gè)字符的編碼輸出。3、 編碼(Encoding)：根據(jù)編碼表對(duì)輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。4、 譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹對(duì)編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。5、 打印(Print)：

2、以直觀的方式打印赫夫曼樹（選作）6、 計(jì)算輸入的字符串編碼前和編碼后的長(zhǎng)度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。測(cè)試數(shù)據(jù)： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用戶界面可以設(shè)計(jì)為“菜單”方式：能夠進(jìn)行交互。 2、根據(jù)輸入的字符串中每個(gè)字符出現(xiàn)的次數(shù)統(tǒng)計(jì)頻度，對(duì)沒(méi)有出現(xiàn)的字符一律不用編碼。2. 程序分析2.1 存儲(chǔ)結(jié)構(gòu)Huffman樹給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，可以構(gòu)造出不同的二叉樹，其中帶權(quán)路徑長(zhǎng)度最小的二叉樹稱為Huffman樹，也叫做最優(yōu)二叉樹

3、。 weight lchild rchild parent2-1-1-15-1-1-16-1-1-17-1-1-19-1-1-1weight lchild rchild parent2-1-155-1-156-1-167-1-169-1-17701713238165482967-12.2 關(guān)鍵算法分析（1）計(jì)算出現(xiàn)字符的權(quán)值 利用ASCII碼統(tǒng)計(jì)出現(xiàn)字符的次數(shù)，再將未出現(xiàn)的字符進(jìn)行篩選，將出現(xiàn)的字符及頻數(shù)存儲(chǔ)在數(shù)組a中。 void Huffman:Init()int nNum256= 0; /記錄每一個(gè)字符出現(xiàn)的次數(shù)int ch = cin.get(); int i=0; while(ch!=

4、r) & (ch!=n)nNumch+; /統(tǒng)計(jì)字符出現(xiàn)的次數(shù)stri+ = ch; /記錄原始字符串ch = cin.get(); /讀取下一個(gè)字符stri=0; n = 0; for ( i=0;i0) /若nNumi=0，字符未出現(xiàn)ln = (char)i; an = nNumi; n+;時(shí)間復(fù)雜度為O（1）；（2）創(chuàng)建哈夫曼樹：算法過(guò)程： Huffman樹采用順序存儲(chǔ)-數(shù)組； 數(shù)組的前n個(gè)結(jié)點(diǎn)存儲(chǔ)葉子結(jié)點(diǎn)，然后是分支結(jié)點(diǎn)，最后是根結(jié)點(diǎn)； 首先初始化葉子結(jié)點(diǎn)元素循環(huán)實(shí)現(xiàn)； 以循環(huán)結(jié)構(gòu)，實(shí)現(xiàn)分支結(jié)點(diǎn)的合成，合成規(guī)則按照huffman樹構(gòu)成規(guī)則進(jìn)行。 關(guān)鍵點(diǎn)：選擇最小和次小結(jié)點(diǎn)合成。 voi

5、d Huffman:CreateHTree()HTree = new HNode 2*n-1; /根據(jù)權(quán)重?cái)?shù)組a0.n-1 初始化Huffman樹for (int j = 0; j n; j+) HTreej.weight = aj;HTreej.LChild = HTreej.RChild = HTreej.parent = -1; int x,y; for (int i = n; i 2*n-1; i+) /開始建Huffman樹 SelectMin( HTree, i, x, y); /從1i中選出兩個(gè)權(quán)值最小的結(jié)點(diǎn)HTreex.parent = HTreey.parent = i;HT

6、reei.weight = HTreex.weight+ HTreey.weight;HTreei.LChild = x;HTreei.RChild = y;HTreei.parent = -1;時(shí)間復(fù)雜度為O(n2)void Huffman:SelectMin( HNode *hTree,int n, int &i1, int &i2 ) int i; /找一個(gè)比較值的起始值 for(i=0; in; i+) /找i1 if(hTreei.parent=-1 ) i1=i; break; i+; for( ; ihTreei2.weight) /i1指向最小的 int j=i2; i2=i1

7、; i1 = j; /開始找最小的兩個(gè) i+; for( ; in; i+) if(hTreei.parent=-1 & hTreei.weight hTreei1.weight ) i2=i1; i1 = i; else if( hTreei.parent=-1 & hTreei.weight hTreei2.weight) i2=i; 時(shí)間復(fù)雜度為O(n)(3)創(chuàng)建編碼表算法過(guò)程：從葉子到根-自底向上 首先定義碼表存儲(chǔ)空間； 循環(huán)對(duì)n個(gè)葉子結(jié)點(diǎn)自底向上回溯到根，記下途徑的左右關(guān)系，形成編碼的逆序串； 將各個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的逆序串反序即可。 void Huffman:CreateCodeTab

8、le() HCodeTable = new HCoden; /生成編碼表for (int i=0;in;i+)HCodeTablei.data = li; int child = i;/孩子結(jié)點(diǎn)編號(hào) int parent = HTreei.parent; /當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào) int k=0; while(parent!=-1) if (child=HTreeparent.LChild) /左孩子標(biāo)0 HCodeTablei.codek = 0; else HCodeTablei.codek = 1 ; /右孩子標(biāo)1 k+; child = parent;/迭代 parent = HTree

9、child.parent;HCodeTablei.codek = 0;Reverse(HCodeTablei.code); /將編碼字符逆置 時(shí)間復(fù)雜度為O(n)(4)生成編碼串將輸入的字符串的每一個(gè)字符與編碼表比較void Huffman:Encode(char *d)/編碼，d為編碼后的字符串 char *s = str; while(*s!=0)for (int i=0;in;i+)if (*s = HCodeTablei.data )strcat(d, HCodeTablei.code); break;s+;時(shí)間復(fù)雜度為O(n)（5）解碼:算法過(guò)程： 從根到葉子-自頂向下 基于huff

10、man樹存儲(chǔ)數(shù)組，從根結(jié)點(diǎn)開始，依據(jù)輸入待解碼串s中碼字0或1，分別向左或右跟蹤至葉子結(jié)點(diǎn)，葉子結(jié)點(diǎn)對(duì)應(yīng)的字符（見(jiàn)碼表），即為解碼得到的字符； 只要s串為結(jié)束，重復(fù)上述過(guò)程 void Huffman:Decode(char* s, char *d) /解碼，s為編碼串，d為解碼后的字符串 while(*s!=0)int parent = 2*n-2; /根結(jié)點(diǎn)在HTree中的下標(biāo) while (HTreeparent.LChild!=-1) /如果不是葉子結(jié)點(diǎn)if (*s=0) parent = HTreeparent.LChild; else parent = HTreeparent.RCh

11、ild;s+;*d = HCodeTableparent.data;d+;時(shí)間復(fù)雜度為O（n） 2.3 其他 （1）哈夫曼樹的輸出是以凹入表示法來(lái)實(shí)現(xiàn)的，具體算法如下：void Huffman:Print(int i, int m)if (HTreei.LChild = -1)coutsetfill( )setw(m+1)lisetfill(-)setw(10-m)n;elsecoutsetfill( )setw(m+1)HTreei.weightsetfill(-)setw(10-m)n;Print(HTreei.LChild,m+1);Print(HTreei.RChild,m+1);（2

12、）統(tǒng)計(jì)字符頻數(shù)時(shí)，利用字符的ASCII碼進(jìn)行計(jì)數(shù)統(tǒng)計(jì)，調(diào)用了cin.get()函數(shù)開始3. 程序運(yùn)行程序框圖：輸入要編碼的字符串統(tǒng)計(jì)字符頻數(shù)生成哈夫曼樹創(chuàng)建編碼表生成編碼串解碼結(jié)束程序源代碼：#include #include using namespace std;struct HNode int weight; /結(jié)點(diǎn)權(quán)值 int parent; /雙親指針int LChild; /左孩子指針int RChild ; /右孩子指針; struct HCode char data;char code100; ;class Huffmanprivate: HNode* HTree; /Huff

13、man樹 HCode* HCodeTable; /Huffman編碼表char str1024; /輸入的原始字符串char l256; /葉子節(jié)點(diǎn)對(duì)應(yīng)的字符int a256; /記錄每個(gè)出現(xiàn)的字符的個(gè)數(shù)public: int n; /葉子節(jié)點(diǎn)數(shù)void Init(); /初始化 void CreateHTree(); /創(chuàng)建huffman樹 void CreateCodeTable(); /創(chuàng)建編碼表void PrintTable(); void Encode(char *d); /編碼void Decode(char *s, char *d); /解碼void Print(int i,in

14、t m); /打印Huffman樹 void SelectMin( HNode *hTree,int n, int &i1, int &i2);/找出最小的兩個(gè)權(quán)值void Reverse(char* s); /逆序void Compare(char*d); /比較壓縮大小 Huffman(); /析構(gòu);void Huffman:Init()int nNum256= 0; /記錄每一個(gè)字符出現(xiàn)的次數(shù)int ch = cin.get(); int i=0; while(ch!=r) & (ch!=n)nNumch+; /統(tǒng)計(jì)字符出現(xiàn)的次數(shù)stri+ = ch; /記錄原始字符串ch = cin.

15、get(); /讀取下一個(gè)字符stri=0; n = 0; for ( i=0;i0) /若nNumi=0，字符未出現(xiàn)ln = (char)i; an = nNumi; n+;void Huffman:CreateHTree()HTree = new HNode 2*n-1; /根據(jù)權(quán)重?cái)?shù)組a0.n-1 初始化Huffman樹for (int j = 0; j n; j+) HTreej.weight = aj;HTreej.LChild = HTreej.RChild = HTreej.parent = -1; int x,y; for (int i = n; i 2*n-1; i+) /開

16、始建Huffman樹 SelectMin( HTree, i, x, y); /從1i中選出兩個(gè)權(quán)值最小的結(jié)點(diǎn)HTreex.parent = HTreey.parent = i;HTreei.weight = HTreex.weight+ HTreey.weight;HTreei.LChild = x;HTreei.RChild = y;HTreei.parent = -1;void Huffman:SelectMin( HNode *hTree,int n, int &i1, int &i2 ) int i; /找一個(gè)比較值的起始值 for(i=0; in; i+) /找i1 if(hTre

17、ei.parent=-1 ) i1=i; break; i+; for( ; ihTreei2.weight) /i1指向最小的 int j=i2; i2=i1; i1 = j; /開始找最小的兩個(gè) i+; for( ; in; i+) if(hTreei.parent=-1 & hTreei.weight hTreei1.weight ) i2=i1; i1 = i; else if( hTreei.parent=-1 & hTreei.weight hTreei2.weight) i2=i; void Huffman:Print(int i, int m)if (HTreei.LChild

18、 = -1)coutsetfill( )setw(m+1)lisetfill(-)setw(10-m)n;elsecoutsetfill( )setw(m+1)HTreei.weightsetfill(-)setw(10-m)n;Print(HTreei.LChild,m+1);Print(HTreei.RChild,m+1);void Huffman:CreateCodeTable() HCodeTable = new HCoden; /生成編碼表for (int i=0;in;i+)HCodeTablei.data = li; int child = i;/孩子結(jié)點(diǎn)編號(hào) int paren

19、t = HTreei.parent; /當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào) int k=0; while(parent!=-1) if (child=HTreeparent.LChild) /左孩子標(biāo)0 HCodeTablei.codek = 0; else HCodeTablei.codek = 1 ; /右孩子標(biāo)1 k+; child = parent;/迭代 parent = HTreechild.parent;HCodeTablei.codek = 0;Reverse(HCodeTablei.code); /將編碼字符逆置 void Huffman:PrintTable()for (int i=0;

20、in;i+)coutHCodeTablei.datatHCodeTablei.codeendl;void Huffman:Encode(char *d)/編碼，d為編碼后的字符串 char *s = str; while(*s!=0)for (int i=0;in;i+)if (*s = HCodeTablei.data )strcat(d, HCodeTablei.code); break;s+;void Huffman:Decode(char* s, char *d) /解碼，s為編碼串，d為解碼后的字符串 while(*s!=0)int parent = 2*n-2; /根結(jié)點(diǎn)在HTre

21、e中的下標(biāo) while (HTreeparent.LChild!=-1) /如果不是葉子結(jié)點(diǎn)if (*s=0) parent = HTreeparent.LChild; else parent = HTreeparent.RChild;s+;*d = HCodeTableparent.data;d+;void Huffman:Reverse(char* s)/換序char ch;int len = strlen(s);for (int i=0;ilen/2;i+)ch = si;si = slen-i-1;slen-i-1 = ch;void Huffman:Compare(char*d)/比較壓縮大小cout編碼前：strlen(str)*8bitendl;cout編碼后：strlen(d)bitendl;Huffman: Huffman()/析構(gòu)函數(shù) delete HTree;delete HCodeTable; void main()Huffman HFCode;char d1024=0;char s1024=0;cout請(qǐng)輸入要編碼的字符串：;HFCode.Init();HFCode.CreateHTree();HFCode.CreateCodeTable();HFCode.Encode(d);H