2021年赫夫曼树实验报告.docVIP

2021年赫夫曼树实验报告 2021年赫夫曼树实验报告 PAGE / NUMPAGES 2021年赫夫曼树实验报告 实 验 报 告 试验原理: 霍夫曼编码（Huffman Coding）是一个编码方法, 是一个用于无损数据压缩熵编码（权编码）算法。1952年, David A. Huffman在麻省理工攻读博士时所发明。 在计算机数据处理中, 霍夫曼编码使用变长编码表对源符号（如文件中一个字母）进行编码, 其中变长编码表是经过一个评定起源符号出现机率方法得到, 出现机率高字母使用较短编码, 反之出现机率低则使用较长编码, 这便使编码以后字符串平均长度、 期望值降低, 从而达成无损压缩数据目。 比如, 在英文中, e出现机率最高, 而z出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时, e极有可能用一个比特来表示, 而z则可能花去25个比特（不是26）。用一般表示方法时, 每个英文字母均占用一个字节（byte）, 即8个比特。二者相比, e使用了通常编码1/8长度, z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率较正确估算, 就能够大幅度提升无损压缩百分比。 霍夫曼树又称最优二叉树, 是一个带权路径长度最短二叉树。所谓树带权路径长度, 就是树中全部叶结点权值乘上其到根结点路径长度（若根结点为0层, 叶结点到根结点路径长度为叶结点层数）。树路径长度是从树根到每一结点路径长度之和, 记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln), N个权值Wi（i=1,2,...n）组成一棵有N个叶结点二叉树, 对应叶结点路径长度为Li（i=1,2,...n）。能够证实霍夫曼树WPL是最小。 试验目: 本试验经过编程实现赫夫曼编码算法, 使学生掌握赫夫曼树结构方法, 了解树这种数据结构应用价值, 并能熟练利用C语言指针实现构建赫夫曼二叉树, 培养理论联络实际和自主学习能力, 加强对数据结构原理了解, 提升编程水平。 试验内容: （1）实现输入英文字符串输入, 并设计算法分别统计不一样字符在该字符串中出现次数, 字符要区分大小写; （2）实现赫夫曼树构建算法; （3）遍历赫夫曼生成每个字符二进制编码; （4）显示输出每个字母编码。 七、 试验器材（设备、 元器件）: PC机一台, 装有C语言集成开发环境。 数据结构与程序: #include iostream #include cctype using namespace std; typedef struct HuffNode { int weight; struct HuffNode *lchild, *rchild, *parent; } HuffNode, *HuffPtr; void select(HuffPtr, int *, int *, int); void createHuffTree(HuffPtr, int *, int); void getCode(HuffPtr, int, int *); void _free(HuffPtr); void main() { char ch; int count = 0; int refer[52] = {0}; coutPlease input:endl; while((ch = getchar()) != \n) { if(isalpha(ch) isupper(ch)) refer[ch-A+26]++; else if(isalpha(ch) islower(ch)) refer[ch-a]++; count++; } HuffPtr header = new HuffNode[2*count-1]; createHuffTree(header, refer, count); getCode(header, count, refer); _free(header); } void select(HuffPtr header, int *node1, int *node2, int all)//选择权值最小 { static bool flag[103] = {false}; int min = all; for(int i = 0;i all;i++) { if(header[i].weight 0 header[i].weight min !flag[i]) { *node1 = i; min = header[i].weight; flag[i] = true; } } min = all; for(int i = 0;i all;i++) { i