哈夫曼树实验报告.doc

《哈夫曼树实验报告.doc》由会员分享，可在线阅读，更多相关《哈夫曼树实验报告.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、d , rchild , parent; /左右孩子及双亲指针HTNode; /树中结点类型typedef HTNode HuffmanTreem+1; /0 号单元不用主要实现函数：n 统计字符串中字符的种类以及各类字符的个数的函数n 构造Huffman 树的函数n Huffman 编码的函数n 建立正文的编码文件的函数n 代码文件的译码函数n 主函数四、实验概要设计1)功能框图Huffman 树的建立Huffman从叶子到根逆向求编码编码程序Huffman 编码的生成编码文件的译码退出五. 使用说明1.运行环境：VC+ 6.02.首先选择主控菜单中的操作，即建表，然后进行其它操作六实验截图

3、七 实验体会1、构建哈夫曼树的关键在于找最小树；在 F 中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。2、由于学习的不足没有实现编码文件的译码，今后会加以改进 (）3、在逆向求编码的 for 循环里犯了一个逻辑错误导致求出来的 3、4 位编码串行，尝试了多钟数据输入才找到原因所在，并加以改正，编写程序需一步一步的去调试并找到错误所在。附源程序：#include#include#include#includetypedef structchar data; /结点字符int weight; /结点权值int parent,

4、lchild,rchild; /父子结点HTNode,* HuffmanTree;typedef char * *HuffmanCode;void Select(HuffmanTree HT, int m, int& s1, int& s2)int i;s1 = s2 = 1;for(i=1; i=m; i+)if (HTi.parent=0)s1=i;break;for(i=i+1; iHTi.weight)s1=i;for(i=1; i=m; i+)if(HTi.parent=0&i!=s1)s2=i;break;for(i=i+1; i=m; i+)if(HTi.parent=0 & H

5、Ti.weightHTs2.weight & i!=s1)s2=i;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) /w 存放 n 个字符的权值，构造赫夫曼树 HT，并求出 n 个字符的赫夫曼树编码 HCint f;int m,i,s1,s2;int c;HuffmanTree p;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,+w)(*p).weight=*

6、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) /建立赫夫曼树 /在 HT1.i-1选择 parent 为 0 且 weight 最小的两个节点，其序号分别为 s1,s2.Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/*从叶子到根逆向求每个字符的赫夫曼编码*HC=(HuffmanCo

7、de)malloc(n+1)*sizeof(char*);/分配 n 个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char); /分配求编码的工作区间cdn-1=0; /编码结束符for(i=1;i=n;+i) /逐个字符求赫夫曼树编码 int start;start=n-1; /编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char

8、); /为第 i 个字符编码分配空间strcpy(HCi,&cdstart); /从 cd 复制编码（串）到 HCfree(cd); /释放空间void main()HuffmanTree HT;HuffmanCode HC;int *w,n,i;printf(请输入权值的个数(): );scanf (%d,&n);w=(int *)malloc(n*sizeof(int);printf(请依次输入%d 个权值(整型):n,n);for(i=0;i=n-1;i+)scanf (%d,w+i);HuffmanCoding(HT,HC,w,n);for(i=1;i=n;i+)printf(对应的编码为：);puts(HCi);