- 相關(guān)推薦
北郵數據結構實(shí)驗報告
北京郵電大學(xué)信息與通信工程學(xué)院
2009級數據結構實(shí)驗報告
實(shí)驗名稱(chēng)： 實(shí)驗三哈夫曼編/解碼器的實(shí)現
學(xué)生姓名：陳聰捷
日 期： 2010年11月28日
1.實(shí)驗要求
一、實(shí)驗目的：
了解哈夫曼樹(shù)的思想和相關(guān)概念;
二、實(shí)驗內容：
利用二叉樹(shù)結構實(shí)現哈夫曼編/解碼器
1.初始化：能夠對輸入的任意長(cháng)度的字符串s進(jìn)行統計，統計每個(gè)字符的頻度，并建立哈夫曼樹(shù)。
2.建立編碼表：利用已經(jīng)建好的哈夫曼樹(shù)進(jìn)行編碼，并將每個(gè)字符的編碼輸出。
3.編碼：根據編碼表對輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。
4.譯碼：利用已經(jīng)建好的哈夫曼樹(shù)對編碼后的字符串進(jìn)行譯碼，并輸出譯碼結果。
5.打�。阂灾庇^(guān)的方式打印哈夫曼樹(shù)。
6.計算輸入的字符串編碼前和編碼后的長(cháng)度，并進(jìn)行分析，討論哈夫曼編碼的壓縮效果。
7.用戶(hù)界面可以設計成“菜單”方式，能進(jìn)行交互，根據輸入的字符串中每個(gè)字符出現的次數統計頻度，對沒(méi)有出現的字符一律不用編碼。
2. 程序分析
2.1 存儲結構
二叉樹(shù)
template
class BiTree
{
public:
BiTree(); //構造函數，其前序序列由鍵盤(pán)輸入
~BiTree(void); //析構函數
BiNode* Getroot(); //獲得指向根結點(diǎn)的指針
protected:
BiNode *root; //指向根結點(diǎn)的頭指針
};
//聲明類(lèi)BiTree及定義結構BiNode
Data：
二叉樹(shù)是由一個(gè)根結點(diǎn)和兩棵互不相交的左右子樹(shù)構成
data:
HCode* HCodeTable;//編碼表
int tSize; //編碼表中的總字符數
二叉樹(shù)的節點(diǎn)結構
template
struct BiNode //二叉樹(shù)的結點(diǎn)結構 {
T data; //記錄數據
T lchild; //左孩子
T rchild; //右孩子
T parent; //雙親
};
編碼表的節點(diǎn)結構
struct HCode
{
char data; //編碼表中的字符
char code[100]; //該字符對應的編碼
};
待編碼字符串由鍵盤(pán)輸入，輸入時(shí)用鏈表存儲，鏈表節點(diǎn)為 struct Node
{
char character; //輸入的字符
unsigned int count;//該字符的權值
bool used; //建立樹(shù)的時(shí)候該字符是否使用過(guò)
Node* next; //保存下一個(gè)節點(diǎn)的地址
};
示意圖：
2.2 關(guān)鍵算法分析
1.初始化函數(void HuffmanTree::Init(string Input))
算法偽代碼：
1.初始化鏈表的頭結點(diǎn)
2.獲得輸入字符串的第一個(gè)字符，并將其插入到鏈表尾部,n=1(n記錄的是鏈表
中字符的個(gè)數)
3.從字符串第2個(gè)字符開(kāi)始，逐個(gè)取出字符串中的字符
3.1 將當前取出的字符與鏈表中已經(jīng)存在的字符逐個(gè)比較，如果當前取出
的字符與鏈表中已經(jīng)存在的某個(gè)字符相同，則鏈表中該字符的權值加1。
3.2 如果當前取出的字符與鏈表中已經(jīng)存在的字符都不相同，則將其加入
到鏈表尾部，同時(shí)n++
4.tSize=n(tSize記錄鏈表中字符總數，即哈夫曼樹(shù)中葉子節點(diǎn)總數)
5.創(chuàng )建哈夫曼樹(shù)
6.銷(xiāo)毀鏈表
源代碼：
void HuffmanTree::Init(string Input)
{
Node *front=new Node; //初始化鏈表的頭結點(diǎn)
if(!front)
throw exception("堆空間用盡");
front->next=NULL;
front->character=NULL;
front->count=0;
Node *pfront=front;
char ch=Input[0]; //獲得第一個(gè)字符
Node* New1=new Node;
if(!New1)
throw exception("堆空間用盡");
New1->character=ch; //將第一個(gè)字符插入鏈表
New1->count=1;
New1->next=pfront->next;
pfront->next=New1;
bool replace=0; //判斷在已經(jīng)寫(xiě)入鏈表的字符中是否有與當前讀出的字符相同的字符 int n=1; //統計鏈表中字符個(gè)數
for(int i=1;i
{
ch=Input[i]; //獲得第i個(gè)字符
do
{
pfront=pfront->next;
if((int)pfront->character == (int)ch) //如果在鏈表中有與當前字符相同的字符，
該字符權值加1
{
pfront->count++;
replace=1;
break;
}
}while(pfront->next);
if(!replace) //如果在鏈表中沒(méi)找到與當前字符相同的字符，則將該字符作為新成 員插入鏈表
{
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記錄的是編碼表中字符個(gè)數
CreateHTree(front,n); //創(chuàng )建哈夫曼樹(shù)
pfront=front;
while(pfront) //銷(xiāo)毀整個(gè)鏈表
{
front=pfront;
pfront=pfront->next;
front;
}
時(shí)間復雜度：
若輸入的字符串長(cháng)度為n，則時(shí)間復雜度為O(n)
2.創(chuàng )建哈夫曼樹(shù)(void HuffmanTree::CreateCodeTable(Node *p))
算法偽代碼：
1. 創(chuàng )建一個(gè)長(cháng)度為2*tSize-1的三叉鏈表
2. 將存儲字符及其權值的鏈表中的字符逐個(gè)寫(xiě)入三叉鏈表的前tSize個(gè)結點(diǎn)
的data域，并將對應結點(diǎn)的孩子域和雙親域賦為空
3. 從三叉鏈表的第tSize個(gè)結點(diǎn)開(kāi)始，i=tSize
3.1 從存儲字符及其權值的鏈表中取出兩個(gè)權值最小的結點(diǎn)x,y，記錄其
下標x,y。
3.2 將下標為x和y的哈夫曼樹(shù)的結點(diǎn)的雙親設置為第i個(gè)結點(diǎn)
3.3 將下標為x的結點(diǎn)設置為i結點(diǎn)的左孩子，將下標為y的結點(diǎn)設置為
i結點(diǎn)的右孩子，i結點(diǎn)的權值為x結點(diǎn)的權值加上y結點(diǎn)的權值，i
結點(diǎn)的雙親設置為空
4. 根據哈夫曼樹(shù)創(chuàng )建編碼表
源代碼：
void HuffmanTree::CreateHTree(Node *p,int n)
{
root= new BiNode[2*n-1]; //初始化哈夫曼樹(shù)
Node *front=p->next;
if(n==0)
throw exception("沒(méi)有輸入字符");
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中選出兩個(gè)權值最小的結點(diǎn)
root[New1].parent=root[New2].parent=i; //用兩個(gè)權值最小的結點(diǎn)生成新結點(diǎn)，
新節點(diǎn)為其雙親
root[i].data=root[New1].data+root[New2].data;//新結點(diǎn)的權值為其孩子的權值的和 root[i].lchild=New1;
root[i].rchild=New2;
root[i].parent=-1;
}
CreateCodeTable(p); //創(chuàng )建編碼表
}
時(shí)間復雜度：
在選取兩個(gè)權值最小的結點(diǎn)的函數中要遍歷鏈表，時(shí)間復雜度為O(n),故該函數
的時(shí)間復雜度為O(n^2)
3.創(chuàng )建編碼表(void HuffmanTree::CreateCodeTable(Node *p))
算法偽代碼：
1.初始化編碼表
2.初始化一個(gè)指針，從鏈表的頭結點(diǎn)開(kāi)始，遍歷整個(gè)鏈表
2.1 將鏈表中指針當前所指的結點(diǎn)包含的字符寫(xiě)入編碼表中
2.2 得到該結點(diǎn)對應的哈夫曼樹(shù)的葉子結點(diǎn)及其雙親
2.3 如果哈夫曼樹(shù)只有一個(gè)葉子結點(diǎn)，將其字符對應編碼設置為0
2.4 如果不止一個(gè)葉子結點(diǎn)，從當前葉子結點(diǎn)開(kāi)始判斷
2.4.1 如果當前葉子結點(diǎn)是其雙親的左孩子，則其對應的編碼為0，否
則為1
2.4.2 child指針指向葉子結點(diǎn)的雙親，parent指針指向child指針的雙親，
重復2.4.1的操作
2.5 將已完成的編碼倒序
2.6 取得鏈表中的下一個(gè)字符
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個(gè)字符寫(xiě)入編碼表
int child=i; //得到第i個(gè)字符對應的葉子節點(diǎn)
int parent=root[i].parent; //得到第i個(gè)字符對應的葉子節點(diǎn)的雙親
int k=0;
if(tSize==1) //如果文本中只有一種字符，它的編碼為0
{
HCodeTable[i].code[k]='0';
k++;
}
while(parent!=-1) //從第i個(gè)字符對應的葉子節點(diǎn)開(kāi)始，尋找它到根結點(diǎn)的路徑
{
if(child==root[parent].lchild) //如果當前結點(diǎn)為雙親的左孩子，則編碼為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; //得到下一個(gè)字符
}
cout<<"編碼表為："<
for(i=0;i
{
cout<
parent=root[parent].lchild;
else //編碼為1則尋找右孩子
parent=root[parent].rchild;
i++;
}
if(tSize==1) //如果編碼表只有一個(gè)字符，則根結點(diǎn)即為葉子結點(diǎn) i++;
d.append(1,HCodeTable[parent].data);//將葉子節點(diǎn)對應的字符追加到解碼串中 }
cout<
}
時(shí)間復雜度：
設待解碼串長(cháng)度為n，則復雜度為O(n)
8. 計算哈夫曼編碼的壓縮比(void HuffmanTree::Calculate(string s1,string s2)) 算法偽代碼：
1. 獲得編碼前字符串的長(cháng)度，即其占用的字節數
2. 獲得編碼后的字符串的長(cháng)度，將其除以8然后向上取整，得到其占用的字
節數
3. 壓縮比將兩個(gè)相除
源代碼：
void HuffmanTree::Calculate(string s1,string s2)
{
int cal1=s1.length();
int cal2=s2.length();
cal2=ceill((float)cal2/8); //將編碼串的比特數轉化為字節數 cout<<"編碼前的字符串長(cháng)度："<
cout<<"編碼后的字符串長(cháng)度："<
cout<<"壓縮比為："<<((double)cal2/(double)cal1)*100<<"%"<
}
時(shí)間復雜度：
O(1)
9. 打印哈夫曼樹(shù)(void HuffmanTree::PrintTree(int TreeNode,int layer) ) 算法偽代碼：
1. 如果待打印結點(diǎn)為空，則返回
2. 遞歸調用函數打印當前結點(diǎn)的右子樹(shù)
3. 根據當前結點(diǎn)所在的層次確定其前面要輸出多少空格，先輸出空格，在打
印當前結點(diǎn)的權值
4. 遞歸調用函數打印當前結點(diǎn)的左子樹(shù)
源代碼：
void HuffmanTree::PrintTree(int TreeNode,int layer)
{
if(TreeNode==-1) //如果待打印結點(diǎn)為空，則返回 return;
else
{
PrintTree(root[TreeNode].rchild,layer+1); //先打印該結點(diǎn)的右子樹(shù)，layer記錄
的是該結點(diǎn)所在的層次
for(int i=0;i
空格
cout<<' ';
cout<
PrintTree(root[TreeNode].lchild,layer+1); //打印該結點(diǎn)的左子樹(shù)
}
}
時(shí)間復雜度：
中序遍歷哈夫曼樹(shù)，復雜度為O(n)
10. 菜單函數(void HuffmanTree::Menu())
算法偽代碼：
1. 逐一讀取鍵盤(pán)緩存區中的字符，并將它們逐一追加到記錄輸入字符串的
string變量中，直到讀到回車(chē)輸入符為止
2. 刪除string變量末尾的回車(chē)輸入符
3.利用string變量創(chuàng )建哈夫曼樹(shù)，初始化編碼表。
4. 直觀(guān)打印哈夫曼樹(shù)
5. 對輸入的字符串進(jìn)行編碼
6. 對編碼后的字符串進(jìn)行解碼
7. 計算編碼前后的壓縮比并輸出
源代碼：
void HuffmanTree::Menu()
{
cout<<"請輸入你要編碼的文本,按回車(chē)鍵確定輸入"<
string Input;
char letter;
do //將字符逐個(gè)讀入Input變量中
{
letter=cin.get();
Input.append(1,letter);
}while(letter!=' ');
Input.erase(Input.length()-1,1); //去掉Input末尾的回車(chē)符
Init(Input); //根據輸入的字符串創(chuàng )建哈夫曼樹(shù)及其編碼表 cout<<"直觀(guān)打印哈夫曼樹(shù)"<
PrintTree(2*tSize-1-1,1); //打印哈夫曼樹(shù)
cout<<' '<<' ';
string d1,d2;
cout<<"編碼后的字符串為"<
Encode(Input,d1); //編碼并打印編碼串
cout<<"解碼后的字符串為"<
Decode(d1,d2); //解碼并打印解碼串
cout<<"ASCII碼編碼與HUFFMAN編碼的比較"<
Calculate(Input,d1); //計算編碼前后的壓縮比
}
2.3 其他
1.由于題目要求能輸入任意長(cháng)的字符串，所以本程序采用了string變量來(lái)記錄輸入
的字符串，并采用string類(lèi)的類(lèi)成員函數來(lái)完成各項任務(wù)
2.打印哈夫曼樹(shù)時(shí)采用了遞歸函數，且采用了凹凸表的形式打印哈夫曼樹(shù)。
3.為了輸入空格，輸入時(shí)采取逐個(gè)字符輸入的方式
3. 程序運行結果
主函數流程圖：
運行結果：
各函數運行正常，沒(méi)有出現bug
4. 總結
經(jīng)過(guò)這次實(shí)驗，我了解了哈夫曼樹(shù)的創(chuàng )建過(guò)程，了解了一種不等長(cháng)編碼的方法，用設斷點(diǎn)調試的方法更加熟練，同時(shí)熟悉了STL中string類(lèi)型的用法，對C++更加熟悉
【北郵數據結構實(shí)驗報告】相關(guān)文章：
北郵研究生在京就業(yè)前景如何07-14
北郵的通信工程就業(yè)前景怎么樣07-14
北郵的工程管理專(zhuān)業(yè)好嗎？以后就業(yè)前景咋樣��？07-11
北郵網(wǎng)絡(luò )工程專(zhuān)業(yè)和通信工程就業(yè)前景誰(shuí)更好？07-14
北郵考研考哪個(gè)院的研究生就業(yè)前景好一些07-14
北郵通信，華科電氣工程及其自動(dòng)哪個(gè)好？哪個(gè)就業(yè)前景好？07-11
同濟大學(xué)的土木工程和北郵的通信工程哪個(gè)就業(yè)前景更好07-14
調劑到北郵軟院讀通信工程專(zhuān)業(yè)怎么樣？就業(yè)前景好嗎？07-14
京東包郵嗎？07-11
科技實(shí)驗報告05-26