導航:首頁 > 源碼編譯 > 哈夫曼樹需要實現的演算法

哈夫曼樹需要實現的演算法

發布時間:2022-08-19 00:19:27

A. 哈夫曼樹演算法

題目的闡述:以N進制編碼方式對一個英文字串中的字元進行編碼,每個不同的字元其編碼不同.使得由新的編碼替代原串後總碼長最小,且輸入0,1,2,...,N-1構成的數字串後,依照該編碼方式可以正確的對譯出唯一的英文原串.如:N=3英文原串為ABBCBADDACE其對應的一種編碼方式為A:00B:01C:020D:021E:022原串對譯後的編碼為000101020010002102100020022其碼長為27若輸入編碼串0102002200則對應的英文原串為BCEA 分析: 假設英文原串中的字元存放於字元集S中,‖S‖=X,每個字元在字串中出現的概率為W[i],L[i]為字元i的編碼長.依題意得,對S集合中的不同字元進行N進制編碼後要求1)新字串的碼長最短WPL=∑W[i]*L[i]
(i∈1..X)使得在WPL是所有編碼方式中的最小值2)編碼無二義性任意一字元編碼都不為其它字元編碼的前綴 此題以哈夫曼樹來解答是非常適宜的.N為此哈夫曼樹的分叉數,S字元集里的元素即為此N叉哈夫曼樹的葉子,概率W[i]即為葉子結點的權重,從根結點到各葉子結點的路徑長即為該葉子結點的編碼長L[i].由哈夫曼樹的思想可以知道哈夫曼樹的建立是一步到位的貪心法,即權重越大的結點越靠近該樹的根,這樣,出現頻率越大的字元其編碼就越短.但具體應該怎樣建立起此N叉哈夫曼樹呢?我們首先以N=2為例:S={A,B,C,D}W=[3,1,2,1]首先從W中選出兩個最小權,1,1,將其刪去,並以2(即1+1)替代W=[3,2,2];再從新的W中取出兩個最小權,2,2,將其刪去,並以4(即2+2)替代W=[3,4];依此類推,直到W中只一個值時合並結束,此時W=[7]以上兩兩合並的過程即為二叉哈夫曼樹的建立過程,每一次的合並即是將兩棵子樹歸於一個根結點下,於是可以建立二叉樹如下: m0åæ1mmA0åæ1mmC0åæ1mmBD MIN-WPL=3*1+1*3+2*2+1*3=13 從某一根結點出發走向其左子樹標記為0,走向其右子樹標記為1,則可以得到以下編碼A,B,C,D對應的編碼為A:0B:110C:10D:111
N=3時又是怎樣一種情況呢?設S={A,B,C,D,E}W=[7,4,2,5,3}則按權重排序可得S={D,B,E,C,A}W=[7,5,4,3,2]那麼此哈夫曼樹的樹形應為怎樣呢?是以下的左圖,還是右圖,或是兩者均不是mmåâæåæmmllmåæåæCAåælllllmADBEDåæ
lmBåællEC 顯然,要帶權路徑長WPL最短,那麼,此樹的高度就應盡可能的小,由此可知將此樹建成豐滿N叉樹是最合理的,於是我們盡量使樹每一層都為N個分枝.對於這道題的情況,我們具體來分析.按照哈夫曼樹的思想,首先從W中取出權最小的三個值,即2,3,4,並以9(2+3+4)來代替,得到新的W=[9,7,5];再將這三個值合並成9+7+5=21這個結點.於是得到三叉哈夫曼樹如下:måâællmDBåâælllECAWPL=1*7+1*5+2*2+2*3+2*4=30以0..N-1依次標記每個根結點的N個分枝,則可以得到每個字元相對應的編碼:A:22B:1C:21D:0E:20我們發現對於這種情況恰巧每層均為N個分枝,但事實上並非所有的N叉哈夫曼樹都可得到每層N個分枝.例於當N=3,‖S‖=6時就不可能構成一棵每層都為三個分枝的三叉樹.如何來處理這種情況呢?最簡單的處理方式就是添加若干出現概率為0的空字元填補在N叉樹的最下一層,這些權為0的虛結點並無實際意義但卻非常方全便於這棵N叉樹的建立.空字元的添加個數add的計算如下:Y=‖S‖mod(n-1)add=0(Y=1)add=1(Y=0)add=N-Y(Y>1) 虛結點的加入使得權重最小的N-add個字元構成了距根結點最遠的分枝,使其它字元構成的N叉樹保持了豐滿的N叉結構.例:N=3S={A,B,C,D,E,F}W=[1,2,3,4,5,6}則y:=6mod(3-1)=0add=1於是構成N叉樹如下:­為虛結點¡åâællmFEåâællmDCåâæBA­WPL=1*6+1*5+2*4+2*3+3*2+3*1+3*0=33對應編碼為:A:221B:220C:21D:20E:1F:0

