使用C語(yǔ)言詳解霍夫曼樹(shù)數(shù)據(jù)結(jié)構(gòu)
1、基本概念
a、路徑和路徑長(zhǎng)度
若在一棵樹(shù)中存在著一個(gè)結(jié)點(diǎn)序列 k1，k2，……，kj， 使得 ki是ki+1 的雙親（1<=i<j），則稱(chēng)此結(jié)點(diǎn)序列是從 k1 到 kj 的路徑。
從 k1 到 kj 所經(jīng)過(guò)的分支數(shù)稱(chēng)為這兩點(diǎn)之間的路徑長(zhǎng)度，它等于路徑上的結(jié)點(diǎn)數(shù)減1.
b、結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度
在許多應(yīng)用中，常常將樹(shù)中的結(jié)點(diǎn)賦予一個(gè)有著某種意義的實(shí)數(shù)，我們稱(chēng)此實(shí)數(shù)為該結(jié)點(diǎn)的權(quán)，(如下面一個(gè)樹(shù)中的藍(lán)色數(shù)字表示結(jié)點(diǎn)的權(quán))
結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度規(guī)定為從樹(shù)根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積。
c、樹(shù)的帶權(quán)路徑長(zhǎng)度
樹(shù)的帶權(quán)路徑長(zhǎng)度定義為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，公式為：
其中，n表示葉子結(jié)點(diǎn)的數(shù)目，wi 和 li 分別表示葉子結(jié)點(diǎn) ki 的權(quán)值和樹(shù)根結(jié)點(diǎn)到 ki 之間的路徑長(zhǎng)度。
如下圖中樹(shù)的帶權(quán)路徑長(zhǎng)度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4 = 122
d、哈夫曼樹(shù)
哈夫曼樹(shù)又稱(chēng)最優(yōu)二叉樹(shù)。它是 n 個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度 WPL 最小的二叉樹(shù)。
如下圖為一哈夫曼樹(shù)示意圖。
2、構(gòu)造哈夫曼樹(shù)
假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹(shù)的構(gòu)造規(guī)則為：
(1) 將w1、w2、…，wn看成是有n 棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；
(2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；
(3)從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；
(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為所求得的哈夫曼樹(shù)。
如：對(duì) 下圖中的六個(gè)帶權(quán)葉子結(jié)點(diǎn)來(lái)構(gòu)造一棵哈夫曼樹(shù)，步驟如下：
注意：為了使得到的哈夫曼樹(shù)的結(jié)構(gòu)盡量唯一，通常規(guī)定生成的哈夫曼樹(shù)中每個(gè)結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)。
具體算法如下：
//2、根據(jù)數(shù)組 a 中 n 個(gè)權(quán)值建立一棵哈夫曼樹(shù)，返回樹(shù)根指針
struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = malloc(n*sizeof(struct BTreeNode));
for (i = 0; i < n; i++) //初始化b指針數(shù)組，使每個(gè)指針元素指向a數(shù)組中對(duì)應(yīng)的元素結(jié)點(diǎn)
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)//進(jìn)行 n-1 次循環(huán)建立哈夫曼樹(shù)
{
//k1表示森林中具有最小權(quán)值的樹(shù)根結(jié)點(diǎn)的下標(biāo)，k2為次最小的下標(biāo)
int k1 = -1, k2;
for (j = 0; j < n; j++)//讓k1初始指向森林中第一棵樹(shù)，k2指向第二棵
{
if (b[j] != NULL && k1 == -1)
{
k1 = j;
continue;
}
if (b[j] != NULL)
{
k2 = j;
break;
}
}
for (j = k2; j < n; j++)//從當(dāng)前森林中求出最小權(quán)值樹(shù)和次最小
{
if (b[j] != NULL)
{
if (b[j]->data < b[k1]->data)
{
k2 = k1;
k1 = j;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
//由最小權(quán)值樹(shù)和次最小權(quán)值樹(shù)建立一棵新樹(shù)，q指向樹(shù)根結(jié)點(diǎn)
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;//將指向新樹(shù)的指針賦給b指針數(shù)組中k1位置
b[k2] = NULL;//k2位置為空
}
free(b); //刪除動(dòng)態(tài)建立的數(shù)組b
return q; //返回整個(gè)哈夫曼樹(shù)的樹(shù)根指針
}
3、哈夫曼編碼
在電報(bào)通信中，電文是以二進(jìn)制的0、1序列傳送的，每個(gè)字符對(duì)應(yīng)一個(gè)二進(jìn)制編碼，為了縮短電文的總長(zhǎng)度，采用不等長(zhǎng)編碼方式，構(gòu)造哈夫曼樹(shù)，
將每個(gè)字符的出現(xiàn)頻率作為字符結(jié)點(diǎn)的權(quán)值賦予葉子結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)的左右分支分別用0和1編碼，從樹(shù)根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑上
所經(jīng)分支的0、1編碼序列等于該葉子結(jié)點(diǎn)的二進(jìn)制編碼。如上文所示的哈夫曼編碼如下：
a 的編碼為：00
b 的編碼為：01
c 的編碼為：100
d 的編碼為：1010
e 的編碼為：1011
f 的編碼為：11
4、哈夫曼樹(shù)的操作運(yùn)算
以上文的哈夫曼樹(shù)作為具體實(shí)例，用詳細(xì)的程序展示哈夫曼樹(shù)的操作運(yùn)算
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
struct BTreeNode
{
ElemType data;
struct BTreeNode* left;
struct BTreeNode* right;
};
//1、輸出二叉樹(shù)，可在前序遍歷的基礎(chǔ)上修改。采用廣義表格式，元素類(lèi)型為int
void PrintBTree_int(struct BTreeNode* BT)
{
if (BT != NULL)
{
printf("%d", BT->data); //輸出根結(jié)點(diǎn)的值
if (BT->left != NULL || BT->right != NULL)
{
printf("(");
PrintBTree_int(BT->left); //輸出左子樹(shù)
if (BT->right != NULL)
printf(",");
PrintBTree_int(BT->right); //輸出右子樹(shù)
printf(")");
}
}
}
//2、根據(jù)數(shù)組 a 中 n 個(gè)權(quán)值建立一棵哈夫曼樹(shù)，返回樹(shù)根指針
struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = malloc(n*sizeof(struct BTreeNode));
for (i = 0; i < n; i++) //初始化b指針數(shù)組，使每個(gè)指針元素指向a數(shù)組中對(duì)應(yīng)的元素結(jié)點(diǎn)
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)//進(jìn)行 n-1 次循環(huán)建立哈夫曼樹(shù)
{
//k1表示森林中具有最小權(quán)值的樹(shù)根結(jié)點(diǎn)的下標(biāo)，k2為次最小的下標(biāo)
int k1 = -1, k2;
for (j = 0; j < n; j++)//讓k1初始指向森林中第一棵樹(shù)，k2指向第二棵
{
if (b[j] != NULL && k1 == -1)
{
k1 = j;
continue;
}
if (b[j] != NULL)
{
k2 = j;
break;
}
}
for (j = k2; j < n; j++)//從當(dāng)前森林中求出最小權(quán)值樹(shù)和次最小
{
if (b[j] != NULL)
{
if (b[j]->data < b[k1]->data)
{
k2 = k1;
k1 = j;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
//由最小權(quán)值樹(shù)和次最小權(quán)值樹(shù)建立一棵新樹(shù)，q指向樹(shù)根結(jié)點(diǎn)
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;//將指向新樹(shù)的指針賦給b指針數(shù)組中k1位置
b[k2] = NULL;//k2位置為空
}
free(b); //刪除動(dòng)態(tài)建立的數(shù)組b
return q; //返回整個(gè)哈夫曼樹(shù)的樹(shù)根指針
}
//3、求哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度
ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始為0
{
if (FBT == NULL) //空樹(shù)返回0
return 0;
else
{
if (FBT->left == NULL && FBT->right == NULL)//訪(fǎng)問(wèn)到葉子結(jié)點(diǎn)
return FBT->data * len;
else //訪(fǎng)問(wèn)到非葉子結(jié)點(diǎn)，進(jìn)行遞歸調(diào)用，返回左右子樹(shù)的帶權(quán)路徑長(zhǎng)度之和，len遞增
return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
//4、哈夫曼編碼（可以根據(jù)哈夫曼樹(shù)帶權(quán)路徑長(zhǎng)度的算法基礎(chǔ)上進(jìn)行修改）
void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值為0
{
static int a[10];//定義靜態(tài)數(shù)組a，保存每個(gè)葉子的編碼，數(shù)組長(zhǎng)度至少是樹(shù)深度減一
if (FBT != NULL)//訪(fǎng)問(wèn)到葉子結(jié)點(diǎn)時(shí)輸出其保存在數(shù)組a中的0和1序列編碼
{
if (FBT->left == NULL && FBT->right == NULL)
{
int i;
printf("結(jié)點(diǎn)權(quán)值為%d的編碼：", FBT->data);
for (i = 0; i < len; i++)
printf("%d", a[i]);
printf("\n");
}
else//訪(fǎng)問(wèn)到非葉子結(jié)點(diǎn)時(shí)分別向左右子樹(shù)遞歸調(diào)用，并把分支上的0、1編碼保存到數(shù)組a
{ //的對(duì)應(yīng)元素中，向下深入一層時(shí)len值增1
a[len] = 0;
HuffManCoding(FBT->left, len + 1);
a[len] = 1;
HuffManCoding(FBT->right, len + 1);
}
}
}
//主函數(shù)
void main()
{
int n, i;
ElemType* a;
struct BTreeNode* fbt;
printf("從鍵盤(pán)輸入待構(gòu)造的哈夫曼樹(shù)中帶權(quán)葉子結(jié)點(diǎn)數(shù)n：");
while(1)
{
scanf("%d", &n);
if (n > 1)
break;
else
printf("重輸n值：");
}
a = malloc(n*sizeof(ElemType));
printf("從鍵盤(pán)輸入%d個(gè)整數(shù)作為權(quán)值：", n);
for (i = 0; i < n; i++)
scanf(" %d", &a[i]);
fbt = CreateHuffman(a, n);
printf("廣義表形式的哈夫曼樹(shù)：");
PrintBTree_int(fbt);
printf("\n");
printf("哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度：");
printf("%d\n", WeightPathLength(fbt, 0));
printf("樹(shù)中每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼：\n");
HuffManCoding(fbt, 0);
}
運(yùn)行結(jié)果：
下面來(lái)看一道ACM題目
題目描述：
哈夫曼樹(shù)，第一行輸入一個(gè)數(shù)n，表示葉結(jié)點(diǎn)的個(gè)數(shù)。需要用這些葉結(jié)點(diǎn)生成哈夫曼樹(shù)，根據(jù)哈夫曼樹(shù)的概念，這些結(jié)點(diǎn)有權(quán)值，即weight，題目需要輸出所有結(jié)點(diǎn)的值與權(quán)值的乘積之和。
輸入：
輸入有多組數(shù)據(jù)。
每組第一行輸入一個(gè)數(shù)n，接著輸入n個(gè)葉節(jié)點(diǎn)（葉節(jié)點(diǎn)權(quán)值不超過(guò)100，2<=n<=1000）。
輸出：
輸出權(quán)值。
樣例輸入：
5
1 2 2 5 9
樣例輸出：
37
ac代碼
鏈表構(gòu)建哈夫曼樹(shù)（插入排序）
#include <stdio.h>
#include <stdlib.h>
#define max 1001
struct htree
{
int weight;
struct htree *lchild;
struct htree *rchild;
struct htree *next;
};
void addNode(struct htree *, struct htree *);
struct htree* createHfmtree(int *, int);
int getWpl(struct htree *, int);
int main()
{
int w[max];
int i, n, wpl;
struct htree *ht;
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i ++)
{
scanf("%d", &w[i]);
}
ht = createHfmtree(w, n);
wpl = getWpl(ht, 0);
printf("%d\n", wpl);
}
return 0;
}
struct htree* createHfmtree(int *w, int n)
{
int i;
struct htree *head, *pl, *pr, *proot;
head = (struct htree *)malloc(sizeof(struct htree));
head->next = NULL;
for(i = 0; i < n; i ++)
{
struct htree *pnode = malloc(sizeof(struct htree));
pnode->weight = *(w + i);
pnode->lchild = pnode->rchild = pnode->next = NULL;
addNode(head, pnode);
}
while(head->next)
{
if(head->next->next == NULL)
break;
pl = head->next;
pr = pl->next;
head->next = pr->next;
proot = (struct htree *)malloc(sizeof(struct htree));
proot->weight = pl->weight + pr->weight;
proot->lchild = pl;
proot->rchild = pr;
addNode(head, proot);
}
return head->next;
}
void addNode(struct htree *head, struct htree *pnode)
{
struct htree *t = head;
while(t->next && t->next->weight < pnode->weight)
t = t->next;
pnode->next = t->next;
t->next = pnode;
}
int getWpl(struct htree *ht, int level)
{
if(ht == NULL)
return 0;
if(!ht->lchild && !ht->rchild)
{
return ht->weight * level;
}
return getWpl(ht->lchild, level + 1) + getWpl(ht->rchild, level + 1);
}
上一篇：淺析C語(yǔ)言中strtol()函數(shù)與strtoul()函數(shù)的用法
欄 目：C語(yǔ)言
下一篇：北郵計(jì)算機(jī)考研復(fù)試題的C語(yǔ)言解答精選
本文標(biāo)題：使用C語(yǔ)言詳解霍夫曼樹(shù)數(shù)據(jù)結(jié)構(gòu)
本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/2875.html
您可能感興趣的文章
- 04-02c語(yǔ)言函數(shù)調(diào)用后清空內(nèi)存 c語(yǔ)言調(diào)用函數(shù)刪除字符
- 04-02c語(yǔ)言的正則匹配函數(shù) c語(yǔ)言正則表達(dá)式函數(shù)庫(kù)
- 04-02func函數(shù)+在C語(yǔ)言 func函數(shù)在c語(yǔ)言中
- 04-02c語(yǔ)言中對(duì)數(shù)函數(shù)的表達(dá)式 c語(yǔ)言中對(duì)數(shù)怎么表達(dá)
- 04-02c語(yǔ)言用函數(shù)寫(xiě)分段 用c語(yǔ)言表示分段函數(shù)
- 04-02c語(yǔ)言編寫(xiě)函數(shù)冒泡排序 c語(yǔ)言冒泡排序法函數(shù)
- 04-02c語(yǔ)言沒(méi)有round函數(shù) round c語(yǔ)言
- 04-02c語(yǔ)言分段函數(shù)怎么求 用c語(yǔ)言求分段函數(shù)
- 04-02C語(yǔ)言中怎么打出三角函數(shù) c語(yǔ)言中怎么打出三角函數(shù)的值
- 04-02c語(yǔ)言調(diào)用函數(shù)求fibo C語(yǔ)言調(diào)用函數(shù)求階乘
閱讀排行
- 1C語(yǔ)言 while語(yǔ)句的用法詳解
- 2java 實(shí)現(xiàn)簡(jiǎn)單圣誕樹(shù)的示例代碼(圣誕
- 3利用C語(yǔ)言實(shí)現(xiàn)“百馬百擔(dān)”問(wèn)題方法
- 4C語(yǔ)言中計(jì)算正弦的相關(guān)函數(shù)總結(jié)
- 5c語(yǔ)言計(jì)算三角形面積代碼
- 6什么是 WSH(腳本宿主)的詳細(xì)解釋
- 7C++ 中隨機(jī)函數(shù)random函數(shù)的使用方法
- 8正則表達(dá)式匹配各種特殊字符
- 9C語(yǔ)言十進(jìn)制轉(zhuǎn)二進(jìn)制代碼實(shí)例
- 10C語(yǔ)言查找數(shù)組里數(shù)字重復(fù)次數(shù)的方法
本欄相關(guān)
- 04-02c語(yǔ)言函數(shù)調(diào)用后清空內(nèi)存 c語(yǔ)言調(diào)用
- 04-02func函數(shù)+在C語(yǔ)言 func函數(shù)在c語(yǔ)言中
- 04-02c語(yǔ)言的正則匹配函數(shù) c語(yǔ)言正則表達(dá)
- 04-02c語(yǔ)言用函數(shù)寫(xiě)分段 用c語(yǔ)言表示分段
- 04-02c語(yǔ)言中對(duì)數(shù)函數(shù)的表達(dá)式 c語(yǔ)言中對(duì)
- 04-02c語(yǔ)言編寫(xiě)函數(shù)冒泡排序 c語(yǔ)言冒泡排
- 04-02c語(yǔ)言沒(méi)有round函數(shù) round c語(yǔ)言
- 04-02c語(yǔ)言分段函數(shù)怎么求 用c語(yǔ)言求分段
- 04-02C語(yǔ)言中怎么打出三角函數(shù) c語(yǔ)言中怎
- 04-02c語(yǔ)言調(diào)用函數(shù)求fibo C語(yǔ)言調(diào)用函數(shù)求
隨機(jī)閱讀
- 08-05織夢(mèng)dedecms什么時(shí)候用欄目交叉功能？
- 08-05DEDE織夢(mèng)data目錄下的sessions文件夾有什
- 01-11Mac OSX 打開(kāi)原生自帶讀寫(xiě)NTFS功能(圖文
- 08-05dedecms(織夢(mèng))副欄目數(shù)量限制代碼修改
- 04-02jquery與jsp,用jquery
- 01-10delphi制作wav文件的方法
- 01-10SublimeText編譯C開(kāi)發(fā)環(huán)境設(shè)置
- 01-10C#中split用法實(shí)例總結(jié)
- 01-11ajax實(shí)現(xiàn)頁(yè)面的局部加載
- 01-10使用C語(yǔ)言求解撲克牌的順子及n個(gè)骰子