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

实验报告实验目的掌握哈夫曼树及其应用。实验内容利用哈夫曼算法，构造最优二叉树，然后对构造好的二叉树的叶子结点进行前缀编码。实验步骤（1）审清题意，分析并理出解决问题的基本思路。（2）根据基本思路，设计好程序的算法。（3）根据算法编写源程序。（4）在计算机上编译程序，检验程序的可运行性数据结构设计：//赫夫曼树和赫夫曼编码的存储结构typedefstruct//结点的结构，在教科书第147页{unsignedintweight;//结点的权值unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)//算法6.12{//w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HCintstart;unsignedf;//以下是从叶子到根逆向求每个字符的赫夫曼编码intm,i,s1,s2;unsignedc;HuffmanTreep;char*cd;if(n<=1)//叶子结点数不大于nreturn;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;//其余结点的双亲域初值为0for(i=n+1;i<=m;++i)//建赫夫曼树{//在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;//i号单元是s1和s2的双亲HT[i].lchild=s1;//i号单元的左右孩子分别是s1和s2HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//i号单元的权值是s1和s2的权值之和}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量([0]不用)cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间cd[n-1]='\0';//编码结束符for(i=1;i<=n;i++){//逐个字符求赫夫曼编码start=n-1;//编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c)//c是其双亲的左孩子cd[--start]='0';//由叶子向根赋值'0'else//c是其双亲的右孩子cd[--start]='1';//由叶子向根赋值'1'HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码(串)到HC}free(cd);//释放工作空间}源代码：#include<string.h>//字符串函数头文件#include<ctype.h>//字符函数头文件#include<malloc.h>//malloc()等#include<limits.h>//INT_MAX等#include<stdio.h>//标准输入输出头文件，包括EOF(=^Z或F6)，NULL等#include<stdlib.h>//atoi()，exit()#include<io.h>//eof()#include<math.h>//数学函数头文件，包括floor()，ceil()，abs()等#include<sys/timeb.h>//ftime()#include<stdarg.h>//提供宏va_start，va_arg和va_end，用于存取变长参数表//函数结果状态代码。在教科书第10页#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;//Status是函数的类型，其值是函数结果状态代码，如OK等typedefintBoolean;//Boolean是布尔类型，其值是TRUE或FALSE，第7、8章用到//赫夫曼树和赫夫曼编码的存储结构typedefstruct//结点的结构，在教科书第147页{unsignedintweight;//结点的权值unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表intmin(HuffmanTreet,inti){//返回赫夫曼树t的前i个结点中权值最小的树的根结点序号，函数select()调用intj,m;unsignedintk;//k存最小权值，初值取为不小于可能的值(无符号整型最大值)for(j=1;j<=i;j++)//对于前i个结点if(t[j].parent==0)//t[j]的权值小于k，又是树的根结点{k=t[j].weight;//t[j]的权值赋给km=j;//序号赋给m}t[m].parent=1;//给选中的根结点的双亲赋非零值，避免第2次查找该结点returnm;//返回权值最小的根结点的序号}voidselect(HuffmanTreet,inti,int&s1,int&s2){//在赫夫曼树t的前i个结点中选择2个权值最小的树的根结点序号，s1为其中序号(权值)较小的intj;s1=min(t,i);//权值最小的根结点序号s2=min(t,i);//权值第2小的根结点序号if(s1>s2)//s1的序号大于s2的{//交换j=s1;s1=s2;//s1是权值最小的2个中序号较小的s2=j;//s2是权值最小的2个中序号较小的}}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)//算法6.12{//w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HCintstart;unsignedf;//以下是从叶子到根逆向求每个字符的赫夫曼编码intm,i,s1,s2;unsignedc;HuffmanTreep;char*cd;if(n<=1)//叶子结点数不大于nreturn;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;//其余结点的双亲域初值为0for(i=n+1;i<=m;++i)//建赫夫曼树{//在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;//i号单元是s1和s2的双亲HT[i].lchild=s1;//i号单元的左右孩子分别是s1和s2HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//i号单元的权值是s1和s2的权值之和}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量([0]不用)cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间cd[n-1]='\0';//编码结束符for(i=1;i<=n;i++){//逐个字符求赫夫曼编码start=n-1;//编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c)//c是其双亲的左孩子cd[--start]='0';//由叶子向根赋值'0'else//c是其双亲的右孩子cd[--start]='1';//由叶子向根赋值'1'HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码(串)到HC}free(cd);//释放工作空间}voidmain(){HuffmanTreeHT;HuffmanCodeHC;int*w,n,i;printf("请输入权值的个数(>1)：");scanf("%d",&n);w=(int*)malloc(n*sizeof(int));//动态生成存放n个权值的空间printf("请依次输入%d个权值(整型)：\n",n);for(i=0;i<=n-1;i++)