B. 哈夫曼的如何構造

然而怎樣構造一棵哈夫曼樹呢?最具有一般規律的構造方法就是哈夫曼演算法。一般的數據結構的書中都可以找到其描述: 重復二和三兩步,直到集合F中只有一棵二叉樹為止。
用C語言實現上述演算法,可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構: struct tree{
float weight; /*權值*/
union{
char leaf; /*葉結點信息字元*/
struct tree *left; /*樹的左結點*/
};
struct tree *right; /*樹的右結點*/
};
struct forest{ /*F集合,以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/
};
例:若字母A,B,C,D出現的概率為:0.75,0.54,0.28,0.43;則相應的權值為:75,54,28,43。
構造好哈夫曼樹後,就可根據哈夫曼樹進行編碼。例如:上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹後,經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹,就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼,即任一個字元的編碼都不是另一個字元的編碼的前綴,否則,編碼就不能進行翻譯。例如:a,b,c,d的編碼為:0,10,110,111,對於編碼串:1010就翻譯為bb。剛才進行哈夫曼編碼的規則是從根結點到葉結點(包含原信息)的路徑,向左孩子前進編碼為0,向右孩子前進編碼為1,當然你也可以反過來規定。

C. 請描述哈夫曼演算法,並用圖描述構造哈夫曼樹的過程。

這個講的相當清楚。
首先介紹什麼是哈夫曼樹。哈夫曼樹又稱最優二叉樹,是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度,就是樹中所有的葉結點的權值乘上其到根結點的路徑長度(若根結點為0層,葉結點到根結點的路徑長度為葉結點的層數)。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹,相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。
哈夫曼在上世紀五十年代初就提出這種編碼時,根據字元出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中,若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列,則編碼的平均長度是最小的。(註:碼字即為符號經哈夫曼編碼後得到的編碼,其長度是因符號出現的概率而不同,所以說哈夫曼編碼是變長的編碼。)
然而怎樣構造一棵哈夫曼樹呢?最具有一般規律的構造方法就是哈夫曼演算法。一般的數據結構的書中都可以找到其描述:
一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉樹Ti中只有一個權值為Wi的根結點,它的左右子樹均為空。(為方便在計算機上實現演算法,一般還要求以Ti的權值Wi的升序排列。)
二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹,新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹,並把這棵新的二叉樹同樣以升序排列加入到集合F中。
四、重復二和三兩步,直到集合F中只有一棵二叉樹為止。
用C語言實現上述演算法,可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構: struct tree{
float weight; /*權值*/
union{
char leaf; /*葉結點信息字元*/
struct tree *left; /*樹的左結點*/
};
struct tree *right; /*樹的右結點*/
};
struct forest{ /*F集合,以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/
};
例:若字母A,B,Z,C出現的概率為:0.75,0.54,0.28,0.43;則相應的權值為:75,54,28,43。
構造好哈夫曼樹後,就可根據哈夫曼樹進行編碼。例如:上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹後,經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹,就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼,即任一個字元的編碼都不是另一個字元的編碼的前綴,否則,編碼就不能進行翻譯。例如:a,b,c,d的編碼為:0,10,101,11,對於編碼串:1010就可翻譯為bb或ca,因為b的編碼是c的編碼的前綴。剛才進行哈夫曼編碼的規則是從根結點到葉結點(包含原信息)的路徑,向左孩子前進編碼為0,向右孩子前進編碼為1,當然你也可以反過來規定。
這種編碼方法是靜態的哈夫曼編碼,它對需要編碼的數據進行兩遍掃描:第一遍統計原數據中各字元出現的頻率,利用得到的頻率值創建哈夫曼樹,並必須把樹的信息保存起來,即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來,(用4Bytes的長度存儲頻率值,頻率值的表示範圍為0--2^32-1,這已足夠表示大文件中字元出現的頻率了)以便解壓時創建同樣的哈夫曼樹進行解壓;第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼,並把編碼後得到的碼字存儲起來。 靜態哈夫曼編碼方法有一些缺點:一、對於過短的文件進行編碼的意義不大,因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間;二、進行哈夫曼編碼,存儲編碼信息時,若用與通訊網路,就會引起較大的延時;三、對較大的文件進行編碼時,頻繁的磁碟讀寫訪問會降低數據編碼的速度。
因此,後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹,對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的,編碼和解碼使用相同的初始哈夫曼樹,每處理完一個字元,編碼和解碼使用相同的方法修改哈夫曼樹,所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比,所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼復雜的多,有興趣的讀者可參考有關數據結構與演算法的書籍。
前面提到的JPEG中用到了哈夫曼編碼,並不是說JPEG就只用哈夫曼編碼就可以了,而是一幅圖片經過多個步驟後得到它的一列數值,對這些數值進行哈夫曼編碼,以便存儲或傳輸。哈夫曼編碼方法比較易懂,大家可以根據它的編碼方法,自己編寫哈夫曼編碼和解碼的程序。

D. 試編寫實現哈夫曼樹和哈夫曼編碼的演算法這是數據結構里的問題,要求用C++6.0來實現

#include <stdio.h>
#include <malloc.h>
#include<math.h>
struct hf
{
char data;
int weight;
struct hf *lc;
struct hf *rc;
struct hf *pc;
int hcd[30];
} *hc[30];
int n;

main()
{struct hf creat();
struct hf bian(struct hf *hc[30]);
struct hf print(struct hf *hc[30]);
int m;
do
{
printf("親!請輸入你所需要的功能:\n1代表構建哈夫曼樹,2代表給哈夫曼樹賦權值,3代表輸出哈夫曼樹的權值");
scanf("%d",&m);
switch(m)
{
case 1:creat();break;
case 2:bian(hc);break;
case 3:print(hc);break;

}
}while (m==1||m==2||m==3);

}

struct hf creat()
{
int i,m,k,p,t,r,u;
int selete (int k,struct hf *hc[30]);
printf("請輸入你所需要構建哈夫曼樹的個數:");
scanf("%d",&n);

for(i=0;i<n;i++)
{
getchar();
printf("請輸入數據的符號");
hc[i]= (struct hf *)malloc(sizeof(struct hf));
scanf("%c",&hc[i]->data);
printf("請輸入數據的權值:");
scanf("%d",&hc[i]->weight);
hc[i]->lc=0;
hc[i]->rc=0;
}
for(t=n;t<(2*n-1);t++)
{
hc[t]=(struct hf *)malloc(sizeof(struct hf));

}
for(u=0;u<(2*n-1);u++)
{
hc[u]->pc=0;
}

for(m=n;m<((2*n)-1);m++)
{ hc[m]->weight=0;
for(r=1;r<=2;r++)
{
p=selete(m,hc);
if(r==1)

{hc[m]->lc=hc[p];
hc[p]->pc=hc[m];

}
if(r==2)
{
hc[m]->rc=hc[p];
hc[p]->pc=hc[m];

}
hc[m]->weight=hc[m]->weight+hc[p]->weight;
}
}
}

int selete(int k,struct hf *hc[30])
{ int a,i,j;

for (i=0;i<k;)
{

if(hc[i]->pc!=0)

i++;

else
{
a=i;
for(j=i+1;j<k;)
{
if(hc[j]->pc!=0)
j++;
else if(hc[a]->weight>hc[j]->weight)
{
a=j;
j++;
}else j++;
}return (a);

}
}

}

struct hf bian(struct hf *hc[30])
{int i,m,t;
struct hf *p1,*p2;
for(i=0;i<n;i++)
{m=0;p1=hc[i];
while(p1->pc!=0)

{ p2=p1->pc;

if(p2->lc==p1)
{hc[i]->hcd[m]=0;
m++;
p1=p1->pc;
}
if(p2->rc==p1)
{ hc[i]->hcd[m]=1;
m++;
p1=p1->pc;
}

}
hc[i]->hcd[29]=m;
}

}

struct hf print(struct hf *hc[30])
{int i,p,m;

printf("其編碼結果如下:\n");
for (i=0;i<n;i++)
{m=hc[i]->hcd[29];
for(p=m-1;p>=0;p--)
{printf("******* %c的哈夫曼編碼為*******\n",hc[i]->data);
for(p=m-1;p>=0;p--)
printf(" %d ",hc[i]->hcd[p]);
printf("\n");
}
}

}

E. 數據結構的問題,求一個構造哈夫曼樹的演算法

void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[])
/*建立葉結點個數為n,權值數組為weight[]的哈夫曼樹*/
{int i,j,m1,m2,x1,x2;
/*哈夫曼樹hafftree[]初始化,n個葉結點共有2n-1個結點*/
for(i=0;i<2*n-1;i++)
{if(i<n) {hafftree[i].data=data[i];
hafftree[i].weight=weight[i]; /*葉結點*/
}
else {hafftree[i].weight=0; /*非葉結點*/
hafftree[i].data='\0';
}
hafftree[i].parent=0; /*初始化沒有雙親結點*/
hafftree[i].flag=0;
hafftree[i].leftchild=-1;
hafftree[i].rightchild=-1;
}
for(i=0;i<n-1;i++) /*構造哈夫曼樹n-1個非葉結點*/
{m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{if(hafftree[j].weight<m1&&hafftree[j].flag==0)
{m2=m1;
x2=x1;
m1=hafftree[j].weight;
x1=j;
}
else if(hafftree[j].weight<m2&&hafftree[j].flag==0)
{m2=hafftree[j].weight;
x2=j;
}
}
hafftree[x1].parent=n+i;
hafftree[x2].parent=n+i;
hafftree[x1].flag=1;
hafftree[x2].flag=1;
hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
hafftree[n+i].leftchild=x1;
hafftree[n+i].rightchild=x2;

}
}
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[])
{/*由n個結點的哈夫曼樹hafftree[]構成的哈夫曼編碼haffcode[]*/
int i,j,child,parent;
struct haffcode newcode;
struct haffcode *cd;
cd=&newcode;
for(i=0;i<n;i++) /*求n個結點的哈夫曼編碼*/
{cd->start=MAXBIT-1; /*不等長編碼的最後一位是n-1*/
cd->weight=hafftree[i].weight;
cd->data=hafftree[i].data; /*取得編碼對應值的字元*/
child=i;
parent=hafftree[child].parent;
while(parent!=0)
{if(hafftree[parent].leftchild==child)
cd->bit[cd->start]=0; /*左孩子編碼為0*/
else
cd->bit[cd->start]=1; /*右孩子編碼為1*/
cd->start--;
child=parent;
parent=hafftree[child].parent;
}
for(j=cd->start+1;j<MAXBIT;j++) /*保存每個葉結點的編碼和等長編碼的起始位*/
haffcode[i].bit[j]=cd->bit[j];
haffcode[i].data=cd->data;
haffcode[i].start=cd->start;
haffcode[i].weight=cd->weight;
}
}

