哈夫曼树的建立及应用C++作业+心得.doc

专业：计算机科学与技术 班级：计算机09-1 姓名： * 学号： 20 指导老师：陈* 评分：实验四 哈夫曼树的建立及应用一、 实验目的1、 掌握哈夫曼树的基本概念及所有的存储结构。2、 掌握哈夫曼树的建立算法。3、 掌握哈夫曼树的应用（哈夫曼编码和译码）。二、 实习内容1、 给定权值5，29，7，8，14，23，3，11，建立哈夫曼树，输出哈夫曼编码。2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二进制编码，输出它的哈夫曼译码。三、算法描述将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数中调用它们。建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。程序清单：#include#includeconst int n=8;const int m=2*n-1;struct treefloat weight; int parent; int lch,rch;struct codetypeint bitsn+1; int start; char ch;tree hftreem+1;struct codetype coden+1;void creathuffmantree()int i,j,p1,p2; float s1,s2; for(i=1;i=m;i+) hftreei.parent=0; hftreei.lch=0; hftreei.rch=0; hftreei.weight=0; cout输入n个权值endl; for(i=1;ihftreei.weight; for(i=n+1;i=m;i+) p1=p2=0; s1=s2=32767; for(j=1;j=i-1;j+) if(hftreej.parent=0) if(hftreej.weights1) s2=s1; s1=hftreej.weight; p2=p1; p1=j; else if(hftreej.weights2) s2=hftreej.weight;p2=j; hftreep1.parent=i; hftreep2.parent=i; hftreei.lch=p1; hftreei.rch=p2; hftreei.weight=hftreep1.weight+hftreep2.weight;void huffcode()codetype cd; int c,p; for(int i=1;i=n;i+) cd.start=n+1; cd.ch=96+i; c=i; p=hftreei.parent; while(p!=0) cd.start-; if(hftreep.lch=c)cd.bitscd.start=0; else cd.bitscd.start=1; c=p; p=hftreep.parent; codei=cd; for(i=1;i=n;i+) cout字符codei.ch的权值为：hftreei.weightsetw(5)编码为：; for(int j=codei.start;j=n;j+) coutcodei.bitsj ; coutendl;void trancode()int i=m;char b; coutb; while(b=0)|(b=1) if(b=0)i=hftreei.lch; else i=hftreei.rch; if(hftreei.lch=0) coutb;void main()creathuffmantree(); huffcode(); trancode();运行结果：结果分析（心得体会）：上网找了相