/*2.2题目2——应用实验
利用二叉树结构实现哈夫曼编/解码器。
基本要求：
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 data Structure.
提示：
1、用户界面可以设计为“菜单”方式：能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的
字符一律不用编码。
3代码要求
1、必须要有异常处理，比如删除空链表时需要抛出异常；
2、保持良好的编程的风格：
?代码段与段之间要有空行和缩近
?标识符名称应该与其代表的意义一致
?函数名之前应该添加注释说明该函数的功能
?
关键代码应说明其功能
3、递归程序注意调用的过程，防止栈溢?
*/
#include<iostream>
#include<string>
#include<iomanip>
using namespace std;
//静态三叉链表，用于存储哈夫曼树
struct hnode
{
char ss;//结点代表的字符
int weight;//结点的权重
int parent;//双亲指针
int lchild;//左孩子指针
int rchild;//右孩子指针
};
//哈夫曼编码表
struct hcode
{
char data;//存储字符
char code[100];//存储字符编码
};
/
/huffman类
class huffman
{
private:
hnode *htree;//哈夫曼树动态数组的指针，huffman树
hcode *hcodetable;//哈夫曼树的编码数组指针,huffman编码表
int hn; //存储哈夫曼数组的大小
public:
void Init(char *s);//初始化哈夫曼树
void createhuffman();//创建哈夫曼树
void selectmin(int &x,int &y,int i);//寻权重最小的两个数
void createcodetable();//创建哈夫曼编码表
void reverse(char m[]);//逆置编码字符，颠倒
void encode(char *s,string *d);//编码
void decode(char *s,char *d);//解码
void printtable();//打印哈夫曼树
~huffman(){
delete[]htree;
delete[]hcodetable;
}//析构函数
};
//初始化
void huffman::Init(char *s)
{
int n=0;
while(*(s+n)!='\0')//统计字符串字符数
{
n++;
}
char *
m=new char[n];//动态字符数组存储字符串
for(int i=0;i<n;i++)
{
m[i]=*(s+i);
}
char temp;
for(int i=0;i<n-1;i++)//冒泡排序法排序
{
for(int j=0;j<n-1-i;j++)
{
if(m[j]>m[j+1])
{
temp=m[j];
m[j]=m[j+1];
m[j+1]=temp;
}
}
}
int k=1;
for(int i=1;i<n;i++)//统计不同的字符数的个数
{
if(m[i]!=m[i-1])
{
k++;
}
}
htree=new hnode[2*k-1];
hn=2*k-1;
int l=0;//统计不同字符出现的频度
k=0;//哈夫曼数组下标
temp=m[0];//标记？
for(int i=0;i<n;i++)
{
if(m[i]==temp)
{
l++;//统计出现次数
if(i==n-1)
htree[k].weight=l;
}
else
{
htree[k].weight=l;
htree[k].ss=temp;
temp=m[i];
k++;
l=1;
htree[k].ss=temp;
htree[k].weight=l;
}
}
delete[]m;//释放动态内存空间
createhuffman();//创建哈夫曼树
createcodetable();//创建哈夫曼编码表
}
//创建哈夫曼树
void huffman::createhuffman()
{
int n=(hn+1)/2;//n表示不同字符的个数
for(int i=0;i<n;i++)//初始化
{
htree[i].lchild=-1;
htree[i].rchild=-1;
htree[i].parent=-1;
}
int x,y;
for(int i=n;i<2*n-1;i++)
{
selectmin(x,y,i);//出权重最小的两个字符
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;
}
}
//寻权重最小的两个字符
void huffman::selectmin(int &x,int &y,int i)
{
x=0;
while(htree[x].parent!=-1)
{
x++;
}
for(int j=1;j<i;j++)
{
if(htree[j].parent!=-1)
{
continue;//如果是之前过的最小值，跳出本次循环
}
x=(htree[x].weight<=htree[j].weight)?x:j;
}
htree[x].parent=-2;//防止重复
y=0;
while(htree[y].parent!=-1)
{
y++;
}
for(int j=1;j<i;j++)
{
if(htree[j].parent!=-1)
{
continue;
}
y=(htree[y].weight<=htree[j].weight)?y:j;
}
}
//创建哈夫曼表
void huffman::createcodetabl
e()
{
int n=(hn+1)/2;
hcodetable=new hcode[n];//存储不同字符代表的编码
for(int i=0;i<n;i++)
{
hcodetable[i].data=htree[i].ss;//存储字符
int child=i;
int parent=htree[i].parent;
int k=0;
while(parent!=-1)//自下而上到达根节点之后结束循环
{
if(child==htree[parent].lchild)//左孩子编码'0'
hcodetable[i].code[k]='0';
else//右孩子编码'1'
hcodetable[i].code[k]='1';
k++;
child=parent;
parent=htree[child].parent;
}
hcodetable[i].code[k]='\0';//字符编码串最后添加结束符
reverse(hcodetable[i].code);//颠倒字符串
}
}
//颠倒字符串
void huffman::reverse(char m[])
{
int n=0;
char temp;
while(m[n+1]!='\0')
n++;
for(int i=0;i<=n/2;i++)
{
temp=m[i];
m[i]=m[n-i];
m[n-i]=temp;
}
}
//编码
void huffman::encode(char *s,string *d)
{
float sum=0;//统计字节数
int n=0;
while(*s!='\0')
{
for(int i=0;i<(hn+1)/2;i++)
{
if(*s==htree[i].ss)
{
for(int j=0;hcodetable[i].code[j]!='\0';j++)
{
*d+=hcodetable[i].code[j];
sum+=1;
}
s++;
n++;
break;
}
}
}
cout<<"编码前长度："<<8*n<<endl;
cout<<"编码后的长度："<<sum<<endl;
cout<<"压缩比为："<<8*n/sum<<endl;
}
//解码函数
void  huffman::decode(char *s,char *d)
{
while(*s!='\0')
{
int parent=hn-1;//根节点
while(htree[parent].lchild!=-1)//从根节点开始到终端节点结束循环
{
if(*s=='0')
parent=htree[parent].lchild;
else
parent=htree[parent].rchild;
if(*s=='\0')//不解码码串最尾部，无编码部分
{
cout<<endl<<"尾端无编码!"<<endl;
return;
}
s++;
}
*d=hcodetable[parent].data;
d++;
}
}
//打印哈夫曼树
void huffman::printtable()
{
cout<<se
tiosflags(ios::left)<<setw(5)<<"n"<<setw(12)<<"weight"<<setw(12)<<"lchild"<<
setw(12)<<"rchild"<<setw(12)<<"parent"<<setw(12)<<"char"<<setw(12)<<"code"<<endl;
for(int i=0;i<hn;i++)
{
if(i<(hn+1)/2)
{
cout<<setiosflags(ios::left)<<setw(5)<<i<<setw(12)<<htree[i].weight<<setw(12)<<htree[i].lchild<<
setw(12)<<htree[i].rchild<<setw(12)<<htree[i].parent<<setw(12)<<hcodetable[i].data<<setw(12)<<hcodetable[i].code<<endl;
}
else
{
cout<<setiosflags(ios::left)<<setw(5)<<i<<setw(12)<<htree[i].weight<<setw(12)<<htree[i].lchild<<
setw(12)<<htree[i].rchild<<setw(12)<<htree[i].parent<<setw(12)<<"无"<<setw(12)<<"无"<<endl;
}                     
}
}
//主函数
int main()
{
char m;
char *ce="I love data Structure.I love Computer.I will try my best to study data Structure.";//测试数据
cout<<"************菜单************"<<endl;
cout<<"请选择：a.测试；"<<endl;
cout<<"        b.进入交互界面。"<<endl;
cin>>m;
while(m!='\n')
{
if(m=='a')//测试
{
cout<<"测试数据为：I love data Structure,I love Computer.I will try my best to study data Structure."<<endl;
huffman h1;
h1.Init(ce);
cout<<"打印哈夫曼表："<<endl;
h1.printtable();
string s1="";
cout<<"编码后的字符串："<<endl;
cout<<s1<<endl;
int s1count=s1.length();
char str1[10000]={'\0'};
char *sce=&str1[0];
char hce[10000]={'\0'};
char *dce=&hce[0];
h1.decode(sce,dce);
cout<<"解码后的字符串："<<endl;
cout<<dce<<endl;
cout<<"请选择：a.测试；"<<endl;
cout<<"        b.进入交互界面。"<<endl;
cin>>m;
}
else
{
if(m=='b')//交互，由用户输入数据
{ 
cout<<"*******************************"<<endl;
cout<<"进入交互界面！"<<endl;                 
cout<<"请输入字符串："<<endl;
char q;
<(q);
char str[1000]={'\0'};
char *s=&str[0];
char c;//输入的单个字符
int i=0;
bool flag=0;//判断不同字符的个数是否大于等于2
(c))
{
if(c=='\n')
字符串长度统计{
if(i==
1||i==0)
{
cout<<"输入不符合要求！请重新输入："<<endl;
i=0;
continue;
}
break;
}
str[i]=c;
i++;
}
huffman h2;//创建哈夫曼树
h2.Init(s);//初始化
cout<<"*******************************"<<endl;
cout<<"请选择操作："<<endl;
cout<<"1.打印哈夫曼树"<<endl;
cout<<"2.编码"<<endl;
cout<<"3.解码"<<endl;
cout<<"4.退出"<<endl;
int n;
while(cin>>n)
{
<(c);
switch(n)
{
case 1:
h2.printtable();
break;
case 2:
{
string sl="";
cout<<"编码后的字符串："<<sl<<endl;
}
break;
case 3:
{
cout<<"请输入要解码的字符串："<<endl;
char str1[1000]={'\0'};
s=&str1[0];
cin>>str1;
char hl[1000]={'\0'};
char *dl=&hl[0];
h2.decode(s,dl);
cout<<"解码后的字符串："<<dl<<endl;
}
break;
case 4:
cout<<"退出成功！"<<endl;
break;
default:
cout<<"请输入正确序号！"<<endl;
break;
}
if(n!=4)
{
cout<<"*******************************"<<endl;
cout<<"请选择操作："<<endl;
cout<<"1.打印哈夫曼树"<<endl;
cout<<"2.编码"<<endl;
cout<<"3.解码"<<endl;
cout<<"4.退出"<<endl;
}
}
if(n==4)
break;//退出菜单
}
else
{
cout<<"输入错误！"<<endl;
cout<<"*******************************"<<endl;
cout<<"请选择：a.测试；"<<endl;
cout<<"        b.进入交互界面。"<<endl;
cin>>m;
}
}
}
system("pause");
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。