c++文件实现.txt

动态规划下的最优子序列问题

#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
using namespace std;

int main()
{
	int i,j,k;
	int n1=0,n2=0;       //n1，n2分别存储两个字符串的长度
	char ch;
	string str;
/*	string str1="abcdef\n"; //输入的字符串要以"\n"结束
	string str2="abghcf\n";*/
	//把数据输入到文件 
	ofstream out;
/*	out.open("c:\\input1.txt");
	if(!out){
			cout<<"cannot open file..\n";
			return 1;
		}
	//out<<str;
	out << str1;//add by cacard
	out.close();
	out.open("c:\\input2.txt");
        if(!out){
			cout<<"cannot open file..\n";
			return 1;
		}
	//out<<str;
	out << str2;//add by cacard
	out.close();*/


	//读取第一个文件的字符串
	ifstream in;
	in.open("c:\\input1.txt"); 

        in.get(ch);
	while(ch!='\n')
	{
	  cout<<ch;
	  n1++;
	  in.get(ch);
	}
	cout<<endl;




        char *p1=new char[n1]; 
        in.seekg(ios::beg);    //返回文件开头重新读取
	for(i=0;i<n1;i++)
	{
		in.get(ch);
		if(ch!='\n')
		{
		    p1[i]=ch;
		    if(p1[i]==' ')  //忽略' '
		    i--;
		}
	}
	in.close();            //先关闭in,再读取第二个文件！
	//读取第二个文件的字符串
        in.open("c:\\input2.txt"); 
        in.get(ch);
	while(ch!='\n')
	{
	  cout<<ch;
	  n2++;
	  in.get(ch);
	  if(n2>10)break;
	}


	char *p2=new char[n2]; 
        in.seekg(ios::beg); 
	for(i=0;i<n2;i++)
	{
		in.get(ch);
		if(ch!='\n')
		{
		    p2[i]=ch;
		    if(p2[i]==' ')  //忽略' '
		    i--;
		}
	}
	in.close();
	//算法的执行过程
	 //为二维数组开辟空间
     int **b = new int*[n1+1];
     for ( i = 0;  i < n1+1;  i++)
    {
          b[i] = new int[n2+1];
    }
	 int **c = new int*[n1+1];
     for ( i = 0;  i < n1+1;  i++)
    {
          c[i] = new int[n2+1];
    }
	for(i=0;i<=n1;i++) {c[i][0]=0;b[i][0]=0;}
	for(i=0;i<=n2;i++) {c[0][i]=0;b[0][i]=0;}
	for(i=1;i<=n1;i++)
		for(j=1;j<=n2;j++)
			if(p1[i-1]==p2[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<=n1;i++)
 {
  for(j=0;j<=n2;j++)
      cout<<c[i][j]<<"  ";
  cout<<'\n';
 }
//输出b[i][j]
 cout<<'\n';
 for(i=0;i<=n1;i++)
 {

  for(j=0;j<=n2;j++)
      cout<<b[i][j]<<"  ";
  cout<<'\n';
 }
 //输出最长公共子序列
 char *p=new char[n1];       //动态一维数组，用来存储结果
	i=n1,j=n2,k=0;
	while(i!=0&&j!=0)
	{
		if(b[i][j]==1)
		{
			p[k]=p1[i-1];
			k++;
			i--;
			j--;
		}
		else if(b[i][j]==2)
		        i--;
		else j--;
	}
	//算法执行完毕
	//输出到文件
	cout<<"The LCSLength string: ";
        out.open("c:\\output.txt");
	if(!out){
			cout<<"cannot open file..\n";
			return 1;
		}
	cout << "output.txt:";
	for(i=k-1;i>=0;i--)
	{
		out<<p[i];        //输出到文件
		cout << p[i];     //屏幕显示
	}
        cout<<endl;
	out.close();
	//释放一维数组占用的空间
	delete[] p1;
	delete[] p2;
	delete[] p;
	//释放二维数组占用的空间
     for ( j = 0; j < n1+1; j++)
    {
          delete[] b[j];
    }
	      for ( j = 0; j < n1+1; j++)
    {
          delete[] c[j];
    }
    delete[] b;
    delete[] c;
    b = NULL;
    c = NULL;
    return 0;
}