北京郵電大學(xué)信通院數(shù)據(jù)結(jié)構(gòu)實驗三-哈夫曼樹實驗報告

./2009級數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗三——哈夫曼編/解碼器的實現(xiàn)學(xué)生：聰捷日期：2010年11月28日1．實驗要求一、實驗?zāi)康模毫私夤蚵鼧涞乃枷牒拖嚓P(guān)概念；二、實驗容：利用二叉樹結(jié)構(gòu)實現(xiàn)哈夫曼編/解碼器1.初始化：能夠?qū)斎氲娜我忾L度的字符串s進行統(tǒng)計,統(tǒng)計每個字符的頻度,并建立哈夫曼樹。2.建立編碼表：利用已經(jīng)建好的哈夫曼樹進行編碼,并將每個字符的編碼輸出。3.編碼：根據(jù)編碼表對輸入的字符串進行編碼,并將編碼后的字符串輸出。4.譯碼：利用已經(jīng)建好的哈夫曼樹對編碼后的字符串進行譯碼,并輸出譯碼結(jié)果。5.打?。阂灾庇^的方式打印哈夫曼樹。6.計算輸入的字符串編碼前和編碼后的長度,并進行分析,討論哈夫曼編碼的壓縮效果。7.用戶界面可以設(shè)計成"菜單"方式,能進行交互,根據(jù)輸入的字符串中每個字符出現(xiàn)的次數(shù)統(tǒng)計頻度,對沒有出現(xiàn)的字符一律不用編碼。2.程序分析2.1存儲結(jié)構(gòu)二叉樹template<classT>classBiTree{public:BiTree<>; //構(gòu)造函數(shù),其前序序列由鍵盤輸入~BiTree<void>; //析構(gòu)函數(shù)BiNode<T>*Getroot<>; //獲得指向根結(jié)點的指針protected:BiNode<T>*root; //指向根結(jié)點的頭指針};//聲明類BiTree及定義結(jié)構(gòu)BiNodeData：二叉樹是由一個根結(jié)點和兩棵互不相交的左右子樹構(gòu)成二叉樹中的結(jié)點具有相同數(shù)據(jù)類型及層次關(guān)系示意圖：rootlchildparentrchild哈夫曼樹類的數(shù)據(jù)域,繼承節(jié)點類型為int的二叉樹classHuffmanTree:publicBiTree<int>data: HCode*HCodeTable;//編碼表 inttSize;//編碼表中的總字符數(shù)二叉樹的節(jié)點結(jié)構(gòu)template<classT>structBiNode//二叉樹的結(jié)點結(jié)構(gòu){ Tdata;//記錄數(shù)據(jù) Tlchild;//左孩子 Trchild;//右孩子 Tparent;//雙親};示意圖：TparentTrchildTlchildTdataTparentTrchildTlchildTdata編碼表的節(jié)點結(jié)構(gòu)structHCode{ chardata;//編碼表中的字符 charcode[100];//該字符對應(yīng)的編碼};示意圖：charcode[100]chardatacharcode[100]chardata待編碼字符串由鍵盤輸入,輸入時用鏈表存儲,鏈表節(jié)點為structNode{ charcharacter;//輸入的字符 unsignedintcount;//該字符的權(quán)值 boolused;//建立樹的時候該字符是否使用過 Node*next;//保存下一個節(jié)點的地址};Node*nextboolusedunsignedintcountcharcharacter示意圖：Node*nextboolusedunsignedintcountcharcharacter2.2關(guān)鍵算法分析1.初始化函數(shù)〔voidHuffmanTree::Init<stringInput>算法偽代碼：1.初始化鏈表的頭結(jié)點2.獲得輸入字符串的第一個字符,并將其插入到鏈表尾部,n=1<n記錄的是鏈表中字符的個數(shù)>3.從字符串第2個字符開始,逐個取出字符串中的字符3.1將當前取出的字符與鏈表中已經(jīng)存在的字符逐個比較,如果當前取出的字符與鏈表中已經(jīng)存在的某個字符相同,則鏈表中該字符的權(quán)值加1。3.2如果當前取出的字符與鏈表中已經(jīng)存在的字符都不相同,則將其加入到鏈表尾部,同時n++4.tSize=n<tSize記錄鏈表中字符總數(shù),即哈夫曼樹中葉子節(jié)點總數(shù)>5.創(chuàng)建哈夫曼樹6.銷毀鏈表源代碼：voidHuffmanTree::Init<stringInput>{Node*front=newNode;//初始化鏈表的頭結(jié)點 if<!front> throwexception<"堆空間用盡">;front->next=NULL; front->character=NULL;front->count=0; Node*pfront=front; charch=Input[0];//獲得第一個字符Node*New1=newNode; if<!New1> throwexception<"堆空間用盡">; New1->character=ch;//將第一個字符插入鏈表New1->count=1; New1->next=pfront->next; pfront->next=New1; boolreplace=0;//判斷在已經(jīng)寫入鏈表的字符中是否有與當前讀出的字符相同的字符 intn=1;//統(tǒng)計鏈表中字符個數(shù) for<inti=1;i<Input.length<>;i++> {ch=Input[i];//獲得第i個字符do { pfront=pfront->next;if<<int>pfront->character==<int>ch>//如果在鏈表中有與當前字符相同的字符,該字符權(quán)值加1 { pfront->count++; replace=1; break; } }while<pfront->next>;if<!replace>//如果在鏈表中沒找到與當前字符相同的字符,則將該字符作為新成員插入鏈表 { Node*New=newNode; if<!New> throwexception<"堆空間用盡">; New->character=ch; New->count=1; New->next=pfront->next; pfront->next=New; n++; } pfront=front;//重置pfront和replace變量為默認值 replace=0; } tSize=n;//tSize記錄的是編碼表中字符個數(shù) CreateHTree<front,n>;//創(chuàng)建哈夫曼樹 pfront=front; while<pfront>//銷毀整個鏈表 { front=pfront; pfront=pfront->next; deletefront; }時間復(fù)雜度：若輸入的字符串長度為n,則時間復(fù)雜度為O<n>2.創(chuàng)建哈夫曼樹〔voidHuffmanTree::CreateCodeTable<Node*p>算法偽代碼：創(chuàng)建一個長度為2*tSize-1的三叉鏈表將存儲字符及其權(quán)值的鏈表中的字符逐個寫入三叉鏈表的前tSize個結(jié)點的data域,并將對應(yīng)結(jié)點的孩子域和雙親域賦為空從三叉鏈表的第tSize個結(jié)點開始,i=tSize從存儲字符及其權(quán)值的鏈表中取出兩個權(quán)值最小的結(jié)點x,y,記錄其下標x,y。將下標為x和y的哈夫曼樹的結(jié)點的雙親設(shè)置為第i個結(jié)點將下標為x的結(jié)點設(shè)置為i結(jié)點的左孩子,將下標為y的結(jié)點設(shè)置為i結(jié)點的右孩子,i結(jié)點的權(quán)值為x結(jié)點的權(quán)值加上y結(jié)點的權(quán)值,i結(jié)點的雙親設(shè)置為空4.根據(jù)哈夫曼樹創(chuàng)建編碼表源代碼：voidHuffmanTree::CreateHTree<Node*p,intn>{root=newBiNode<int>[2*n-1];//初始化哈夫曼樹 Node*front=p->next; if<n==0> throwexception<"沒有輸入字符">; for<inti=0;i<n;i++>//將n個字符的權(quán)值存儲在哈夫曼樹數(shù)組的前n位 { root[i].data=front->count; root[i].lchild=-1; root[i].rchild=-1; root[i].parent=-1; front=front->next; } front=p;intNew1,New2;for<i=n;i<2*n-1;i++> { SelectMin<New1,New2,0,i>;//從0~i中選出兩個權(quán)值最小的結(jié)點root[New1].parent=root[New2].parent=i;//用兩個權(quán)值最小的結(jié)點生成新結(jié)點,新節(jié)點為其雙親 root[i].data=root[New1].data+root[New2].data;//新結(jié)點的權(quán)值為其孩子的權(quán)值的和 root[i].lchild=New1; root[i].rchild=New2; root[i].parent=-1; } CreateCodeTable<p>;//創(chuàng)建編碼表}時間復(fù)雜度：在選取兩個權(quán)值最小的結(jié)點的函數(shù)中要遍歷鏈表,時間復(fù)雜度為O<n>,故該函數(shù)的時間復(fù)雜度為O〔n^23．創(chuàng)建編碼表〔voidHuffmanTree::CreateCodeTable<Node*p>算法偽代碼：1.初始化編碼表2.初始化一個指針,從鏈表的頭結(jié)點開始,遍歷整個鏈表2.1將鏈表中指針當前所指的結(jié)點包含的字符寫入編碼表中2.2得到該結(jié)點對應(yīng)的哈夫曼樹的葉子結(jié)點及其雙親2.3如果哈夫曼樹只有一個葉子結(jié)點,將其字符對應(yīng)編碼設(shè)置為02.4如果不止一個葉子結(jié)點,從當前葉子結(jié)點開始判斷如果當前葉子結(jié)點是其雙親的左孩子,則其對應(yīng)的編碼為0,否則為1child指針指向葉子結(jié)點的雙親,parent指針指向child指針的雙親,重復(fù)2.4.1的操作2.5將已完成的編碼倒序2.6取得鏈表中的下一個字符3．輸出編碼表源代碼：voidHuffmanTree::CreateCodeTable<Node*p>{HCodeTable=newHCode[tSize];//初始化編碼表 Node*front=p->next; for<inti=0;i<tSize;i++> { HCodeTable[i].data=front->character;//將第i個字符寫入編碼表 intchild=i;//得到第i個字符對應(yīng)的葉子節(jié)點 intparent=root[i].parent;//得到第i個字符對應(yīng)的葉子節(jié)點的雙親 intk=0; if<tSize==1>//如果文本中只有一種字符,它的編碼為0 { HCodeTable[i].code[k]='0'; k++; } while<parent!=-1>//從第i個字符對應(yīng)的葉子節(jié)點開始,尋找它到根結(jié)點的路徑 { if<child==root[parent].lchild>//如果當前結(jié)點為雙親的左孩子,則編碼為0,否則編碼為1HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1'; k++; child=parent; parent=root[child].parent; } HCodeTable[i].code[k]='\0'; Reverse<HCodeTable[i].code>;//將編碼逆置 front=front->next;//得到下一個字符 } cout<<"編碼表為："<<endl; for<i=0;i<tSize;i++>//輸出編碼表 { cout<<HCodeTable[i].data<<''<<HCodeTable[i].code<<endl; }}時間復(fù)雜度：需要遍歷哈夫曼樹獲取編碼,時間復(fù)雜度為O〔n^24.選擇兩個最小權(quán)值的函數(shù)〔voidHuffmanTree::SelectMin<int&New1,int&New2,intbegin,intend>算法偽代碼：從下標為begin的結(jié)點開始,尋找第一個沒用過的結(jié)點遍歷哈夫曼樹中從下標為begin到下標為end的結(jié)點序列,尋找沒用過的同時權(quán)值又是最小的結(jié)點。暫時改變找到的權(quán)值最小結(jié)點的雙親域,防止第2次找到相同的結(jié)點。將權(quán)值最小結(jié)點的下標記錄下來。重復(fù)步驟1~4,找到第2個權(quán)值最小的結(jié)點源代碼：voidHuffmanTree::SelectMin<int&New1,int&New2,intbegin,intend>{ intmin; for<intj=0;j<2;j++>//要選擇兩個權(quán)值最小的結(jié)點 { intsign=begin;for<inti=begin;i<end;i++>//從下標為begin的結(jié)點開始,尋找第1個沒用過的結(jié)點 { if<root[i].parent==-1>//沒用過的結(jié)點其雙親應(yīng)為空 { min=root[i].data; sign=i; break; } }for<i=begin;i<end;i++>//從begin到end,尋找權(quán)值最小的沒用過的結(jié)點 {if<root[i].parent==-1> { if<min>root[i].data> { min=root[i].data; sign=i; } } } root[sign].parent=0;//暫時改變所找最小結(jié)點的雙親域,防止第2次找到的是同一個結(jié)點 if<!j> New1=sign; else New2=sign; }}時間復(fù)雜度：兩次遍歷鏈表,時間復(fù)雜度為O〔n5.將字符串倒序的函數(shù)〔voidHuffmanTree::Reverse<char*pch>算法偽代碼：得到字符串的長度初始化兩個記錄下標的變量,一個為字符串開頭字符所在的下標i,另一個為字符串結(jié)尾字符所在的下標j將下標為i和j的字符交換i++,j--時間復(fù)雜度：時間復(fù)雜度為O〔n6.編碼函數(shù)〔voidHuffmanTree::Encode<string&s,string&d>算法偽代碼：1.從s開頭的字符開始,逐一對s中的字符進行編碼2.在編碼表中查找與當前字符對應(yīng)的字符3．如果找到了與當前字符對應(yīng)的編碼表中的字符,將其編碼追加到解碼串的末尾。4.重復(fù)以上步驟,直到所有待編碼串中的字符都編碼完畢5.輸出編碼后的字符串源代碼：voidHuffmanTree::Encode<string&s,string&d>{for<intj=0;j<s.length<>;j++>//逐個對待編碼字符串中的字符進行編碼 { for<inti=0;i<tSize;i++>//在編碼表中查找與當前字符對應(yīng)的編碼 { if<s[j]==HCodeTable[i].data> { d.append<HCodeTable[i].code>;//編碼 break; } } } cout<<d<<endl;//輸出編碼后的字符串}時間復(fù)雜度：設(shè)待編碼字符串長度為n,編碼表中字符個數(shù)為m,則復(fù)雜度為O〔n*m7.解碼函數(shù)〔voidHuffmanTree::Decode<string&s,string&d>算法偽代碼：得到指向哈夫曼樹的根結(jié)點的指針和指向待解碼串中的第1個字符的指針逐個讀取待解碼串中的字符,若為0,則指向哈夫曼樹當前結(jié)點的指針指向當前結(jié)點的左孩子,若為1,則指向當前結(jié)點的右孩子指向待解碼串的指針指向解碼串中的下一個字符,直到指向哈夫曼樹結(jié)點的指針的孩子結(jié)點為空如果哈夫曼樹只有一個葉子結(jié)點,直接將待解碼串中的編碼轉(zhuǎn)換為對應(yīng)的字符如果指向哈夫曼樹結(jié)點的指針的孩子結(jié)點已經(jīng)為空,則將葉子結(jié)點下標對應(yīng)的字符追加到解碼串中。輸出解碼串源代碼：voidHuffmanTree::Decode<string&s,string&d>{ for<inti=0;i<s.length<>;> {intparent=2*tSize-1-1;//得到哈夫曼樹的根結(jié)點 while<root[parent].lchild!=-1>//如果結(jié)點不為葉子結(jié)點 { if<s[i]=='0'>//編碼為0則尋找其左孩子 parent=root[parent].lchild; else//編碼為1則尋找右孩子 parent=root[parent].rchild; i++; } if<tSize==1>//如果編碼表只有一個字符,則根結(jié)點即為葉子結(jié)點 i++;d.append<1,HCodeTable[parent].data>;//將葉子節(jié)點對應(yīng)的字符追加到解碼串中 } cout<<d<<endl;}時間復(fù)雜度：設(shè)待解碼串長度為n,則復(fù)雜度為O<n>8.計算哈夫曼編碼的壓縮比〔voidHuffmanTree::Calculate<strings1,strings2>算法偽代碼：獲得編碼前字符串的長度,即其占用的字節(jié)數(shù)獲得編碼后的字符串的長度,將其除以8然后向上取整,得到其占用的字節(jié)數(shù)壓縮比將兩個相除源代碼：voidHuffmanTree::Calculate<strings1,strings2>{ intcal1=s1.length<>; intcal2=s2.length<>; cal2=ceill<<float>cal2/8>;//將編碼串的比特數(shù)轉(zhuǎn)化為字節(jié)數(shù) cout<<"編碼前的字符串長度："<<cal1<<endl; cout<<"編碼后的字符串長度："<<cal2<<endl; cout<<"壓縮比為："<<<<double>cal2/<double>cal1>*100<<"%"<<endl;}時間復(fù)雜度：O<1>9.打印哈夫曼樹〔voidHuffmanTree::PrintTree<intTreeNode,intlayer>算法偽代碼：如果待打印結(jié)點為空,則返回遞歸調(diào)用函數(shù)打印當前結(jié)點的右子樹根據(jù)當前結(jié)點所在的層次確定其前面要輸出多少空格,先輸出空格,在打印當前結(jié)點的權(quán)值遞歸調(diào)用函數(shù)打印當前結(jié)點的左子樹源代碼：voidHuffmanTree::PrintTree<intTreeNode,intlayer>{if<TreeNode==-1>//如果待打印結(jié)點為空,則返回 return; else {PrintTree<root[TreeNode].rchild,layer+1>;//先打印該結(jié)點的右子樹,layer記錄的是該結(jié)點所在的層次for<inti=0;i<layer*2;i++>//根據(jù)該結(jié)點所在的層次,確定在它之前需要打印多少空格 cout<<''; cout<<root[TreeNode].data<<endl;//打印該結(jié)點的權(quán)值 PrintTree<root[TreeNode].lchild,layer+1>;//打印該結(jié)點的左子樹 }}時間復(fù)雜度：中序遍歷哈夫曼樹,復(fù)雜度為O<n>10.菜單函數(shù)〔voidHuffmanTree::Menu<>算法偽代碼：1.逐一讀取鍵盤緩存區(qū)中的字符,并將它們逐一追加到記錄輸入字符串的string變量中,直到讀到回車輸入符為止2.刪除string變量末尾的回車輸入符3．利用string變量創(chuàng)建哈夫曼樹,初始化編碼表。4.直觀打印哈夫曼樹5.對輸入的字符串進行編碼6.對編碼后的字符串進行解碼7.計算編碼前后的壓縮比并輸出源代碼：voidHuffmanTree::Menu<>{