实验五034100549.cpp

输入一段文本

#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
struct HuffmanTree
{
	int weight;
	int parent,lchild,rchild;
	char ch;
};
typedef char** HuffmanCode;

struct return_value_sel
{
	int re_s1;
	int re_s2;

};
struct return_value_def
{
	char  re_p[100];
	int   *re_in;
	int	  re_count;
};
struct return_value_HTHC
{
	HuffmanTree *re_HT;
	HuffmanCode re_HC;
	
};
return_value_def def_wei(char in_ch[])
{
	char ch[100];
	int ch_wei[100];
	int i,j,n = 0,tab = 1;
	return_value_def re;

	for(i = 0;in_ch[i] != '\0';i++)
	{
		for(j = 0;j <= n;j++)
		{
			if(ch[j] == in_ch[i])
			{
				ch_wei[j]++;
				tab = 1;
				break;
			}
			else
				tab = 0;
		}
		if(tab == 0)
		{
			ch[n] = in_ch[i];
			ch_wei[n] = 1;
			n++;
			
		}
	}
	ch[n] = '\0';
	strcpy(re.re_p,ch);
	re.re_in = ch_wei;
	re.re_count = n;
	return re;
}

return_value_sel Select(HuffmanTree* HT,int i)
{	
	return_value_sel re;
	int t = i;
	int s1,s2,HT_wei = HT[i].weight;

	for(;i>=1;i--)
		if(HT[i].parent==0 && HT_wei>=HT[i].weight) 
		{HT_wei = HT[i].weight; s1 = i;}
	if(s1==t)
	{
		HT_wei = HT[t-1].weight;
			
	}
		else
		{	
			HT_wei = HT[t].weight;
			
		}
	for(i=t;i>=1;i--)
		if(HT[i].parent==0 && HT_wei>=HT[i].weight && i!=s1)
			{HT_wei = HT[i].weight; s2 = i;}
		re.re_s1 = s1;
		re.re_s2 = s2;
	return re;

}



