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信号槽中槽函数为虚函数的一些感想