数据结构+哈夫曼编码+实验报告.doc

1、实验报告一、 实验目的掌握哈夫曼树及其应用。二、 实验内容利用哈夫曼算法，构造最优二叉树，然后对构造好的二叉树的叶子结点进行前缀编码。三、 实验步骤（1）审清题意，分析并理出解决问题的基本思路。（2） 根据基本思路，设计好程序的算法。 （3）根据算法编写源程序。（4） 在计算机上编译程序，检验程序的可运行性数据结构设计：/ 赫夫曼树和赫夫曼编码的存储结构 typedef struct / 结点的结构，在教科书第147页 unsigned int weight; / 结点的权值 unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; / 动

2、态分配数组存储赫夫曼树 typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码表void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) / 算法6.12 / w存放n个字符的权值(均0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC int start; unsigned f; / 以下是从叶子到根逆向求每个字符的赫夫曼编码 int m,i,s1,s2; unsigned c; HuffmanTree p; char *cd; if(n=1) / 叶子结点数不大于n return; m=

3、2*n-1; / n个叶子结点的赫夫曼树共有m个结点 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1;i=n;+i,+p,+w) / 从1号单元开始到n号单元，给叶子结点赋值 / p的初值指向1号单元 (*p).weight=*w; / 赋权值 (*p).parent=0; / 双亲域为空(是根结点) (*p).lchild=0; / 左右孩子为空(是叶子结点，即单结点树) (*p).rchild=0; for(;i=m;+i,+p) / i从n+1到m (*p).parent=0; / 其余结点的双亲域初

4、值为0 for(i=n+1;i=m;+i) / 建赫夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; / i号单元是s1和s2的双亲 HTi.lchild=s1; / i号单元的左右孩子分别是s1和s2 HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; / i号单元的权值是s1和s2的权值之和 HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配n个字符

5、编码的头指针向量(0不用) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1=0; / 编码结束符 for(i=1;i=n;i+) / 逐个字符求赫夫曼编码 start=n-1; / 编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 从叶子到根逆向求编码 if(HTf.lchild=c) / c是其双亲的左孩子 cd-start=0; / 由叶子向根赋值0 else / c是其双亲的右孩子 cd-start=1; / 由叶子向根赋值1 HCi=(char*)malloc(n-star

6、t)*sizeof(char); / 为第i个字符编码分配空间 strcpy(HCi,&cdstart); / 从cd复制编码(串)到HC free(cd); / 释放工作空间 源代码：#include / 字符串函数头文件 #include / 字符函数头文件 #include / malloc()等 #include / INT_MAX等 #include / 标准输入输出头文件，包括EOF(=Z或F6)，NULL等 #include / atoi()，exit() #include / eof() #include / 数学函数头文件，包括floor()，ceil()，abs()等 #i

7、nclude / ftime() #include / 提供宏va_start，va_arg和va_end，用于存取变长参数表 / 函数结果状态代码。在教科书第10页 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int Status; / Status是函数的类型，其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型，其值是TRUE或FALSE，第7、8章用到 / 赫夫曼树和赫夫曼编码的存储结构 typedef struct / 结点的结构，在教科书第

8、147页 unsigned int weight; / 结点的权值 unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; / 动态分配数组存储赫夫曼树 typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码表 int min(HuffmanTree t,int i) / 返回赫夫曼树t的前i个结点中权值最小的树的根结点序号，函数select()调用 int j,m; unsigned int k; / k存最小权值，初值取为不小于可能的值(无符号整型最大值) for(j=1;js2) / s1的序号大于s2

9、的 / 交换 j=s1; s1=s2; / s1是权值最小的2个中序号较小的 s2=j; / s2是权值最小的2个中序号较小的 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) / 算法6.12 / w存放n个字符的权值(均0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC int start; unsigned f; / 以下是从叶子到根逆向求每个字符的赫夫曼编码 int m,i,s1,s2; unsigned c; HuffmanTree p; char *cd; if(n=1) / 叶子结点数不大于n r

10、eturn; m=2*n-1; / n个叶子结点的赫夫曼树共有m个结点 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1;i=n;+i,+p,+w) / 从1号单元开始到n号单元，给叶子结点赋值 / p的初值指向1号单元 (*p).weight=*w; / 赋权值 (*p).parent=0; / 双亲域为空(是根结点) (*p).lchild=0; / 左右孩子为空(是叶子结点，即单结点树) (*p).rchild=0; for(;i=m;+i,+p) / i从n+1到m (*p).parent=0; /

11、其余结点的双亲域初值为0 for(i=n+1;i=m;+i) / 建赫夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; / i号单元是s1和s2的双亲 HTi.lchild=s1; / i号单元的左右孩子分别是s1和s2 HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; / i号单元的权值是s1和s2的权值之和 HC=(HuffmanCode)malloc(n+1)*sizeof(char*);

12、 / 分配n个字符编码的头指针向量(0不用) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1=0; / 编码结束符 for(i=1;i1)：); scanf(%d,&n); w=(int*)malloc(n*sizeof(int); / 动态生成存放n个权值的空间 printf(请依次输入%d个权值(整型)：n,n); for(i=0;i=n-1;i+) scanf(%d,w+i); / 依次输入权值 HuffmanCoding(HT,HC,w,n); / 根据w所存的n个权值构造赫夫曼树HT，n个赫夫曼编码存于HC for(i=1;i=n;i+) puts(HCi); / 依次输出赫夫曼编码 程序调试结果：四、 体会和总结在给出算法后要实现哈夫曼编码程序主要解决的就是算法中的select函数，该函数实现那么整个程序就很快能完成。Select函数中需要比较所有输入权值的大小，取最小两个组合。已经选取的权值必须做标记，否则程序将出错。