h_weight.cpp

哈夫曼码的编码译码系统 问题描述 利用哈夫曼编码进行信息通讯可以大大提高信道利用率

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<iostream>
#define n1 27

typedef struct
{
	int weight;
	int lchild;
	int rchild;
	int parent;
}hufmtree;

typedef struct
{
	int bits[n1];
	int start;
	char ch;
}codetype;

codetype code[n1];

void SetW()
{
	FILE *fw;
	int k;
	char ch;

	fw=fopen("weight.txt","wb");
	printf("now creat the weight file,input the leafe and it's weight\n");
	printf("enter '#' to end!\n");
	do
	{
		printf("input the leafe:");
		ch=getchar();
		getchar();
		if(ch=='#')
			break;
		printf("input it's weight:");
		scanf("%d",&k);
		getchar();
		printf("\n***************************\n");
		fwrite(&ch,sizeof(char),1,fw);
		fwrite(&k,sizeof(int),1,fw);
	}while(ch!='#');
	printf("the file has created ! enter any key to continue\n");
	getchar();
	fclose(fw);
}

void CheckWF()
{
	char ch;
	int k;
	FILE *fw;
	int i=0;
	if((fw=fopen("weight.txt","rb"))==NULL)
	{
		printf("creat the leafe-weight file first\n");
		getchar();
		return;
	}

	printf("leafe-name  weight  |   leafe-name  weight  |   leafe-name  weight\n");

	while((fread(&ch,sizeof(char),1,fw))!=NULL)
	{
		printf("%-12c",ch);
		fread(&k,sizeof(int),1,fw);
		printf("%-12d",k);
		i++;
		if(i%3==0)
			printf("\n");
	}
	printf("\npress any key to continue\n");
	getchar();
	fclose(fw);
}

void CHuffman()
{
	int i,j,p1,p2;
	int small1,small2;
	int k;
	FILE *fw,*ft;
	char ch;
	int m,n;
	hufmtree *tree;
	int sum=0;

	if((fw=fopen("weight.txt","rb"))==NULL)
	{
		printf("creat the leafe-weight file first\n");
		getchar();
		return;
	}
	ft=fopen("htree.txt","wb");

	fseek(fw,0,2);
	n=ftell(fw)/(sizeof(int)+sizeof(char));
	rewind(fw);
	m=2*n-1;
	tree=(hufmtree *)malloc(m*sizeof(hufmtree));

	for(i=0;i<m;i++)
	{
		tree[i].parent=0;
		tree[i].lchild=0;
		tree[i].rchild=0;
		tree[i].weight=0;
	}

	for(i=0;i<n;i++)
	{
		fread(&ch,sizeof(char),1,fw);
		fread(&k,sizeof(int),1,fw);
		tree[i].weight=k;
	}

	for(i=n;i<m;i++)
	{
		p1=0;
		p2=0;
		small1=10000;
		small2=10000;
		for(j=0;j<i;j++)
			if((tree[j].weight<small1)&&(tree[j].parent==0))
			{
				small2=small1;
				small1=tree[j].weight;
				p2=p1;
				p1=j;
			}
			else if((tree[j].weight<small2)&&(tree[j].parent==0))
			{
				small2=tree[j].weight;
				p2=j;
			}
		tree[p1].parent=i+1;
		tree[p2].parent=i+1;
		tree[i].lchild=p1+1;
		tree[i].rchild=p2+1;
		tree[i].weight=tree[p1].weight+tree[p2].weight;
	}

	for(i=0;i<m;i++)
	{
		fwrite(&tree[i],sizeof(hufmtree),1,ft);

	}
	for(i=n;i<m;i++)
		sum=sum+tree[i].weight;
	fclose(fw);
	fclose(ft);
	free(tree);
	printf("the huffman tree has been created %d,press any key to continue\n",sum);
	getchar();
}

void CheckHT()
{
	FILE *ft;
	int i,n;
	hufmtree *ji;
	if((ft=fopen("htree.txt","rb"))==NULL)
	{
		printf("creat the huffman tree first\n");
		getchar();
		return;
	}
	
	ji=(hufmtree *)malloc(sizeof(hufmtree));
	fseek(ft,0,2);
	n=ftell(ft)/sizeof(hufmtree);
	rewind(ft);
	printf("weight      lchild      rchild      parent\n");   
	for(i=0;i<n;i++)
	{
		fread(ji,sizeof(hufmtree),1,ft);
		printf("%-12d%-12d%-12d%-12d\n",ji->weight,ji->lchild,ji->rchild,ji->parent);
	}
	fclose(ft);
	free(ji);
	printf("press any key to continue\n");
	getchar();
}

