《哈夫曼编码实验》由会员分享，可在线阅读，更多相关《哈夫曼编码实验（15页珍藏版）》请在金锄头文库上搜索。
1、实验哈夫曼编码一、实验目的及内容：要求：给定一个纯英文文本news.txt1、统计其中字母及其它符号的个数；2、对在文中出现的英文字母及符号进行哈夫曼编码；3、利用得到的哈夫曼编码转换英文文本内容，将结果保存至文件news_huff.txt。二、实验原理：1、哈夫曼简介：哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长 度，就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层，叶结点 到根结点的路径长度为叶结点的层数)。树的带权路径长度记为 WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N 个权值 Wi(i=1,2,.n)构成一棵有 N
2、 个叶结 点的二叉树，相应的叶结点的路径长度为Li(i=1,2,.n)。可以证明哈夫曼树的WPL是最小 的。2、编码步骤：1)对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F= T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树 均为空。(为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。)2) 在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点 的权值为其左右子树的根结点的权值之和。3) 从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。4) 重复二和三两
3、步，直到集合F中只有一棵二叉树为止。三、实验结果：1、节点权值的统计结果字符总个数s为1272。以下为每个字符出现次数及频率：25119.73%30.23%,10.08%.201.57%!30.24%”40.31%B10.08%H60.47%I40.31%L10.08%O10.08%R40.31%S20.16%T10.08%W10.08%Y10.08%a826.45%b120.94%c201.57%d453.54%e1189.28%f262.04%g272.12%h796.21%i604.72%k90.71%l393.07%m362.83%n614.80%o695.42%p120.94%r51
4、4.01%s524.09%t937.31%u221.73%v60.47%w251.97%x20.16%y221.73%2、哈夫曼树的构造系列图1.00a:1111h0c:110d;1110e:10哈夫曼编码0.40；0.60）（0.25）（0.35）哈夫曼编码树3、各个字符的编码结果:000，:001.:0101: 011000k: 01100100I: 011001010T: 011001011c: 0110011h: 01101a: 01110y: 0111100u: 0111101d: 011111t: 10000v: 100010000H: 100010001b: 10001001w:
5、 1000101r: 100011f: 1001000g: 1001001s: 100101e: 10011i: 101000n: 101001p: 10101000j: 10101001000L: 101010010010W: 101010010011C: 101010010100B: 101010010101S: 10101001011x: 10101001100Y: 101010011010O: 101010011011R: 1010100111m: 1010101o: 101011: 1011!: 1100：1101: 1110-:11114、关键性程序代码：#include#incl
6、ude#include#include#include#define MAX 1000using namespace std;struct Node /huffman 树节点char c;int num;int l,r;int value;bool operator (const Node& rhs) const return value rhs.value;pMAX,qMAX;char hashMAX;int ans100MAX,lengMAX,cont; /与编码相关,记录编码结果int aMAX;int pathMAX;void print_path(int root, int cnt)
7、(/编码过程：遍历 huffman 树int lt = qroot.l;int rt = qroot.r;if (lt = 0 & rt = 0)(hashcont+ = qroot.c;lengcont-1 = cnt;for (int i = 0; icnt; i+) anscont-1i = pathi;return;if (lt != 0)(pathcnt = 0;print_path(lt,cnt+1);if (rt != 0)(pathcnt = 1;print_path(rt,cnt+1);char decoding(int root, char u, int len)(/解码：
8、在 huffman 树上查找for (int i = 0; ilen; i+)(if (ui = 0)(root = qroot.l; else(root = qroot.r;if (qroot.l = 0 & qroot.r = 0)( return qroot.c;return #;int main()(memset(a,0,sizeof(a);cont = 0;char c;freopen(news.txt”,r”,stdin);while (scanf(%c”,&c) != EOF)(if (islower(c)(ac-a+;else if (isupper(c)(ac-A + 26+
9、;else if (isdigit(c)( ac-0+52+;else(for(int i=62;i=69;i+)ai+;fclose(stdin);int cnt = 0;for (int i = 0; i 0)(小写字母pcnt+ = (Node)i+a,cnt,0,0,ai;0for (int i = 26; i 0)/次写字母pcnt+ = (Node)i-26+A,cnt,0,0,ai;for (int i = 52; i 0)pcnt+ = (Node)i-52+0,cnt,0,0,ai;if (a62) pcnt+ = (Node)n,cnt,0,0,a62;/换行符if (a6
10、3) pcnt+ = (Node),cnt,0,0,a63;if (a64) pcnt+ = (Node).,cnt,0,0,a64;if (a65) pcnt+ = (Node)?,cnt,0,0,a65;if (a66) pcnt+ = (Node)!,cnt,0,0,a66;if (a67) pcnt+ = (Node),cnt,0,0,a67;if (a68) pcnt+ = (Node) ,cnt,0,0,a68;if (a69) pcnt+ = (Node)-,cnt,0,0,a69;/for (int i = 0; icnt; i+) printf(%c: %dn”,pi.c,p
11、i.value);if (cnt = 1) 当只有一种字符时，该字符的huffman编码为0;freopen(new_in.txt”,w”,stdout);for (int i = 0; ipcnt-1.value; i+) printf(%c”,pcnt-1.c);fclose(stdout);return 0;sort(p,p+cnt);int r = 0;while (r+1 cnt)/建 huffman 树sort(p+r+2,p+cnt);pr.num = r+1;pr+1.num = r+2;qr+1 = pr;qr+2 = pr+1;int u = pr.value + pr+1
12、.value;pcnt+ = (Node) ,cnt,pr.num,pr+1.num,u;r = r + 2;qcnt = pcnt-1;print_path(cnt,0);freopen(maunal.txt”,w”,stdout); /字符对应 huffman 码for(int i = 0; icont; i+)(printf(%c: ,hashi);for (int j = 0; jlengi; j+) printf(%d,ansij);printf(n);fclose(stdout);freopen(news.txt,r,stdin); /对 news.txt 生成 huffman 编码，并将其写入 news_huff.txt 中freopen(news_huff.txt,w,stdout);while (scanf(%c”,&c) != EOF)(int i;for (i = 0; icont; i+) if (hashi = c)(break;for(int j = 0; jlengi; j+) printf(%d,ansij);fclose(stdin);fclose(stdout);freopen(news_huff.txt,r,stdin); / 读出 news_huff.txt 中的
