《數(shù)據(jù)結(jié)構(gòu)哈夫曼樹C++實(shí)現(xiàn)》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)哈夫曼樹C++實(shí)現(xiàn)（5頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、實(shí)驗(yàn)報(bào)告
一、 實(shí)驗(yàn)?zāi)康?
1. 掌握哈夫曼樹的基本概念及所用的存儲(chǔ)結(jié)構(gòu)。
2. 掌握哈夫曼樹的建立算法。
3. 掌握哈夫曼樹的應(yīng)用（哈夫曼樹的編碼和譯碼） 。
二、 實(shí)驗(yàn)內(nèi)容
給定權(quán)值 5、 29、 7、 8、 14、 23、 3、 11，建立哈夫曼樹，輸出哈夫曼編碼。
對(duì)上述給定的哈夫曼樹及得到的哈夫曼編碼， 試輸入一串二進(jìn)制編碼， 輸出它的 哈夫曼譯碼。 三、 實(shí)驗(yàn)與算法分析
建立哈夫曼樹， 將哈夫曼樹的機(jī)構(gòu)定義為一個(gè)結(jié)構(gòu)型的一維數(shù)組每個(gè)元素含
有四項(xiàng)：權(quán)值、雙親、左孩子、右孩子。給定的權(quán)值可以從鍵盤輸入，要輸出所
建立的哈夫曼樹，只要輸出表示哈夫曼樹的一維數(shù)組中的全部
2、元素即可。
要實(shí)現(xiàn)哈夫曼編碼，只要在所建立的哈夫曼樹上進(jìn)行二進(jìn)制編碼：往左走，
編碼為 0，往右走編碼為 1，然后將從根結(jié)點(diǎn)到樹葉中的所有 0,1 排列起來(lái)，則
得到該樹葉的哈夫曼編碼。 哈夫曼編碼可以用一個(gè)結(jié)構(gòu)型的一維數(shù)組保存， 每個(gè)
元素包含：編碼，編碼的開始位置，編碼所對(duì)應(yīng)的字符三項(xiàng)。
哈夫曼譯碼，就是將輸入的譯碼還原成對(duì)應(yīng)的字符。
抽象的算法描述： 將建立哈夫曼樹、 實(shí)現(xiàn)哈夫曼編碼、 哈夫曼譯碼都定義成
子函數(shù)的的形式， 然后在主函數(shù)中調(diào)用它們。 哈夫曼樹的構(gòu)造： 假設(shè)有 n 個(gè)權(quán)值，
則構(gòu)造出的有n個(gè)葉子結(jié)點(diǎn)。n個(gè)權(quán)值分別設(shè)為w1,w2, ,wn,則哈夫曼樹的
構(gòu)造
3、規(guī)則為：（1）將w1,w2, ,wn看成是有n棵樹的森林（每棵樹僅有一個(gè)結(jié)
點(diǎn)） ； （ 2）在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹合并，作為一棵新樹的左右
子樹， 且新樹的根結(jié)點(diǎn)權(quán)值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之； （ 3） 從森林中刪除
選取的兩棵樹，并將新樹加入森林。 （ 4）重復(fù)（ 2） 、 （ 3）步，直到森林中只剩一
棵樹為止，該樹即為我們所求得的哈夫曼樹。
四、 可執(zhí)行程序及注釋
實(shí)驗(yàn)代碼
#include
#include
const int n=8; //maxn 表示葉子數(shù)目
const int m=2*n-1;
4、 //m 為森林中樹的棵數(shù)
struct tree //哈夫曼樹中的一個(gè)結(jié)點(diǎn)
{
float weight; // 權(quán)值 int parent; //雙親 int lch,rch; //左孩子、右孩子
}; struct codetype //哈弗曼編碼
{
int bits[n+1]; //哈弗曼編碼
int start; //編碼的存放位置 char ch; //所對(duì)應(yīng)的字符
};
tree hftree[m+1];
codetype code[n+1];
void creathuffmantree() //建立哈夫曼樹 {
int i,j,p1,p2;
flo
5、at s1,s2;
for(i=1;i<=m;i++) {
hftree[i].parent=0;
hftree[i].lch=0;
hftree[i].rch=0;
hftree[i].weight=0;
}
cout<<"請(qǐng)輸入"<>hftree[i].weight; //輸入權(quán)值
{
p1=p2=0;
s1=s2=32767;
for(j=1;j<=i-1;j++)
for(i=n+1;i<=m;i++) //進(jìn)行次合并
//p1,p2 分別指向兩個(gè)權(quán)值最小的值的位置
//s1,
6、s2代表兩個(gè)最小權(quán)值
//選兩個(gè)最小值 if(hftree[j].parent==0) //該權(quán)值還沒(méi)有選中
if(hftree[j].weight
7、hftree[p1].weight+hftree[p2].weight;
}
}
void huffcode() // 哈弗曼編碼
codetype cd;
int c,p;
for(int i=1;i<=n;i++)
(
cd.start=n+1;
cd.ch=96+i; //第一個(gè)樹葉對(duì)應(yīng)字母a,其余依此類推
c=i;
p=hftree[i].parent;
while(p!=0)
(
cd.start--;
if(hftree[p].lch==c)
cd.bits[cd.start]=0;
else
cd.bits[cd.start]=1;
c=p;
8、
p=hftree[p].parent;
}
code[i]=cd;
}
for(i=1;i<=n;i++)
(
cout<<"字 符"<>b;
while((b==0)||(b==1))
(
if(b==0)
i=hftree[i].lch;
else
i=hftree[i].rch;
if(hftree[i].lch==0)
(
cout<>b;
}
}
void main()
{
creathuffmantree(); 〃建立哈夫曼樹
huffcode(); //實(shí)現(xiàn)哈弗曼編碼
trancode(); //進(jìn)行哈弗曼譯碼
cout<
數(shù)據(jù)結(jié)構(gòu)哈夫曼樹C++實(shí)現(xiàn)