F. 哈夫曼樹及哈夫曼編碼的C程序實現(數據結構題)

去年做的課程設計,有什麼不合要求的自己改改

#include<string.h>
#include<stdlib.h>
#include<stdio.h>

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動態分配數組存儲哈夫曼樹
typedef char *HuffmanCode; //動態分配數組存儲哈夫曼編碼表

void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 演算法6.13
// w存放n個字元的權值(均>0),構造哈夫曼樹HT,
// 並求出n個字元的哈夫曼編碼HC
int i, j;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號單元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼樹的構造過程如下所示:");
printf("HT初態:\n 結點 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意鍵,繼續 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼樹
// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點,
// 其序號分別為s1和s2。
Select(HT, i-1);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 結點 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意鍵,繼續 ...");
getchar();
}

//------無棧非遞歸遍歷哈夫曼樹,求哈夫曼編碼
cd = (char *)malloc(n*sizeof(char)); // 分配求編碼的工作空間
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍歷哈夫曼樹時用作結點狀態標志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登記葉子結點的字元的編碼
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 復制編碼(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2,退回退到父結點,編碼長度減1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("輸入結點數:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("輸入%d個結點的權值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各結點的哈夫曼編碼:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}

G. 哈夫曼演算法

計算過程如圖所示:

H. 哈夫曼樹的構造演算法

/*-------------------------------------------------------------------------
*Name:哈夫曼編碼源代碼。
*Date:2011.04.16
*Author:JeffreyHill+Jezze(解碼部分)
*在Win-TC下測試通過
*實現過程:著先通過HuffmanTree()函數構造哈夫曼樹,然後在主函數main()中
*自底向上開始(也就是從數組序號為零的結點開始)向上層層判斷,若在
*父結點左側,則置碼為0,若在右側,則置碼為1。最後輸出生成的編碼。
*------------------------------------------------------------------------*/
#include<stdio.h>
#include<stdlib.h>

#defineMAXBIT100
#defineMAXVALUE10000
#defineMAXLEAF30
#defineMAXNODEMAXLEAF*2-1

typedefstruct
{
intbit[MAXBIT];
intstart;
}HCodeType;/*編碼結構體*/
typedefstruct
{
intweight;
intparent;
intlchild;
intrchild;
intvalue;
}HNodeType;/*結點結構體*/

/*構造一顆哈夫曼樹*/
voidHuffmanTree(HNodeTypeHuffNode[MAXNODE],intn)
{
/*i、j:循環變數,m1、m2:構造哈夫曼樹不同過程中兩個最小權值結點的權值,
x1、x2:構造哈夫曼樹不同過程中兩個最小權值結點在數組中的序號。*/
inti,j,m1,m2,x1,x2;
/*初始化存放哈夫曼樹數組HuffNode[]中的結點*/
for(i=0;i<2*n-1;i++)
{
HuffNode[i].weight=0;//權值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
HuffNode[i].value=i;//實際值,可根據情況替換為字母
}/*endfor*/

/*輸入n個葉子結點的權值*/
for(i=0;i<n;i++)
{
printf("Pleaseinputweightofleafnode%d: ",i);
scanf("%d",&HuffNode[i].weight);
}/*endfor*/

/*循環構造Huffman樹*/
for(i=0;i<n-1;i++)
{
m1=m2=MAXVALUE;/*m1、m2中存放兩個無父結點且結點權值最小的兩個結點*/
x1=x2=0;
/*找出所有結點中權值最小、無父結點的兩個結點,並合並之為一顆二叉樹*/
for(j=0;j<n+i;j++)
{
if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}/*endfor*/
/*設置找到的兩個子結點x1、x2的父結點信息*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;

printf("x1.weightandx2.weightinround%d:%d,%d ",i+1,HuffNode[x1].weight,HuffNode[x2].weight);/*用於測試*/
printf(" ");
}/*endfor*/
/*for(i=0;i<n+2;i++)
{
printf("Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d ",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///測試
}/*endHuffmanTree*/

//解碼
voiddecodeing(charstring[],HNodeTypeBuf[],intNum)
{
inti,tmp=0,code[1024];
intm=2*Num-1;
char*nump;
charnum[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];

while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{

if(*nump==0)
{
tmp=Buf[tmp].lchild;
}
elsetmp=Buf[tmp].rchild;
nump++;

}

printf("%d",Buf[tmp].value);
}


}


intmain(void)
{

HNodeTypeHuffNode[MAXNODE];/*定義一個結點結構體數組*/
HCodeTypeHuffCode[MAXLEAF],cd;/*定義一個編碼結構體數組,同時定義一個臨時變數來存放求解編碼時的信息*/
inti,j,c,p,n;
charpp[100];
printf("Pleaseinputn: ");
scanf("%d",&n);
HuffmanTree(HuffNode,n);


for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1)/*父結點存在*/
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;/*求編碼的低一位*/
c=p;
p=HuffNode[c].parent;/*設置下一循環條件*/
}/*endwhile*/

