北邮数据结构实验报告三题目2-哈夫曼树

北邮数据结构实验报告三题目2-哈夫曼树北京邮电大学电信工程学院第1页1．实验要求利用二叉树结构实现哈夫曼编/解码器(1).初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。(2).建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。(3).编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。(4).译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。(5).打印：以直观的方式打印哈夫曼树。(6).计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。(7).用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2.程序分析2.1存储结构二叉树：示意图：rootParentlchildrchild北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第1页。2.2程序流程函数HTree建立哈夫曼树北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第1页。函数HTree建立哈夫曼树函数List统计字符权值建立单链表SelectMin()选最小值CreatTable（）建立码表，并将信息存在链表Reverse（）将字符串倒置编码解码打印打印计算比较压缩结果控制函数2.3关键算法分析1.定义哈夫曼树的模板类#include<iostream>#include<string.h>usingnamespacestd;structLNode //链表的节点,用来统计字符频率，并编码{ charch; //字符 intweight; //权值 charcode[20]; //字符编码 LNode*next; //指向下一个节点};structTNode //哈弗曼树结点的结构体{ intweight;//结点权值 intLchild;//左孩子指针 intRchild;//右孩子指针 intParent;//双亲指针};classHuffman北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第2页。{北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第2页。public: Huffman(); //构造函数，输入、统计字符，创建哈弗曼树、码表 ~Huffman(); //释放链表空间、哈弗曼树的节点 voidCreateTable(); //建立编码表，并将信息存入链表 voidPrintTable(); //输出码表 voidEncoding(); //哈弗曼编码 voidDecoding(); //译码 voidComrate(); //计算编码的压缩率 voidSelectMin(int&x,int&y,intbegin,intend); //选取权值最小的两个数，创建哈弗曼树 voidreverse(charch[]); //将码值倒置，用来编码 voidcontrol(); //对菜单交互等提示操作private: TNode*troot; LNode*lroot; //在统计字符频率是构建链表的根节点 voidList(chara[]); //统计字符的权值建立的单链表 voidHTree(); //哈弗曼树建立 intLetter; //共有不同字符总数 charastr[1000]; //用户输入的一串字符 charbstr[1000]; //将字符串的码值保存};Huffman::Huffman(){ lroot=newLNode; bstr[0]='\0'; lroot->next=NULL; Letter=0; //初始化字符总数为1 cout<<"请输入一串字符，以回车键结束"<<endl; cin.getline(astr,1000,'\n'); if(strlen(astr)==0)throw1; else { List(astr); //用链表存储每个字符 HTree(); CreateTable(); Encoding(); }};Huffman::~Huffman(){ deletetroot; LNode*p=lroot;北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第3页。 while(p=lroot->next)北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第3页。 { lroot=p->next; deletep; p=lroot; } deletep;};2.建立哈夫曼树voidHuffman::HTree(){ LNode*p=lroot; inta=0; troot=newTNode[2*Letter-1];//2n-1个结点 while(p=p->next) //建立叶子节点 { troot[a].weight=p->weight; troot[a].Parent=-1; troot[a].Lchild=-1; troot[a].Rchild=-1; a++; }; for(inti=Letter;i<2*Letter-1;i++) troot[i].Parent=-1; intx,y,begin=0; //是两个最小值的角标 for(intj=Letter;j<2*Letter-1;j++)北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第4页。 {北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第4页。 while(troot[begin].Parent!=-1) begin++; SelectMin(x,y,begin,j); troot[j].weight=troot[x].weight+troot[y].weight; troot[j].Lchild=x; troot[j].Rchild=y; troot[j].Parent=-1; troot[x].Parent=j; troot[y].Parent=j; } };3.统计字符的频率voidHuffman::List(chara[]){ LNode*p=lroot; inti=0; while(a[i]!='\0') { while(p&&p->ch!=a[i]) //查找链表中没有该字符或者找到该字符 p=p->next; if(!p) //如果没有该字符，创建节点。北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第5页。 {北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第5页。 p=newLNode; p->ch=a[i]; p->weight=1; p->next=lroot->next; lroot->next=p; Letter++; } else p->weight++; i++; p=lroot->next; };};4.选最小值voidHuffman::SelectMin(int&x,int&y,intbegin,intend){ intt1,b,t2; //分别表示临时最小值、对应角标、从b开始比较 t1=troot[begin].weight,b=t2=begin; for(;b<end;b++) { if(troot[b].weight<t1&&troot[b].Parent==-1)北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第6页。 {北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第6页。 t1=troot[b].weight; t2=b; } } x=t2; troot[x].Parent=100; //临时为该最小的双亲赋值，防止再次被找出 if(t2!=begin) //判断最小是否是第一个 b=begin; else { b=begin; while(troot[++b].Parent!=-1); } t1=troot[b].weight;t2=b; for(;b<end;b++) { if(troot[b].weight<t1&&troot[b].Parent==-1) { t1=troot[b].weight; t2=b; }北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第7页。 }北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第7页。 y=t2;};5.倒置字符串voidHuffman::reverse(charch[]){ for(inti=0;i<strlen(ch)/2;i++) { chartemp=ch[i]; ch[i]=ch[strlen(ch)-i-1]; ch[strlen(ch)-i-1]=temp; }}6.建立码表，并将信息存在链表voidHuffman::CreateTable(){ LNode*p=lroot; inti=0,j,k; //将letter个字符都编码，与p相对应 while(p=p->next) { j=i,k=0; while(troot[j].Parent!=-1) { if(troot[troot[j].Parent].Lchild==j) p->code[k++]='0'; else p->code[k++]='1'; j=troot[j].Parent; } p->code[k]='\0'; reverse(p->code);北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第8页。 i++;北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第8页。 }}7.打印码表和编码结果voidHuffman::PrintTable(){ LNode*p=lroot; cout<<"字符:频率:编码:\n"; while(p=p->next) { cout<<p->ch<<"\t"<<p->weight<<"\t"<<p->code<<endl; }; cout<<"原字符编码结果为："<<bstr<<endl;}8.编码voidHuffman::Encoding(){ intk=0; //输入字符串的脚标 LNode*p; while(astr[k]!='\0') //所有字符编码完为止 { p=lroot; while((p=p->next)->ch!=astr[k]) ; //找到字符的码值为止 strcat(bstr,p->code); k++; }}9.解码voidHuffman::Decoding(){ cout<<"对码值"<<bstr<<"进行解码……"<<endl; cout<<"编码结果为：\t"; intk=0,parent=2*Letter-2; while(bstr[k]!='\0') //码值读取结束 { if(bstr[k]=='0') parent=troot[parent].Lchild; else parent=troot[parent].Rchild; if(troot[parent].Lchild==-1) { LNode*p=lroot; for(inti=0;i<parent+1;i++) p=p->next;北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第9页。 cout<<p->ch;北邮数据结构实验报告三题目2-哈夫曼树全文共13页，当前为第9页。 parent=2*Letter-2; } k++; } cout<<endl;}10.计算压缩结果voidHuffman::Comrate(){ cout<<"编码前大小:"<<strlen(astr)*8<<"bit\n"; cout<<"编码后大小:"<<strlen(bstr)<<"bit\n"; cout<<"压缩率为:"<<100*float(strlen(bstr))/strlen(astr)/8<<"%"<<endl;}11.控制voidHuffman::control() { intm; while(1) { cout<<"请选择执行功能:\n"; cout<<"1.打印编码表\n2.原始数据解码\n3.数据大小及压缩率\n4.结束\n\n"; cin>>m; switch(m) { case1: { cout<<"打印编码表\n"; PrintTable(); break; } case2: { cout<<"原始数据解码\