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

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

2、CDEFGHIJ1918161412864212.編寫函數(shù)求出A~J的霍夫曼編碼。#include#include#includetypedefHuffmanCodetypedefstructdataunsignedintweightunsignedintparentLChildRChildHTNodeHuffmanTree選出權(quán)值最小的兩個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個權(quán)值，構(gòu)造哈夫曼樹htintmiwints1s2cm=2n1

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

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