数据结构实验报告实验名称：哈夫曼树学生：袁普班级：2013211125班班序号：14号学号：2013210681 日期：2014年12月1.实验目的和容利用二叉树结构实现哈夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印哈夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

7、可采用二进制编码方式（选作）测试数据：I love data Structure, I love Computer。

I will try my best to study dataStructure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。

2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码2. 程序分析2.1 存储结构用struct结构类型来实现存储树的结点类型struct HNode{int weight; //权值int parent; //父节点int lchild; //左孩子int rchild; //右孩子};struct HCode //实现编码的结构类型{char data; //被编码的字符char code[100]; //字符对应的哈夫曼编码};2.2 程序流程2.3 关键算法分析算法1：void Huffman::Count()[1] 算法功能：对出现字符的和出现字符的统计，构建权值结点，初始化编码表[2] 算法基本思想：对输入字符一个一个的统计，并统计出现次数，构建权值数组，[3] 算法空间、时间复杂度分析：空间复杂度O（1），要遍历一遍字符串，时间复[4] 代码逻辑：leaf=0; //初始化叶子节点个数int i,j=0;int s[128]={0}; 用于存储出现的字符for(i=0;str[i]!='\0';i++) 遍历输入的字符串s[(int)str[i]]++; 统计每个字符出现次数for(i=0;i<128;i++)if(s[i]!=0){data[j]=(char)i; 给编码表的字符赋值weight[j]=s[i]; 构建权值数组j++;}leaf=j; //叶子节点个数即字符个数for(i=0;i<leaf;i++)cout<<data[i]<<"的权值为："<<weight[i]<<endl;算法2：void Init();[1] 算法功能：构建哈弗曼树[2] 算法基本思想：根据哈夫曼树构建要求，选取权值最小的两个结点结合，新结点加入数组，再继续选取最小的两个结点继续构建。

[3] 算法空间、时间复杂度分析：取决于叶子节点个数，时间复杂度O（n），空间[4] 代码逻辑HTree=new HNode[2*leaf-1]; n2=n0-1，一共需要2n-1个结点空间for(int i=0;i<leaf;i++){HTree[i].weight=weight[i]; 给每个结点附权值HTree[i].lchild=-1; 初始化左右孩子和父节点，都为-1HTree[i].rchild=-1;HTree[i].parent=-1;}int x,y; //用于记录两个最小权值for(int i=leaf;i<2*leaf-1;i++){Selectmin(HTree,i,x,y); 选出两个最小权值的结点HTree[x].parent=i; 父节点设置为新建立的结点HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight; 父节点权值为两个相加HTree[i].lchild=x; 使父节点指向这两个孩子结点HTree[i].rchild=y;HTree[i].parent=-1; 父节点的父节点设为-1}算法3：void Selectmin(HNode*hTree,int n,int&i1,int &i2);[1] 算法功能：从现有的结点中选择出两个最小的结点，返回其位置[2] 算法基本思想：先选出两个没有构建的结点，然后向后依次比较，筛选出最小的两个结点[3] 算法空间、时间复杂度分析：空间复杂度O(1)，要遍历所有结点，时间复杂度O(N)[4] 代码逻辑int i;for(i=0;i<n;i++) //n为现在有的结点个数，是个变化值,会有相加后的新权值加入{if(hTree[i].parent==-1) //父节点不是-1意味着这个结点还没有被选择过{i1=i; 记录结点位置break;}}i++; //执行一遍for循环就加1，意为下次查找从当前位置开始查找for(;i<n;i++){if(hTree[i].parent==-1){i2=i; 记录第二个没选择过的结点编号break;}}if(hTree[i1].weight>hTree[i2].weight) 进行比较，使I1为最小的，I2为第二小的{int j=0;j=i2;i2=i1;i1=j;}i++;for(;i<n;i++) 将I1 I2 与后面的结点进行比较{if(hTree[i].parent==-1&&hTree[i].weight<hTree[i1].weight) 如果结点小于I1 {i2=i1; 使I2=I1 I1=新结点i1=i;}else if(hTree[i].parent==-1&&hTree[i].weight<hTree[i2].weight){ I1《新结点《I2，使I2为新节点i2=i;}}算法4：void CreateT able();[1] 算法功能：对出现的字符进行编码[2] 算法基本思想：根据字符在哈夫曼树中的位置，从下到上编码，是左孩子编0，右孩子编1[3] 算法空间、时间复杂度分析：空间复杂度O(1)，要遍历data数组，时间复杂度0(N)[4] 代码逻辑HCodeTable=new HCode[leaf]; 新建编码结点，个数为叶子节点个数for(int i=0;i<leaf;i++){HCodeT able[i].data=data[i];int child=i; 初始化要编码的结点的位置int parent=HTree[i].parent; 初始化父结点int k=0; //统计编码个数while(parent!=-1){if(child==HTree[parent].lchild)HCodeT able[i].code[k]='0'; //左孩子标‘0’elseHCodeTable[i].code[k]='1'; //右孩子标‘1’k++;child=parent; 孩子结点上移parent=HTree[child].parent; 父节点也上移}HCodeT able[i].code[k]='\0'; //将编码反向char code[100];for(int u=0;u<k;u++)code[u]=HCodeTable[i].code[k-u-1];for(int u=0;u<k;u++)HCodeTable[i].code[u]=code[u];cout<<data[i]<<"的哈夫曼编码为：";cout<<HCodeT able[i].code<<endl;length3[i]=k; //每一个字符编码的长度，为求编码总长度做准备}算法5：void Encoding();[1] 算法功能：对输入的字符串进行编码[2] 算法基本思想：找到每个字符对应的编码，将编码按顺序输出[3] 算法空间、时间复杂度分析：空间复杂度O(1),时间复杂度0（n）[4] 代码逻辑cout<<endl<<"输入的字符串转化为哈夫曼编码为:"<<endl;for (int i=0;str[i]!='\0';i++) 遍历输入的每一个字符{for(int j=0;j<leaf;j++)if(str[i]==HCodeT able[j].data) 找到字符对应的编码{ s1=s1+HCodeTable[j].code; 将所有编码按顺序加起来cout<<HCodeT able[j].code; 输出编码}}cout<<endl;算法6：void Decoding();[1] 算法功能：对编码串进行解码[2] 算法基本思想：找到每段编码对应的字符，输出字符[3] 算法空间、时间复杂度分析：时间复杂度0(N)，空间复杂度0（1）[4] 代码逻辑（可用伪代码描述）cout<<"解码后的字符串为: "<<endl;char *s = const_cast<char*>(s1.c_str()); 将编码字符串转化为char while(*s!='\0'){int parent=2*leaf-2; 父节点为最后一个节点while(HTree[parent].lchild!=-1) //还有左子树，不可能是叶子节点{if(*s=='0') 编码为0，为左孩子parent=HTree[parent].lchild;elseparent=HTree[parent].rchild; 编码为1，为右孩子s++;}cout<<HCodeTable[parent].data; 输出字符}cout<<endl;……注意分析程序的时间复杂度、存申请和释放，以及算法思想的体现。

2.4 其他在此次试验中使用了类和STL中的string，使用string可以方便的将单个字符的编码加起来成为总的编码后的数值，再利用STL中的转化函数可以直接将string转化为char，方便进行解码工作。

总而言之，使用STL使得编码大大的简洁了。