/*?哈夫曼編碼?*/
#include<stdio.h>
#include<stdlib.h>?
#include<string.h>
#include<ctype.h>
#define?MAX????100
/*哈夫曼樹結(jié)點(diǎn)結(jié)構(gòu)定義?*/
typedef?struct?{
?int?weight;??//存放字符ch的權(quán)值?
?char?ch;?????//記錄字符?
?int?lchild,?rchild,?parent;//存儲(chǔ)左孩子、右孩子以及父結(jié)點(diǎn)?
}?TNode,?*PHT;
/*?哈夫曼編碼表的元素結(jié)構(gòu)定義??*/
typedef?struct?{
???char?ch;???????//?編碼對(duì)應(yīng)的字符
???char?*pcode;???//?指向編碼字符串的指針
}?TCode,?*PCode;
/*?
?*統(tǒng)計(jì)字符串text中字符出現(xiàn)的頻率，參數(shù)n為字符串長(zhǎng)度
?*返回值：text中出現(xiàn)的不同種類的字符個(gè)數(shù)
?*副作用：通過指針參數(shù)間接返回兩個(gè)數(shù)組：
?*??1)dict：字符數(shù)組，存放?text中出現(xiàn)的不同種類的字符
?*??2)freq：整型數(shù)組，存放?text中出現(xiàn)的不同種類的字符的出現(xiàn)頻率?
?*/
int?calc_freq(char?text[],?int?**freq,?char?**dict,?int?n){
?int?i,j,?k,?nchar?=?0;
?int?*pwght;
?char?*pch;
?int?tokens[256]?=?{0};
?//根據(jù)輸入的文本字符串逐一統(tǒng)計(jì)字符出現(xiàn)的頻率?
?for(i?=?0;?i?<?n;?++i){
??tokens[text[i]]++;
?}
?
?//統(tǒng)計(jì)共有多少個(gè)相異的字符出現(xiàn)在文本串中?
?for(i?=?0;?i?<?256;?i++){
??if(?tokens[i]?>?0?){
???nchar++;
??}
?}
?//為權(quán)重?cái)?shù)組分配空間?
?pwght=(int*)malloc(sizeof(int)*nchar);
?if(!pwght){
??printf("為權(quán)重?cái)?shù)組分配空間失敗！\n");
??exit(0);
?}
?
?//為字符數(shù)組（字典）分配空間?
?pch=(char?*)malloc(sizeof(char)*nchar);
?if(?!pch?){
??printf("為字符數(shù)組（字典）分配空間失?。n");
??exit(0);
?}
?
?k?=?0;
?for(i?=?0;?i?<?256;?++i){
??if(?tokens[i]?>?0?){
???pwght[k]?=?tokens[i];
???pch[k]?=?(char)i;??//強(qiáng)制類型轉(zhuǎn)換?
???k++;
??}
?}
?
?*freq?=?pwght;
?*dict?=?pch;
?for(i=0;i<nchar;i++)
????printf("%c\t%d\n",pch[i],pwght[i]);
?
?return?nchar;
}
/*構(gòu)建哈夫曼樹?*/
PHT?create_htree(?int?**freq,?int?n?){
?PHT?pht;?
?int?i,?lc,?rc,?ntotal?=?0;
?ntotal?=?(2?*?n)?-?1;?//?Huffman樹的結(jié)點(diǎn)總數(shù)
?
?pht?=?(PHT)?malloc(?sizeof(?TNode?)?*?ntotal?);
?for(?i?=?0;?i?<?ntotal;?++i?){?//?Huffman樹結(jié)點(diǎn)初始化
??pht[i].weight?=?(i?<?n)???*freq[i]?:?0;
??pht[i].lchild?=?-1;?
??pht[i].rchild?=?-1;?
??pht[i].parent?=?-1;
?}
?for(?i?=?n;?i?<?ntotal;?++i?){?//?構(gòu)建Huffman樹
??select_subtree(?pht,?(i-1),?&lc,?&rc?);
??pht[lc].parent?=?i;?
??pht[rc].parent?=?i;
??pht[i].lchild?=?lc;?
??pht[i].rchild?=?rc;
??pht[i].weight?=?pht[lc].weight?+?pht[rc].weight;
?}
?printf("創(chuàng)建哈夫曼樹成功！\n");
?return?pht;
}
/*子樹選擇算法?*/
int?select_subtree(PHT?pht,?int?n,?int?*pa,?int?*pb){//n為哈夫曼樹結(jié)點(diǎn)數(shù)目?
?int?id,?ida?=?-1,?idb=?-1;??????????????//?ida存放權(quán)重最小的結(jié)點(diǎn)下標(biāo)
?int?wa?=?INT_MAX,?wb?=?INT_MAX;?????????//?wa最小值?wb次小值
?for(id?=?0;?id?<=?n;?id++){
??if(pht[id].parent?==?-1){
???if(?pht[id].weight?<?wa?){
????idb?=?ida;??????????????????//?重置次小值結(jié)點(diǎn)下標(biāo)?
????wb?=?wa;????????????????????//將較大的權(quán)值復(fù)制給wb?
????ida?=?id;???????????????????//重置最小值結(jié)點(diǎn)下標(biāo)?
????wa?=?pht[id].weight;????????//將最小的權(quán)值記錄為wa?
????}
???else?if(pht[id].weight?<?wb?){??//新權(quán)值大于wa小于wb?
???????idb?=?id;???????????????????//重置次小值結(jié)點(diǎn)下標(biāo)?
????wb?=?pht[id].weight;????????//重置次小值?
????}
??}
?}
?*pa?=?ida;?
?*pb?=?idb;?
?return?0;
}
/*?根據(jù)哈夫曼樹pht求哈夫曼編碼表book?*/
void?htree_encoding?(PHT?pht,?TCode?*book,?int?n){
?int?i,?c,?p,?start;?//?start表示編碼在cd中的起始位置
?char?cd[n+1];?
?cd[n]='\0';?//?臨時(shí)存放編碼
?for(i?=?0;?i?<?n;?i++){?//?依次求葉子pht[i]的編碼
??book[i].ch?=?pht[i].ch;?//?讀入葉結(jié)點(diǎn)pht[i]對(duì)應(yīng)的字符
??start?=?n;?
??c?=?i;?//?從葉結(jié)點(diǎn)pht[i]開始上溯
??while(?p?=?pht[c].parent?>?0){
???if(pht[p].lchild?==?c)?
??????cd[--start]='0';?
???else?
??????cd[--start]?='1';?
???c?=?p;?
??}?//?繼續(xù)上溯直到根節(jié)點(diǎn)
??strcpy(book[i].pcode,?&cd[start]);?//?復(fù)制編碼位串
????}??
????printf("哈夫曼編碼成功！\n");
}
void?print_htreecode(TCode?*book,int?n){
?int?i;
?for(i=0;i<n;i++){
??printf("%c\t%d\n",book[i].ch,book[i].pcode);
?}
?printf("哈夫曼編碼打印成功！\n");
}
?
void?main(){
????char?text[MAX];
????int?scount=0,nchar=0,n;
????int?weights[MAX];
????int?**freq;
????char?**dict;
????PHT?pht;
????TCode?*book;
????
????//從鍵盤輸入英文字符串?
????printf("請(qǐng)輸入英文字符串：\n");
????while((text[scount]=getchar())!='\n')
????????scount++;?
????????
????//統(tǒng)計(jì)字符串中不同字符出現(xiàn)的頻率并打印相應(yīng)信息????
????calc_freq(text,freq,dict,scount);
????
????//?構(gòu)建哈夫曼樹
????create_htree(freq,nchar);?
????
?//遍歷哈夫曼樹生成哈夫曼編碼
?htree_encoding?(pht,book,nchar);
?
?printf("打印每個(gè)字符的哈夫曼編碼如下：\n");
?printf("字符\t編碼\n");
?print_htreecode(book,nchar);
?
??
}
求大大指教，，，寫了個(gè)C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)的哈夫曼編碼，可是哪里出錯(cuò)了，，，？？?
lukuang
2016-06-06 10:51:52