/*保存求出的每個葉結點的哈夫曼編碼和編碼的起始位*/
for(j=cd.start+1;j<n;j++)
{HuffCode[i].bit[j]=cd.bit[j];}
HuffCode[i].start=cd.start;
}/*endfor*/

/*輸出已保存好的所有存在編碼的哈夫曼編碼*/
for(i=0;i<n;i++)
{
printf("%d'sHuffmancodeis:",i);
for(j=HuffCode[i].start+1;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("start:%d",HuffCode[i].start);

printf(" ");

}
/*for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf(" ");
}*/
printf("Decoding?PleaseEntercode: ");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return0;
}

http://www.cnblogs.com/Jezze/archive/2011/12/23/2299884.html

I. 數據結構哈夫曼樹的演算法

每次取最小的2個合並後的值繼續加入集合進行比較,直到集合里只有一個數為止,這樣就可以達到權值最小的路徑越長,權值越大的路徑越短,即可以找到最小權值路徑

閱讀全文

與哈夫曼樹需要實現的演算法相關的資料

熱點內容
單片機句子 瀏覽:228
程序員燙燙燙燙 瀏覽:392
華碩電腦如何解壓別人發的文件 瀏覽:417
移植gcc編譯器需要 瀏覽:655
源程序它無需編譯 瀏覽:286
lattice可編程介面器件 瀏覽:463
域名伺服器縮寫為什麼 瀏覽:226
華為與小米不能連接到伺服器地址 瀏覽:256
誠信可靠的重慶伺服器託管雲主機 瀏覽:209
解壓蘇軾的小視頻 瀏覽:616
android修改通知欄 瀏覽:251
壓縮變形計算公式 瀏覽:721
資料庫電腦伺服器名稱怎麼查詢 瀏覽:455
變異率范圍遺傳演算法 瀏覽:671
geek在手機里是啥文件夾 瀏覽:902
url編譯js 瀏覽:831
安卓怎麼有壓感 瀏覽:669
怎麼把安卓機改成蘋果機主題布局 瀏覽:420
程序員提現 瀏覽:537
解壓小游戲全部鏟走就勝利了 瀏覽:409