/*?哈夫曼編碼?*/ #include<stdio.h> #include<stdlib.h>? #include<string.h> #include<ctype.h> #define?MAX????100 /*哈夫曼樹結點結構定義?*/ typedef?struct?{ ?int?weight;??//存放字符ch的權值? ?char?ch;?????//記錄字符? ?int?lchild,?rchild,?parent;//存儲左孩子、右孩子以及父結點? }?TNode,?*PHT; /*?哈夫曼編碼表的元素結構定義??*/ typedef?struct?{ ???char?ch;???????//?編碼對應的字符 ???char?*pcode;???//?指向編碼字符串的指針 }?TCode,?*PCode; /*? ?*統計字符串text中字符出現的頻率，參數n為字符串長度 ?*返回值：text中出現的不同種類的字符個數 ?*副作用：通過指針參數間接返回兩個數組： ?*??1)dict：字符數組，存放?text中出現的不同種類的字符 ?*??2)freq：整型數組，存放?text中出現的不同種類的字符的出現頻率? ?*/ 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}; ?//根據輸入的文本字符串逐一統計字符出現的頻率? ?for(i?=?0;?i?<?n;?++i){ ??tokens[text[i]]++; ?} ? ?//統計共有多少個相異的字符出現在文本串中? ?for(i?=?0;?i?<?256;?i++){ ??if(?tokens[i]?>?0?){ ???nchar++; ??} ?} ?//為權重數組分配空間? ?pwght=(int*)malloc(sizeof(int)*nchar); ?if(!pwght){ ??printf("為權重數組分配空間失??！\n"); ??exit(0); ?} ? ?//為字符數組（字典）分配空間? ?pch=(char?*)malloc(sizeof(char)*nchar); ?if(?!pch?){ ??printf("為字符數組（字典）分配空間失敗！\n"); ??exit(0); ?} ? ?k?=?0; ?for(i?=?0;?i?<?256;?++i){ ??if(?tokens[i]?>?0?){ ???pwght[k]?=?tokens[i]; ???pch[k]?=?(char)i;??//強制類型轉換? ???k++; ??} ?} ? ?*freq?=?pwght; ?*dict?=?pch; ?for(i=0;i<nchar;i++) ????printf("%c\t%d\n",pch[i],pwght[i]); ? ?return?nchar; } /*構建哈夫曼樹?*/ PHT?create_htree(?int?**freq,?int?n?){ ?PHT?pht;? ?int?i,?lc,?rc,?ntotal?=?0; ?ntotal?=?(2?*?n)?-?1;?//?Huffman樹的結點總數 ? ?pht?=?(PHT)?malloc(?sizeof(?TNode?)?*?ntotal?); ?for(?i?=?0;?i?<?ntotal;?++i?){?//?Huffman樹結點初始化 ??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?){?//?構建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("創建哈夫曼樹成功！\n"); ?return?pht; } /*子樹選擇算法?*/ int?select_subtree(PHT?pht,?int?n,?int?*pa,?int?*pb){//n為哈夫曼樹結點數目? ?int?id,?ida?=?-1,?idb=?-1;??????????????//?ida存放權重最小的結點下標 ?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;??????????????????//?重置次小值結點下標? ????wb?=?wa;????????????????????//將較大的權值復制給wb? ????ida?=?id;???????????????????//重置最小值結點下標? ????wa?=?pht[id].weight;????????//將最小的權值記錄為wa? ????} ???else?if(pht[id].weight?<?wb?){??//新權值大于wa小于wb? ???????idb?=?id;???????????????????//重置次小值結點下標? ????wb?=?pht[id].weight;????????//重置次小值? ????} ??} ?} ?*pa?=?ida;? ?*pb?=?idb;? ?return?0; } /*?根據哈夫曼樹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';?//?臨時存放編碼 ?for(i?=?0;?i?<?n;?i++){?//?依次求葉子pht[i]的編碼 ??book[i].ch?=?pht[i].ch;?//?讀入葉結點pht[i]對應的字符 ??start?=?n;? ??c?=?i;?//?從葉結點pht[i]開始上溯 ??while(?p?=?pht[c].parent?>?0){ ???if(pht[p].lchild?==?c)? ??????cd[--start]='0';? ???else? ??????cd[--start]?='1';? ???c?=?p;? ??}?//?繼續上溯直到根節點 ??strcpy(book[i].pcode,?&cd[start]);?//?復制編碼位串 ????}?? ????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("請輸入英文字符串：\n"); ????while((text[scount]=getchar())!='\n') ????????scount++;? ???????? ????//統計字符串中不同字符出現的頻率并打印相應信息???? ????calc_freq(text,freq,dict,scount); ???? ????//?構建哈夫曼樹 ????create_htree(freq,nchar);? ???? ?//遍歷哈夫曼樹生成哈夫曼編碼 ?htree_encoding?(pht,book,nchar); ? ?printf("打印每個字符的哈夫曼編碼如下：\n"); ?printf("字符\t編碼\n"); ?print_htreecode(book,nchar); ? ?? }