exp2.cpp

香农和LZW快速算法源代码

#include <iostream>
#include <algorithm>
#include <time.h>
#include <string>
#include <math.h>
#include <functional>
#include <vector>
using namespace std;
vector<string> dic;//LZW的动态字典
string LWZ_Code;//LZW最终编码
char ch[100];
long hash[26],num[26];
string str;
string LZW_code;
string::iterator p;
string::reverse_iterator rp;
string ss[26];
string huff_in[101][2],huff_code[26];
long n;
class huff
{
public:
	string code_str;
	bool f;
	long value ;
	huff()
	{
		f=true;
		code_str.erase();
		value=0;
	}
	bool operator >(const huff &T) const
	{
		return this->value>T.value;	
	}
	bool operator ==(const huff &T) const
	{
		return this->value==T.value;	
	}
	bool operator <(const huff &T) const
	{
		return this->value<T.value;	
	}
	bool operator >=(const huff &T) const
	{
		return this->value>=T.value;	
	}
	bool operator <=(const huff &T) const
	{
		return this->value<=T.value;	
	}


};
long nu(string str)
{
	long x=0;
	for(p=str.begin();p!=str.end();p++)
	{
			x+=hash[*p-'A'];
	}
	return x;
}
void decode(string st) //香农
{
	long n=nu(st);
	long x=0;
	string sf,sb;
	if(st.length()>1)
	{	
		for(p=st.begin();p!=st.end();p++)
		{
			x+=hash[*p-'A'];
			if(sf.length()==0)
			{
				sf+=*p;
			}
			else if(x>n/2)
			{
				sb+=*p;
			}
			else
			{
				sf+=*p;
			}
		}
		cout<<"把"<<st<<"分成"<<sf<<"和"<<sb<<endl;
		for(p=sf.begin();p!=sf.end();p++)
		{
			ss[*p-'A']+='0';
		}
		for(p=sb.begin();p!=sb.end();p++)
		{
			ss[*p-'A']+='1';
		}
		if(sf.length()>1)
			decode(sf);
		if(sb.length()>1)
			decode(sb);
	}

}
void ccode_str(string in_str,char cc)
{
	string::iterator pp=in_str.begin();
	for (;pp!=in_str.end();pp++)
	{
		huff_code[*pp-'A']+=cc;
	}
}
void huff_encode(string temp_str)
{
	long j=temp_str.length();
	p=temp_str.begin();
	huff hh[100];
	for (long i=0;i<j;i++)
	{
		hh[i].code_str+=(char)(num[i]+'A');
		hh[i].value=hash[num[i]];
	}
	while (--j)
	{
		sort(&hh[0],&hh[j+1],greater<huff>());
		hh[j-1].value=hh[j].value+hh[j-1].value;
		ccode_str(hh[j].code_str,'0');
		ccode_str(hh[j-1].code_str,'1');
		hh[j-1].code_str+=hh[j].code_str;
	}



}
long find(string find_str)
{
	vector<string>::iterator vec_p=dic.begin();
	bool is_find=false;
	for (long i=0;i<dic.size();i++,vec_p++)
	{
		if (*(vec_p)==find_str)
		{
			return i+1;
		}	
	}
	return 0;
}
string ltostr(long x)
{
	string str;
	while (x!=0)
	{
		x=x%10;
		str+=(char)(x+'0');
		x=x/10;
	}
	str.reserve(str.length());
	return str;
}
bool LZW()
{
	dic.clear();
	LWZ_Code="";
	string LZW_ch;
	LZW_ch=ch;
	string::iterator strp=LZW_code.begin();
	vector<string>::iterator vec_p=dic.begin();
	for (strp=LZW_code.begin();strp!=LZW_code.end();strp++)
	{
		string sss="";
		sss+=(*strp);
		dic.push_back(sss);//初始化字典	
	}
	string s,c,code;
	s.erase();
	c.erase();
	strp=LZW_ch.begin();
	s+=*(strp++);
	c+=*(strp);
	for (;strp!=LZW_ch.end();)
	{
		string te;
		te=s+c;
		long x=find(s);
		if (find(te))
		{
			s=te;
			c.erase();
			c+=*(++strp);
			continue;	
		}
		else 
		{
			dic.push_back(te);
			s.erase();
			s=c;
			c.erase();
			c+=*(++strp);
		}
		LWZ_Code+=ltostr(x);
		LWZ_Code+=" ";
	}
	long x=find(s);
	LWZ_Code+=ltostr(x);
	LWZ_Code+=" ";
	cout<<LWZ_Code<<endl;
	cout<<"================================================="<<endl;
	cout<<"字典为:"<<endl;
	x=0;
	for (x=0,vec_p=dic.begin();x<dic.size();x++,vec_p++)
	{
		cout<<x+1<<" "<<(*vec_p)<<endl;
	}	
	cout<<"===================结束=========================="<<endl;
	return true;
}
void main()
{
	long x,j;
	double answer;
	srand(time(NULL));	
	cout<<"请输入您要生成的字符数(<=100):";
	while(cin>>n)
	{
		memset(huff_code,'\0',sizeof(huff_code));
		str="";
		memset(hash,0,sizeof(hash));
		memset(ss,'\0',sizeof(ss));
		memset(num,0,sizeof(num));
		answer=0;
		for(long i=0;i<=n-1;i++)
		{
			ch[i]='A'+rand()%26;
			hash[ch[i]-'A']++;
		}
		for (i=0;i<26;i++)
		{
			num[i]=i;
		}
		cout<<"**********************随机生成的字符串**********************"<<endl<<ch<<endl;
		for(i=0;i<26;i++)
		{
			if(hash[i]!=0)
				answer+=((double)hash[i]/n)*(log(1/((double)hash[i]/n))/log(2));
		}
		cout<<"火商 ="<<answer<<endl;
		for (i=0;i<25;i++)
		{
			for (j=i;j<26;j++)
			{
				if(hash[num[i]]<hash[num[j]])
				{
					x=num[i];
					num[i]=num[j];
					num[j]=x;
				}
			}
		}
		cout<<"排序后:"<<endl;
		for(i=0;i<26;i++)
		{
			if(hash[num[i]]!=0)
			{
				char xx='A'+num[i];
				cout<<xx<<"("<<hash[num[i]]<<")";
				str+=xx;
			}
		}
		string temp=str;
		LZW_code=str;
		cout<<endl<<endl;
		cout<<"============香农-凡诺编码过程============"<<endl;
		decode(str);
		str+=':';
		cout<<"----------编码后----------"<<endl;
		for(i=0;i<26;i++)
		{
			if(hash[num[i]]!=0)
			{
				char xx='A'+num[i];
				cout<<xx<<":"<<ss[num[i]]<<endl;
				str+=ss[num[i]];
			}
		}
		cout<<"---------最终编码---------"<<endl;
		cout<<str<<endl;
		cout<<"================================================="<<endl<<endl;
		cout<<"按任意键进行HUFFMAN编码...";
		system("pause");
		cout<<endl;
		cout<<"===============传说中的HUFFMAN编码==============="<<endl;
		huff_encode(temp);
		char te_ch;
		str="";
		cout<<"----------编码后----------"<<endl;
		for (i=0;i<temp.length();i++)
		{
			te_ch=(char)(num[i]+'A');
			string ss_temp=huff_code[num[i]];
			cout<<te_ch<<":";
			for (rp=ss_temp.rbegin();rp!=ss_temp.rend();rp++)
			{
				cout<<*rp;
				str+=*rp;
			}
			cout<<endl;
		}
		cout<<"----------编码后----------"<<endl;
		cout<<temp<<":"<<str<<endl;
		cout<<"================================================="<<endl;
		cout<<"按任意键进行LZW编码...";
		system("pause");
		cout<<"================================================="<<endl;
		LZW();
	
	}
}