哈夫曼树编码实验报告.doc

哈夫曼树编码实验报告姓名：沈雅丽 班级：09092311 学号：09923102需求分析：构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。掌握树的有关操作算法。熟悉树的基本存储方法。学习利用树求解实际问题概要设计：ADT HuffmanTree数据对象：D=ai| aiCharSet,i=1,2,n, n0数据关系：R= ai-1, aiD, ai-1ai ,i=2，3，n构造哈夫曼树：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; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; 求哈弗曼编码：HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配n个字符编码的头指针向量(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) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(HCi,&cdstart); / 从cd复制编码(串)到HC详细设计：typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; / 动态分配数组存储赫夫曼树 typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码表/建立哈夫曼树 int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 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) / 建赫夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; 源代码：#include / malloc()等 #include / INT_MAX等 #include / EOF(=Z或F6),NULL#include / cout,cin typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; / 动态分配数组存储赫夫曼树 typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码表 int min(HuffmanTree t,int i) / 函数void select()调用 int j,flag; unsigned int k=UINT_MAX; / 取k为不小于可能的值 for(j=1;j=i;j+) if(tj.weights2) j=s1; s1=s2; s2=j; / 以上同algo6-1.cpp void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) / 前半部分为算法6.12 / w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 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) / 建赫夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配n个字符编码的头指针向量(0不用) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1=0; / 编码结束符 for(i=1;i1)：); 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+) puts(HCi); 运行结果及指示： 调试分析：1.深刻体会构建哈夫曼树的整个过程，对整体有个总的理解；2.复习以前所学C语言的一些语法，例如：for循环，if循环，while循环3.理解哈夫曼的编码过程，编码思想4.此程序的不足之处在于在进行哈夫曼编码时未能对字符进行编制，有待改进。5.基本上没有什么太大的问题，在调用select（）这个函数时，想把权值最小的两个结点的序号带回Hu