//HuffmanTree.h #include <stdlib.h> #include <stdio.h> #include <string.h> #define OVERFLOW -1 typedef struct{ char data; //节点所存字符 unsigned int weight; //节点权重 unsigned int parent,lchild,rchild; }HTNode, *HuffmanTree; //动态分配数组存储赫夫曼树 typedef char** HuffmanCode;//动态分配数组存储赫夫曼编码表 //从T的1到n个节点中找出没有结合（即parent=0）的节点中权重weight最小的两个节点的下标；用l，r带回； void Select(HuffmanTree T,int n,int&l,int&r) { HuffmanTree p=T+1;int a=0,b=0; for(int i=1;i<=n;++i,++p){ if(!p->parent){//找出双亲节点为空的节点； if(!a){l=i;a=1;} else if(!b){r=i;b=1;} else if(p->weight<(T+l)->weight||p->weight<(T+r)->weight){ if((T+l)->weight<=(T+r)->weight)r=i; else l=i; } } } } //w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC //HT为赫夫曼树，HC为赫夫曼编码，w为权重数组，n为w长度 void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, char* c, int n){ if(n<=1) return; int m = 2*n-1; HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用 HuffmanTree p; int i; for(p=HT+1,i=1; i<=n; ++i,++p,++w) *p = {c[i-1],*w,0,0,0}; for(i=n+1; i<=m; ++i, ++p) *p = {0,0,0,0,0}; for(i=n+1; i<=m; ++i){ //建赫夫曼树 //在HT[1..i-1]选择parent为0且weight最小的两个节点，其序号分别为s1和s2。 int s1,s2; Select(HT, i-1, s1, s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } //---从叶子到根逆向求每个字符的赫夫曼编码--- HC = (HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量 char* cd = (char *)malloc(n*sizeof(char)); //分配求编码的工作空间 cd[n-1] = ' '; //编码结束符 for(i=1; i<=n; ++i){ //逐个字符求赫夫曼编码 int start = n-1; //编码结束符位置 int c,f; for(c=i, f=HT[i].parent; f!=0; c=f,f=HT[f].parent) //从叶子到根逆向求编码 if(HT[f].lchild == c) cd[--start] = '0'; else cd[--start] = '1'; HC[i] = (char *)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间 strcpy(HC[i],&cd[start]); //从cd复制编码(串)到HC } free(cd); //释放工作空间 } //输出赫夫曼编码 //HC为赫夫曼编码，w为权重数组，n为w长度，c为字符数组 void PrintHuffmanCode(HuffmanCode HC,int* w,char* c,int n) { char *p; int i; for(i=1;i<=n;++i){ printf("字符：%c，权重：%3d，编码：", c[i-1], w[i-1]); p=HC[i]; printf("%s ",p); } } //返回某字符的赫夫曼编码 //HC为赫夫曼编码，c为字符数组，n为c长度，ch为要编码的字符 char* EnCode(HuffmanCode HC, char* c, char ch, int n) { int i; for(i=0;i<n;++i){ if(c[i]==ch){ char *p = HC[i+1]; return p; } } } //解码 //s为待解码字符串，HT为赫夫曼树 char* DeCode(const char*s, HuffmanTree HT){ int i; HuffmanTree p=HT; static char result[500]; int j=0; //寻找根节点 while(p->parent!=0) p++; const HuffmanTree root = p; for(i=0; i<strlen(s); ++i){ if(s[i]=='0'){ if(p->lchild!=0){ p=HT+p->lchild; } } else if(s[i]=='1'){ if(p->rchild!=0){ p=HT+p->rchild; } } if(p->lchild==0&&p->rchild==0){ result[j]=p->data;++j; p = root; } } result[j] = ' '; return result; }
#include "HuffmanTree.h" #include <stdio.h> int main(void){ char s[500]; READ: printf("请输入一段话："); gets(s); int i=0,w[1000]={0},*word; char *c; //word记录权值，c记录字符 while(s[i]!=' '){ //出现次数计数 w[s[i]+500]++; ++i; } int j=0; word = (int*)malloc(sizeof(int)); c = (char*)malloc(sizeof(char)); for(i=-500;i<500;++i){ if(w[i+500]!=0){ word = (int*)realloc(word,(j+1)*sizeof(int)); c = (char*)realloc(c,(j+1)*sizeof(char)); word[j] = w[i+500]; c[j] = i; ++j; } } const int len = j; //字符数组、权重数组长度 if(len==1){ printf("请输入大于1种字符！ "); goto READ; } HuffmanCode HC;HuffmanTree HT; HuffmanCoding(HT,HC,word,c,len); PrintHuffmanCode(HC,word,c,len); i=0; printf("赫夫曼编码后结果为："); char code[1000]={' '}; while(s[i]!=' '){ strcat(code,EnCode(HC,c,s[i],len)); ++i; } printf("%s ",code); printf("解码结果为：%s",DeCode(code,HT)); printf(" "); getchar(); return 0; }
运行截图:
