- 相關推薦
北郵數據結構實驗報告
北京郵電大學信息與通信工程學院
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++更加熟悉
【北郵數據結構實驗報告】相關文章：
北郵研究生在京就業前景如何07-14
北郵的通信工程就業前景怎么樣07-14
北郵考研考哪個院的研究生就業前景好一些07-14
北郵通信，華科電氣工程及其自動哪個好？哪個就業前景好？07-11
同濟大學的土木工程和北郵的通信工程哪個就業前景更好07-14
調劑到北郵軟院讀通信工程專業怎么樣？就業前景好嗎？07-14
京東包郵嗎？07-11
科技實驗報告05-26