姓名：周小蓬 16019110037
轉(zhuǎn)載自：http://blog.csdn.net/F__shigang/article/details/65442550
[嵌牛導(dǎo)讀]
Huffman樹(shù)是一類(lèi)帶權(quán)路徑長(zhǎng)度WPL最短的二叉樹(shù)括授，中文名叫哈夫曼樹(shù)或最優(yōu)二叉樹(shù)坞笙。
相關(guān)概念：
結(jié)點(diǎn)的路徑長(zhǎng)度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目岩饼。
樹(shù)的路徑長(zhǎng)度：樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。
樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和薛夜。
[嵌牛鼻子]
c語(yǔ)言
[嵌牛提問(wèn)]
如何學(xué)習(xí)哈夫曼樹(shù)以及步驟
[嵌牛正文]
構(gòu)造Huffman樹(shù)的步驟：
1）? 根據(jù)給定的n個(gè)權(quán)值籍茧，構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)，n個(gè)權(quán)值分別是這些二叉樹(shù)根結(jié)點(diǎn)的權(quán)梯澜；
2）? 設(shè)F是由這n棵二叉樹(shù)構(gòu)成的集合寞冯，在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為左、右子樹(shù)晚伙，構(gòu)造成一顆新的二叉樹(shù)吮龄，置新二叉樹(shù)根結(jié)點(diǎn)的權(quán)值等于左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和咆疗。為了使得到的哈夫曼樹(shù)的結(jié)構(gòu)唯一漓帚，規(guī)定根結(jié)點(diǎn)權(quán)值最小的作為新二叉樹(shù)的左子樹(shù)。
3）? 從F中刪除這兩棵樹(shù)午磁，并將新樹(shù)加入F尝抖；
4）? 重復(fù)2）毡们、3）步，直到F中只含一棵樹(shù)為止昧辽，這棵樹(shù)便是Huffman樹(shù)衙熔。
說(shuō)明：n個(gè)結(jié)點(diǎn)需要進(jìn)行n-1次合并，每次合并都產(chǎn)生一個(gè)新的結(jié)點(diǎn)搅荞，最終的Huffman樹(shù)共有2n-1個(gè)結(jié)點(diǎn)红氯。
2、Huffman編碼
Huffman樹(shù)在通訊編碼中的一個(gè)應(yīng)用：
利用哈夫曼樹(shù)構(gòu)造一組最優(yōu)前綴編碼取具。主要用途是實(shí)現(xiàn)數(shù)據(jù)壓縮脖隶。在某些通訊場(chǎng)合，需將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符組成的字符串進(jìn)行傳輸暇检。
方法：
利用哈夫曼樹(shù)構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼产阱，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，使所傳電文的總長(zhǎng)度最短块仆。
不等長(zhǎng)編碼：即各個(gè)字符的編碼長(zhǎng)度不等（如：0,10,110,011）构蹬，可以使傳送電文的字符串的總長(zhǎng)度盡可能地短。對(duì)出現(xiàn)頻率高的字符采用盡可能短的編碼悔据，則傳送電文的總長(zhǎng)度便盡可能短庄敛。
前綴編碼：任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。
二科汗、代碼實(shí)現(xiàn)
使用鏈表結(jié)構(gòu)構(gòu)建哈夫曼樹(shù)并進(jìn)行編碼藻烤、解碼，代碼如下：
[cpp]view plaincopy
#include?
#include?
#include?
typedefintELEMTYPE;
//?哈夫曼樹(shù)結(jié)點(diǎn)結(jié)構(gòu)體
typedefstructHuffmanTree
{
ELEMTYPE?weight;
ELEMTYPE?id;//?id用來(lái)主要用以區(qū)分權(quán)值相同的結(jié)點(diǎn)头滔，這里代表了下標(biāo)
structHuffmanTree*?lchild;
structHuffmanTree*?rchild;
}HuffmanNode;
//?構(gòu)建哈夫曼樹(shù)
HuffmanNode*?createHuffmanTree(int*?a,intn)
{
inti,?j;
HuffmanNode?**temp,?*hufmTree;
temp?=?malloc(n*sizeof(HuffmanNode));
for(i=0;?i
{
temp[i]?=?(HuffmanNode*)malloc(sizeof(HuffmanNode));
temp[i]->weight?=?a[i];
temp[i]->id?=?i;
temp[i]->lchild?=?temp[i]->rchild?=?NULL;
}
for(i=0;?i
{
intsmall1=-1,?small2;//?small1怖亭、small2分別作為最小和次小權(quán)值的下標(biāo)
for(j=0;?j
{
if(temp[j]?!=?NULL?&&?small1==-1)
{
small1?=?j;
continue;
}elseif(temp[j]?!=?NULL)
{
small2?=?j;
break;
}
}
for(j=small2;?j
{
if(temp[j]?!=?NULL)
{
if(temp[j]->weight?<?temp[small1]->weight)
{
small2?=?small1;
small1?=?j;
}elseif(temp[j]->weight?<?temp[small2]->weight)
{
small2?=?j;
}
}
}
hufmTree?=?(HuffmanNode*)malloc(sizeof(HuffmanNode));
hufmTree->weight?=?temp[small1]->weight?+?temp[small2]->weight;
hufmTree->lchild?=?temp[small1];
hufmTree->rchild?=?temp[small2];
temp[small1]?=?hufmTree;
temp[small2]?=?NULL;
}
free(temp);
returnhufmTree;
}
//?以廣義表的形式打印哈夫曼樹(shù)
voidPrintHuffmanTree(HuffmanNode*?hufmTree)
{
if(hufmTree)
{
printf("%d",?hufmTree->weight);
if(hufmTree->lchild?!=?NULL?||?hufmTree->rchild?!=?NULL)
{
printf("(");
PrintHuffmanTree(hufmTree->lchild);
printf(",");
PrintHuffmanTree(hufmTree->rchild);
printf(")");
}
}
}
//?遞歸進(jìn)行哈夫曼編碼
voidHuffmanCode(HuffmanNode*?hufmTree,intdepth)//?depth是哈夫曼樹(shù)的深度
{
staticintcode[10];
if(hufmTree)
{
if(hufmTree->lchild==NULL?&&?hufmTree->rchild==NULL)
{
printf("id為%d權(quán)值為%d的葉子結(jié)點(diǎn)的哈夫曼編碼為?",?hufmTree->id,?hufmTree->weight);
inti;
for(i=0;?i
{
printf("%d",?code[i]);
}
printf("\n");
}else
{
code[depth]?=?0;
HuffmanCode(hufmTree->lchild,?depth+1);
code[depth]?=?1;
HuffmanCode(hufmTree->rchild,?depth+1);
}
}
}
//?哈夫曼解碼
voidHuffmanDecode(charch[],?HuffmanNode*?hufmTree,charstring[])//?ch是要解碼的01串，string是結(jié)點(diǎn)對(duì)應(yīng)的字符
{
inti;
intnum[100];
HuffmanNode*?tempTree?=?NULL;
for(i=0;?i
{
if(ch[i]?=='0')
num[i]?=?0;
else
num[i]?=?1;
}
if(hufmTree)
{
i?=?0;//?計(jì)數(shù)已解碼01串的長(zhǎng)度
while(i
{
tempTree?=?hufmTree;
while(tempTree->lchild!=NULL?&&?tempTree->rchild!=NULL)
{
if(num[i]?==?0)
{
tempTree?=?tempTree->lchild;
}else
{
tempTree?=?tempTree->rchild;
}
++i;
}
printf("%c",?string[tempTree->id]);//?輸出解碼后對(duì)應(yīng)結(jié)點(diǎn)的字符
}
}
}
intmain()
{
inti,?n;
printf("請(qǐng)輸入葉子結(jié)點(diǎn)的個(gè)數(shù)：\n");
while(1)
{
scanf("%d",?&n);
if(n>1)
break;
else
printf("輸入錯(cuò)誤坤检，請(qǐng)重新輸入n值兴猩！");
}
int*?arr;
arr=(int*)malloc(n*sizeof(ELEMTYPE));
printf("請(qǐng)輸入%d個(gè)葉子結(jié)點(diǎn)的權(quán)值：\n",?n);
for(i=0;?i
{
scanf("%d",?&arr[i]);
}
charch[100],?string[100];
printf("請(qǐng)連續(xù)輸入這%d個(gè)葉子結(jié)點(diǎn)各自所代表的字符：\n",?n);
fflush(stdin);//?強(qiáng)行清除緩存中的數(shù)據(jù)，也就是上面輸入權(quán)值結(jié)束時(shí)的回車(chē)符
gets(string);
HuffmanNode*?hufmTree?=?NULL;
hufmTree?=?createHuffmanTree(arr,?n);
printf("此哈夫曼樹(shù)的廣義表形式為：\n");
PrintHuffmanTree(hufmTree);
printf("\n各葉子結(jié)點(diǎn)的哈夫曼編碼為：\n");
HuffmanCode(hufmTree,?0);
printf("要解碼嗎早歇？請(qǐng)輸入編碼:\n");
gets(ch);
printf("解碼結(jié)果為：\n");
HuffmanDecode(ch,?hufmTree,?string);
printf("\n");
free(arr);
free(hufmTree);
return0;
}
運(yùn)行結(jié)果如圖：
三倾芝、程序?qū)崿F(xiàn)過(guò)程當(dāng)中遇到的問(wèn)題總結(jié)
1）關(guān)于哈夫曼樹(shù)，知道了葉子結(jié)點(diǎn)箭跳，如何不用靜態(tài)數(shù)組存儲(chǔ)整個(gè)哈夫曼樹(shù)及構(gòu)建過(guò)程中的生成樹(shù)晨另？
答：使用malloc函數(shù)開(kāi)辟一段內(nèi)存空間存結(jié)構(gòu)體類(lèi)型的樹(shù)，若往樹(shù)中添加新的結(jié)點(diǎn)掛在結(jié)構(gòu)體指針上即可谱姓，這就要求定義的結(jié)構(gòu)體里面包含結(jié)構(gòu)體指針借尿，這也是結(jié)構(gòu)體指針的作用。也就是使用鏈表動(dòng)態(tài)存儲(chǔ)逝段，每個(gè)結(jié)點(diǎn)都是一個(gè)包含結(jié)構(gòu)體指針的結(jié)構(gòu)體垛玻，生成過(guò)程中動(dòng)態(tài)開(kāi)辟割捅，不管這棵樹(shù)有多少個(gè)結(jié)點(diǎn)都可以存下。
2）
[cpp]view plaincopy
typedefstructstHuNode
{
intdata;//?權(quán)值
structstHuNode*?lchild;//這兩句等價(jià)于?struct?stHuNode*?lchild,?*rchild;
structstHuNode*?rchild;
}HUNODE;
3）scanf語(yǔ)句里不要有換行符帚桩？scanf函數(shù)的用法亿驾，scanf(" %d", &i);和scanf("%d ",&i);效果不同，差別在哪账嚎？
答：scanf函數(shù)的一般形式為：scanf(“格式控制字符串”, 地址表列);格式控制字符串中不能顯示非格式字符串莫瞬，也就是不能顯示提示字符串和換行符」叮” %d” 和“%d”作用一樣疼邀，%d前面的空格不起作用，”%d “空格加在%d后面賦值時(shí)要多輸入一個(gè)值召锈，實(shí)際賦值操作時(shí)多輸入的數(shù)并沒(méi)有被賦值只是緩存到了輸入流stdin中旁振，下次如果再有scanf和gets語(yǔ)句要求賦值時(shí)，要先用fflush(stdin);語(yǔ)句強(qiáng)制清除緩存再賦值涨岁，否則原先在stdin中的值就會(huì)被賦過(guò)去導(dǎo)致錯(cuò)誤拐袜。
4）靈感：怎樣解碼？根據(jù)輸入的01串解出相應(yīng)的權(quán)值梢薪？
答：No蹬铺！如果兩個(gè)不同的字符對(duì)應(yīng)的權(quán)值相同呢？如何區(qū)分秉撇？起初想到如果在建立哈夫曼樹(shù)的過(guò)程中可以記錄下相應(yīng)的下標(biāo)就不會(huì)導(dǎo)致相同權(quán)值無(wú)法區(qū)別的問(wèn)題甜攀，但在具體如何實(shí)現(xiàn)上，剛開(kāi)始想輸出每一次建樹(shù)的small1和small2琐馆，但發(fā)現(xiàn)這樣很不清晰规阀，用戶(hù)要想確定每個(gè)字符的下標(biāo)得按照建樹(shù)過(guò)程走一遍才行，那要程序何用啡捶，而且給用戶(hù)造成了很大的麻煩姥敛，不可取奸焙。后來(lái)想到瞎暑，可以在結(jié)點(diǎn)的結(jié)構(gòu)體中添加id信息，這樣即使權(quán)值相同的結(jié)點(diǎn)也可以區(qū)分開(kāi)來(lái)与帆，這里的id可以是下標(biāo)了赌，因?yàn)橛脩?hù)輸入權(quán)值的順序一定則下標(biāo)唯一。如果解碼解出來(lái)的是權(quán)值標(biāo)號(hào)的話就沒(méi)有異議了玄糟，可是下標(biāo)又不是很直觀清晰勿她，不如直接輸出相應(yīng)的字符好，又想到兩個(gè)解決辦法：a）將結(jié)點(diǎn)id信息直接定義成字符阵翎，只不過(guò)在建樹(shù)的過(guò)程中要將字符和權(quán)值都加入結(jié)點(diǎn)中逢并；b）id仍然是下標(biāo)之剧，在用戶(hù)輸入權(quán)值對(duì)應(yīng)的字符時(shí)，用字符數(shù)組存儲(chǔ)并和id對(duì)應(yīng)起來(lái)砍聊，這樣解碼得到id之后背稼，可以輸出對(duì)應(yīng)的字符，實(shí)現(xiàn)起來(lái)相對(duì)比較簡(jiǎn)單玻蝌。
5）疑問(wèn)：如果根據(jù)用戶(hù)輸入的字符串進(jìn)行編碼解碼得到了新的字符串蟹肘，舊字符串和新字符串有沒(méi)有直接看出來(lái)的規(guī)律，就是說(shuō)人眼觀察和推導(dǎo)能否得到相應(yīng)的規(guī)律俯树，或者說(shuō)有沒(méi)有可能直接能得出規(guī)律不用經(jīng)過(guò)編碼解碼帘腹。留為疑問(wèn)！
答：后經(jīng)測(cè)試發(fā)現(xiàn)不行许饿。
6）gets()函數(shù)的用法阳欲，如何獲取一個(gè)字符串，賦值時(shí)跳過(guò)gets()函數(shù)的執(zhí)行陋率，貌似gets()沒(méi)起作用的問(wèn)題胸完。
答：當(dāng)使用gets()函數(shù)之前有過(guò)數(shù)據(jù)輸入，并且翘贮，操作者輸入了回車(chē)確認(rèn)赊窥，這個(gè)回車(chē)符沒(méi)有被清理，被保存在輸入緩存中時(shí)狸页，gets()會(huì)讀到這個(gè)字符锨能，結(jié)束讀字符操作。因此芍耘，從用戶(hù)表面上看址遇，gets()沒(méi)有起作用，跳過(guò)了斋竞。
解決辦法：
方法一倔约、在gets()前加fflush(stdin); //強(qiáng)行清除緩存中的數(shù)據(jù)（windows下可行）
方法二、根據(jù)程序代碼坝初，確定前面是否有輸入語(yǔ)句浸剩，如果有，則增加一個(gè)getchar()命令鳄袍，然后再調(diào)用 gets()命令绢要。
方法三、檢查輸入結(jié)果拗小，如果得到的字符串是空串重罪，則繼續(xù)讀入，如：
[cpp]view plaincopy
charstr[100]={0};
do{
gets(str);
}while(?!str[0]?);
7）初始化數(shù)組語(yǔ)句：memset(str,0, sizeof(str)); 理解一下！
答：函數(shù)解釋?zhuān)簩?str 中前 n 個(gè)字節(jié)用 ch 替換并返回 str剿配。memset(str, 0, sizeof(str));意思是將數(shù)組str的長(zhǎng)度（字節(jié)數(shù)搅幅，不是元素個(gè)數(shù)）置零。
memset：作用是在一段內(nèi)存塊中填充某個(gè)給定的值呼胚，它是對(duì)較大的結(jié)構(gòu)體或數(shù)組進(jìn)行清零操作的一種最快方法盏筐。
8）關(guān)于strlen()函數(shù)
答：strlen函數(shù)的用法，包含頭文件string.h砸讳。且是對(duì)字符數(shù)組中的字符串求長(zhǎng)度琢融！
其原型為： ?unsigned int strlen (char *s);
【參數(shù)說(shuō)明】s為指定的字符串。
strlen()用來(lái)計(jì)算指定的字符串s 的長(zhǎng)度簿寂，不包括結(jié)束字符"\0"漾抬。
【返回值】返回字符串s 的字符數(shù)。
注意：strlen() 函數(shù)計(jì)算的是字符串的實(shí)際長(zhǎng)度常遂，遇到第一個(gè)'\0'結(jié)束纳令。如果你只定義沒(méi)有給它賦初值，這個(gè)結(jié)果是不定的克胳，它會(huì)從首地址一直找下去平绩，直到遇到'\0'停止。而sizeof返回的是變量聲明后所占的內(nèi)存數(shù)漠另，不是實(shí)際長(zhǎng)度捏雌，此外sizeof不是函數(shù)，僅僅是一個(gè)操作符笆搓，strlen()是函數(shù)性湿。
