1.cpp

应用算法设计与分析知识

#include<iostream>
#include<cstdlib>
#include<fstream>
using namespace std;
typedef char* ch;
void LCSLength(int m,int n,char *x,char *y,int (*c)[7],int (*b)[7]);
//void LCSLength(int m,int n,char *x,char *y,int **c,int **b);
void LCS(int i,int j,char *x,int (*b)[7]);
//void LCS(int i,int j,char *x,int **b);
int main()
{   int i,m,n,j;
	ifstream in_stream1("li.txt");
	ifstream in_stream2("juan.txt");
	if(in_stream1.fail()||in_stream2.fail())
	{
		cout<<"打开文件失败";
		exit(1);
	}
    cout<<"input the length :"<<endl;
	cin>>m>>n;
    int (*l)[7];
	l=new int[m][7];
	for(i=0;i<m;i++)	
		for(j=0;j<6;j++)
			*(*(l+i)+j)=0; 
	int (*b)[7]=new int[m][7];
	for(i=0;i<m;i++)	
		for(j=0;j<7;j++)
			b[i][j]='0';
    //cout<<"请输入数组p:\n";
	ch p=new char[m+1];
	p[0]='0';
    for(i=1;i<8;i++)
	in_stream1>>p[i];
	cout<<"序列A为:\n";
	for(i=1;i<8;i++)
	cout<<p[i]<<' ';
	cout<<endl;
	ch q=new char[n+1];
    //cout<<"请输入数组q:\n";
	q[0]='0';
    for(i=1;i<7;i++)
   in_stream2>>q[i];
    cout<<"序列B为:\n";
	for(i=1;i<7;i++)
	cout<<q[i]<<' ';
	cout<<endl;
    LCSLength(m,n,p,q,l,b);
	cout<<"最长公共自序列为:\n";
    LCS(m,n,p,b);
	in_stream1.close();
	in_stream2.close();
    system("pause");
    return 0;
}
void LCSLength(int m,int n,char *x,char *y,int (*c)[7],int (*b)[7])
//void LCSLength(int m,int n,char *x,char *y,int **c,int **b)
{
     int i,j;
         for(i=1;i<=m;i++) c[i][0]=0;
         for(i=1;i<=n;i++) c[0][i]=0;
            for(i=1;i<=m;i++)
               for(j=1;j<=n;j++){
                 if(x[i]==y[j]){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;}
                 }
}
void LCS(int i,int j,char *x,int (*b)[7])
//void LCS(int i,int j,char *x,int **b)
{
     if(i==0||j==0) return;
     if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i]<<' ';}
     else if(b[i][j]==2)LCS(i-1,j,x,b);
     else LCS(i,j-1,x,b);
}