《哈夫曼树的建立及应用》由会员分享，可在线阅读，更多相关《哈夫曼树的建立及应用（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告专业: 班级: 姓名: 学号: 指导老师: 评分:实验四 哈夫曼树的建立及应用一、实验目的1、掌握哈夫曼树的基本概念及所有的存储结构。2、掌握哈夫曼树的建立算法。3、掌握哈夫曼树的应用（哈夫曼编码和译码）。二、实习内容1、 给定权值 5，29，7，8，14，23，3，11，建立哈夫 曼树，输出哈夫曼编码。2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一 串二进制编码，输出它的哈夫曼译码。三、算法描述将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子 函数的形式，然后在主函数中调用它们。建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一 维数组，每个元素含有四项：权值，双
2、亲，左孩子，右孩子。给 定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出 表示哈夫曼树的一维数组中的全部元素即可。要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制 编码：往左走，编码为0，往右走，编码为1，然后将从根结点到 树叶中的所有 0、1排列起来，则得到该树叶的哈夫曼编码。哈夫 曼编码可以用一个结构型的一维数组保存，每个元素包含：编码、 编码的开始位置、编码所对应的字符三项。四、程序清单:#include#includeusing namespace std;int x1,x2,s,mm;int ww100;struct elementint weight,lchild,rc
3、hild,parent;string bianma;element huffTree100;int huff100;存储100个权值的数组 void Select(element huffTree,int m) int min,min2,i; min=min2=1000;for(i=0;ihuffTreei.weight ) min2=min; min=huffTreei.weight ;x2=x1;x1=i;else if(min2huffTreei.weight )min2=huffTreei.weight ;x2=i;/哈夫曼树函数void HuffmanTree(element huf
4、fTree)int i;coutvv请设置叶子节点的数量：; cins;coutvv请依次输入这VVSVV个叶子节点的权值(以回车 或者空格为结束输入一个叶子节点的权值)： huffi;for(i=0;iv2*S-1;i+) huffTreei.parent =-1; huffTreei.lchild =-1; huffTreei.rchild =-1;for(int i1=0;i1vS;i1+)huffTreei1.weight=huffi1;for(int k=s;kn-1;i-)huffTreehuffTreei.lchild .bianma =0; huffTreehuffTreei.
5、rchild .bianma =1;for(i=0,j=0;jn;j+) while(huffTreei.parent !=-1) huffTreej.bianma=huffTreehuffTreei.parent.bianma +huffTreej.bianma ; i=huffTreei.parent ;i=j+1;for(i=0;in;i+)coutendl 叶 子 节 点 的 权 值 为 : huffTreei.weight 的编码为: huffTreei.bianma mm; coutvv请输入依次输入解码串(以回车或者空格为结束输 入一个字符): endl;for(int i1=0
6、;i1wwi1;int j=n,j1;int i=0; while(huffTreej.lchild !=-1&imm)if(wwi=1) j=huffTreej.rchild ;else j=huffTreej.lchild ;i+; if(huffTreej.lchild =-1) couthuffTreej.weight endl; j1=j;j=n; else j1=j;if(huffTreejl.lchild !=-1) coutvv部分信息丢失，输入错误, 解码失败!vvendl;void main()HuffmanTree(huffTree); HuffmanBianMa(huffTree,s); HuffmanJieMa(huffTree,2*(s-1); system(pause); 解码成功:解码失败:心得体会：这次实验主要是让我们掌握哈夫曼树的建立算法和掌握哈夫曼树的应用。
