哈夫曼树实验报告

1、实验报告实验名称 Huffman编码 专业班级 计科三班 姓名 学号 指导教师 日期 2014.12.20 一、实验目的 熟练掌握二叉树应用（Huffman编码）的基本算法实现。二、实验内容l 1对输入的一串电文字符实现Huffman编码，再对Huffman编码生成的代码串进行译码，输出电文字符串。实现功能如下： Huffman树的建立 Huffman编码的生成编码文件的译码三、实验要求l 设计思路：数据结构：#define n 100/叶子结点数#define m 2*n-1/ Huffman树中结点总数typedef struct int weight;/权值 int lchild , r

2、child , parent; /左右孩子及双亲指针HTNode; /树中结点类型typedef HTNode HuffmanTreem+1;/0号单元不用主要实现函数：n 统计字符串中字符的种类以及各类字符的个数的函数n 构造Huffman树的函数n Huffman编码的函数n 建立正文的编码文件的函数n 代码文件的译码函数n 主函数四、实验概要设计1)功能框图Huffman树的建立从叶子到根逆向求编码退出Huffman编码程序Huffman编码的生成编码文件的译码五. 使用说明1.运行环境：VC+ 6.0 2.首先选择主控菜单中的操作，即建表，然后进行其它操作六实验截图七 实验体会1、构建

3、哈夫曼树的关键在于找最小树；在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。2、由于学习的不足没有实现编码文件的译码，今后会加以改进 (）3、在逆向求编码的for循环里犯了一个逻辑错误导致求出来的3、4位编码串行，尝试了多钟数据输入才找到原因所在，并加以改正，编写程序需一步一步的去调试并找到错误所在。附源程序：#include#include#include#includetypedef struct char data; /结点字符 int weight; /结点权值 int parent,lchild,rchild

4、; /父子结点 HTNode,* HuffmanTree;typedef char * *HuffmanCode;void Select(HuffmanTree HT, int m, int& s1, int& s2) int i; s1 = s2 = 1; for(i=1; i=m; i+) if (HTi.parent=0) s1=i; break; for(i=i+1; iHTi.weight) s1=i; for(i=1; i=m; i+) if(HTi.parent=0&i!=s1) s2=i; break; for(i=i+1; i=m; i+) if(HTi.parent=0 &

5、 HTi.weightHTs2.weight & i!=s1) s2=i; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) /w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼树编码HCint f; int m,i,s1,s2;int c;HuffmanTree p;char *cd;if (n=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;i=n;+i,+p,+w) (*p).weight=*w

6、; (*p).parent=0; (*p).lchild=0; (*p).rchild=0;for( ;i=m;+i,+p) (*p).parent=0;for(i=n+1;i=m;+i) /建立赫夫曼树 /在HT1.i-1选择parent为0且weight最小的两个节点，其序号分别为s1,s2.Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/*从叶子到根逆向求每个字符的赫夫曼编码*HC=(HuffmanCode)m

7、alloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char); /分配求编码的工作区间cdn-1=0; /编码结束符for(i=1;i=n;+i) /逐个字符求赫夫曼树编码 int start; start=n-1; /编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间strcpy(HCi,&cdstart); /从cd复制编码（串）到HCfree(cd); /释放空间void main()HuffmanTree HT;HuffmanCode HC;int *w,n,i; printf(请输入权值的个数(): );scanf (%d,&n);w=(int *)malloc(n*sizeof(int);print