问题描述:
已知字符出现的概率，如何设计为这些字符设计一定长度的位串，使得位串平均长度最短.
前缀码是指，对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，而最优前缀码是指平均码长最小的前缀编码。
问题解析:
数据结构:二叉树
哈夫曼树的性质:
1:一共有2n-1个节点，其中n为叶子节点数，所以可以存在一个2n-1的一维数组中。
2：哈夫曼树没有度为1的节点
2:为求编码需要从叶子节点出发走到根节点，并且对于每个节点既要知道双亲节点，也要知道孩子节点
算法步骤:
1:从集合中选出权值最小的两个节点，然后形成一颗新的树，这颗树的根的权值为这两个节点的权值的和，然后将这颗树再放回集合。
2：重复步骤一，直至集合中只有一棵树。
3：根据这颗树，可对每个字符进行编码或解码，编码即从树根走到这个字符的路径所连成的二进制码，树中所有向左标记为0，向右标记为1.而解码就是读取该编码字符串，若该串与对应字符的前缀码对应，则输出字符，然后重新开始读取。
伪代码设计
// // main.c // 作业11 // // Created by yizhihenpidehou on 2020/5/12. // Copyright © 2020 yizhihenpidehou. All rights reserved. // #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct{ int weight; int lchild,rchild,parent; }HTNode,*HuffmanTree; typedef char **HuffmanCode; HuffmanCode HC; HuffmanTree HT; int s1; int s2; void SelectMin(HuffmanTree tree,int n){ //找出权值最小的两棵树 int minn=1;//存放临时最小值 for(int i=1;i<=n;i++){ if(tree[i].parent==0){//找出一个暂时的最小值 minn=i; break; } } for(int i=1;i<=n;i++){ if(tree[i].parent==0&&tree[i].weight<tree[minn].weight){//找出第一个最小值 minn=i; } } s1=minn; for(int i=1;i<=n;i++){ if(tree[i].parent==0&&i!=s1){//找出一个暂时的最小值 minn=i; break; } } for(int i=1;i<=n;i++){ if(tree[i].parent==0&&tree[i].weight<tree[minn].weight&&i!=s1){//找出第二个最小值 minn=i; } } s2=minn; // printf("s1:%d s2:%d ",s1,s2); } void Huffman(HuffmanTree tree,int *w,int n){//哈夫曼编码 int m=2*n-1;//哈夫曼树的节点数 tree=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//申请节点 for(int i=1;i<=m;i++){//初始化树 tree[i].lchild=0; tree[i].rchild=0; tree[i].parent=0; if(i<=n){//设置每个叶子节点的权值 tree[i].weight=w[i]; } else{ tree[i].weight=0; } } for(int i=n+1;i<=m;i++){ SelectMin(tree,i-1); // printf("s1 %d s2 %d ",s1,s2); tree[s1].parent=i;//将s1的父亲设置为i tree[s2].parent=i;//将s2的父亲设置为i tree[i].lchild=s1;//将s1作为i的左孩子 tree[i].rchild=s2;//将s2作为i的右孩子 tree[i].weight=tree[s1].weight+tree[s2].weight;//i的权值为s1与s2的和 // printf("val s1:%d s2:%d ",tree[s1].weight,tree[s2].weight); // printf("new NODE %d %d %d %d ",tree[i].parent,tree[i].lchild,tree[i].rchild,tree[i].weight); } //以上为建造一颗哈夫曼树，以下为求哈夫曼编码 HC=(HuffmanCode)malloc((n+1)*(sizeof(char *)));//相当于申请一个二维数组，存放n个哈夫曼编码 char *cd; cd=(char *)malloc(n*sizeof(char));//相当于申请一个一维数组，暂存哈夫曼编码 cd[n-1]=' ';//编码结束符 int start; for(int i=1;i<=n;i++){ start=n-1;//初始点 for(int j=i,f=tree[i].parent;f!=0;j=f,f=tree[f].parent){ //逆向求哈夫曼编码 if(tree[f].lchild==j) cd[--start]='0'; //向左为0 else cd[--start]='1';//向右为1 } HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]);//将该字符的哈夫曼编码赋到HC中 //printf("%c",cd[start]); } free(cd); } int main(int argc, const char * argv[]) { int n=10; int w[200]={0,30,40,20,10,5,15,10,45,20,60};//存放每个字符的权值 // int w1[200]={0,10,5,20}; Huffman(HT, w, n); // Huffmancode(HT,HC,n); for(int k=1;k<n;k++){//输出每个字符的哈夫曼编码 printf("%s ",HC[k]); } printf(" "); return 0; }
源代码
// // main.c // 作业11 // // Created by yizhihenpidehou on 2020/5/12. // Copyright © 2020 yizhihenpidehou. All rights reserved. // #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct{ int weight; int lchild,rchild,parent; }HTNode,*HuffmanTree; typedef char **HuffmanCode; HuffmanCode HC; HuffmanTree HT; int s1; int s2; void SelectMin(HuffmanTree tree,int n){ //找出权值最小的两棵树 int minn=1;//存放临时最小值 for(int i=1;i<=n;i++){ if(tree[i].parent==0){//找出一个暂时的最小值 minn=i; break; } } for(int i=1;i<=n;i++){ if(tree[i].parent==0&&tree[i].weight<tree[minn].weight){//找出第一个最小值 minn=i; } } s1=minn; for(int i=1;i<=n;i++){ if(tree[i].parent==0&&i!=s1){//找出一个暂时的最小值 minn=i; break; } } for(int i=1;i<=n;i++){ if(tree[i].parent==0&&tree[i].weight<tree[minn].weight&&i!=s1){//找出第二个最小值 minn=i; } } s2=minn; // printf("s1:%d s2:%d ",s1,s2); } void Huffman(HuffmanTree tree,int *w,int n){//哈夫曼编码 int m=2*n-1;//哈夫曼树的节点数 tree=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//申请节点 for(int i=1;i<=m;i++){//初始化树 tree[i].lchild=0; tree[i].rchild=0; tree[i].parent=0; if(i<=n){//设置每个叶子节点的权值 tree[i].weight=w[i]; } else{ tree[i].weight=0; } } for(int i=n+1;i<=m;i++){ SelectMin(tree,i-1); // printf("s1 %d s2 %d ",s1,s2); tree[s1].parent=i;//将s1的父亲设置为i tree[s2].parent=i;//将s2的父亲设置为i tree[i].lchild=s1;//将s1作为i的左孩子 tree[i].rchild=s2;//将s2作为i的右孩子 tree[i].weight=tree[s1].weight+tree[s2].weight;//i的权值为s1与s2的和 // printf("val s1:%d s2:%d ",tree[s1].weight,tree[s2].weight); // printf("new NODE %d %d %d %d ",tree[i].parent,tree[i].lchild,tree[i].rchild,tree[i].weight); } //以上为建造一颗哈夫曼树，以下为求哈夫曼编码 HC=(HuffmanCode)malloc((n+1)*(sizeof(char *)));//相当于申请一个二维数组，存放n个哈夫曼编码 char *cd; cd=(char *)malloc(n*sizeof(char));//相当于申请一个一维数组，暂存哈夫曼编码 cd[n-1]=' ';//编码结束符 int start; for(int i=1;i<=n;i++){ start=n-1;//初始点 for(int j=i,f=tree[i].parent;f!=0;j=f,f=tree[f].parent){ //逆向求哈夫曼编码 if(tree[f].lchild==j) cd[--start]='0'; //向左为0 else cd[--start]='1';//向右为1 } HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]);//将该字符的哈夫曼编码赋到HC中 //printf("%c",cd[start]); } free(cd); } int main(int argc, const char * argv[]) { int n=10; int w[200]={0,30,40,20,10,5,15,10,45,20,60};//存放每个字符的权值 // int w1[200]={0,10,5,20}; Huffman(HT, w, n); // Huffmancode(HT,HC,n); for(int k=1;k<n;k++){//输出每个字符的哈夫曼编码 printf("%s ",HC[k]); } printf(" "); return 0; }
时间复杂度 O(n^2*logn)
因为构造一棵哈夫曼树需要n^2，而编码只需从叶子节点走到根节点，大约是logn