您好,登錄后才能下訂單哦!
從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑,路徑上的分支數(shù)目稱作路徑長度。樹的路徑長度是從樹根到每個結(jié)點的路徑長度之和。結(jié)點的帶權(quán)路徑長度為結(jié)點到樹根之間的路徑長度與結(jié)點上權(quán)的乘機,樹的帶權(quán)路徑長度為樹中所有葉子節(jié)點的帶權(quán)路徑長度之和。
頭文件:
/*****************************************************************************************************
*Copyright: Yue Workstation
*
*FileName: HuffmanTree.h
*
*Function: Huffman樹的數(shù)據(jù)結(jié)構(gòu)定義
*
*Author: Abel Lee
*
*CreateOn: 2012-2-19
*
*Log: 2012-2-19 由Abel Lee創(chuàng)建
*****************************************************************************************************/
#ifndef HUFFMAN_TREE_H
#define HUFFMAN_TREE_H
#include "global.h"
#define NUMBER 4
typedef struct
{
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;
void PrintHuffmanTree(HuffmanTree ht, int n);
#endif
源文件:
/*****************************************************************************************************
*Copyright:Yue Workstation
*
*FileName: HuffmanTree.c
*
*Function: Huffman樹的操作
*
*Author:Abel Lee
*
*CreateOn:2012-2-19
*
*Log:2011-5-3 由Abel Lee創(chuàng)建
*****************************************************************************************************/
#include "../inc/HuffmanTree.h"
//最小數(shù)
static int _min(HuffmanTree ht, int i)
{
int j=0;
int temp=0;
for(j = 0; j<i; ++j)
{
if (ht[j].parent == 0)
{
temp = j;
break;
}
}
for(j = temp; j<i; ++j)
{
if (ht[j].parent == 0 && ht[j].weight<ht[temp].weight)
{
temp = j;
}
}
return temp;
}
//次小數(shù)
static int _sec_min(HuffmanTree ht, int i)
{
int min = _min(ht, i);
int j=0;
int temp=0;
for(j = 0; j<i; ++j)
{
if (ht[j].parent == 0 && j != min)
{
temp = j;
break;
}
}
for(j = temp; j<i; ++j)
{
if (ht[j].parent == 0 && ht[j].weight<ht[temp].weight && j != min)
{
temp = j;
}
}
return temp;
}
//打印赫夫曼樹
void PrintHuffmanTree(HuffmanTree ht, int n)
{
int i = 0;
int temp = 0;
int val = 0;
for (i = 0; i < n; ++i)
{
printf("%d:", ht[i].weight);
val = i;
temp = ht[i].parent;
while (temp)
{
if (ht[temp].lchild == val)
{
printf("0");
}
else if (ht[temp].rchild == val)
{
printf("1");
}
else
{
}
val = temp;
temp = ht[temp].parent;
}
printf("\n");
}
}
/****************************************************************************************************
*Function Name: Huffmancoding
*
*Function: 獲取霍夫曼編碼
*
*Parameter: ht:huffman樹
* w:權(quán)值
* n:數(shù)量
*
*Return Value: 無
*
*Author:Abel Lee
*
*Log:2012-2-19
***************************************************************************************************/
void Huffmancoding(HuffmanTree ht, int *w, int n)
{//w 存放 n 個字符的權(quán)值,構(gòu)造赫夫曼樹 ht, 并求出 n 個字符的赫夫曼編碼 hc
int m;
int i;
int min=0, sec_min=0;
HuffmanTree p;
if (n<=1) return;
m = 2*n-1;
ht = (HuffmanTree)malloc(m*sizeof(HTNode));
p = ht;
for(i=0; i<n; ++i, ++p, ++w)//給葉子節(jié)點賦值,前n個為葉子節(jié)點
{
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for(; i<m; ++i,++p)//給非葉子節(jié)點賦值,第n個到(2*n - 1)個為葉子節(jié)點
{
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for(i = n; i<m; ++i)
{
min = _min(ht, i);
sec_min = _sec_min(ht, i);
ht[min].parent = ht[sec_min].parent = i;
ht[i].lchild = min;
ht[i].rchild = sec_min;
ht[i].weight = ht[min].weight + ht[sec_min].weight;
}
PrintHuffmanTree(ht, n);
}
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。