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