void HCode()
{
	hufmtree *tree;
	FILE *fc,*ft,*fw;
	int i,c,p,k;
	int m;
	codetype cd;
	char ch;

	fc=fopen("coding.txt","wb");
	ft=fopen("htree.txt","rb");
	fw=fopen("weight.txt","rb");
	fseek(ft,0,2);
	m=ftell(ft)/sizeof(hufmtree);
	rewind(ft);
	tree=(hufmtree *)malloc(m*sizeof(hufmtree));
	for(i=0;i<m;i++)
		fread(&tree[i],sizeof(hufmtree),1,ft);

	for(i=0;i<n1;i++)
	{
		cd.start=n1;
		c=i+1;
		p=tree[i].parent;
		while(p!=0)
		{
			cd.start--;
			if(tree[p-1].lchild==c)
				cd.bits[cd.start]=0;
			else
				cd.bits[cd.start]=1;
			c=p;
			p=tree[p-1].parent;
		}
		code[i]=cd;
	}

	for(i=0;i<n1;i++)
	{
		fread(&ch,sizeof(char),1,fw);
		code[i].ch=ch;
		fread(&k,sizeof(int),1,fw);
		fwrite(&code[i],sizeof(codetype),1,fc);
	}
	fclose(fc);
	fclose(ft);
	free(tree);
	printf("coding successful!press any key to continue\n");
	getchar();
}

void CheckCd()
{
	int i,j,n=n1;
	FILE *fc;
	codetype *code1;

	if((fc=fopen("coding.txt","rb"))==NULL)
	{
		printf("coding first\n");
		getchar();
		return;
	}
	code1=(codetype *)malloc(n*sizeof(codetype));
	for(i=0;i<n;i++)
		fread(&code1[i],sizeof(codetype),1,fc);
	printf("leafe   start   bits\n");
	for(i=0;i<n;i++)
	{
		printf("%-8c",code1[i].ch);
		printf("%-8d",code1[i].start);
		for(j=code1[i].start;j<n;j++)
			printf("%d",code1[i].bits[j]);
		printf("\n");
	}
	fclose(fc);
	free(code1);
	printf("press any key to continue\n");
	getchar();
}

void Calculate()
{
	int i,j;
	int sum=0;
	FILE *fw,*fc;
	char ch;
	codetype *code1;

	code1=(codetype *)malloc(n1*sizeof(codetype));
	fw=fopen("weight.txt","rb");
	fc=fopen("coding.txt","rb");
	for(i=0;i<n1;i++)
	{
		fread(&ch,sizeof(char),1,fw);
		fread(&j,sizeof(int),1,fw);
		fread(&code1[i],sizeof(codetype),1,fc);
		sum=sum+(n1-code1[i].start)*j;
	}
	fclose(fw);
	fclose(fc);
	free(code1);
	printf("the weighted path length of this huffman tree is :%d\n",sum);
	printf("\npress any key to continue\n");
	getchar();
}

void InputChar()
{
	char ch;
	int i,j;
	FILE *ff,*fc,*finput;
	codetype *code1;

	code1=(codetype *)malloc(n1*sizeof(codetype));
	ff=fopen("codefile.txt","wb");
	fc=fopen("coding.txt","rb");
	finput=fopen("input.txt","wb");

	for(i=0;i<n1;i++)
		fread(&code1[i],sizeof(codetype),1,fc);

	printf("\nplease input the coding message\n");
	do 
	{
		ch=getchar();
		if(ch=='#')
		{
			getchar();
			break;
		}
		else if(((ch>='a')&&(ch<='z'))||(ch==' '))
		{
			for(i=0;i<n1;i++)
			{
				if(code1[i].ch==ch)
					for(j=code1[i].start;j<n1;j++)
						fwrite(&code1[i].bits[j],sizeof(int),1,ff);
			}
			fwrite(&ch,sizeof(char),1,finput);
		}

		else 
		{
			getchar();
			printf("you input the wrong character\n");
			getchar();
			return;
		}
	}while(ch!='#');
	i=-1;
	fwrite(&i,sizeof(int),1,ff);
	fclose(ff);
	fclose(fc);
	fclose(finput);
	free(code1);
	printf("the code file has created!enter any key to continue\n");
	getchar();
}

