实验五哈夫曼树的建立、编码、解码

成绩实验五成绩实验题目：哈夫曼树的应用一、实验目的加深理解哈夫曼树的定义和特性；掌握哈夫曼树的存储结构与实现；掌握哈夫曼树的应用二、实验内容根据输入的权值信息建立哈夫曼树输出各个叶子结点所表示字符的哈夫曼编码对给定的密码串进行解码三、设计与编码1、基本思想2、编码#include<iostream.h>#include<string.h>constintMAX=20;structhuffnode{ intweight; intlchild,rchild,parent;};structhuffinit//输入的权值信息的结构{chardata;intweight;};structhuffcode//哈夫曼树编码的结构{chardata;charcode[MAX+1];};classHuffTree//哈夫曼树类的声明{public:HuffTree(huffinitw[],intn);~HuffTree(){}voidSelect(int&min1,int&min2,intm);voidOutput();//输出哈夫曼树最终状态（tree数组）voidEncode();//编码voidDecode(charcode[]);//解码private:huffnodetree[2*MAX-1];//存储哈夫曼树huffcodecd[MAX];//存储各个哈夫曼编码intsize;//哈夫曼树的叶子结点数};HuffTree::HuffTree(huffinitw[],intn){size=n; for(inti=0;i<2*n-1;i++) { tree[i].parent=-1; tree[i].lchild=-1; tree[i].rchild=-1; } for(i=0;i<n;i++) {tree[i].weight=w[i].weight; cd[i].data=w[i].data;} intmin1=-1; intmin2=-1; intm=size; for(intk=n;k<2*n-1;k++) { Select(min1,min2,m); tree[min1].parent=k; tree[min2].parent=k; tree[k].weight=tree[min1].weight+tree[min2].weight; tree[k].lchild=min1; tree[k].rchild=min2; m++; }}voidHuffTree::Select(int&min1,int&min2,intm)//选择两个权值最小的结点{inta=100; intb=100; for(inti=0;i<m;i++) { if(tree[i].weight<a&&tree[i].parent==-1) { a=tree[i].weight; min1=i; } } for(i=0;i<m;i++) { if(tree[i].weight<b&&tree[i].parent==-1&&i!=min1) { b=tree[i].weight; min2=i; }}}voidHuffTree::Output(){ for(inti=0;i<2*size-1;i++) { cout<<tree[i].weight<<""<<tree[i].parent<<""<<tree[i].lchild<<""<<tree[i].rchild<<endl; }}voidHuffTree::Encode()//编码{intm;inta;intj;charb[100];intk;for(inti=0;i<size;i++) {m=i;j=0; while(tree[m].parent!=-1) { a=m;m=tree[m].parent; if(tree[m].lchild==a) b[j++]='0'; else b[j++]='1'; }for(k=0,j=j-1;j>=0;j--)cd[i].code[k++]=b[j];cd[i].code[k]='\0';cout<<cd[i].data<<"--->"<<cd[i].code<<endl;;} }voidHuffTree::Decode(charcode[])//解码{intn=strlen(code);inta=2*size-2;//根节点的下标 for(inti=0;i<n;i++) { if(code[i]=='0') { a=tree[a].lchild; } if(code[i]=='1') a=tree[a].rchild;if(tree[a].lchild==-1&&tree[a].rchild==-1) {cout<<cd[a].data; a=2*size-2; } else if(code[i+1]=='\0') cout<<"error"; } cout<<endl;}voidmain(){huffinitw[20]; intn; chars[100]; cout<<"请输入字符个数："; cin>>n; for(inti=0;i<n;i++) { cout<<"请输入第"<<i+1<<"个字符及权值："; cin>>w[i].data; cin>>w[i].weight; }HuffTreeH(w,n); cout<<"已经建好的节点信息为"<<endl; H.Output(); cout<<"已经建好的节点编码信息为"<<endl; H.Encode(); charq;do { cout<<"请输入密