北邮数据结构实验三-哈夫曼树

数据结构实验报告实验名称：实验三——树学生姓名：班级：班内序号：学号：日期：1实验目的通过选择下面两个题目之一进行实现，掌握如下内容：掌握二叉树基本操作的实现方法了解哈夫曼树的思想和相关概念学习使用二叉树解决实际问题的能力实验内容：利用二叉树结构实现哈夫曼编/解码器。基本要求：初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。打印(Print)：以直观的方式打印哈夫曼树（选作）计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。(选作)可采用二进制编码方式（选作）测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.2程序分析2.1存储结构：三叉树：classHuffman{private: HNode*HTree;//哈夫曼树结点 HCode*HCodeTable;//哈夫曼编码表 charb[1000];//记录所有输入内容被编码后的结果 charc[127];charletter[1000];//输入内容的保存 voidSelectMin(int&x,int&y,intk);//求最小权重的字符 node*count;//计算各个字符出现次数 intn;//输入字符的种类（个数） intl;public:Huffman(); voidCreateHTree();//创建哈夫曼树 voidCreateCodeTable();//创建哈夫曼编码表 voidEncode();//编码 voidDecode();//解码};结点结构为如下所示：三叉树的节点结构：structHNode//哈夫曼树结点的结构体{intweight;//结点权值 intparent;//双亲指针 intlchild;//左孩子指针 intrchild;//右孩子指针 chardata;//字符};示意图为：intweightintparentintlchildintrchildchardata编码表节点结构：structHCode//编码表结构体{ chardata;//字符 charcode[100];//编码内容};示意图为：chardatacharcode[100]基本结构体记录字符和出现次数:structnode{ intnum; chardata;};示意图为:intnumchardata2.关键算法分析(1).初始化:伪代码：输入需要编译的文本内容将输入的内容保存到动态建立的node型数组count中统计出现的字符种类的数目,并且保存到private型变量nHuffman::Huffman()//将输入数据保存到Huffman类中{ l=0; n=0; count=newnode[127]; cout<<"请输入需要编译压缩的内容"<<endl; cin.getline(letter,200,'\n'); for(intj=0;j<127;j++)//一个号码代表一种字符 { count[j].num=0; } while(letter[l]!='\0')//在结束之前，每输入一个字符，则对应字符的数目则自增1 { ++count[letter[l]].num; count[letter[l]].data=letter[l]; ++l; } for(intk=0;k<127;k++) { if(count[k].num>0) {n++;}//在某个字符出现此书num不为0时，n自增1，最终n为出现的字符种类数目 }其时间复杂度为O(n)（2）.创建哈夫曼树（voidHuffmanTree::CreateCodeTable(Node*p)）算法伪代码：创建一个长度为2*n-1的三叉链表将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空从三叉链表的第n个结点开始，从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空根据哈夫曼树创建编码表源代码为：voidHuffman::CreateHTree(){ l=0; HTree=newHNode[2*n-1];//建立含有n种字符的哈夫曼树只需要2*n-1个结点即可 for(inti=0;i<n;i++) { while(count[l].num==0)//如果count内的权重为0，即该字符没有出现，则跳过，i自增继续寻找出现过的字符 {l++;} HTree[i].weight=count[l].num;//将count里统计的次数传入哈夫曼树的节点中，作为字符权重 HTree[i].lchild=-1; HTree[i].rchild=-1; HTree[i].parent=-1;//将左右孩子结点和父节点都置空 HTree[i].data=count[l].data;//将count内的有效字符传入哈夫曼树的结点 l++; } intx=-1,y=-1; for(inti=n;i<2*n-1;i++)//开始建立哈夫曼树 { SelectMin(x,y,i);//挑选三者中的权重较小的两个 HTree[x].parent=HTree[y].parent=i;//令较小的x、y为孩子节点，该两个结点的父节点是i HTree[i].weight=HTree[x].weight+HTree[y].weight;//i结点字符的权重赋为是左右孩子字符权重之和HTree[i].lchild=x;//左孩子为x HTree[i].rchild=y;//右孩子为y HTree[i].parent=-1;//父节点置空 x=-1; y=-1;//将x、y重新赋值为零，进行下一次比较建树｝其时间复杂度为：O(n)（3）．创建编码表算法伪代码：1.初始化编码表2.初始化一个指针，从链表的头结点开始，遍历整个链表2.1将链表中指针当前所指的结点包含的字符写入编码表中2.2得到该结点对应的哈夫曼树的叶子结点及其双亲2.3如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为02.4如果不止一个叶子结点，从当前叶子结点开始判断2.4.1如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否则为12.4.2child指针指向叶子结点的双亲，parent指针指向child指针的双亲，重复2.4.1的操作2.5将已完成的编码倒序2.6取得链表中的下一个字符3．输出编码表 源代码为：voidHuffman::CreateCodeTable()//建立哈夫曼编码表{ HCodeTable=newHCode[n];//建立动态编码表 for(inti=0;i<n;i++) { HCodeTable[i].data=HTree[i].data; intchild=i; intparent=HTree[i].parent; intk=0; while(parent!=-1) { if(child==HTree[parent].lchild)//判断该节点是父节点的左孩子或右孩子，左孩子则编码为0，右孩子则编码为1 HCodeTable[i].code[k]='0'; else HCodeTable[i].code[k]='1'; k++; child=parent;//将该节点的父节点作为新的孩子节点，继续进行编码输出 parent=HTree[child].parent; } HCodeTable[i].code[k]='\0';//code数组以\0结尾 Reverse(HCodeTable[i].code);//由于是从下到上输出，顺序是相反的，所以还需要逆置才能输出字符的编码值 } cout<<endl<<endl<<"每个字符的编码为："<<endl; for(inti=0;i<n;i++) { cout<<HCodeTable[i].data<<"："<<HCodeTable[i].code<<endl;//逐个输出对应的字符和其编码 }} }其时间复杂度为：O(n)（4）选择两个最小权值的函数voidHuffman::SelectMin(int&x,int&y,intk)算法伪代码：从下标为i=0的开始遍历。前两次将x，y赋值为序号最小的两个结点的地址序号。开始进行比较：进行如下分类对于任何不存在父节点的结点：若x权值<=y权值且i权值>=y权值，则无疑i权值最大，为输出x、y为权值较小的两个故而x，y值不便；其余情况皆为x、i的权值是较小的两个，令y赋值为i，则保证x、y权值是最小的两个。若y权值<=x权值且i权值>=x权值，则i权值是最大，x、y不变。其余情况皆为i、y权值最小，令x赋值为i，保证x、y序号结点的权值最小完成如上循环，直至i=k则推出循环，第k个结点在树的位置已经确定源代码为：voidHuffman::SelectMin(int&x,int&y,intk)//选出权值较小的两个字符结点{ inti=0; while(i<k) { while(i<k&&HTree[i].parent==-1)//若结点不具有父结点且满足i<k则进行如下循环，建立新子树 { if(x==-1) x=i; elseif(y==-1) y=i; else if(HTree[x].weight<=HTree[y].weight) { if(HTree[y].weight<=HTree[i].weight) {y=y;x=x;} else y=i; } else if(HTree[x].weight>HTree[y].weight) { if(HTree[i].weight>=HTree[x].weight) {x=x;y=y;} else x=i; } i++; } i++; }}其时间复杂度为O(n)（5）.将字符串倒序的函数（voidHuffmanTree::Reverse(char*pch)）算法伪代码：得到字符串的长度初始化两个记录下标的变量，一个为字符串开头字符所在的下标i，另一个为字符串结尾字符所在的下标j将下标为i和j的字符交换i++,j--源代码：voidReverse(chara[]){ charb[100]; inti=0,j=0; while(a[i]!='\0') { b[i]=a[i]; i++; } b[i]='\0'; i--; while(i>=0) { a[j]=b[i]; i--; j++; } a[j]='\0';}其时间复杂度为O(n)（6）.编码函数（voidHuffman::Encode(a[])）算法伪代码：1.从开头的字符开始，逐一对a中的字符进行编码2.在编码表中查找与当前字符对应的字符3．如果找到了与当前字符对应的编码表中的字符，将其编码追加到解码串的末尾。4.重复以上步骤，直到所有待编码串中的字符都编码完毕5.输出编码后的字符串voidHuffman::Encode()//编译输入内容为代码内容用0和1表示{ cout<<"编码结果为：";intk=0; for(inti=0;letter[i]!='\0';i++) { intj=0; while(HCodeTable[j].data!=letter[i])//编码表的字符等于输入内容的字符时进行下一个while循环 {j++;} intm=0;while(HCodeTable[j].code[m]!='\0')//输出该字符的编码 { b[k]=HCodeTable[j].code[m];//用数组b记录所有的编码数据，以备后续解码使用 k++; m++; } }b[k]='\0'; cout<<b; cout<<endl;}其时间复杂度为：O(n)（7）.解码函数（voidHuffman::Decode()）算法伪代码：得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针逐个读取待解码串中的字符，若为0，则指向哈夫曼树当前结点的指针指向当前结点的左孩子，若为1，则指向当前结点的右孩子指向待解码串的指针指向解码串中的下一个字符，直到指向哈夫曼树结点的指针的孩子结点为空如果