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

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