赫夫曼编码！

ゞ浴缸里的玫瑰 2022-04-11 08:08 215阅读 0赞

**算法描述：**

**         ** **1.为结点（包括叶子结点和根结点）赋值。  
            设叶子结点有n个，则总结点数有2n-1个。首先为前n个结点，即叶子结点赋值。规定叶子节点的左右孩子均为0，根结点的双亲为0；赋值完叶子结点后从n+1到2n-1为根结点赋值。  
          2.构造赫夫曼树  
            首先在n个叶子结点中挑选权值最小的俩个叶子结点，它们的双亲则为第n+1个结点，即第一个子根。并且该双亲的权值等于这两个孩子的权值之和。下一次在n+1个结点中（包括新构造的第一个双亲结点）中再次挑选权值最小的两个结点，去构造第二个双亲结点。。。。以此类推。。  
          3.进行编码  
            规定左路赋值为0，右路赋值为1，每个叶子对应的编码则为从根到该结点的路径上所对应的编码。程序中是从结点到根逆序赋值。**

1.  \#include<string.h>   
2.  \#include<malloc.h> // malloc()等   
3.  \#include<limits.h> // INT\_MAX等   
4.  \#include<stdio.h> // EOF(=^Z或F6),NULL   
5.  //huffman树的存储结构   
6.  typedef struct  
7.  \{  
8.   unsigned int weight;//权值   
9.   unsigned int parent,lchild,rchild;//双亲，左右孩子的序号   
10. \}HTNode,\*HuffmanTree;  
11. typedef char \*\*HuffmanCode;  
12.   
13.   
14. int min(HuffmanTree t,int i)  
15. \{ // 返回i个结点中权值最小的树的根结点序号，函数select()调用   
16.  int j,flag;  
17.  unsigned int k=UINT\_MAX; // 取k为不小于可能的值(无符号整型最大值)   
18.  for(j=1;j<=i;j++)  
19.   if(t\[j\].weight<k&&t\[j\].parent==0) // t\[j\]是树的根结点   
20.    k=t\[j\].weight,flag=j;  
21.   t\[flag\].parent=1; // 给选中的根结点的双亲赋1，避免第2次查找该结点   
22.   return flag;  
23. \}  
24.   
25. void select(HuffmanTree t,int i,int &s1,int &s2)  
26. \{ // 在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个   
27.  int j;  
28.  s1=min(t,i);  
29.  s2=min(t,i);  
30.  if(s1>s2)  
31.  \{  
32.   j=s1;  
33.   s1=s2;  
34.   s2=j;  
35.  \}  
36. \}  
37.   
38. void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int \*w,int n)   
39. \{ // w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC   
40.  int m,i,s1,s2,start;  
41.  unsigned c,f;  
42.  HuffmanTree p;  
43.  char \*cd;  
44.  if(n<=1)  
45.   return;  
46.  m=2\*n-1;  
47.  HT=(HuffmanTree)malloc((m+1)\*sizeof(HTNode)); // 0号单元未用   
48.  for(p=HT+1,i=1;i<=n;++i,++p,++w)  
49.  \{  
50.   (\*p).weight=\*w;  
51.   (\*p).parent=0;  
52.   (\*p).lchild=0;  
53.   (\*p).rchild=0;  
54.  \}  
55.  for(;i<=m;++i,++p)  
56.   (\*p).parent=0;  
57.  for(i=n+1;i<=m;++i) // 建赫夫曼树   
58.  \{ // 在HT\[1～i-1\]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2   
59.   select(HT,i-1,s1,s2);  
60.   HT\[s1\].parent=HT\[s2\].parent=i;  
61.   HT\[i\].lchild=s1;  
62.   HT\[i\].rchild=s2;  
63.   HT\[i\].weight=HT\[s1\].weight+HT\[s2\].weight;  
64.  \}  
65.  // 从叶子到根逆向求每个字符的赫夫曼编码   
66.  HC=(HuffmanCode)malloc((n+1)\*sizeof(char\*));  
67.  // 分配n个字符编码的头指针向量(\[0\]不用)   
68.  cd=(char\*)malloc(n\*sizeof(char)); // 分配求编码的工作空间   
69.  cd\[n-1\]='\\0'; // 编码结束符   
70.  for(i=1;i<=n;i++)  
71.  \{ // 逐个字符求赫夫曼编码   
72.   start=n-1; // 编码结束符位置   
73.   for(c=i,f=HT\[i\].parent;f!=0;c=f,f=HT\[f\].parent)  
74.    // 从叶子到根逆向求编码   
75.    if(HT\[f\].lchild==c)  
76.     cd\[--start\]='0';  
77.    else  
78.     cd\[--start\]='1';  
79.    HC\[i\]=(char\*)malloc((n-start)\*sizeof(char));  
80.    // 为第i个字符编码分配空间   
81.    strcpy(HC\[i\],&cd\[start\]); // 从cd复制编码(串)到HC   
82.  \}  
83.  free(cd); // 释放工作空间   
84. \}  
85.   
86. void main()  
87. \{  
88.  HuffmanTree HT;  
89.  HuffmanCode HC;  
90.  int \*w,n,i;  
91.  printf("请输入权值的个数(>1): ");  
92.  scanf("%d",&n);  
93.  w=(int\*)malloc(n\*sizeof(int));  
94.  printf("请依次输入%d个权值(整型):\\n",n);  
95.  for(i=0;i<=n-1;i++)  
96.   scanf("%d",w+i);  
97.  HuffmanCoding(HT,HC,w,n);  
98.  for(i=1;i<=n;i++)  
99.   puts(HC\[i\]);  
100. ** \}  **

![1357383960_3063.jpg][]

[1357383960_3063.jpg]: https://img-my.csdn.net/uploads/201301/05/1357383960_3063.jpg