北郵數(shù)據(jù)結(jié)構(gòu)實驗三-哈夫曼樹

數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗三——樹學(xué)生姓名：班級：班內(nèi)序號：學(xué)號：日期：1實驗?zāi)康耐ㄟ^選擇下面兩個題目之一進行實現(xiàn)，掌握如下內(nèi)容：掌握二叉樹基本操作的實現(xiàn)方法了解哈夫曼樹的思想和相關(guān)概念學(xué)習(xí)使用二叉樹解決實際問題的能力實驗內(nèi)容：利用二叉樹結(jié)構(gòu)實現(xiàn)哈夫曼編/解碼器?；疽螅撼跏蓟?Init)：能夠?qū)斎氲娜我忾L度的字符串s進行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立哈夫曼樹建立編碼表(CreateTable)：利用已經(jīng)建好的哈夫曼樹進行編碼，并將每個字符的編碼輸出。編碼(Encoding)：根據(jù)編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出。譯碼(Decoding)：利用已經(jīng)建好的哈夫曼樹對編碼后的字符串進行譯碼，并輸出譯碼結(jié)果。打印(Print)：以直觀的方式打印哈夫曼樹（選作）計算輸入的字符串編碼前和編碼后的長度，并進行分析，討論赫夫曼編碼的壓縮效果。(選作)可采用二進制編碼方式（選作）測試數(shù)據(jù)：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.2程序分析2.1存儲結(jié)構(gòu)：三叉樹：classHuffman{private: HNode*HTree;//哈夫曼樹結(jié)點 HCode*HCodeTable;//哈夫曼編碼表 charb[1000];//記錄所有輸入內(nèi)容被編碼后的結(jié)果 charc[127];charletter[1000];//輸入內(nèi)容的保存 voidSelectMin(int&x,int&y,intk);//求最小權(quán)重的字符 node*count;//計算各個字符出現(xiàn)次數(shù) intn;//輸入字符的種類（個數(shù)） intl;public:Huffman(); voidCreateHTree();//創(chuàng)建哈夫曼樹 voidCreateCodeTable();//創(chuàng)建哈夫曼編碼表 voidEncode();//編碼 voidDecode();//解碼};結(jié)點結(jié)構(gòu)為如下所示：三叉樹的節(jié)點結(jié)構(gòu)：structHNode//哈夫曼樹結(jié)點的結(jié)構(gòu)體{intweight;//結(jié)點權(quán)值 intparent;//雙親指針 intlchild;//左孩子指針 intrchild;//右孩子指針 chardata;//字符};示意圖為：intweightintparentintlchildintrchildchardata編碼表節(jié)點結(jié)構(gòu)：structHCode//編碼表結(jié)構(gòu)體{ chardata;//字符 charcode[100];//編碼內(nèi)容};示意圖為：chardatacharcode[100]基本結(jié)構(gòu)體記錄字符和出現(xiàn)次數(shù):structnode{ intnum; chardata;};示意圖為:intnumchardata2.關(guān)鍵算法分析(1).初始化:偽代碼：輸入需要編譯的文本內(nèi)容將輸入的內(nèi)容保存到動態(tài)建立的node型數(shù)組count中統(tǒng)計出現(xiàn)的字符種類的數(shù)目,并且保存到private型變量nHuffman::Huffman()//將輸入數(shù)據(jù)保存到Huffman類中{ l=0; n=0; count=newnode[127]; cout<<"請輸入需要編譯壓縮的內(nèi)容"<<endl; cin.getline(letter,200,'\n'); for(intj=0;j<127;j++)//一個號碼代表一種字符 { count[j].num=0; } while(letter[l]!='\0')//在結(jié)束之前，每輸入一個字符，則對應(yīng)字符的數(shù)目則自增1 { ++count[letter[l]].num; count[letter[l]].data=letter[l]; ++l; } for(intk=0;k<127;k++) { if(count[k].num>0) {n++;}//在某個字符出現(xiàn)此書num不為0時，n自增1，最終n為出現(xiàn)的字符種類數(shù)目 }其時間復(fù)雜度為O(n)（2）.創(chuàng)建哈夫曼樹（voidHuffmanTree::CreateCodeTable(Node*p)）算法偽代碼：創(chuàng)建一個長度為2*n-1的三叉鏈表將存儲字符及其權(quán)值的鏈表中的字符逐個寫入三叉鏈表的前n個結(jié)點的data域，并將對應(yīng)結(jié)點的孩子域和雙親域賦為空從三叉鏈表的第n個結(jié)點開始，從存儲字符及其權(quán)值的鏈表中取出兩個權(quán)值最小的結(jié)點x,y，記錄其下標(biāo)x,y。將下標(biāo)為x和y的哈夫曼樹的結(jié)點的雙親設(shè)置為第i個結(jié)點將下標(biāo)為x的結(jié)點設(shè)置為i結(jié)點的左孩子，將下標(biāo)為y的結(jié)點設(shè)置為i結(jié)點的右孩子，i結(jié)點的權(quán)值為x結(jié)點的權(quán)值加上y結(jié)點的權(quán)值，i結(jié)點的雙親設(shè)置為空根據(jù)哈夫曼樹創(chuàng)建編碼表源代碼為：voidHuffman::CreateHTree(){ l=0; HTree=newHNode[2*n-1];//建立含有n種字符的哈夫曼樹只需要2*n-1個結(jié)點即可 for(inti=0;i<n;i++) { while(count[l].num==0)//如果count內(nèi)的權(quán)重為0，即該字符沒有出現(xiàn)，則跳過，i自增繼續(xù)尋找出現(xiàn)過的字符 {l++;} HTree[i].weight=count[l].num;//將count里統(tǒng)計的次數(shù)傳入哈夫曼樹的節(jié)點中，作為字符權(quán)重 HTree[i].lchild=-1; HTree[i].rchild=-1; HTree[i].parent=-1;//將左右孩子結(jié)點和父節(jié)點都置空 HTree[i].data=count[l].data;//將count內(nèi)的有效字符傳入哈夫曼樹的結(jié)點 l++; } intx=-1,y=-1; for(inti=n;i<2*n-1;i++)//開始建立哈夫曼樹 { SelectMin(x,y,i);//挑選三者中的權(quán)重較小的兩個 HTree[x].parent=HTree[y].parent=i;//令較小的x、y為孩子節(jié)點，該兩個結(jié)點的父節(jié)點是i HTree[i].weight=HTree[x].weight+HTree[y].weight;//i結(jié)點字符的權(quán)重賦為是左右孩子字符權(quán)重之和HTree[i].lchild=x;//左孩子為x HTree[i].rchild=y;//右孩子為y HTree[i].parent=-1;//父節(jié)點置空 x=-1; y=-1;//將x、y重新賦值為零，進行下一次比較建樹｝其時間復(fù)雜度為：O(n)（3）．創(chuàng)建編碼表算法偽代碼：1.初始化編碼表2.初始化一個指針，從鏈表的頭結(jié)點開始，遍歷整個鏈表2.1將鏈表中指針當(dāng)前所指的結(jié)點包含的字符寫入編碼表中2.2得到該結(jié)點對應(yīng)的哈夫曼樹的葉子結(jié)點及其雙親2.3如果哈夫曼樹只有一個葉子結(jié)點，將其字符對應(yīng)編碼設(shè)置為02.4如果不止一個葉子結(jié)點，從當(dāng)前葉子結(jié)點開始判斷2.4.1如果當(dāng)前葉子結(jié)點是其雙親的左孩子，則其對應(yīng)的編碼為0，否則為12.4.2child指針指向葉子結(jié)點的雙親，parent指針指向child指針的雙親，重復(fù)2.4.1的操作2.5將已完成的編碼倒序2.6取得鏈表中的下一個字符3．輸出編碼表 源代碼為：voidHuffman::CreateCodeTable()//建立哈夫曼編碼表{ HCodeTable=newHCode[n];//建立動態(tài)編碼表 for(inti=0;i<n;i++) { HCodeTable[i].data=HTree[i].data; intchild=i; intparent=HTree[i].parent; intk=0; while(parent!=-1) { if(child==HTree[parent].lchild)//判斷該節(jié)點是父節(jié)點的左孩子或右孩子，左孩子則編碼為0，右孩子則編碼為1 HCodeTable[i].code[k]='0'; else HCodeTable[i].code[k]='1'; k++; child=parent;//將該節(jié)點的父節(jié)點作為新的孩子節(jié)點，繼續(xù)進行編碼輸出 parent=HTree[child].parent; } HCodeTable[i].code[k]='\0';//code數(shù)組以\0結(jié)尾 Reverse(HCodeTable[i].code);//由于是從下到上輸出，順序是相反的，所以還需要逆置才能輸出字符的編碼值 } cout<<endl<<endl<<"每個字符的編碼為："<<endl; for(inti=0;i<n;i++) { cout<<HCodeTable[i].data<<"："<<HCodeTable[i].code<<endl;//逐個輸出對應(yīng)的字符和其編碼 }} }其時間復(fù)雜度為：O(n)（4）選擇兩個最小權(quán)值的函數(shù)voidHuffman::SelectMin(int&x,int&y,intk)算法偽代碼：從下標(biāo)為i=0的開始遍歷。前兩次將x，y賦值為序號最小的兩個結(jié)點的地址序號。開始進行比較：進行如下分類對于任何不存在父節(jié)點的結(jié)點：若x權(quán)值<=y權(quán)值且i權(quán)值>=y權(quán)值，則無疑i權(quán)值最大，為輸出x、y為權(quán)值較小的兩個故而x，y值不便；其余情況皆為x、i的權(quán)值是較小的兩個，令y賦值為i，則保證x、y權(quán)值是最小的兩個。若y權(quán)值<=x權(quán)值且i權(quán)值>=x權(quán)值，則i權(quán)值是最大，x、y不變。其余情況皆為i、y權(quán)值最小，令x賦值為i，保證x、y序號結(jié)點的權(quán)值最小完成如上循環(huán)，直至i=k則推出循環(huán)，第k個結(jié)點在樹的位置已經(jīng)確定源代碼為：voidHuffman::SelectMin(int&x,int&y,intk)//選出權(quán)值較小的兩個字符結(jié)點{ inti=0; while(i<k) { while(i<k&&HTree[i].parent==-1)//若結(jié)點不具有父結(jié)點且滿足i<k則進行如下循環(huán)，建立新子樹 { if(x==-1) x=i; elseif(y==-1) y=i; else if(HTree[x].weight<=HTree[y].weight) { if(HTree[y].weight<=HTree[i].weight) {y=y;x=x;} else y=i; } else if(HTree[x].weight>HTree[y].weight) { if(HTree[i].weight>=HTree[x].weight) {x=x;y=y;} else x=i; } i++; } i++; }}其時間復(fù)雜度為O(n)（5）.將字符串倒序的函數(shù)（voidHuffmanTree::Reverse(char*pch)）算法偽代碼：得到字符串的長度初始化兩個記錄下標(biāo)的變量，一個為字符串開頭字符所在的下標(biāo)i，另一個為字符串結(jié)尾字符所在的下標(biāo)j將下標(biāo)為i和j的字符交換i++,j--源代碼：voidReverse(chara[]){ charb[100]; inti=0,j=0; while(a[i]!='\0') { b[i]=a[i]; i++; } b[i]='\0'; i--; while(i>=0) { a[j]=b[i]; i--; j++; } a[j]='\0';}其時間復(fù)雜度為O(n)（6）.編碼函數(shù)（voidHuffman::Encode(a[])）算法偽代碼：1.從開頭的字符開始，逐一對a中的字符進行編碼2.在編碼表中查找與當(dāng)前字符對應(yīng)的字符3．如果找到了與當(dāng)前字符對應(yīng)的編碼表中的字符，將其編碼追加到解碼串的末尾。4.重復(fù)以上步驟，直到所有待編碼串中的字符都編碼完畢5.輸出編碼后的字符串voidHuffman::Encode()//編譯輸入內(nèi)容為代碼內(nèi)容用0和1表示{ cout<<"編碼結(jié)果為：";intk=0; for(inti=0;letter[i]!='\0';i++) { intj=0; while(HCodeTable[j].data!=letter[i])//編碼表的字符等于輸入內(nèi)容的字符時進行下一個while循環(huán) {j++;} intm=0;while(HCodeTable[j].code[m]!='\0')//輸出該字符的編碼 { b[k]=HCodeTable[j].code[m];//用數(shù)組b記錄所有的編碼數(shù)據(jù)，以備后續(xù)解碼使用 k++; m++; } }b[k]='\0'; cout<<b; cout<<endl;}其時間復(fù)雜度為：O(n)（7）.解碼函數(shù)（voidHuffman::Decode()）算法偽代碼：得到指向哈夫曼樹的根結(jié)點的指針和指向待解碼串中的第1個字符的指針逐個讀取待解碼串中的字符，若為0，則指向哈夫曼樹當(dāng)前結(jié)點的指針指向當(dāng)前結(jié)點的左孩子，若為1，則指向當(dāng)前結(jié)點的右孩子指向待解碼串的指針指向解碼串中的下一個字符，直到指向哈夫曼樹結(jié)點的指針的孩子結(jié)點為空如果