fano_coding.cpp

fano coding 费诺编码,数据结构和算法经典问题,c++实现.

//Fano.h:
#include"myhead.h"

typedef struct Node * Tree;
typedef struct Node * PNode;

struct Node
{
	double weight;
	int code;
	struct Node *parent;
	struct Node *leftchild;
	struct Node *rightchild;
};

void Build_Fano_Tree(Tree &T,double x[],int n,PNode pleaf[]);//n为信源信号个数

PNode Build_Child_Tree(int left,int right,double x[],PNode pleaf[]);

void Coding(Tree T);

void ReadCode(PNode child);

void Sort(int n,double x[]);


void Build_Fano_Tree(Tree &T,double x[],int n,PNode pleaf[])
{
	int left=0,right=n-1;
	T = Build_Child_Tree(left,right,x,pleaf);
	T->parent = NULL;
	Coding(T);
}

PNode Build_Child_Tree(int left,int right,double x[],PNode pleaf[])
{
	int Mid,i;
	double sum=x[left],stemp,total=0,comp;
	PNode leftchild,rightchild,T;
	T = (PNode)malloc(sizeof(PNode));
	
	if(left==right) 
	{
		static int LeafNum=0;
		
		T->weight = x[left];
		T->leftchild = T->rightchild = NULL;
		
		pleaf[LeafNum++]=T;
		return T;
	}
	
	for(i=left;i<=right;i++)
		total+=x;
	comp = total/2;
	
	for(i=left+1;i<=right;i++)
	{
		stemp=sum;
		sum += x;
		
		if(fabs(sum-comp)>fabs(stemp-comp)) break;
	}
	Mid = i-1;
	
	leftchild = Build_Child_Tree(left,Mid,x,pleaf);
	rightchild = Build_Child_Tree(Mid+1,right,x,pleaf);
	
	T->leftchild = leftchild;
	T->rightchild = rightchild;
	
	leftchild->parent = rightchild->parent = T;
	
	return T;
}

void Coding(Tree T)
{
	if(T->leftchild==NULL||T->rightchild==NULL) return;
	
	T->leftchild->code = 1;
	T->rightchild->code = 0;
	
	Coding(T->leftchild);
	Coding(T->rightchild);
	
}

void ReadCode(PNode child)
{
	printf("%d",child->code);
	if(child->parent->parent==NULL) return; 
	ReadCode(child->parent);
	
}

void Sort(int n,double x[])
{
	int i,j;
	double temp;
	for(i=0;i<n-1;i++)
		for(j=0;j<n-j;j++)
			if(x<x[i+1])
			{
				temp = x;
				x=x[i+1];
				x[i+1]=temp;
			}
}

void main()
{
	double *x;
	int n,i;
	Tree T;
	PNode *pleaf;
	cout<<"Input the source code number:";
	cin>>n;
	x=(double *) malloc(sizeof(double)*n);
	pleaf = (PNode *) malloc(sizeof(PNode)*n);
	
	for(i=0;i<n;i++)
	{
		cout<<"Input the code:";
		cin>>x;
	}
	Sort(n,x);
	Build_Fano_Tree(T,x,n,pleaf);
	for(i=0;i<n;i++)
	{
		cout<<"coding is: "<<x;
		ReadCode(pleaf);
		cout<<"\n";
	}
}