哈夫曼树实验报告x.pdf

《哈夫曼树实验报告x.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、权值谢谢阅读intlchild,rchild,parent;//左右孩子及双亲指针}HTNode;//树中结点类型typedefHTNodeHuffmanTree[m+1];//0号单元不用主要实现函数：统计字符串中字符的种类以及各类字符的个数的函数构造Huffman树的函数Huffman编码的函数建立正文的编码文件的函数代码文件的译码函数主函数四、实验概要设计1)功能框图Huffman树的建立Huffman从叶子到根逆向编码程Huffman编码的编码文件的译码退出五.使用说明1.运行环境：VC++6.

3、02.首先选择主控菜单中的操作１，即建表，然后进行其它操作．六．实验截图谢谢阅读谢谢阅读七实验体会1、构建哈夫曼树的关键在于找最小树；在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。2、由于学习的不足没有实现编码文件的译码，今后会加以改进(╯﹏╰）3、在逆向求编码的for循环里犯了一个逻辑错误导致求出来的3、4位编码串行，尝试了多钟数据输入才找到原因所在，并加以改正，编写程序需一步一步的去调试并找到错误所在。附源程序：#incl

4、ude#include#include#includetypedefstruct{chardata;//结点字符intweight;//结点权值intparent,lchild,rchild;//父子结点}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreeHT,intm,int&s1,int&s2)谢谢阅读谢谢阅读{inti;s1=s2=1;f

5、or(i=1;i<=m;i++){if(HT[i].parent==0){s1=i;break;}}for(i=i+1;i<=m;i++){if(HT[i].parent==0&&HT[s1].weight>HT[i].weight)s1=i;}for(i=1;i<=m;i++){if(HT[i].parent==0&&i!=s1){s2=i;break;谢谢阅读谢谢阅读}}for(i=i+1;i<=m;i++){if(HT[i].parent==0&&HT[i].weight

6、t&&i!=s1)s2=i;}}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼树编码HCintf;intm,i,s1,s2;intc;HuffmanTreep;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,

7、++w){谢谢阅读谢谢阅读(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(;i<=m;++i,++p)(*p).parent=0;for(i=n+1;i<=m;++i)//建立赫夫曼树{//在HT[1..i-1]选择parent为0且weight最小的两个节点，其序号分别为s1,s2.Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i

8、].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}//****从叶子到根逆向求每个字符的赫夫曼编码****HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char));//分配求编码的工作区间cd[n-1]='';//编码结束符for(i=1;i<=n;++