void CInputChar()
{
	FILE *ff,*finput;
	int i;
	char ch;

	if((ff=fopen("codefile.txt","rb"))==NULL)
	{
		printf("please input the message first\n");
		getchar();
		return;
	}
	finput=fopen("input.txt","rb");

	printf("the input message as follow\n\n");
	while((fread(&ch,sizeof(char),1,finput))!=NULL)
		printf("%c",ch);
	printf("\n\nthe message after coding as follow\n\n");
	while((fread(&i,sizeof(int),1,ff))!=NULL)
	{
		printf("%d",i);
	}
	fclose(ff);
	fclose(finput);
	printf("\npress any key to continue\n");
	getchar();
}

void DeCode()
{
	FILE *ff,*fc,*ft,*fout;
	hufmtree *tree;
	codetype *code1;
	int i,b,n,m;

	n=n1;
	m=2*n-1;

	if((ff=fopen("codefile.txt","rb"))==NULL)
	{
		printf("please input the message first\n");
		getchar();
		return;
	}
	if((fc=fopen("coding.txt","rb"))==NULL)
	{
		printf("coding first\n");
		getchar();
		return;
	}
	if((ft=fopen("htree.txt","rb"))==NULL)
	{
		printf("creat the huffman tree first\n");
		getchar();
		return;
	}
	fout=fopen("out.txt","wb");
	tree=(hufmtree *)malloc(m*sizeof(hufmtree));
	code1=(codetype *)malloc(n*sizeof(codetype));
	for(i=0;i<n;i++)
		fread(&code1[i],sizeof(codetype),1,fc);
	for(i=0;i<m;i++)
		fread(&tree[i],sizeof(hufmtree),1,ft);

	i=m-1;

	while(((fread(&b,sizeof(int),1,ff))!=NULL)&&(b!=-1))
	{
		if(b==0)
			i=tree[i].lchild-1;
		else
			i=tree[i].rchild-1;
		if(tree[i].lchild==0)
		{
			fwrite(&code1[i].ch,sizeof(char),1,fout);
			i=m-1;
		}
	}
	fclose(fout);
	fclose(ft);
	fclose(ff);
	fclose(fc);
	free(tree);
	free(code1);
	printf("\n\nthe codes have been translation,press any key to continue\n");
	getchar();
}

void CheckOut()
{
	FILE *fout;
	char ch;

	if((fout=fopen("out.txt","rb"))==NULL)
	{
		printf("don't have this file\n");
		getchar();
		return;
	}

	while((fread(&ch,sizeof(char),1,fout))!=NULL)
		printf("%c",ch);
	fclose(fout);
	printf("\n\npress any key to continue\n");
	getchar();
}

void Window()
{
	int i;
	do
	{
		system("cls");

		printf("        *************************************************************\n");
		printf("                        ");
		printf("1---creat the leafe-weight file\n");
        printf("                        ");
		printf("2---check the leafe-weight file\n");
		printf("                        ");
		printf("3---creat a huffman tree\n");
		printf("                        ");
		printf("4---check the huffman tree\n");
		printf("                        ");
		printf("5---coding\n");
		printf("                        ");
		printf("6---check coding\n");
		printf("                        ");
		printf("7---weighted path length of tree\n");
		printf("                        ");
		printf("8---input the message which need to code\n");
		printf("                        ");
		printf("9---check the message coding file\n");
		printf("                        ");
		printf("10--translation\n");
		printf("                        ");
		printf("11--watch the translation message\n");
		printf("                        ");
		printf("0---exit\n");
		printf("        *************************************************************\n");
		scanf("%d",&i);
		getchar();
		if(i==1)
			SetW();
		else if(i==2)
			CheckWF();
		else if(i==3)
			CHuffman();
		else if(i==4)
			CheckHT();
		else if(i==5)
			HCode();
		else if(i==6)
			CheckCd();
		else if(i==7)
			Calculate();
		else if(i==8)
			InputChar();
		else if(i==9)
			CInputChar();
		else if(i==10)
			DeCode();
		else if(i==11)
			CheckOut();
		else if(i==0)
			break;
	}while(i!=0);
}

void main()
{
	Window();
}