2022-03-01
记得大一上的通信原理课提到了霍夫曼编码
目的：实现某段文本的编码压缩，以及对其的解压操作
分步骤：
1.进行构造霍夫曼树
1 #include<iostream>
2 using namespace std;
3 #define maxn 3000
4 typedef struct HUFFMANTREE {
5 double pinlv;
6 HUFFMANTREE* ltree;
7 HUFFMANTREE* rtree;
8 }htree;
9 htree* forest[maxn];
10 htree* creathtree(double a[],int len)
11 {
12 for (int i = 1;i <= len;i++)
13 {
14 htree* temp = new htree;
15 temp->pinlv = a[i];
16 temp->ltree = NULL;
17 temp->rtree = NULL;
18 forest[i] = temp;
19 cout << forest[i]->pinlv << endl;
20 }
21 //把哈夫曼森林给初始化喽
22
23 int minn1 = -1, minn2;
24 for (int i = 1;i <= len - 1;i++)
25 {
26 for (int j = 1;j <= len;j++)
27 {
28 if (forest[j] != NULL && minn1 == -1)
29 minn1 = j;
30 else if (forest[j] != NULL)
31 {
32 minn2 = j;
33 break;
34 }
35 }
36 //挑选可选的初始值
37
38 for (int j = 1;j <= len;j++)
39 {
40 if (forest[j]!=NULL&&forest[j]->pinlv < forest[minn1]->pinlv)
41 {
42 minn2 = minn1;
43 minn1 = j;
44 }
45 else if (forest[j] != NULL&& forest[j]->pinlv < forest[minn2]->pinlv)
46 minn2 = j;
47 }
48 //寻找最小的两个结点
49
50
51 htree* root = new htree;
52 root->pinlv = forest[minn1]->pinlv + forest[minn2]->pinlv;
53 root->ltree = forest[minn1];
54 root->rtree = forest[minn2];
55 forest[minn1] = root;
56 forest[minn2] = NULL;
57 //将那两个最频率的结点给结合成新的树，并将树给存进哈夫曼森林中去，继续卷
58 }
59 return forest[minn1];
60 }
2.算wpl，即总字节数
1 int wpl(htree* root,int deep)
2 {
3 if (root == NULL)
4 return 0;
5 if (root->ltree == NULL && root->rtree == NULL)
6 return root->cost*deep;
7 else
8 {
9 int left = wpl(root->ltree, deep + 1);
10 int right = wpl(root->rtree, deep + 1);
11 return left + right;
12 }
3.编码的方式（自己搞的感觉很繁琐且拖沓迟钝）
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 #define maxn 3000
5 typedef struct HUFFMANTREE {
6 double pinlv;
7 char ch;
8 int bianma[maxn];
9 HUFFMANTREE* ltree;
10 HUFFMANTREE* rtree;
11 }htree;
12 htree* forest[maxn];
13 void pinlv_count(htree* codes[],int len)
14 {
15 int book[53] = { 0 };
16 for (int i = 1;i <= len;i++)
17 {
18
19 if (codes[i]->ch >= 'a' && codes[i]->ch <= 'z')
20 {
21 if (book[codes[i]->ch - 'a' + 1] == 0)
22 book[codes[i]->ch - 'a' + 1]++;
23 else
24 {
25 book[codes[i]->ch - 'a' + 1]++;
26 codes[i] = NULL;
27 }
28 }
29 else if (codes[i]->ch >= 'A' && codes[i]->ch <= 'Z')
30 {
31 if (book[codes[i]->ch - 'A' + 27] == 0)
32 book[codes[i]->ch - 'A' + 27]++;
33 else
34 {
35 book[codes[i]->ch - 'A' + 27]++;
36 codes[i] = NULL;
37 }
38 }
39 }
40 for (int i = 1;i <= len;i++)
41 {
42 if (codes[i] != NULL)
43 {
44 if (codes[i]->ch >= 'a' && codes[i]->ch <= 'z')
45 codes[i]->pinlv = (double)book[codes[i]->ch - 'a' + 1] / len;
46 else if (codes[i]->ch >= 'A' && codes[i]->ch <= 'Z')
47 codes[i]->pinlv = (double)book[codes[i]->ch - 'A' + 1] / len;
48 }
49 }
50 }
51 htree* creathtree(char a[],int len)
52 {
53 for (int i = 1;i <= len;i++)
54 {
55 htree* temp = new htree;
56 temp->ch=a[i];
57 temp->ltree = NULL;
58 temp->rtree = NULL;
59 forest[i] = temp;
60 }
61 //把哈夫曼森林给初始化喽
62 pinlv_count(forest, len);
63 int len_quchonghou=0;
64 for (int i = 1;i <= len;i++)
65 if (forest[i] != NULL)
66 len_quchonghou++;
67 len = len_quchonghou;
68 int minn1 = -1, minn2;
69 for (int i = 1;i <= len - 1;i++)
70 {
71 minn1 = -1;
72 for (int j = 1;j <= len;j++)
73 {
74 if (forest[j] != NULL && minn1 == -1)
75 minn1 = j;
76 else if (forest[j] != NULL)
77 {
78 minn2 = j;
79 break;
80 }
81 }
82 //挑选可选的初始值
83
84 for (int j = 1;j <= len;j++)
85 {
86 if (forest[j]!=NULL&&forest[j]->pinlv < forest[minn1]->pinlv)
87 {
88 minn2 = minn1;
89 minn1 = j;
90 }
91 else if (j!=minn1&&forest[j] != NULL&& forest[j]->pinlv < forest[minn2]->pinlv)
92 minn2 = j;
93 }
94 //寻找最小的两个结点
95
96
97 htree* root = new htree;
98 root->ltree = forest[minn1];
99 root->rtree = forest[minn2];
100 root->pinlv = forest[minn1]->pinlv + forest[minn2]->pinlv;
101 forest[minn1] = root;
102 forest[minn2] = NULL;
103 //将那两个最频率的结点给结合成新的树，并将树给存进哈夫曼森林中去，继续卷
104 }
105 return forest[minn1];
106 }
107 void HUFFMANBIANMA(htree* root,int len,int a[])
108 {
109 if (root != NULL)
110 {
111 if (root->ltree == NULL && root->rtree == NULL)
112 {
113 cout << root->ch<<": ";
114 for (int i = 1;i < len;i++)
115 {
116 root->bianma[i] = a[i];
117 cout << root->bianma[i];
118 }
119 cout << endl;
120 }
121 else
122 {
123 a[len] = 0;
124 HUFFMANBIANMA(root->ltree, len + 1, a);
125 a[len] = 1;
126 HUFFMANBIANMA(root->rtree, len + 1, a);
127 }
128 }
129 }
130 int main(void)
131 {
132 char a[] = { 'x','a','b','c','d','e','f','a','a','a' };
133 htree* root = creathtree(a,9);
134 int bianma[maxn];
135 HUFFMANBIANMA(root, 1, bianma);
136 return 0;
137 }