return_value_HTHC HuffmanCoding(HuffmanTree *HT,int *w,int n,char ch_in[])
{
	int m,i;
	HuffmanTree *p;
	char *cd;
	HuffmanCode HC;
	return_value_HTHC re_value_HTHC;
	return_value_sel get_re;

	if(n<=1) exit(0);
	m = 2 * n - 1;
	
	HT = (HuffmanTree*)malloc((m+1)*sizeof(HuffmanTree));
	
	for(p=HT,i=1,p++;i<=n;++i,++p,++w) 
	{
		p->weight = *w;
		p->lchild = 0;
		p->rchild = 0;
		p->parent = 0;
		p->ch	  = ch_in[i-1];
	
	}
	for(;i<=m;++i,++p)
	{
		p->weight = 0;
		p->lchild = 0;
		p->rchild = 0;
		p->parent = 0;
		p->ch	  = NULL;
	
	}
	for(i=n+1;i<=m;++i)
	{
		get_re = Select(HT,i-1);
		HT[get_re.re_s1].parent = i;
		HT[get_re.re_s2].parent = i;
		HT[i].lchild = get_re.re_s1;
		HT[i].rchild = get_re.re_s2;
		HT[i].weight = HT[get_re.re_s1].weight + HT[get_re.re_s2].weight;
		
		
	}
	
	int c,f,start,j=0;
	HC = (HuffmanCode)malloc((n+1)*sizeof(char*));
	cd = (char *)malloc(n*sizeof(char));
	
	cd[n-1] = '\0';
	for(i=1;i<=n;++i)
	{
		
		start = n-1;
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
		{
			if(HT[f].lchild==c) cd[--start] = '0';
			else cd[--start] = '1';
		}
		HC[i] = (char*)malloc((n-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);
		cout<<"字符"<<HT[i].ch<<"的编码为: "<<HC[i]<<endl;
		
	}
	free(cd);
	
	re_value_HTHC.re_HC = HC;
	re_value_HTHC.re_HT = HT;
	
	return re_value_HTHC;
}

void HuffmanTrans(char* tran_ch,HuffmanTree *HT,int count)
{
	int i,n=count;
	cout<<"译码结果为:"<<endl;
	for(i=0;tran_ch[i]=='0'||tran_ch[i]=='1';i++)
		if(tran_ch[i]=='0')
		{
			n = HT[n].lchild;
			if(HT[n].lchild==0&&HT[n].rchild==0)
			{
				cout<<HT[n].ch;
				n = count;
			}
		}
		else
		{
			n = HT[n].rchild;
			if(HT[n].lchild==0&&HT[n].rchild==0)
			{
				cout<<HT[n].ch;
				n = count;
			}
		}
	cout<<endl;
}

void main()
{
	char edit_str[100],trans_str[1000],trans_str1[1000];
	int m[100];
	int i,n,j,t=0;
	HuffmanTree *HT;
    return_value_def get_value_def;
	return_value_HTHC get_value_HTHC;
	int start1 = 0;
	char choose_re = 'y',choose,ch[10];
	
	while(choose_re=='y'||choose_re=='Y')
	{
		cout<<"请选择您所将进行的操作！"<<endl;
		cout<<"(1)字符编码"<<endl
			<<"(2)需要对已编码过的字符译码"<<endl
			<<"(3)通过输入进行译码"<<endl
			<<"请输入您的选择:";
		cin>>ch;
		choose = ch[0];
		for(;;)
		{
			if(choose != '1'&&choose!='2'&&choose!= '3'&&choose!='0')
			{
				cout<<"输入错误，请重新输入"<<endl;
				cout<<"1、字符编码"<<endl
				<<"2、对编码过的字符译码"<<endl
				<<"3、通过输入进行译码"<<endl
				<<"0、退出"<<endl
				<<"清输入您要进行的选择:";
				cin>>ch;
				choose = ch[0];
			}
			else
				break;
		}
		switch(choose)
		{
		case '1':
			cout<<"请输入您要编码的字符串:"<<endl;
			cin>>edit_str;
			cout<<"进行编码..."<<endl;
			get_value_def = def_wei(edit_str);
			for( i=0;i<get_value_def.re_count;i++)
			{
				m[i] = *(get_value_def.re_in+i);
			}
			HT = (HuffmanTree*)malloc((2*get_value_def.re_count)*sizeof(HuffmanTree));
			get_value_HTHC = HuffmanCoding(HT,m,get_value_def.re_count,get_value_def.re_p);
			cout<<"编码为:"<<endl;
			for(n=0;edit_str[n]!='\0';n++)
				for(j=0;j<=get_value_def.re_count;j++)
					if(edit_str[n]==get_value_HTHC.re_HT[j].ch)
					{
						cout<<get_value_HTHC.re_HC[j];
						for(int x=0;get_value_HTHC.re_HC[j][x]=='0'||get_value_HTHC.re_HC[j][x]=='1';t++,x++)
							trans_str1[t]=get_value_HTHC.re_HC[j][x];
						

					}
			
			cout<<endl;
			start1 = 1;
			break;
		case '2':
			if(start1!=1)
			{
				cout<<"您还没有进行建立编码表,请先执行第一步操作!!"<<endl;
				break;
			}
			HuffmanTrans(trans_str1,get_value_HTHC.re_HT,2*get_value_def.re_count-1);
			
			break; 
		case '3':
			if(start1!=1)
			{
				cout<<"您还没有进行建立编码表,请先执行第一步操作!!"<<endl;
				break;
			}
			cout<<"请输入您要译的代码:"<<endl;
			cin>>trans_str;
			for(i=0;trans_str[i]!='\0';i++)
			if(trans_str[i]!='0'&&trans_str[i]!='1')
			{
				cout<<"输入中有非法字符，请重新输入!!"<<endl;
				cout<<"请输入您要译的代码:"<<endl;
				cin>>trans_str;
			}
			
			cout<<endl;
			HuffmanTrans(trans_str,get_value_HTHC.re_HT,2*get_value_def.re_count-1);
			break;
		case '0':
			break;
		}
		cout<<"是否继续进行操作(是:y 否:n )"<<endl;
		cin>>choose_re;
		for(;;)
		{if(choose_re != 'y'&&choose_re != 'Y'&&choose_re != 'n'&&choose_re != 'N')
			{
				cout<<"输入错误请重新输入!!"<<endl;
				cout<<"是否继续进行操作(是:y 否:n )"<<endl;
				cin>>choose_re;
			}
			else
				break;
		}
	
	}


}