fangfa2.cpp

huffman编码 希望对大家有用

//来自网上,很直观,摘录下来了 
#include <iostream>
using namespace std;
const Limit_Size=20;

int main()
{
	int i,j,k,m,n;
	char s1[Limit_Size],s2[Limit_Size],s[Limit_Size];
	cout<<"请输入第一个子序列：";
    cin>>s1;
	m=strlen(s1);
	cout<<"请输入第二个子序列：";
	cin>>s2;
	n=strlen(s2);
	//为二维数组开辟空间
	int **b = new int*[m+1];
	for ( i = 0;  i < m+1;  i++)
    {
		b[i] = new int[n+1];
    }
	int **c = new int*[m+1];
	for ( i = 0;  i < m+1;  i++)
    {
		c[i] = new int[n+1];
    }
	for(i=0;i<=m;i++) {c[i][0]=0;b[i][0]=0;}
	for(i=0;i<=n;i++) {c[0][i]=0;b[0][i]=0;}
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(s1[i-1]==s2[j-1])
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1;
			}
			else if(c[i-1][j]>=c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i][j]=2;
			}
			else {
				c[i][j]=c[i][j-1];
				b[i][j]=3;
			}
			//输出c[i][j]
			cout<<'\n';
			for(i=0;i<=m;i++)
			{
				for(j=0;j<=n;j++)
					cout<<c[i][j]<<"  ";
				cout<<'\n';
			}
			//输出b[i][j]
			cout<<'\n';
			for(i=0;i<=m;i++)
			{
				
				for(j=0;j<=n;j++)
					cout<<b[i][j]<<"  ";
				cout<<'\n';
			}
			//输出最长公共子序列
			i=m,j=n,k=0;
			while(i!=0&&j!=0)
			{
				if(b[i][j]==1)
				{
					s[k]=s1[i-1];
					k++;
					i--;
					j--;
				}
				else if(b[i][j]==2)
					i--;
				else j--;
			}
			cout<<"The LCSLength string: ";
			for(i=k-1;i>=0;i--)
				cout<<s[i];
			cout<<endl;
			//释放二维数组占用的空间
			for ( j = 0; j < m+1; j++)
			{
				delete[] b[j];
			}
			for ( j = 0; j < m+1; j++)
			{
				delete[] c[j];
			}
			delete[] b;
			delete[] c;
			b = NULL;
			c = NULL;
			return 0;
}