一、 实验目的
构造一个哈夫曼树，并根据所构造的哈夫曼树求其哈夫曼树的编码；
二、 基本思路
1. 将每个英文字母依照出现频率由小排到大，最小在左，组成一个序列
2. 每个字母都代表一个终端节点（叶节点），比较每个字母的出现频率，将最小的两个字母频率相加合成一个新的节点，将两个字母从序列中删除，将生成的节点加入到字母队列中
3. 重复前面两步，直到序列中没有字母为止
进行编码：
1. 给霍夫曼树的所有左链结'0'与右链结'1'
2. 从树根至树叶依序记录所有字母的编码
三、基本代码
1.Huffman.h文件
|
1 2 3 4 5 6 7 8 9 |
typedef struct{ int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n); void HuffmanSelect(HuffmanTree HT,int k,int &s1,int &s2); |
2.主要函数
①select函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
void HuffmanSelect(HuffmanTree HT,int n,int &s1,int &s2) { int minn=10000000,maxx=10000000; s1=s2=0; for(int i=1; i<=n; i++) { if(HT[i].parent==0) { if(HT[i].weight<minn) { minn=HT[i].weight;s1=i; } } } int t=HT[s1].weight; HT[s1].weight=maxx; minn=99999998; for(int i=1; i<=n; i++) { if(HT[i].parent==0) { if(HT[i].weight<minn) { minn=HT[i].weight; s2=i; } } } HT[s1].weight=t; } |
②编码函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) { if(n<=1)return; int m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); int i; for(i=1;i<=n;i++) { HT[i].weight=w[i]; HT[i].parent=HT[i].rchild=HT[i].lchild=0; } for(;i<=m;i++) { HT[i].weight=HT[i].parent=HT[i].rchild=HT[i].lchild=0; } int s1=0,s2=0; for(i=n+1;i<=m;i++) { HuffmanSelect(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*)); char *cd; cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; int start; for(i=1;i<=n;++i) { start=n-1; int c=0;int f=0; 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)); strcpy(HC[i],&cd[start]); } free(cd); } |
太强了
太强了
太强了