數(shù)據(jù)結(jié)構(gòu)赫夫曼樹(shù)2

1、1、實(shí)驗(yàn)?zāi)康?.進(jìn)一步掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和相應(yīng)算法2.掌握霍夫曼樹(shù)樹(shù)的創(chuàng)建和霍夫曼編碼2、實(shí)驗(yàn)環(huán)境1.硬件：每個(gè)學(xué)生需配備計(jì)算機(jī)一臺(tái)。操作系統(tǒng)：DOS或Windows2.軟件：DOS或Windows操作系統(tǒng)TurboC3、實(shí)驗(yàn)要求1.要求采用二叉鏈表作為存貯結(jié)構(gòu)，完成霍夫曼樹(shù)的創(chuàng)建2.輸出對(duì)應(yīng)數(shù)據(jù)的霍夫曼編碼，并求出平均編碼長(zhǎng)度4、實(shí)驗(yàn)內(nèi)容1.現(xiàn)在某電報(bào)公司假設(shè)有10字符進(jìn)行編碼，這10個(gè)字符的使用頻率如下表所示，請(qǐng)創(chuàng)建霍夫曼樹(shù)。AB

2、CDEFGHIJ1918161412864212.編寫(xiě)函數(shù)求出A~J的霍夫曼編碼。#include#include#includetypedefHuffmanCodetypedefstructdataunsignedintweightunsignedintparentLChildRChildHTNodeHuffmanTree選出權(quán)值最小的兩個(gè)void(HuffmanTreehtintnints1ints2)intiintmin1=0mi

3、n2=0(ht)[min1].weight=(ht)[min2].weight=101f(i=1i=ni)if((ht)[i].weight(ht)[min1].weightf(i=1i=ni)if((ht)[i].weight(ht)[min2].weights1=min2s2=min1voidCrtHuffmanTree(HuffmanTreehtintn)w存放已知的n個(gè)權(quán)值，構(gòu)造哈夫曼樹(shù)htintmiwints1s2cm=2n1

4、ht=(HuffmanTree)malloc((m1)sizeof(HTNode))0號(hào)單元未使用cdintiunsignedintcintstartintphc=(HuffmanCode)malloc((n1)sizeof())分配n個(gè)編碼的頭指針cd=()malloc(nsizeof())分配求當(dāng)前編碼的工作空間cd[n1]=0從右向左逐位存放編碼，首先存放編碼結(jié)束符f(i=1i=ni)求n個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼編碼start=n1

5、初始化編碼起始指針f(c=ip=(ht)[i].parentp!=0c=pp=(ht)[p].parent)從葉子到根結(jié)點(diǎn)求編碼if((ht)[p].LChild==c)cd[start]=0左分支標(biāo)0elsecd[start]=1右分支標(biāo)1hc[i]=()malloc((nstart)sizeof())為第i個(gè)編碼分配空間strcpy(hc[i]free(cd)f(i=1i=ni)printf(“%c編碼為%sn“(ht)[i].da