哈弗曼树实验报告.doc

哈夫曼树及其的应用 一、实验目的1在二叉树基本操作的基础上，掌握对二叉树的一些其它操作的具体实现方法。2.掌握构造哈夫曼树以及哈夫曼编码的方法。3、熟练掌握哈夫曼树（最优二叉树）特征及其应用二、实验内容 题目一、哈夫曼树和哈夫曼编码： 从终端输入若干个字符，统计（或指定）字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的哈夫曼编码。设计要求： 哈夫曼殊和哈夫曼编码的存储表示参考教材事例 在程序中构造四个子程序为 int freqchar(char *text, HTree *t) /统计字符出现的频率 int createhtree(HTree *t) /根据字符出现的频率建立哈夫曼树 void coding(HTree *t,int head_i,char *code)/对哈夫曼树进行编码 void printhtree(HTree *t,int head_i,int deep,int* path)/中序打印树 三、实验步骤、数据结构与核心算法的设计描述void Frequent()/计算输入字母出现的频率void Select(HuffmanTree HT,int i,int &s1,int &s2) /选择函数voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int *w,int n) /w存放n个权值, 构造哈夫曼树p, 并求出哈夫曼编码hc并输出哈弗曼编码、函数调用及主函数设计主函数Frequent( )计算输入字母出现的频率Select(HuffmanTree HT,int i,int &s1,int &s2)选择函数HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int *w,int n)构造哈夫曼树p, 并求出哈夫曼编码hc打印哈弗曼树表 程序调试及运行结果分析首先调用Frequent()，计算输入字母出现的频率，输入一串字符串，并以字符#号结束，运行结果如下：然后根据输入字符的个数与出现的频率输入哈弗曼所要编码的个数，然后输入这几个字母的权值，即出现的频率，运行结果如下：然后输出哈弗曼树的建立次序，哈弗曼树表以及哈弗曼编码,结果如下： 实验总结通过这次实验使我掌握了哈夫曼树与哈夫曼码的转换。其中就是要求的函数不能正确的写出来，这次没按照实验要求的函数写，弄了很长时间也没弄出来，就这样把几个函数放在一起啦。四、主要算法流程图及程序清单 1、主要算法流程图：主函数开始界面统计频率构造哈夫曼树p输出哈夫曼编码打印哈弗曼树表选择函数主函数输出数据结束 2、程序清单 #include#include#include#include#include#define maxsize 100struct frequence/统计频率char a;/存放字符 int n;/该字符出现的次数;typedef structunsigned int weight;/ 用来存放各个结点的权值unsigned int parent,lchild,rchild;/指向双亲、 孩子结点的指针HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedef char *HuffmanCode;/动态分配数组存储赫夫曼编码表void Frequent()frequence ch27;/26个英文字母，0号位置不存储字符，用来存储总共的字符个数,多次出现的只记一次int i=0;for(;i=26;i+)/初始化结构体数组chi.n=0;coutc;bool flag;while(c!=#)i=1;flag=false;for(;ic;for(int j=1;j=ch0.n;j+)coutchj.a chj.nendl;void Select(HuffmanTree HT,int i,int &s1,int &s2) int j,k=1; while(HTk.parent!=0)k+;s1=k;for(j=1;j=i;+j)if(HTj.parent=0&HTj.weightHTs1.weight)s1=j;k=1;while(HTk.parent!=0|k=s1)k+;s2=k;for(j=1;j=i;+j)if(HTj.parent=0&HTj.weightHTs2.weight&j!=s1)s2=j;void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n) /w存放n个权值, 构造哈夫曼树p, 并求出哈夫曼编码hc int m,i,s1,s2,start,c,f;HuffmanTree p;if(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0号单元未用for(p=HT+1,i=1;iweight=*w;cout输出各个元素的权值endl;coutHTi.weight=weightparent=0;p-lchild=0; p-rchild=0;for(;iweight=0;p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;+i)/建立赫夫曼树 Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;coutn哈弗曼树表endl;/打印哈弗曼树表cout i weight parent lchild rchildendl;for(p=HT+1,i=1;i=m;i+,p+)coutsetw(2)isetw(7)weightsetw(6)parentsetw(7)lchildsetw(8)rchildendl;/从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)malloc(n+1)*sizeof(char *);/分配n个字符编码的走指针向量char *cd;cd=(char *)malloc(n*sizeof(char);/分配求编码的工作空间cdn-1=0;/编码结束符cout哈夫曼编码如下:endl;for(i=1;i=n;+i)/逐个字符求赫夫曼编码 start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间strcpy(HCi,&cdstart);/从cd复制编码到HCprintf(nHT%d 节点的哈夫曼编码是: %s,i,HCi);coutendl;fre