fano_coding.cpp

费诺编码

#include <iostream.h>
#include <math.h>
#include<string.h>
//
class DATA//数据类,采用双向表
{
public://初始化PXi=1是为了在排序迭代时方便
	DATA()
	{
		next=NULL;
		qian=NULL;
		r=NULL;
		PXi=1;
		for(int i=0;i<11;i++)
		{
			key[i]='\0';
		}
	}
	char Xi;//信源符号
	double PXi;//信源概率
	char key[11];//码字
	DATA *next,*qian,*r;//地址
};

class info
{
public:
	double length;
	double then;
	info(){length=0;then=0;};
};
double hen(double a)
{
	return a*(-log(a)/log(2));
}

DATA *head=new DATA,*p=head;//mainini
int k=(-1);//编码函数用
void a(DATA* pp,info& aa);//编码函数声明

DATA* sort(DATA* pp);//排序函数声明
DATA *HEAD=new DATA,*tt=HEAD,*T;//排序函数用
//
void main()
{
	//输入数据	
	cout<<"请输入数据，第一个为字符，第二个为概率。输入概率超过或输入字符为*，结束输入"<<endl;
	cout<<"eg：a 0.2,然后回车，继续输入，或者a,然后回车再输入概率，回车               "<<endl;
	cout<<"当然您还可以用这种方式输入数据：a 0.2 b 0.3 c 0.5"<<endl;
	double l,temp=0;
	char L;
	int cou=0;
	while(cin>>L>>l)
	{
		if(l<=0.0||L=='*'||l>0.99999)
		{
			break;
		}
		p->Xi=L;
		p->PXi=l;
		p->next=new DATA;
		p->next->qian=p;//对新开类赋值
		p->r=p->next;
		p=p->next;
		temp+=l;
		cou++;
		if(temp==1.0) break;
	}
	//排序
	T=sort(head);//因为sort要改变tt，故需要一个中间变量
	tt->next=T;//由于迭代产生的链表格式不规范，以下句用来整理sort函数的返回结果
	tt->next->qian=tt;
	tt=tt->next;
	tt->next=new DATA;
	tt->next->qian=tt;//对新开类赋值
	tt=tt->next;
	HEAD->next->next->qian=NULL;
	HEAD=HEAD->next->next;
	cout<<"对输入信源排序结果如下："<<endl;

	for(p=HEAD;p->next!=NULL;p=p->next)//排序输出
		cout<<"字符:"<<p->Xi<<"  概率:"<<p->PXi<<endl;
	//编码
	cout<<"对输入信源编码结果如下："<<endl;
	info aa;
	a(HEAD,aa);//编码
	double ads=aa.length/cou;
	cout<<"平均码长："<<ads<<endl;
	cout<<"编码效率："<<aa.then/ads<<endl;
}
//编码．k
void a(DATA* pp,info& aa)//定义递归函数
{
	double y=1;//y定义为1是因为概率最多为1
	k++;//递归自增值，用于字符数组定位
	DATA *head1=pp,*head2;
	int o=1;
	while(1)//分01组
	{
		double l=0,z=0;
		for(int i=1;i<=o;i++)
		{
			if(pp->next==NULL) break;
			l=l+pp->PXi;
			pp=pp->next;
		}
		head2=pp->qian;//从这里分01段
		for(;pp->next!=NULL;pp=pp->next) 
			z=z+pp->PXi;
		if(y>fabs(l-z))//判断两组值之差是否最小
		{
			y=fabs(l-z);
			pp=head1;
			o++;
			continue;
		}
		else if(z==0&&i<=2)//z=0i<1表示只有一个概率了
		{
			cout<<"字符: "<<head1->Xi<<" 编码:"<<head1->key<<endl;
			aa.length+=strlen(head1->key);
			aa.then+=hen(head1->PXi);
			break;
		}
		for(DATA* u=head1;u->next!=head2->next;u=u->next) u->key[k]='0';//为字符串赋值
		for(DATA* h=head2;h->next!=NULL;h=h->next) h->key[k]='1';
		head2->qian->next=new DATA;//分段：标记head2为上一段结束位置
		head2->qian->next->qian=head2->qian;//ini
		a(head1,aa);//递归
		a(head2,aa);
		break;
	}
	k--;//迭代还原到上一个数组位置
}
//排序．HEAD,tt,T
DATA* sort(DATA* pp)//函数递归后头变到HEAD->next->next.返回值得到最后个head2没有与tt相连，需另设．得不到结尾为空的（next=MULL）地址
{
	DATA *head1=pp,*head2=pp;
	if(pp->next==NULL) return pp;//当pp是最后一个直时
	for(;pp->next!=NULL;pp=pp->next)
	{
		if(1-pp->PXi>=1-head2->PXi) //两个以上的值时,由于最后一个pxi为1，所以每次都会有个最小值
			head2=pp; 
	}
	if(head2->qian==NULL)//当pp是第一个直时
	{
		head2->next->qian=NULL;
		head1=head1->next;
	}
	else //当pp是最后一个值及中间的值时
	{head2->qian->next=head2->next;
	head2->next->qian=head2->qian;
	}
	tt->next=sort(head1);//递归，先得第一个，再得下一个
	tt->next->qian=tt;
	tt=tt->next;
	return head2;
}