《北郵 大數(shù)據(jù)結(jié)構(gòu) 哈夫曼樹報告材料》由會員分享，可在線閱讀，更多相關(guān)《北郵 大數(shù)據(jù)結(jié)構(gòu) 哈夫曼樹報告材料（12頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、word
數(shù) 據(jù) 結(jié) 構(gòu)
實
驗
報
告
實驗名稱：哈夫曼樹
學(xué)生：袁普
班 級：2013211125班
班序號：14號
學(xué) 號：2013210681
日 期：2014年12月
1. 實驗?zāi)康暮腿?
利用二叉樹結(jié)構(gòu)實現(xiàn)哈夫曼編/解碼器。
基本要求：
1、 初始化(Init)：能夠?qū)斎氲娜我忾L度的字符串 s進行統(tǒng)計，統(tǒng)計每個字符的頻度，
并建立哈夫曼樹
2、 建立編碼表(CreateTable)：利用已經(jīng)建好的哈夫曼樹進行編碼，并將每個字符的編碼輸出。
3、 編碼(Encoding)：根據(jù)編碼表對輸入的字符串進行編
2、碼，并將編碼后的字符串輸
出。
4、 譯碼(Decoding)：利用已經(jīng)建好的哈夫曼樹對編碼后的字符串進行譯碼，并輸出
譯碼結(jié)果。
5、 打印(Print)：以直觀的方式打印哈夫曼樹（選作）
6、 計算輸入的字符串編碼前和編碼后的長度，并進行分析，討論赫夫曼編碼的壓
縮效果。
7、 可采用二進制編碼方式（選作）
測試數(shù)據(jù)：
I love data Structure, I love puter。I will try my best to study data Structure.
提示：
1、用戶界面可以設(shè)計為“菜單”方式：能夠進行交互。
2、根據(jù)輸入的字符串中每個字符
3、出現(xiàn)的次數(shù)統(tǒng)計頻度，對沒有出現(xiàn)的字符一律不用編碼
2. 程序分析
2.1 存儲結(jié)構(gòu)
用struct結(jié)構(gòu)類型來實現(xiàn)存儲
樹的結(jié)點類型
struct HNode
{
int weight; //權(quán)值
int parent; //父節(jié)點
int lchild; //左孩子
int rchild; //右孩子
};
struct HCode //實現(xiàn)編碼的結(jié)構(gòu)類型
{
char data; //被編碼的字符
char code[100]; //字符對應(yīng)的
4、哈夫曼編碼
};
2.2 程序流程
輸入字符串
統(tǒng)計出現(xiàn)的字符種類和次數(shù)，構(gòu)建權(quán)值數(shù)組，初始化樹結(jié)點與編碼表
根據(jù)哈夫曼構(gòu)建規(guī)則構(gòu)建哈夫曼樹，根據(jù)編碼規(guī)則對出現(xiàn)字符進行編碼，構(gòu)建編碼表
將輸入的字符挨個編碼
對編碼后的字符進行解碼
分析存儲大小
2.3 關(guān)鍵算法分析
算法1：void Huffman::Count()
[1] 算法功能：對出現(xiàn)字符的和出現(xiàn)字符的統(tǒng)計，構(gòu)建權(quán)值結(jié)點，初始化編碼表
[2] 算法基本思想：對輸入字符一個一個的統(tǒng)計，并統(tǒng)計
5、出現(xiàn)次數(shù)，構(gòu)建權(quán)值數(shù)組，
[3] 算法空間、時間復(fù)雜度分析：空間復(fù)雜度O（1），要遍歷一遍字符串，時間復(fù)雜度O（n）
[4] 代碼邏輯：
leaf=0; //初始化葉子節(jié)點個數(shù)
int i,j=0;
int s[128]={0}; 用于存儲出現(xiàn)的字符
for(i=0;str[i]!='\0';i++) 遍歷輸入的字符串
s[(int)str[i]]++; 統(tǒng)計每個字符出現(xiàn)次數(shù)
for(i=0;i<128;i++)
if(s[i]!=0)
{
da
6、ta[j]=(char)i; 給編碼表的字符賦值
weight[j]=s[i]; 構(gòu)建權(quán)值數(shù)組
j++;
}
leaf=j; //葉子節(jié)點個數(shù)即字符個數(shù)
for(i=0;i
7、夫曼樹構(gòu)建要求，選取權(quán)值最小的兩個結(jié)點結(jié)合，新結(jié)點加入數(shù)組，再繼續(xù)選取最小的兩個結(jié)點繼續(xù)構(gòu)建。
[3] 算法空間、時間復(fù)雜度分析：取決于葉子節(jié)點個數(shù)，時間復(fù)雜度O（n），空間復(fù)雜度O（1）
[4] 代碼邏輯
HTree=new HNode[2*leaf-1]; n2=n0-1，一共需要2n-1個結(jié)點空間
for(int i=0;i
8、ild=-1; 初始化左右孩子和父節(jié)點，都為-1
HTree[i].rchild=-1;
HTree[i].parent=-1;
}
int x,y; //用于記錄兩個最小權(quán)值
for(int i=leaf;i<2*leaf-1;i++)
{
Selectmin(HTree,i,x,y); 選出兩個最小權(quán)值的結(jié)點
HTree[x].parent=i;
9、 父節(jié)點設(shè)置為新建立的結(jié)點
HTree[y].parent=i;
HTree[i].weight=HTree[x].weight+HTree[y].weight; 父節(jié)點權(quán)值為兩個相加
HTree[i].lchild=x; 使父節(jié)點指向這兩個孩子結(jié)點
HTree[i].rchild=y;
HTree[i].parent=-1; 父節(jié)點的父節(jié)點設(shè)為-1
}
算法3：void Selectmin(HNode*hTree,int
10、n,int&i1,int &i2);
[1] 算法功能：從現(xiàn)有的結(jié)點中選擇出兩個最小的結(jié)點，返回其位置
[2] 算法基本思想：先選出兩個沒有構(gòu)建的結(jié)點，然后向后依次比較，篩選出最小的兩個結(jié)點
[3] 算法空間、時間復(fù)雜度分析：空間復(fù)雜度O(1)，要遍歷所有結(jié)點，時間復(fù) 雜度O(N)
[4] 代碼邏輯
int i;
for(i=0;i
11、 //父節(jié)點不是-1意味著這個結(jié)點還沒有被選擇過
{
i1=i; 記錄結(jié)點位置
break;
}
}
i++; //執(zhí)行一遍for循環(huán)就加1，意為下次查找從當(dāng)前位置開始查找
for(;ihTree[i2].weight) 進行比較，使I1為最小
12、的，I2為第二小的
{
int j=0;
j=i2;
i2=i1;
i1=j;
}
i++;
for(;i
13、ght
14、=new HCode[leaf]; 新建編碼結(jié)點，個數(shù)為葉子節(jié)點個數(shù)
for(int i=0;i
15、 while(parent!=-1)
{
if(child==HTree[parent].lchild)
HCodeTable[i].code[k]='0'; //左孩子標(biāo)‘0’
else
HCodeTable[i].code[k]='1'; //右孩子標(biāo)‘1’
k++;
child=parent; 孩子結(jié)點上移
16、 parent=HTree[child].parent; 父節(jié)點也上移
}
HCodeTable[i].code[k]='\0'; //將編碼反向
char code[100];
for(int u=0;u
17、[u];
cout<
18、(1),時間復(fù)雜度0（n）
[4] 代碼邏輯
cout<
19、
cout<
20、s = const_cast(s1.c_str()); 將編碼字符串轉(zhuǎn)化為char
while(*s!='\0')
{
int parent=2*leaf-2; 父節(jié)點為最后一個節(jié)點
while(HTree[parent].lchild!=-1) //還有左子樹，不可能是葉子節(jié)點
{
if(*s=='0') 編碼為0，為左孩子
21、 parent=HTree[parent].lchild;
else
parent=HTree[parent].rchild; 編碼為1，為右孩子
s++;
}
cout<
22、以方便的將單個字符的編碼加起來成為總的編碼后的數(shù)值，再利用STL中的轉(zhuǎn)化函數(shù)可以直接將string轉(zhuǎn)化為char，方便進行解碼工作。總而言之，使用STL使得編碼大大的簡潔了。
3. 程序運行結(jié)果分析
調(diào)試過程中遇到的問題主要是執(zhí)行時有存錯誤，檢查后發(fā)現(xiàn)是數(shù)組有越界現(xiàn)象，這提醒我在編寫時一定要仔細(xì)，特別是在for循環(huán)條件上一定要注意圍
總結(jié)
4.1實驗的難點和關(guān)鍵點
首先在輸入字符串時我發(fā)現(xiàn)直接用cin無法輸入空格，在上網(wǎng)查詢后找到了getline函數(shù)解決了這個問題。然后還有就是如何存儲編碼后總的那個字符串，因為每一個字符編碼的長度不定，無法用char數(shù)組來存儲，于是用了string的相加函數(shù)來將所有編碼加起來。最后由于在解碼時要用char數(shù)組，又上網(wǎng)查詢到了string轉(zhuǎn)化成char的函數(shù)解決了這個問題，實驗難點也在于如何找到兩個最小權(quán)值來構(gòu)建哈夫曼樹，尋找兩個最小權(quán)值的思想主要是通過一個個的比較來找到最小值，而且注意形參要用引用。
4.2心得體會
通過此次實驗我體會到了stl的優(yōu)越性。還有就是編碼時要注意數(shù)組的大小。再者就是有問題時可以試著去網(wǎng)上查詢答案。
12 / 12
北郵 大數(shù)據(jù)結(jié)構(gòu) 哈夫曼樹報告材料
