hanming.cpp

我们经常遇到的问题 山农编码 网络上代码极少 值得关注 不好意思我上传的那个山农编码其实是汉明码

#include<iostream.h>
#include<math.h>
#include <stdlib.h>
static char code[10]={9,9,9,9,9,9,9}, juzhen[100][10];
static int t=0,NUM=0,x;
static float NUM_c=0, Han=0,H=0;
typedef struct TNode{
	char data;
	float p;
	char code[10];
	struct TNode *LC, *RC;
}TNode, *LTree;
//////////////////////////创建链表并对链表排序////////////////////////
LTree creatlist(){
	LTree t=0, p=0;
	LTree p2, te1, te2;
	float n=0;
	cout<<"请输入要编码的字符及相应的概率：		";
	do{					//输入数据  （以链表方式输入）
		t=new TNode;
		t->RC=0;
		t->LC=p;
		p=t;
		cin>>t->data>>t->p;
		n=n+t->p;
		if(n<1)
			cout<<"条件不足，继续输入: 		";
		if(n>1){
			cout<<"输入错误，终止执行！！\n";
			exit(0);
		}
	}while(n<1);
	cout<<"输入成功！\n";				//接下来对输入的数据进行排序 （降序）
	p2=p;
	p=0;
	te2=p2;
	while(p2!=0)	{	//找p2中的最小值
		te1=p2;
		while(te1->LC!=0)	{	//交换数据
			if(te1->LC->p < p2->p)	{
				te2=te1->LC;
				te1->LC=te1->LC->LC;
				te2->LC=p2;
				p2=te2;
			}
			if(te1->LC!=0)
				te1=te1->LC;
		}
		te2=p2;
		p2=p2->LC;
		te2->LC=p;
		p=te2;
	}
	return p;
}
//////////////////////将链表转化为编码树///////////////////
LTree creatTree(LTree p){
	LTree t,tt;
	float count, countp ,tag;
	if(p->RC==0)	{		//确定rc
		count=0;
		t=p->LC;
		while(t!=0)	{	//求和
			count=count+ t->p;
			t=t->LC;
		}
		t=p->LC;
		countp=0;
		tag=1;
		while(t!=0)	{		//切断链表
			countp+=t->p;
			if(tag>fabs(countp-count/2))
				tag=(float)fabs(countp-count/2);
			else{
				p->RC=tt->LC;
				tt->LC=0;
				break;
			}
			tt=t;
			t=t->LC;
		}	}
	if(p->LC->LC!=0)	{	//需要分组
		t=new TNode;
		t->LC=p->LC;
		t->RC=0;
		p->LC=t;
		creatTree(t);
	}
	if(p->RC->LC!=0)	{	//左子树确定 创建新节点 递归右子树		LC完
		t=new TNode;
		t->LC=p->RC;
		t->RC=0;
		p->RC=t;
		creatTree(t);		
	}
	return p;
}
////////////////////////////译码////////////////////////////////////
void unshannong(LTree p){			//输入译码树及待译序列
	char c;
	LTree temp=p;
	cout<<"请输入待译序列：";
	do	{					//左0 右1 编码 到叶子节点时输出
		cin>>c;
		if(c=='1')	{
			if(temp->RC!=0)	{
				temp=temp->RC;
				if(temp->LC==0 && temp->RC==0)	{
					cout<<temp->data;
					temp=p;
				}
				continue;
			}		}
		if(c=='0')	{
			if((*temp).LC!=0 ){
				temp=temp->LC;
				if(temp->LC==0 && temp->RC==0)	{
					cout<<temp->data;
					temp=p;
				}
				continue;
			}	}
		else
			break;
	}while(1);
}
/////////////////////////////访问函数////////////////////////////////
int visit(LTree p){
	float NUMC=0;
	if(p->LC==p->RC && p->LC==0){
		cout<<p->data<<"	"<<p->p<<"		";
		NUMC=0;
		for(int k=0; k<10; k++){
			if(code[k]=='0'||code[k]=='1'){
				cout<<code[k];
				p->code[k]=code[k];
				juzhen[x][k+1]=code[k];
				NUMC+=1;			//记录编码长度
			}		}
		juzhen[x][0]=p->data;
		x++;
		NUMC=NUMC*(p->p);			//求权
		NUM_c=NUM_c+NUMC;		//求和
		H=(float) -1*(p->p * log(p->p)/log(2));
		Han=Han+H;
		NUM++;			//记录字符数
		cout<<endl;
	}
	return 1;
}
/////////////////////////////遍历树////////////////////////////////////////
int  pre(LTree p , int (*visit)(LTree p)){
	if(p!=0){
		if(visit(p))	{
			code[t]='0';
			t++;
			if(pre(p->LC, visit)){
				if(pre(p->RC, visit)){
					if(code[t]!='1'){
						code[t]='1';
						t++;
					}
					else	{
						code[t]=9;
						t--;
					}
					return 1;
				}		}		}
		return 0;		}
	else{
		code[t]=9;
		t--;
		return 1;		//转为访问右子树
	}}
void main(){
	LTree p=0;
	TNode t;
	char c;
	cout<<"			"<<"***20052840	 胡浩	05计科2	山农－范诺编码***\n\n";
		for(int i=0; i<100; i++)
			for(int j=0; j<10; j++)
				juzhen[i][j]=9;
	p=creatlist();
	t.LC=p;
	t.RC=0;
	p=creatTree(&t);
	pre(p,visit);
	cout<<"****平均编码长度为：	"<<NUM_c<<endl;
	cout<<"****信源熵为：	"<<Han<<endl;
	cout<<"****编码效率为：	"<<100*Han/NUM_c<<"%\n";
	unshannong(p);
	cout<<"****请输入待编码的字符序列：";
	do{
		cin>>c;
		for( i=0; i<100; i++){
			if(c==juzhen[i][0])	{		//shuchubianma
				for(int j=1; juzhen[i][j]!=9; j++)
					cout<<juzhen[i][j];
				break;
			}
			if(i==99)
				cout<<"不能对"<<c<<" 进行编码！\n";
		}
	}while(1);
}