北大計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)講義

樹點(diǎn)的個數(shù)。：wi是第i個外部結(jié)點(diǎn)的權(quán)值。HoufengWang,ICLof w1,w2,w3w｝，w（i=，）為權(quán)的個外度LHoufengWang,ICLof HoufengWang,ICLof WPL=1×11+2×4+3×2+3×3=WPL=2×3+3×4+3×11+1×2=WPL=2×2+2×11+2×3+2×4=HoufengWang,ICLof 552 由給定的m個權(quán)值{w1,w2,…,wm}構(gòu)造由m棵二叉樹組成的樹林F={T1,T2,…,Tm}，其中每棵樹Ti(1≤i≤m)只 HoufengWang,ICLof 下面以w9,6,3,2為例說明這個算法思想。圖HoufengWang,ICLof HoufengWang,ICLof structHtNode {intintstruct structHtNode typedefstructHtTree HoufengWang,ICLof HoufengWang,ICLof PHtTreehuffman(intm,int/*構(gòu)造具有m個葉結(jié)點(diǎn) 樹{PHtTreeintpht=(PHtTree)malloc(sizeof(struct 樹if{printf("Outofspace!!\n");returnpht;}HoufengWang,ICLof for(i=0;i<2*m-1;i++{pht->ht[i].llink=-1;pht->ht[i].rlink=-1;pht->ht[i].parent=-

if(i<m)

pht->ht[i].ww=pht->ht[i].ww=-for(i=0;im1;i++)//{m1=MAXINT;x1=-1;

m2 x2=- if(pht->ht[j].ww<m1&&pht->ht[j].parent==- m2= x2=HoufengWang,ICLof m1=pht->ht[j].ww;x1=j;} if(pht->ht[j].ww<m2&&pht->ht[j].parent==- m2=pht-x2=}pht->ht[x1].parent=m+i;pht->ht[x2].parent=m+i;pht->ht[m+i].ww=m1+m2;pht->ht[m+i].llink=x1;pht->ht[m+i].rlink=x2;pht->root=m+i;}

return}HoufengWang,ICLof #define#defineMAXNUM /*數(shù)m<=MAXNUM*/#defineMAXNODE1<MAXNODE*/

HoufengWang,ICLof 例如，對于一組權(quán)值w={2，3，5，7， 所示，終結(jié)狀態(tài)如圖5.27(b)所示。HoufengWang,ICLof HoufengWang,ICLof HoufengWang,ICLof d={d1，d2，…，dn}w={w1，w2，…，wn}現(xiàn)要對d中的字符進(jìn)行二進(jìn)制編碼，使得：(1)通迅編碼總長最短；(2)若di≠dj，則di的編碼不可能是dj的編碼的HoufengWang,ICLof 用d1，d2，…，dn作為外部結(jié)點(diǎn)，用w1，w2，…，wn 權(quán)值大的字符，編碼較短(符合編碼原則HoufengWang,ICLof d={d1，d2，…，d13w={ HoufengWang,ICLof HoufengWang,ICLof ?，HoufengWang,ICLof HoufengWang,ICLof 假定用于通信的電文僅由8個字母c1,c2,