实验三哈夫曼树实验报告

..数据结构实验报告实验名称：实验三树学生姓名：班级：班内序号：学号：日期：2012年12月7号1、实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。..2、程序分析2.1存储结构（1）二叉树templateclassTclassBiTree{public:BiTree();//构造函数，其前序序列由键盘输入~BiTree(void);//析构函数BiNodeT*Getroot();//获得指向根结点的指针protected:BiNodeT*root;//指向根结点的头指针};//声明类BiTree及定义结构BiNodeData：二叉树是由一个根结点和两棵互不相交的左右子树构成。二叉树中的结点具有相同数据类型及层次关系。示意图：rootlchildparentrchild（2）静态三叉链表structHNode//哈夫曼树的静态三叉链表{unsignedintweight;//结点权值unsignedintparent;//双亲指针unsignedintLchild;//左孩子指针unsignedintRchild;//右孩子指针};示意图：(3)编码表的节点结构structHCode//字符及其编码结构{chardata;dataLchildRchildparent..charcode[100];};示意图：2.2关键算法分析一：关键算法(一)初始化函数voidHuffman::Init(inta[],intn)（1）算法自然语言1.创建一个长度为2*n-1的三叉链表2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空3.从三叉链表的第n个结点开始，i=n3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空4.根据哈夫曼树创建编码表（2）源代码voidHuffman::Init(inta[],intn)//创建哈夫曼树{//二叉树只有度为和度为的结点时，总结点数为（n-1）个HTree=newHNode[2*n-1];//根据权重数组a[1—n]初始化哈夫曼树inti,x,y;for(i=0;in;i++)//n个叶子结点{HTree[i].weight=a[i];HTree[i].Lchild=-1;HTree[i].Rchild=-1;HTree[i].parent=-1;}for(inti=n;i2*n-1;i++)//开始建哈夫曼树，从底层向顶层搭建{SelectMin(HTree,i,x,y);//从--(i-1)中选出两个权值最小的结点HTree[x].parent=i;HTree[y].parent=i;//左右孩子权值相加为父结点的权值HTree[i].weight=HTree[x].weight+HTree[y].weight;chardatacharcode[100]..HTree[i].Lchild=x;HTree[i].Rchild=y;HTree[i].parent=-1;}}(3)时间复杂度在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数的时间复杂度为O（n^2）（二）统计字符出现频度的代码（1）算法自然语言①用cin.getline（）函数获取一段字符串。同时设置一个权值数组weight，以及暂时统计和存放权值的数组s。②用strlen（）函数获取未编码时的字符串长度。③从字符串的起始位置进行权值统计，即获得str[i]每个字符的ASⅡ编码，并在s[(int)str[i]]数组中进行+1统计，为字符出现一次。④i进行自加，统计下面字符出现的频度，在相应的数组元素中进行+1统计。⑤继续循环，直到字符串结束。（2）源代码（在main（）函数中实现）inti,j=0,v;ints[200]={0};intweight[M];//权值数组cout请输入一段字符串，按回车键结束：endl;cin.getline(str,1000,'\n');//由用户输入一段字符串coutendl;Len1=strlen(str);//得到未编码时的字符串长度for(i=0;str[i]!='\0';i++)//统计每个字符的权值s[(int)str[i]]++;//(int)str[i]为每个字符的ASⅡ编码for(i=0;i200;i++)if(s[i]!=0)//如果权值不为{c[j]=i;//ASⅡ编码为i的字符写入字符数组cweight[j]=s[i];//权值s数组赋给权值weight数组j++;}n=j;//叶子结点个数for(v=0;vn;v++)//循环输出字符权值coutc[v]的权值为：weight[v]endl;(3)时间复杂度：若输入的字符串长度为n，则时间复杂度为O(n)..（三）选择两个最小权值的函数（1）算法自然语言①先暂时将前两个叶子结点作为权值最小的两个结点i1，i2②从第三个叶子结点开始，每一个结点的权值与i1，i2进行比较，如果此结点权值比i1权值要小，则将i1结点赋给i2，此结点赋给i1。③如果此结点权值比i2要小，此结点赋给i2。④每进行一次循环，总结点个数－1.（两个结点进行权值合并）⑤继续执行循环，直到循环到根结点，循环结束。（2）源代码voidHuffman::SelectMin(HNode*hTree,intn,int&i1,int&i2){inti,j;//找一个比较的起始值for(i=0;in;i++)//找i1{if(hTree[i].parent==-1){i1=i;break;}}i++;for(;in;i++)//找i2{//先让前两个叶子结点分别为i1，i2if(hTree[i].parent==-1){i2=i;break;}}if(hTree[i1].weighthTree[i2].weight)//i1指向最小的{j=i2;i2=i1;i1=j;}i++;for(;in;i++)//开始找最小的两个{..if(hTree[i].parent==-1&&hTree[i].weighthTree[i1].weight){//如果之后的叶子结点权值小于前两个，那么进行交换i2=i1;//把i1赋给i2i1=i;}elseif(hTree[i].parent==-1&&hTree[i].weighthTree[i2].weight){i2=i;//始终保证i2权值大于i1}}}（3）时间复杂度若输入的字符串长度为n，则时间复杂度为O(n)（四）创建编码表（1）算法自然语言1.生成一个编码表2.从终端结点开始，如果此结点是其父结点的左孩子，则标“0”；如果是其父结点的右孩子，则标“1”。3.将父结点赋给孩子结点，并将新的孩子结点的父结点作为当前父结点，重复2操作。4.继续循环，直到根结点，即不满足循环条件时，将编码表的最后一位置0.5.将编码字符逆置。将编码串的最后一位置换成新编码串的第一位，倒数第二位置换成新编码串的第二位，直到置换完毕。6.将新的编码串重新赋给编码表。7.输出字符的哈夫曼编码。8.循环将字符编码后的长度赋给Len3数组。（2）源代码voidHuffman::CreateTable(chardata[],intn){HCodeTable=newHCode[n];//生成编码表for(inti=0;in;i++){HCodeTable[i].data=data[i];intchild=i;intparent=HTree[i].parent;intk=0;//从终端结点开始编码，代表每个编码串的长度while(parent!=-1){if(child==HTree[parent].Lchild)..HCodeTable[i].code[k]='0';//左孩子标“0”elseHCodeTable[i].code[k]='1';//右孩子标“1”k++;child=parent;//向上追溯parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';//当编码到根结点时循环结束，编码串最后一位置表结束{//将编码字符逆置charcode[M];intu;for(u=0;uk;u++)code[u]=HCodeTable[i].code[k-u-1];//上述编码串的最后一位变成新的编码表中编码串的第一位for(u=0;uk;u++)HCodeTable[i].code[u]=code[u];//将新的编码串重新赋给编码表coutc[i]的哈夫曼编码为：;coutHCodeTable[i].codeendl;Len3[i]=k;//每个字符编码后的长度}}}（3）时间复杂度若输入的字符串长度为n，则时间复杂度为O(n)。（五）编码算法（1）算法自然语言1.从字符串的起始位置开始，将每个字符与编码表中的字符进行比对。2.当两字符相等时，输出编码表中字符对应的编码。3.将此字符编码的长度加到Len2中，循环结束后，Len2的数值为字符串编码后的总长度。（2）源代码voidHuffman::Encoding(intn)//编码{coutendl输入的字符串转化为哈夫曼编码为:endl;for(inti=0;str[i]!='\0';i++)//只要字符串不结束就执行循环{for(intj=0;jn;j++)if(str[i]==HCodeTable[j].data)//如果字符串中的字符与编码表中的字符相等{..coutHCodeTable[j].code;//输出编码表中字符对应的编码Len2+=Len3[j];//求编码后的字符总的编码长度，为了求压缩比}}coutendl;}（3）时间复杂度设待编码字符串长度为n，编码表中字符个数为m，则复杂度为O（n*m）。（六）解码算法（1）算法自然语言1.从根节点开始，如果编码串为0，则下溯到此结点的左孩子结点；如果编码串为1，则下溯到此结点的右孩子结点。2.执行循环，直到不满足while循环条件，即追溯到叶子结点。输出叶子结点的字符。（2）源代码voidHuffman::Decoding(char*p)//p为编码串{cout解码后的字符串为:endl;char*q=0;while(*p!='\0'){intparent=2*n-1-1;//根结点在哈夫曼树中的下标while(HTree[parent].Lchild!=-1)//如果不是叶子结点就执行循环{if(*p=='0')parent=HTree[parent].Lchild;elseif(*p=='1')parent=HTree[parent].Rchild;p++;}cou