haffman.cpp

哈夫曼编码用 c语言编写的 比较简单 初学者 编码与字符的转换

#include "stdio.h"
#include "stdlib.h"
#include "fstream.h"
#include "string.h"
#define MAX 1000
//****************************************************************************
typedef struct{
	char c,s;
	int w;
}datatype;
typedef datatype *data;
//****************************************************************************
 typedef struct node {
datatype data;
struct node *leftchild, *rightchild,*parent;
}BinTNode;
 typedef BinTNode *BinTree;

//****************************************************************************
void chuanzhi(datatype *data1)
{

	char f;
	int n;
	ifstream txtfile;
	txtfile.open("D:\\hafuman.txt");
	if(!txtfile)
	{
		cerr<<"asd"<<endl;
		exit(1);
	}
for(int i=0;i<26;i++)
{
		txtfile>>f;
	    data1[i].c=f;
		txtfile>>n;
		data1[i].w=n;
}
data1[26].c=' ';
data1[26].w=186;
}
void paixu(data data1)
{
	datatype da;
	for(int i=0;i<27;i++)
	{
	for(int j=i+1;j<27;j++)
	{
		if(data1[i].w>data1[j].w)
		{
		da=data1[j];
		data1[j]=data1[i];
		data1[i]=da;
		}
	}
	}
}
void Insert(datatype dat,data data1,int j,int dalen)
{
	int i=j,n;
		while(dat.w>data1[i].w) i++;
		n=i;
		for(i=dalen;i>n;i--)
		{
          data1[i]=data1[i-1];
		}
		data1[n]=dat;
}
//****************************************************************************
int found(BinTree *Q,int a)
{
	int i=0;
	while((Q[i]->data.w!=a)&&i<100) i++;
	return i; 
}
//****************************************************************************
BinTree CreateHafumanTree(data data1,BinTree *Q,BinTree W[])
{
	int j=0,k=0,e=0;
	datatype d;
	BinTree q;
	int dalen=27;
	while(data1[j+1].w!=10000)
	{
		BinTree a,b;
	if(data1[j].c!='@')
	{
	a=(BinTree)malloc(sizeof(BinTNode));
	a->leftchild=NULL;a->rightchild=NULL;
	a->data=data1[j];
			W[e]=a;e++;
	}
	else a=Q[found(Q,data1[j].w)];
//	printf("%c-",a->data.c);
//	printf("%d ",a->data.w);
	a->data.s='0';
	if(data1[j+1].c!='@')
	{   

		b=(BinTree)malloc(sizeof(BinTNode));
	    b->data=data1[j+1];
		b->leftchild=NULL;b->rightchild=NULL;
						W[e]=b;e++;
	}
	else b=Q[found(Q,data1[j+1].w)];
//	printf("%c-",b->data.c);
//		printf("%d ",b->data.w);
	b->data.s='1';
	q=(BinTree)malloc(sizeof(BinTNode));
	d.w=a->data.w+b->data.w;
	d.c='@';
	q->data=d;
	q->leftchild=a;q->rightchild=b;
	a->parent=q;b->parent=q;
	Q[k]=q;
	k++;
//	printf("%c-",q->data.c);
//		printf("%d",q->data.w);
		j=j+2;
	Insert(d,data1,j,dalen);
	dalen++;
//	printf("\n");
	}
	q->parent=NULL;
	return q;
}
BinTree search(char a,BinTree W[])
{
	int k=0;
	while(W[k]->data.c!=a)
		k++;
	return W[k];
}
void bianma(char *string1,char *string2,int len,BinTree W[])
{
	BinTree q;
	int i=0,j=0;
	for(j=0;j<len;j++)
	{
      q=search(string1[j],W);
	  while(q->parent!=NULL)
	  {
	  string2[i]=q->data.s;
	  q=q->parent;
	  i++;
	  }
	  string2[i]=' ';i++;
	}
	string2[i]='#';
}
//****************************************************************************
void yima(BinTree bt,char *string1,char *string2,int len)
{
  	BinTree q;
	q=bt;
	int i=0,j=0;
while(i<len)
{
	while(q->data.c=='@')
	{
		if(string1[i]=='0')
			q=q->leftchild;
		else
			if(string1[i]=='1')
			q=q->rightchild;
			else {printf("输入有误！请重新选择输入。\n");
			string2[0]='#';return;}
		i++;
	}
		string2[j]=q->data.c;j++;q=bt;
}
	string2[j]='#';
}
//****************************************************************************

void main()
{
BinTree W[MAX];
BinTree bt;
datatype d;
BinTree Q[MAX];
d.c='#';d.w=10000;
datatype data1[MAX];
for(int k=0;k<MAX;k++)
data1[k]=d;
chuanzhi(data1);
paixu(data1);	
 int xz;
while(xz!=5) {	
	int r=0;
	int len;
	int f=0;
char string1[MAX];
char string2[MAX];
printf("           哈夫曼编码器     \n");
printf("==========================\n");
printf("     1.建立哈夫曼编码树    \n");
printf("     2.输入编码或代码  \n");
printf("     3.编码     \n");
printf("     4.译码     \n");
printf("     5.退出         \n");
printf("       请选择：1-5：          \n");
scanf("%d",&xz);
getchar();
	switch(xz) 
	{
	case 1:
     printf("建立哈夫曼树:\n");
     bt=CreateHafumanTree(data1,Q,W);
     printf("哈夫曼的链式存储结构建成立完成!\n");
     break;
	case 2: 


len=1;
string1[0]='A';
while(f<27)
{
	bianma(string1,string2,len,W);
	if(f==26) printf("(空格) ");
	else
	printf(" %c ",string1[0]);
	if(f==25) string1[0]=' ';
	else
	string1[0]=string1[0]+1;
	int e=0;
	while(string2[e]!='#')
	{
//		printf("%c",string2[e]);
	e++;
	}
	for(int j=e-1;j>=0;j--)
		printf("%c",string2[j]);
	f++;
}
		 break;
	case 3:
    printf("待翻译的字符串为（仅限大写） :\n");
	gets(string1);
	len=strlen(string1);
	bianma(string1,string2,len,W);
	printf("代码如下：\n ");
	int l;
	while(string2[r]!='#')
	{
		if(string2[r]==' ')
		{
			l=r;
		while(string2[r-1]!=' '&&r>0)
		{
	printf("%c",string2[r-1]);
	r--;
		}
		r=l;
		printf(" ");
		}
	r++;
	}
	printf("\n");
	break;
	case 4:
		printf("待翻译的代码串为（仅限0和1，不要有空格） :\n");
	gets(string1);
	len=strlen(string1);
	printf("代表的字符为：\n");
     yima(bt,string1,string2,len);
	 while(string2[r]!='#')
	 {
	 printf("%c",string2[r]);
	 r++;
	 }
		break;
	case 5:break;
	default:
		printf("输入出错！\n");
    }
  }
}