huffman.c

霍夫曼树的简单的原代码,可以进行一些简单的操作

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct leaves1             //权值结点结构体
{
	int x;
	int parent;
	int lchild;
	int rchild;
}hfnode1;
typedef struct codetype                    //字符结点结构体
{
	char key;
	char *code;
}codedata;
typedef struct tree1                         //树结点结构体
{
	int root;
	hfnode1 nodes[59];
	codedata table[30];
}huffmantree1;

void inputquanzhi(huffmantree1 *a,int n)         //字符集及权值输入函数
{	
	int i;
	FILE *fp;
	if((fp=fopen("data.txt","w"))==NULL)
	{
		printf("data.txt打开失败!\n");
		exit(0);
	}

	for(i=0;i<n;i++)
	{
		printf("请输入字符 权值\n");
		fflush(stdin);
		scanf("%c %d",&a->table[i].key,&a->nodes[i].x);
		fflush(stdin);
		if(a->table[i].key!=' ')
			fprintf(fp,"%c %d\n",a->table[i].key,a->nodes[i].x);
		else
			fprintf(fp,"%c %d\n",'#',a->nodes[i].x);
		a->nodes[i].parent=-1;
		a->nodes[i].lchild=-1;
		a->nodes[i].rchild=-1;
	}
	fclose(fp);
}

void getquanzhi(huffmantree1 *a)                 //字符集调入函数
{	
	int i;
	FILE *fp;
	if((fp=fopen("numbers.txt","r"))==NULL)
	{
		printf("numbers.txt打开失败!\n");
		exit(0);
	}
	for(i=0;i<27&&!feof(fp);i++)
	{	
		a->table[i].key=fgetc(fp);
		if(a->table[i].key=='#')
			a->table[i].key=' ';
		fscanf(fp,"%d\n",&a->nodes[i].x);
		a->nodes[i].parent=-1;
		a->nodes[i].lchild=-1;
		a->nodes[i].rchild=-1;
	}
	fclose(fp);
}


void createhuffmantree(huffmantree1 *T,int n)            //建立哈夫曼树函数
{
	int m1,m2,x1,x2,i,j;
	for(i=0;i<n-1;i++)
	{
		m1=1000;m2=m1;x1=0;x2=x1;
		for(j=0;j<n+i;j++)
		{
			if(T->nodes[j].parent==-1)
				if(T->nodes[j].x<m1)
				{
					m2=m1;
					x2=x1;
					m1=T->nodes[j].x;
					x1=j;
				}
				else
					if(T->nodes[j].x<m2)
					{
						m2=T->nodes[j].x;
						x2=j;
					}
		}
		T->nodes[x1].parent=n+i;
		T->nodes[x2].parent=n+i;
		T->nodes[n+i].x=T->nodes[x1].x+T->nodes[x2].x;
		T->nodes[n+i].lchild=x1;
		T->nodes[n+i].rchild=x2;
		T->nodes[n+i].parent=-1;
	}
	T->root=n*2-2;
}
void scan(huffmantree1 *t,int root)                 //遍历树，输出（前序）
{
	printf("%d  ",t->nodes[root].x);
	printf("(");
	if(t->nodes[root].lchild!=-1)
		scan(t,t->nodes[root].lchild);
	if(t->nodes[root].rchild!=-1)
		scan(t,t->nodes[root].rchild);
	printf(")");
}
void setcode(huffmantree1 *t,int n)                   //生成字符编码
{
	int i,j,x,p;
	char c[27];
	FILE *fp;
	fp=fopen("letter'scode.txt","w+");
	c[26]='\0';
	for(i=0;i<n;i++)
	{
		x=i;
		j=25;
		p=t->nodes[x].parent;
		while(p!=-1)
		{
			if(t->nodes[p].lchild==x)
				c[j--]='0';
			else
				c[j--]='1';
			x=p;
			p=t->nodes[x].parent;
		}
		t->table[i].code=(char *)malloc((27-j+1)*sizeof(char));
		strcpy(t->table[i].code,c+j+1);
		fprintf(fp,"%c %s\n",t->table[i].key,t->table[i].code);
	}
	fclose(fp);
}
void savecodes(char *codes)                      //存储编译出的代码
{
	FILE *fp;
	if((fp=fopen("codes.txt","a+"))==NULL)
	{
		printf("codes.txt打开失败!\n");
		exit(0);
	}
	fprintf(fp,"%s\n",codes);
	if(fclose(fp))
	{
		printf("codes.txt关闭失败!\n");
		exit(0);
	}
}
void getcode(huffmantree1 *t,char *codes,int n)              //编译器
{
	int i=0,j,x;
	char y;
	do
	{
		printf("\n**************\n--1.编码\n--0.退出\n**************\n");
		scanf("%d",&x);
		fflush(stdin);
		switch(x)
		{
		case 1:{
			char a[100];
			printf("请输入报文:\n");
			scanf("%[^\n]",a);
			fflush(stdin);
			while(a[i]!='\0')
			{
				for(j=0;j<n;j++)
				{
					if(t->table[j].key==a[i])
					{
						strcat(codes,t->table[j].code);
						break;
					}
				}
				i++;
			}
			printf("该报文编码为:\n");
			puts(codes);
			printf("是否保存该编码?(y/n)\n");
			scanf("%c",&y);
			if(y=='y')
				savecodes(codes);
			break;
			   }
		case 0:break;
		default:printf("输入错误,请重新输入\n");
		}
	}while(x!=0);
}

