《哈夫曼樹實驗報告》由會員分享，可在線閱讀，更多相關(guān)《哈夫曼樹實驗報告（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、
數(shù)據(jù)結(jié)構(gòu)實驗報告
實驗名稱：實驗三哈夫曼樹
學(xué)生姓名：
班 級：
班內(nèi)序號：
學(xué) 號：
日 期：
程序分析：
2.1 存儲結(jié)構(gòu)：二叉樹
2.2 程序流程：
template
class BiTree
{
public:
BiTree(); //構(gòu)造函數(shù)，其前序序列由鍵盤輸入
2、 ~BiTree(void); //析構(gòu)函數(shù)
BiNode* Getroot(); //獲得指向根結(jié)點的指針
protected:
BiNode *root; //指向根結(jié)點的頭指針
};
//聲明類BiTree及定義結(jié)構(gòu)BiNode
Data：
二叉樹是由一個根結(jié)點和兩棵互不相交的左右子樹構(gòu)成
二叉樹中的結(jié)點具有相同數(shù)據(jù)類型及層次關(guān)系
示意圖： root
lchild parent rchild
哈
3、夫曼樹類的數(shù)據(jù)域，繼承節(jié)點類型為int的二叉樹
class HuffmanTree:public BiTree
data:
HCode* HCodeTable;//編碼表
int tSize; //編碼表中的總字符數(shù)
二叉樹的節(jié)點結(jié)構(gòu)
template
struct BiNode //二叉樹的結(jié)點結(jié)構(gòu)
{
T data; //記錄數(shù)據(jù)
T lchild; //左孩子
T rchild; //右孩子
T pare
4、nt; //雙親
};
示意圖：
T data
T lchild
T rchild
T parent
編碼表的節(jié)點結(jié)構(gòu)
struct HCode
{
char data; //編碼表中的字符
char code[100]; //該字符對應(yīng)的編碼
};
示意圖：
char data
char code[100]
待編碼字符串由鍵盤輸入，輸入時用鏈表存儲，鏈表節(jié)點為
struct Node
{
char character; //輸入的字符
unsigned int cou
5、nt;//該字符的權(quán)值
bool used; //建立樹的時候該字符是否使用過
Node* next; //保存下一個節(jié)點的地址
};
Node* next
bool used
unsigned int count
char character
示意圖：
2.3 關(guān)鍵算法分析：
1.初始化函數(shù)（void HuffmanTree::Init(string Input)）
算法偽代碼：
1.初始化鏈表的頭結(jié)點
2.獲得輸入字符串的第一個字符，并將其插入到鏈表尾部,n=1(n記錄的是鏈表中字符的個數(shù))
3.從字符
6、串第2個字符開始，逐個取出字符串中的字符
3.1 將當(dāng)前取出的字符與鏈表中已經(jīng)存在的字符逐個比較，如果當(dāng)前取出的字符與鏈表中已經(jīng)存在的某個字符相同，則鏈表中該字符的權(quán)值加1。
3.2 如果當(dāng)前取出的字符與鏈表中已經(jīng)存在的字符都不相同，則將其加入到鏈表尾部，同時n++
4.tSize=n(tSize記錄鏈表中字符總數(shù)，即哈夫曼樹中葉子節(jié)點總數(shù))
5.創(chuàng)建哈夫曼樹
6.銷毀鏈表
源代碼：
void HuffmanTree::Init(string Input)
{
Node *front=new Node; //初始化鏈表的頭結(jié)點
7、 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->nex
8、t=pfront->next;
pfront->next=New1;
bool replace=0; //判斷在已經(jīng)寫入鏈表的字符中是否有與當(dāng)前讀出的字符相同的字符
int n=1; //統(tǒng)計鏈表中字符個數(shù)
for(int i=1;inext;
if((int)pfront->character == (int)ch) /
9、/如果在鏈表中有與當(dāng)前字符相同的字符，該字符權(quán)值加1
{
pfront->count++;
replace=1;
break;
}
}while(pfront->next);
if(!replace) //如果在鏈表中沒找到與當(dāng)前字符相同的字符，則將該字符作為新成
員插入鏈表
{
Node* New=new Node;
if(!New)
throw exception("堆空間用盡");
New->character=ch;
New->cou
10、nt=1;
New->next=pfront->next;
pfront->next=New;
n++;
}
pfront=front; //重置pfront和replace變量為默認(rèn)值
replace=0;
}
tSize=n; //tSize記錄的是編碼表中字符個數(shù)
CreateHTree(front,n); //創(chuàng)建哈夫曼樹
pfront=front;
while(pfront)
11、 //銷毀整個鏈表
{
front=pfront;
pfront=pfront->next;
delete front;
}
時間復(fù)雜度：
若輸入的字符串長度為n，則時間復(fù)雜度為O(n)
2.創(chuàng)建哈夫曼樹（void HuffmanTree::CreateCodeTable(Node *p)）
算法偽代碼：
1. 創(chuàng)建一個長度為2*tSize-1的三叉鏈表
2. 將存儲字符及其權(quán)值的鏈表中的字符逐個寫入三叉鏈表的前tSize個結(jié)點的data域，并將對應(yīng)結(jié)點的孩子域和雙親域
12、賦為空
3. 從三叉鏈表的第tSize個結(jié)點開始，i=tSize
3.1 從存儲字符及其權(quán)值的鏈表中取出兩個權(quán)值最小的結(jié)點x,y，記錄其下標(biāo)x,y。
3.2 將下標(biāo)為x和y的哈夫曼樹的結(jié)點的雙親設(shè)置為第i個結(jié)點
3.3 將下標(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è)置為空
4. 根據(jù)哈夫曼樹創(chuàng)建編碼表
源代碼：
void HuffmanTree::CreateHTree(Node *p,int n)
{
root= new BiNode[2*n-1]
13、; //初始化哈夫曼樹
Node *front=p->next;
if(n==0)
throw exception("沒有輸入字符");
for(int i=0;icount;
root[i].lchild=-1;
root[i].rchild=-1;
root[i].parent=-1;
front=front->next;
}
front=p;
int New1,New2
14、;
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;
roo
15、t[i].rchild=New2;
root[i].parent=-1;
}
CreateCodeTable(p); //創(chuàng)建編碼表
}
時間復(fù)雜度：
在選取兩個權(quán)值最小的結(jié)點的函數(shù)中要遍歷鏈表，時間復(fù)雜度為O(n),故該函數(shù)的時間復(fù)雜度為O（n^2）
3．創(chuàng)建編碼表（void HuffmanTree::CreateCodeTable(Node *p)）
算法偽代碼：
1.初始化編碼表
2.初始化一個指針，從鏈表
16、的頭結(jié)點開始，遍歷整個鏈表
2.1 將鏈表中指針當(dāng)前所指的結(jié)點包含的字符寫入編碼表中
2.2 得到該結(jié)點對應(yīng)的哈夫曼樹的葉子結(jié)點及其雙親
2.3 如果哈夫曼樹只有一個葉子結(jié)點，將其字符對應(yīng)編碼設(shè)置為0
2.4 如果不止一個葉子結(jié)點，從當(dāng)前葉子結(jié)點開始判斷
2.4.1 如果當(dāng)前葉子結(jié)點是其雙親的左孩子，則其對應(yīng)的編碼為0，否則為1
2.4.2 child指針指向葉子結(jié)點的雙親，parent指針指向child指針的雙親，重復(fù)2.4.1的操作
2.
17、5 將已完成的編碼倒序
2.6 取得鏈表中的下一個字符
3．輸出編碼表
源代碼：
void HuffmanTree::CreateCodeTable(Node *p)
{
HCodeTable=new HCode[tSize]; //初始化編碼表
Node *front=p->next;
for(int i=0;icharacter; //將第i個字符寫入編碼表
18、 int child=i; //得到第i個字符對應(yīng)的葉子節(jié)點
int parent=root[i].parent; //得到第i個字符對應(yīng)的葉子節(jié)點的雙親
int k=0;
if(tSize==1) //如果文本中只有一種字符，它的編碼為0
{
HCodeTable[i].code[k]=0;
k++;
}
while(parent!=-1) //從第i個字符對應(yīng)的葉子節(jié)點開始，尋找它到根結(jié)點的
19、路徑
{
if(child==root[parent].lchild) //如果當(dāng)前結(jié)點為雙親的左孩子，則編碼為0， 否則編碼為1
HCodeTable[i].code[k]=0;
else
HCodeTable[i].code[k]=1;
k++;
child=parent;
parent=root[child].parent;
}
HCodeTable[i
20、].code[k]=\0;
Reverse(HCodeTable[i].code); //將編碼逆置
front=front->next; //得到下一個字符
}
cout<<"編碼表為："<
21、曼樹獲取編碼，時間復(fù)雜度為O（n^2）
4． 選擇兩個最小權(quán)值的函數(shù)
算法偽代碼：
1. 從下標(biāo)為begin的結(jié)點開始，尋找第一個沒用過的結(jié)點
2. 遍歷哈夫曼樹中從下標(biāo)為begin到下標(biāo)為end的結(jié)點序列，尋找沒用過的同時權(quán)值又是最小的結(jié)點。
3. 暫時改變找到的權(quán)值最小結(jié)點的雙親域，防止第2次找到相同的結(jié)點。
4. 將權(quán)值最小結(jié)點的下標(biāo)記錄下來。
5. 重復(fù)步驟1~4，找到第2個權(quán)值最小的結(jié)點
源代碼：
void HuffmanTree::SelectMin(int &New1,int &New2,int begin,int e
22、nd)
{
int min;
for(int j=0;j<2;j++) //要選擇兩個權(quán)值最小的結(jié)點
{
int sign=begin;
for(int i=begin;i
23、 for(i=begin;iroot[i].data)
{
min=root[i].data;
sign=i;
}
}
}
root[sign].parent=0;//暫時改變所找最小結(jié)點的雙親域，防止第2次找到的是同一個結(jié)點
if(!j)
New1=sign;
else
New2=sign;
24、
}
}
時間復(fù)雜度：
兩次遍歷鏈表，時間復(fù)雜度為O（n）
5. 將字符串倒序的函數(shù)（void HuffmanTree::Reverse(char *pch)）
算法偽代碼：
1． 得到字符串的長度
2． 初始化兩個記錄下標(biāo)的變量，一個為字符串開頭字符所在的下標(biāo)i，另一個為字符串結(jié)尾字符所在的下標(biāo)j
3． 將下標(biāo)為i和j的字符交換
4． i++,j - -
時間復(fù)雜度：
時間復(fù)雜度為O（n）
6.編碼函數(shù)（void HuffmanTree::Encode(string &
25、s,string &d)）
算法偽代碼：
1. 從s開頭的字符開始，逐一對s中的字符進(jìn)行編碼
2. 在編碼表中查找與當(dāng)前字符對應(yīng)的字符
3．如果找到了與當(dāng)前字符對應(yīng)的編碼表中的字符，將其編碼追加到解碼串的末尾。
4. 重復(fù)以上步驟，直到所有待編碼串中的字符都編碼完畢
5. 輸出編碼后的字符串
源代碼：
void HuffmanTree::Encode(string &s,string &d)
{
for(int j=0;j
26、);j++) //逐個對待編碼字符串中的字符進(jìn)行編碼
{
for(int i=0;i
27、 設(shè)待編碼字符串長度為n，編碼表中字符個數(shù)為m，則復(fù)雜度為O（n*m）
7.解碼函數(shù)
算法偽代碼：
1. 得到指向哈夫曼樹的根結(jié)點的指針和指向待解碼串中的第1個字符的指針
2. 逐個讀取待解碼串中的字符，若為0，則指向哈夫曼樹當(dāng)前結(jié)點的指針指向當(dāng)前結(jié)點的左孩子，若為1，則指向當(dāng)前結(jié)點的右孩子
3. 指向待解碼串的指針指向解碼串中的下一個字符，直到指向哈夫曼樹結(jié)點的指針的孩子結(jié)點為空
4. 如果哈夫曼樹只有一個葉子結(jié)點，直接將待解碼串中的編碼轉(zhuǎn)換為對應(yīng)的字符
5. 如果指向哈夫曼樹結(jié)點的指針的孩子結(jié)點已經(jīng)為空，則將葉子結(jié)點下標(biāo)對應(yīng)的字符追加到解碼串中。
28、
6. 輸出解碼串
源代碼：
void HuffmanTree::Decode(string &s,string &d)
{
for(int i=0;i
29、 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<
30、度：
設(shè)待解碼串長度為n，則復(fù)雜度為O(n)
8. 計算哈夫曼編碼的壓縮比（void HuffmanTree::Calculate(string s1,string s2)）
算法偽代碼：
1. 獲得編碼前字符串的長度，即其占用的字節(jié)數(shù)
2. 獲得編碼后的字符串的長度，將其除以8然后向上取整，得到其占用的字節(jié)數(shù)
3. 壓縮比將兩個相除
源代碼：
void HuffmanTree::Calculate(string s1,string s2)
{
int cal1=s1.length();
31、
int cal2=s2.length();
cal2=ceill((float)cal2/8); //將編碼串的比特數(shù)轉(zhuǎn)化為字節(jié)數(shù)
cout<<"編碼前的字符串長度："<
32、rintTree(int TreeNode,int layer) ）
算法偽代碼：
1. 如果待打印結(jié)點為空，則返回
2. 遞歸調(diào)用函數(shù)打印當(dāng)前結(jié)點的右子樹
3. 根據(jù)當(dāng)前結(jié)點所在的層次確定其前面要輸出多少空格，先輸出空格，在打印當(dāng)前結(jié)點的權(quán)值
4. 遞歸調(diào)用函數(shù)打印當(dāng)前結(jié)點的左子樹
源代碼：
void HuffmanTree::PrintTree(int TreeNode,int layer)
{
if(TreeNode==-1) //如果待打印結(jié)點為空，則返回
33、
return;
else
{
PrintTree(root[TreeNode].rchild,layer+1); //先打印該結(jié)點的右子樹，layer記錄的是該結(jié)點所在的層次
for(int i=0;i
34、度：
中序遍歷哈夫曼樹，復(fù)雜度為O(n)
10. 菜單函數(shù)（void HuffmanTree::Menu()）
算法偽代碼：
1. 逐一讀取鍵盤緩存區(qū)中的字符，并將它們逐一追加到記錄輸入字符串的string變量中，直到讀到回車輸入符為止
2. 刪除string變量末尾的回車輸入符
3．利用string變量創(chuàng)建哈夫曼樹，初始化編碼表。
4. 直觀打印哈夫曼樹
5. 對輸入的字符串進(jìn)行編碼
35、 6. 對編碼后的字符串進(jìn)行解碼
7. 計算編碼前后的壓縮比并輸出
源代碼：
void HuffmanTree::Menu()
{
cout<<"請輸入你要編碼的文本,按回車鍵確定輸入"<
36、etter!=\n);
Input.erase(Input.length()-1,1); //去掉Input末尾的回車符
Init(Input); //根據(jù)輸入的字符串創(chuàng)建哈夫曼樹及其編碼表
cout<<"直觀打印哈夫曼樹"<
37、打印編碼串
cout<<"解碼后的字符串為"<
38、打印哈夫曼樹。
3.為了輸入空格，輸入時采取逐個字符輸入的方式
三．程序運行結(jié)果分析：
主函數(shù)流程圖：
開始
調(diào)用菜單函數(shù)
等待用戶輸入字符串
利用用戶輸入的字符串創(chuàng)建哈夫曼樹和編碼表
直觀打印哈夫曼樹和編碼表
對輸入的字符串編碼
對編碼串解碼
計算編碼前后的壓縮比
結(jié)束
運行結(jié)果
各函數(shù)運行正常，沒有bug
四. 總結(jié)：
在實現(xiàn)整個算法設(shè)計中運用了二叉樹結(jié)構(gòu)及類創(chuàng)新，同時又復(fù)習(xí)了上學(xué)期C++的相應(yīng)內(nèi)容。總結(jié)與流程分析過程雖然很辛苦但屢敗屢戰(zhàn)，獲益匪淺，收獲了很多。也認(rèn)識到自己的不足，希望自己繼續(xù)努力。
哈夫曼樹實驗報告
