哈夫曼树实验报告.doc

《哈夫曼树实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、子及双亲指针}HTNode;//树中结点类型typedefHTNodeHuffmanTree[m+1];//0号单元不用主要实现函数：n统计字符串中字符的种类以及各类字符的个数的函数n构造Huffman树的函数nHuffman编码的函数n建立正文的编码文件的函数n代码文件的译码函数n主函数四、实验概要设计1)功能框图Huffman树的建立从叶子到根逆向求编码退出Huffman编码程序Huffman编码的生成编码文件的译码五.使用说明　1.运行环境：VC++6.02.首先选择主控菜单中的操作１，即建表，然后进行其它操作．六．实验截图七实验体会1、构建哈夫曼树的关键在于找最小树；在F中选择两棵根

3、结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。2、由于学习的不足没有实现编码文件的译码，今后会加以改进(╯﹏╰）3、在逆向求编码的for循环里犯了一个逻辑错误导致求出来的3、4位编码串行，尝试了多钟数据输入才找到原因所在，并加以改正，编写程序需一步一步的去调试并找到错误所在。附源程序： #include#include#include#includetypedefstruct{chardata;//结点字符intweight;//结点权值intparen

4、t,lchild,rchild;//父子结点}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreeHT,intm,int&s1,int&s2){inti;s1=s2=1;for(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

5、;break;}}for(i=i+1;i<=m;i++){if(HT[i].parent==0&&HT[i].weight

6、;for(p=HT+1,i=1;i<=n;++i,++p,++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].rchild=s2;HT[i].weight

7、=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;++i)//逐个字符