void translatcode(huffmantree1 *tree,char *codes,int n)             //译码器
{
	char a[100];
	char temp[50];
	char voidstr[]=" ";   //空字符串，用于置空字符串temp
	int i,j,t=0,s=0,x;
	x=strlen(codes);
	for(i=0;i<x;i++)
	{
		temp[t]=codes[i];
		t++;
		temp[t]='\0';
		for(j=0;j<n;j++)
		{
			if(strcmp(tree->table[j].code,temp)==0)      //比较
			{
				a[s]=tree->table[j].key;
				s++;
				strcpy(temp,voidstr);          //置空temp
				t=0;
				break;
			}
		}
	}
	if(s==0)      //并没有字符编码与之匹配
		printf("编码出错!不能翻译!\n");
	else
	{
		a[s]='\0';
		printf("翻译得:\n");
		puts(a);
	}
}

void inputcodes(huffmantree1 *tree,int n)       //编码读取函数
{
	int x;
	char codes[200];
	do
	{
		printf("\n*******************\n--1.从文件读取编码\n--2.输入编码\n--0.退出\n*******************\n");
		scanf("%d",&x);
		switch(x)
		{
		case 1:{
			FILE *fp;
			if((fp=fopen("codes.txt","r+"))==NULL)
			{
				printf("codes.txt打开失败!\n");
				exit(0);
			}
			fscanf(fp,"%s",codes);
			translatcode(tree,codes,n);
			if(fclose(fp))
			{
				printf("codes.txt关闭失败!\n");
				exit(0);
			}
			break;
			   }
		case 2:printf("请输入报文的编码:\n");fflush(stdin);gets(codes);translatcode(tree,codes,n);break;
		case 0:break;
		default:printf("输入出错,请重新输入:\n");break;
		}
	}while(x!=0);
}

void main()
{
	int i,x,y=0;            //x为选项标记值，y为哈夫曼树是否建立的标记参数
	int n;
	char codes[200]="\0";
	huffmantree1 tree;
	printf("****************************\n      哈夫曼编译码器\n****************************\n");
	do
	{
		printf("\n--1.输入字符权值\n--2.从文件读取字符频率集\n--3.建立哈夫曼树求得字符编码\n--4.编码器\n--5.译码器\n--0.退出\n");
		printf("\n请选择:\n");
		scanf("%d",&x);
		switch(x)
		{
		case 1:{
			printf("请输入字符集大小n的值:\n");
			scanf("%d",&n);
			inputquanzhi(&tree,n);
			break;
			   }
		case 2:{
			n=27;
			getquanzhi(&tree);
			printf("输出字符集及权值:\n");
			for(i=0;i<27;i++)
			{
				printf("%c %d\n",tree.table[i].key,tree.nodes[i].x);
			}
			break;
			   }
		case 3:{
			createhuffmantree(&tree,n);
			printf("\n***************输出哈夫曼树***************:\n");
			scan(&tree,tree.root);
			setcode(&tree,n);
			y=1;              //标记位变更
			break;
			   }
		case 4:{
			if(y)               //若标记位为零，以存储的标准字符集为准建立哈夫曼树，确定字符编码
				getcode(&tree,codes,n);
			else
			{
				n=27;
				getquanzhi(&tree);
				createhuffmantree(&tree,n);
				setcode(&tree,n);
				getcode(&tree,codes,n);
			}
			break;
			   }
		case 5:{
			if(y)
				inputcodes(&tree,n);
			else
			{
				n=27;
				getquanzhi(&tree);
				createhuffmantree(&tree,n);
				setcode(&tree,n);
				inputcodes(&tree,n);
			}
			break;
			   }
		case 0:break;
		default:printf("输入错误,请重新选择:\n");break;
		}
	}while(x!=0);
	
	
}