shannong.c

香农-范诺 和 霍夫曼无损 压缩算法

#include <stdio.h>
#include <conio.h>
#include <string.h>
struct node
{
	char sym[10];
	float pro;
	int arr[20];
	int top;
}s[20];

typedef struct node node;
//输出函数
void prints(int l,int h,node s[])
{
	int i;
	for(i=l;i<=h;i++)
	{
		printf("\n%s\t%f",s[i].sym,s[i].pro);
	}
}

//编码函数--香浓编码
void shannon(int l,int h,node s[])
{
	float pack1=0,pack2=0,diff1=0,diff2=0;
	int i,k,j;
	if((l+1)==h || l==h || l>h)
	{
		if(l==h || l>h)
			return;
		s[h].arr[++(s[h].top)]=0;
		s[l].arr[++(s[l].top)]=1;
		return;
	}
	else
	{
		for(i=l;i<=h-1;i++)
			pack1=pack1+s[i].pro;
		pack2=pack2+s[h].pro;
		diff1=pack1-pack2;
		if(diff1< 0)
			diff1=diff1*-1;
		j=2;
		while(j!=h-l+1)
		{
			k=h-j;
			pack1=pack2=0;
			for(i=l;i<=k;i++)
				pack1=pack1+s[i].pro;
			for(i=h;i>k;i--)
				pack2=pack2+s[i].pro;
			diff2=pack1-pack2;
			if(diff2< 0)
				diff2=diff2*-1;
			if(diff2>=diff1)
				break;
			diff1=diff2;
			j++;
		}
		k++;
		for(i=l;i<=k;i++)
			s[i].arr[++(s[i].top)]=1;
		for(i=k+1;i<=h;i++)
			s[i].arr[++(s[i].top)]=0;
		shannon(l,k,s);
		shannon(k+1,h,s);
	}
}

void main()
{
	int n,i,j;
	float x,total=0;
	char ch[10];
	node temp;
	//clrscr();
	printf("请输入字母个数:\t: ");
	scanf("%d",&n);
	for(i=0;i< n;i++)
	{
		printf("请输入符号 %d ---> ",i+1);
		scanf("%s",ch);
		strcpy(s[i].sym,ch);
	}
	for(i=0;i< n;i++)
	{
	   printf("\n\t请输入概率 %s ---> ",s[i].sym);
	   scanf("%f",&x);
	   s[i].pro=x;
	   total=total+s[i].pro;
	   if(total>1)
	   {
		printf("\t\t概率不合法，请输入一个新的概率");
		total=total-s[i].pro;
		i--;
	   }
	}
	s[i].pro=1-total;

	//对字符的概率进行排序
	for(j=1;j<=n-1;j++)
	{
		for(i=0;i<n-1;i++)
		{
			if((s[i].pro)>(s[i+1].pro))
			{
				temp.pro=s[i].pro;
				strcpy(temp.sym,s[i].sym);
				s[i].pro=s[i+1].pro;
				strcpy(s[i].sym,s[i+1].sym);
				s[i+1].pro=temp.pro;
				strcpy(s[i+1].sym,temp.sym);
			}
		}
	}
	for(i=0;i< n;i++)
		s[i].top=-1;

	//香浓编码
	shannon(0,n-1,s);

	//输出编码结果
	printf("---------------------------------------------------------------");
	printf("\n\n\n\t符号\t概率\t编码");
	for(i=n-1;i>=0;i--)
	{
		printf("\n\t%s\t%f\t",s[i].sym,s[i].pro);
		for(j=0;j<=s[i].top;j++)
			printf("%d",s[i].arr[j]);
	}
	printf("\n---------------------------------------------------------------");
	getch();
}