Huffman编码实验
生活随笔
收集整理的这篇文章主要介绍了
Huffman编码实验
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
一、实验目的
熟练掌握哈夫曼树的建立和哈夫曼编码的算法实现。
二、实验内容
根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求赫夫曼编码，并能把给定的编码进行译码。
三、 实验要求
（1）初始化：从键盘输入一字符串（或读入一文件），统计出现的字符和每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树。对各个字符进行哈夫曼编码，最后打印输出字符及每个字符对应的哈夫曼编码。
（2）编码：利用已建好的哈夫曼树对“输入串”进行哈夫曼编码，最后打印输入串对应的哈夫曼编码（写入文件）。
（3）计算压缩比（选作）
（4）译码：利用已建好的哈夫曼树对给定的一串代码进行译码，并打印输出得到的字符串。（选作）
测试数据：对字符串{casbcatbsatbat}进行编码；对电文“1101000”译码。字符集D={ ？},出现频率为w={？}
1 #include <stdio.h>
2 #include <string.h>
3 #include <iostream>
4 #include <string>
5 #include <math.h>
6 #include <algorithm>
7 #include <vector>
8 #include <stack>
9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=1e4+10;
17 using namespace std;
18
19 struct node
20 {
21 int val;//权值
22 int lc;//左孩子
23 int rc;//右孩子
24 int parent;//双亲
25 char c;//节点字符
26 int flag;//标志
27 }Huffman_Tree[26*2];
28
29 int num[26]={0};//每种字符的个数
30 char Huffman_code[26][100];//每种字符对应的编码
31 char str[maxn];//原字符串
32 int cnt;//Huffman树节点个数计数器
33
34 void Init()//初始化
35 {
36 printf("请输入一串字符串(该字符串只能为小写字母)：
");
37 gets(str);
38 for(int i=0;str[i];i++)
39 {
40 num[str[i]-'a']++;
41 }
42 int sum=0;
43 for(int i=0;i<26;i++)
44 {
45 if(num[i])//初始化
46 {
47 sum++;
48 Huffman_Tree[++cnt].c=i+'a';
49 Huffman_Tree[cnt].val=num[i];
50 Huffman_Tree[cnt].lc=0;
51 Huffman_Tree[cnt].rc=0;
52 Huffman_Tree[cnt].parent=0;
53 Huffman_Tree[cnt].flag=0;
54 }
55 }
56 for(int k=0;k<sum-1;k++)//建树
57 {
58 int MIN1=INF;
59 int MIN2=INF;
60 int Index1,Index2;
61 for(int i=1;i<=cnt;i++)
62 {
63 if(Huffman_Tree[i].flag==0)
64 {
65 if(Huffman_Tree[i].val<MIN1)
66 {
67 MIN2=MIN1;
68 Index2=Index1;
69 MIN1=Huffman_Tree[i].val;
70 Index1=i;
71 }
72 else if(Huffman_Tree[i].val<MIN2)
73 {
74 MIN2=Huffman_Tree[i].val;
75 Index2=i;
76 }
77 }
78 }
79 Huffman_Tree[Index1].flag=1;
80 Huffman_Tree[Index2].flag=1;
81 int t=MIN1+MIN2;
82 Huffman_Tree[++cnt].val=t;
83 Huffman_Tree[cnt].c='*';
84 Huffman_Tree[cnt].lc=Index1;
85 Huffman_Tree[cnt].rc=Index2;
86 Huffman_Tree[cnt].parent=0;
87 Huffman_Tree[cnt].flag=0;
88 Huffman_Tree[Index1].parent=cnt;
89 Huffman_Tree[Index2].parent=cnt;
90 }
91 for(int i=0;i<26;i++)//求Huffman编码
92 {
93 if(num[i])
94 {
95 char tem[100];
96 int len=0;
97 int p;
98 for(int j=1;j<=cnt;j++)
99 {
100 if(Huffman_Tree[j].c==i+'a')
101 {
102 p=j;
103 break;
104 }
105 }
106 while(Huffman_Tree[p].parent)
107 {
108 if(Huffman_Tree[Huffman_Tree[p].parent].lc==p)
109 tem[len++]='0';
110 else
111 tem[len++]='1';
112 p=Huffman_Tree[p].parent;
113 }
114 tem[len]='';
115 int ccnt=0;
116 for(int j=len-1;j>=0;j--)
117 {
118 Huffman_code[i][ccnt++]=tem[j];
119 }
120 Huffman_code[i][ccnt]='';
121 // for(int j=0;j<len/2;j++)
122 // {
123 // char t=tem[j];
124 // tem[j]=tem[len-1-j];
125 // tem[len-1-j]=t;
126 // }
127 // NUM[i]=tem;
128 // puts(NUM[i]);
129 }
130 }
131 printf("每个字母对应的Huffman编码为：
");
132 for(int i=0;i<26;i++)
133 {
134 if(num[i])
135 {
136 printf("%c:",i+'a');
137 puts(Huffman_code[i]);
138 }
139 }
140 }
141
142 void Print_out()//编码
143 {
144 printf("输入串对应的哈夫曼编码为:
");
145 for(int i=0;str[i];i++)//根据字符匹配编码
146 {
147 printf("%s",Huffman_code[str[i]-'a']);
148 }
149 printf("
");
150 }
151
152 void Solve1()//计算压缩比
153 {
154 int sum=0;//字符种类个数
155 for(int i=0;i<26;i++)
156 {
157 if(num[i])
158 sum++;
159 }
160 double a=0;//平均码长
161 int b;//等长码
162 if(sum==1)
163 b=1;
164 else b=(int)log2(sum-1)+1;
165 double ans;
166 for(int i=0;i<26;i++)
167 {
168 if(num[i])
169 {
170 a+=(num[i]*1.0/strlen(str))*strlen(Huffman_code[i]);
171 }
172 }
173 ans=a/b*1.0;
174 printf("该字符串压缩比为：
");
175 printf("%.2lf%%
",ans*100);
176 }
177
178 void Solve2()//译码
179 {
180 char tem[maxn];
181 // char ans[maxn];
182 // int len=0;
183 printf("请输入要进行译码的0-1串：
");
184 scanf("%s",tem);
185 // int i,j,k;
186 // for(i=0;tem[i];i++)
187 // {
188 // for(k=0;k<26;k++)
189 // {
190 // if(num[k])
191 // {
192 // for(j=0;j<strlen(Huffman_code[k]);)
193 // {
194 // if(tem[i]==Huffman_code[k][j])
195 // {
196 // i++;
197 // j++;
198 // }
199 // else
200 // {
201 // i-=j;
202 // j=0;
203 // break;
204 // }
205 // }
206 // if(j==strlen(Huffman_code[k]))
207 // {
208 // i--;
209 // ans[len++]=k+'a';
210 // break;
211 // }
212 // }
213 // }
214 // }
215 // ans[len]='';
216 // printf("该0-1串译文为：
");
217 // puts(ans);
218 int rt;//Huffman树根
219 for(int i=1;i<=cnt;i++)//找到根
220 {
221 if(Huffman_Tree[i].parent==0)
222 {
223 rt=i;
224 break;
225 }
226 }
227 for(int i=0;tem[i];i++)//类似于字典树匹配
228 {
229 for(int p=rt;;i++)
230 {
231 if(tem[i]=='0')
232 p=Huffman_Tree[p].lc;
233 else
234 p=Huffman_Tree[p].rc;
235 if(Huffman_Tree[p].c!='*')
236 {
237 printf("%c",Huffman_Tree[p].c);
238 break;
239 }
240 }
241 }
242 printf("
");
243 }
244
245 int main()
246 {
247 Init();
248 printf("--------------------------------
");
249 Print_out();
250 printf("--------------------------------
");
251 Solve1();
252 printf("--------------------------------
");
253 Solve2();
254 printf("--------------------------------
");
255 return 0;
256 }
总结
以上是生活随笔为你收集整理的Huffman编码实验的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 对《GGX》shader的分析-卡通渲染
- 下一篇： Qt信号槽中槽函数为虚函数的一些感想