c語言哈夫曼編碼

2019-11-10 18:30:19

字體：大中小

來源：轉載

供稿：網友

#include<stdio.h>#include<string.h>#include<malloc.h>typedef struct character{char str;int count;int index; } character; //一棵樹需要左孩子，右孩子，非葉子節點上的數字 typedef struct Tree { int left; int right; int count; int index; char str; char code[256]; }Tree;//統計字符串的各字符的頻率，以及記錄不同字符的個數，排序character *getCharCount(int *count,char *String);//輸出統計后各個字符，頻率 void showChar(Tree *tree,int count);//形成一個二叉樹 void PRoTree(Tree *tree,int count,character *chars);//形成編碼void decode(Tree *tree,int root,int index,char *code);//編碼void afterDecode(Tree *tree,char *String,int count,char *afterString); //編碼后輸出void putcode(char *String); void putcode(char *String){puts(String);}void afterDecode(Tree *tree,char *String,int count,char *afterString){int i,j;for(i=0;String[i];i++){for(j=0;j<count;j++){if(tree[j].str==String[i]){strcat(afterString,tree[j].code);}}}strcpy(String,afterString);}void decode(Tree *tree,int root,int index,char *code) {if(tree[root].left==-1){code[index]=0;strcpy(tree[root].code,code);}else {code[index]='1';decode(tree,tree[root].left,index+1,code);code[index]='0';decode(tree,tree[root].right,index+1,code);}}void proTree(Tree *tree,int count,character *chars){int i;int j;for(i=0;i<count;i++){tree[i].index=i;tree[i].left=-1;tree[i].right=-1;tree[i].count=chars[i].count;tree[i].str=chars[i].str; }for(i=count,j=i-2;i<2*count-1;i++){tree[i].index=i;tree[i].left=tree[i-1].index;tree[i].right=tree[j].index;tree[i].count=tree[i-1].count+tree[j--].count;tree[i].str=' '; }}void showChar(Tree *tree,int count) {int i;printf("下標字符頻率編碼左孩子右孩子/n");for(i=0;i<2*count-1;i++){printf("%2d %5c %4d %7s %5d %6d/n",tree[i].index,tree[i].str,tree[i].count,tree[i].code,tree[i].left,tree[i].right);} } character *getCharCount(int *count,char *String){character *p=NULL;character t;int i,j=0;int k=0;int chars[256]={0};for(i=0;String[i];i++)chars[String[i]]++;for(i=0;i<256;i++){if(chars[i]){k++;}}*count=k;p=(character *)(calloc(sizeof(character),k));for(i=0;i<256;i++){if(chars[i]){p[j].str=i;p[j++].count=chars[i];}}for(i=0;i<k;i++)for(j=0;j<k-i-1;j++)if(p[j].count<p[j+1].count){t=p[j];p[j]=p[j+1];p[j+1]=t; }for(i=0;i<k;i++)p[i].index=i;return p; }int main(){char String[256];char afterString[256]={0};character *chars;Tree *tree;int count;char code[256];printf("請輸入一串字符串：/n");gets(String);chars=getCharCount(&count,String);tree=(Tree *)(calloc(sizeof(Tree),2*count-1));proTree(tree,count,chars);decode(tree,2*count-2,0,code);showChar(tree,count);afterDecode(tree,String,count,afterString);putcode(String);free(chars);free(tree); }

上一篇：RandomAccessFile使用

下一篇：數據結構實驗之串一：KMP簡單應用