北郵資料結構實驗報告
北京郵電大學資訊與通訊工程學院
2009級資料結構實驗報告
實驗名稱： 實驗三哈夫曼編/解碼器的實現
學生姓名：陳聰捷
日 期： 2010年11月28日
1.實驗要求
一、實驗目的：
瞭解哈夫曼樹的思想和相關概念;
二、實驗內容：
利用二叉樹結構實現哈夫曼編/解碼器
1.初始化：能夠對輸入的任意長度的字串s進行統計，統計每個字元的頻度，並建立哈夫曼樹。
2.建立編碼表：利用已經建好的哈夫曼樹進行編碼，並將每個字元的編碼輸出。
3.編碼：根據編碼表對輸入的字串進行編碼，並將編碼後的字串輸出。
4.譯碼：利用已經建好的哈夫曼樹對編碼後的字串進行譯碼，並輸出譯碼結果。
5.列印：以直觀的方式列印哈夫曼樹。
6.計算輸入的字串編碼前和編碼後的長度，並進行分析，討論哈夫曼編碼的壓縮效果。
7.使用者介面可以設計成“選單”方式，能進行互動，根據輸入的字串中每個字元出現的次數統計頻度，對沒有出現的字元一律不用編碼。
2. 程式分析
2.1 儲存結構
二叉樹
template
class BiTree
{
public:
BiTree(); //建構函式，其前序序列由鍵盤輸入
~BiTree(void); //解構函式
BiNode* Getroot(); //獲得指向根結點的指標
protected:
BiNode *root; //指向根結點的頭指標
};
//宣告類BiTree及定義結構BiNode
Data：
二叉樹是由一個根結點和兩棵互不相交的左右子樹構成
data:
HCode* HCodeTable;//編碼表
int tSize; //編碼表中的總字元數
二叉樹的節點結構
template
struct BiNode //二叉樹的結點結構 {
T data; //記錄資料
T lchild; //左孩子
T rchild; //右孩子
T parent; //雙親
};
編碼表的節點結構
struct HCode
{
char data; //編碼表中的字元
char code[100]; //該字元對應的編碼
};
待編碼字串由鍵盤輸入，輸入時用連結串列儲存，連結串列節點為 struct Node
{
char character; //輸入的字元
unsigned int count;//該字元的權值
bool used; //建立樹的時候該字元是否使用過
Node* next; //儲存下一個節點的地址
};
示意圖：
2.2 關鍵演算法分析
1.初始化函式(void HuffmanTree::Init(string Input))
演算法虛擬碼：
1.初始化連結串列的頭結點
2.獲得輸入字串的第一個字元，並將其插入到連結串列尾部,n=1(n記錄的是連結串列
中字元的個數)
3.從字串第2個字元開始，逐個取出字串中的字元
3.1 將當前取出的字元與連結串列中已經存在的字元逐個比較，如果當前取出
的字元與連結串列中已經存在的某個字元相同，則連結串列中該字元的權值加1。
3.2 如果當前取出的字元與連結串列中已經存在的字元都不相同，則將其加入
到連結串列尾部，同時n++
4.tSize=n(tSize記錄連結串列中字元總數，即哈夫曼樹中葉子節點總數)
5.建立哈夫曼樹
6.銷燬連結串列
原始碼：
void HuffmanTree::Init(string Input)
{
Node *front=new Node; //初始化連結串列的頭結點
if(!front)
throw exception("堆空間用盡");
front->next=NULL;
front->character=NULL;
front->count=0;
Node *pfront=front;
char ch=Input[0]; //獲得第一個字元
Node* New1=new Node;
if(!New1)
throw exception("堆空間用盡");
New1->character=ch; //將第一個字元插入連結串列
New1->count=1;
New1->next=pfront->next;
pfront->next=New1;
bool replace=0; //判斷在已經寫入連結串列的字元中是否有與當前讀出的字元相同的字元 int n=1; //統計連結串列中字元個數
for(int i=1;i
{
ch=Input[i]; //獲得第i個字元
do
{
pfront=pfront->next;
if((int)pfront->character == (int)ch) //如果在連結串列中有與當前字元相同的字元，
該字元權值加1
{
pfront->count++;
replace=1;
break;
}
}while(pfront->next);
if(!replace) //如果在連結串列中沒找到與當前字元相同的字元，則將該字元作為新成 員插入連結串列
{
Node* New=new Node;
if(!New)
throw exception("堆空間用盡");
New->character=ch;
New->count=1;
New->next=pfront->next;
pfront->next=New;
n++;
}
pfront=front; //重置pfront和replace變數為預設值 replace=0;
}
tSize=n; //tSize記錄的是編碼表中字元個數
CreateHTree(front,n); //建立哈夫曼樹
pfront=front;
while(pfront) //銷燬整個連結串列
{
front=pfront;
pfront=pfront->next;
front;
}
時間複雜度：
若輸入的字串長度為n，則時間複雜度為O(n)
2.建立哈夫曼樹(void HuffmanTree::CreateCodeTable(Node *p))
演算法虛擬碼：
1. 建立一個長度為2*tSize-1的三叉連結串列
2. 將儲存字元及其權值的連結串列中的字元逐個寫入三叉連結串列的前tSize個結點
的data域，並將對應結點的孩子域和雙親域賦為空
3. 從三叉連結串列的第tSize個結點開始，i=tSize
3.1 從儲存字元及其權值的.連結串列中取出兩個權值最小的結點x,y，記錄其
下標x,y。
3.2 將下標為x和y的哈夫曼樹的結點的雙親設定為第i個結點
3.3 將下標為x的結點設定為i結點的左孩子，將下標為y的結點設定為
i結點的右孩子，i結點的權值為x結點的權值加上y結點的權值，i
結點的雙親設定為空
4. 根據哈夫曼樹建立編碼表
原始碼：
void HuffmanTree::CreateHTree(Node *p,int n)
{
root= new BiNode[2*n-1]; //初始化哈夫曼樹
Node *front=p->next;
if(n==0)
throw exception("沒有輸入字元");
for(int i=0;i
root[i].data=front->count;
root[i].lchild=-1;
root[i].rchild=-1;
root[i].parent=-1;
front=front->next;
}
front=p;
int New1,New2;
for(i=n;i<2*n-1;i++)
{
SelectMin(New1,New2,0,i); //從0~i中選出兩個權值最小的結點
root[New1].parent=root[New2].parent=i; //用兩個權值最小的結點生成新結點，
新節點為其雙親
root[i].data=root[New1].data+root[New2].data;//新結點的權值為其孩子的權值的和 root[i].lchild=New1;
root[i].rchild=New2;
root[i].parent=-1;
}
CreateCodeTable(p); //建立編碼表
}
時間複雜度：
在選取兩個權值最小的結點的函式中要遍歷連結串列，時間複雜度為O(n),故該函式
的時間複雜度為O(n^2)
3.建立編碼表(void HuffmanTree::CreateCodeTable(Node *p))
演算法虛擬碼：
1.初始化編碼表
2.初始化一個指標，從連結串列的頭結點開始，遍歷整個連結串列
2.1 將連結串列中指標當前所指的結點包含的字元寫入編碼表中
2.2 得到該結點對應的哈夫曼樹的葉子結點及其雙親
2.3 如果哈夫曼樹只有一個葉子結點，將其字元對應編碼設定為0
2.4 如果不止一個葉子結點，從當前葉子結點開始判斷
2.4.1 如果當前葉子結點是其雙親的左孩子，則其對應的編碼為0，否
則為1
2.4.2 child指標指向葉子結點的雙親，parent指標指向child指標的雙親，
重複2.4.1的操作
2.5 將已完成的編碼倒序
2.6 取得連結串列中的下一個字元
3.輸出編碼表
原始碼：
void HuffmanTree::CreateCodeTable(Node *p)
{
HCodeTable=new HCode[tSize]; //初始化編碼表
Node *front=p->next;
for(int i=0;i
{
HCodeTable[i].data=front->character; //將第i個字元寫入編碼表
int child=i; //得到第i個字元對應的葉子節點
int parent=root[i].parent; //得到第i個字元對應的葉子節點的雙親
int k=0;
if(tSize==1) //如果文字中只有一種字元，它的編碼為0
{
HCodeTable[i].code[k]='0';
k++;
}
while(parent!=-1) //從第i個字元對應的葉子節點開始，尋找它到根結點的路徑
{
if(child==root[parent].lchild) //如果當前結點為雙親的左孩子，則編碼為0，
否則編碼為1
HCodeTable[i].code[k]='0';
else
HCodeTable[i].code[k]='1';
k++;
child=parent;
parent=root[child].parent;
}
HCodeTable[i].code[k]='';
Reverse(HCodeTable[i].code); //將編碼逆置
front=front->next; //得到下一個字元
}
cout<<"編碼表為："<
for(i=0;i
{
cout<
parent=root[parent].lchild;
else //編碼為1則尋找右孩子
parent=root[parent].rchild;
i++;
}
if(tSize==1) //如果編碼表只有一個字元，則根結點即為葉子結點 i++;
d.append(1,HCodeTable[parent].data);//將葉子節點對應的字元追加到解碼串中 }
cout<
}
時間複雜度：
設待解碼串長度為n，則複雜度為O(n)
8. 計算哈夫曼編碼的壓縮比(void HuffmanTree::Calculate(string s1,string s2)) 演算法虛擬碼：
1. 獲得編碼前字串的長度，即其佔用的位元組數
2. 獲得編碼後的字串的長度，將其除以8然後向上取整，得到其佔用的字
節數
3. 壓縮比將兩個相除
原始碼：
void HuffmanTree::Calculate(string s1,string s2)
{
int cal1=s1.length();
int cal2=s2.length();
cal2=ceill((float)cal2/8); //將編碼串的位元數轉化為位元組數 cout<<"編碼前的字串長度："<
cout<<"編碼後的字串長度："<
cout<<"壓縮比為："<<((double)cal2/(double)cal1)*100<<"%"<
}
時間複雜度：
O(1)
9. 列印哈夫曼樹(void HuffmanTree::PrintTree(int TreeNode,int layer) ) 演算法虛擬碼：
1. 如果待列印結點為空，則返回
2. 遞迴呼叫函式列印當前結點的右子樹
3. 根據當前結點所在的層次確定其前面要輸出多少空格，先輸出空格，在打
印當前結點的權值
4. 遞迴呼叫函式列印當前結點的左子樹
原始碼：
void HuffmanTree::PrintTree(int TreeNode,int layer)
{
if(TreeNode==-1) //如果待列印結點為空，則返回 return;
else
{
PrintTree(root[TreeNode].rchild,layer+1); //先列印該結點的右子樹，layer記錄
的是該結點所在的層次
for(int i=0;i
空格
cout<<' ';
cout<
PrintTree(root[TreeNode].lchild,layer+1); //列印該結點的左子樹
}
}
時間複雜度：
中序遍歷哈夫曼樹，複雜度為O(n)
10. 選單函式(void HuffmanTree::Menu())
演算法虛擬碼：
1. 逐一讀取鍵盤快取區中的字元，並將它們逐一追加到記錄輸入字串的
string變數中，直到讀到回車輸入符為止
2. 刪除string變數末尾的回車輸入符
3.利用string變數建立哈夫曼樹，初始化編碼表。
4. 直觀列印哈夫曼樹
5. 對輸入的字串進行編碼
6. 對編碼後的字串進行解碼
7. 計算編碼前後的壓縮比並輸出
原始碼：
void HuffmanTree::Menu()
{
cout<<"請輸入你要編碼的文字,按回車鍵確定輸入"<
string Input;
char letter;
do //將字元逐個讀入Input變數中
{
letter=cin.get();
Input.append(1,letter);
}while(letter!=' ');
Input.erase(Input.length()-1,1); //去掉Input末尾的回車符
Init(Input); //根據輸入的字串建立哈夫曼樹及其編碼表 cout<<"直觀列印哈夫曼樹"<
PrintTree(2*tSize-1-1,1); //列印哈夫曼樹
cout<<' '<<' ';
string d1,d2;
cout<<"編碼後的字串為"<
Encode(Input,d1); //編碼並列印編碼串
cout<<"解碼後的字串為"<
Decode(d1,d2); //解碼並列印解碼串
cout<<"ASCII碼編碼與HUFFMAN編碼的比較"<
Calculate(Input,d1); //計算編碼前後的壓縮比
}
2.3 其他
1.由於題目要求能輸入任意長的字串，所以本程式採用了string變數來記錄輸入
的字串，並採用string類的類成員函式來完成各項任務
2.列印哈夫曼樹時採用了遞迴函式，且採用了凹凸表的形式列印哈夫曼樹。
3.為了輸入空格，輸入時採取逐個字元輸入的方式
3. 程式執行結果
主函式流程圖：
執行結果：
各函式執行正常，沒有出現bug
4. 總結
經過這次實驗，我瞭解了哈夫曼樹的建立過程，瞭解了一種不等長編碼的方法，用設斷點除錯的方法更加熟練，同時熟悉了STL中string型別的用法，對C++更加熟悉
【北郵資料結構實驗報告】相關文章：