lcs（c实现）.txt

最优自序列问题

/* 标准文档模板 */

#include "Stdio.h"
#include "Conio.h"


main()
{

int m,n;
int **c,**b;
char *x,*y,*z;
int i,j,k;
char ch;
FILE *rp;
FILE *wp;
m=0;
n=0;
/*从文件中读两个序列，并且将两都存到数组x,y中*/
rp=fopen("input.txt","r");
   if(rp==NULL)             /*判断文件是否打开成功*/
      printf("File open error");/*提示打开不成功*/
      ch=fgetc(rp);
   while(ch!='\n'){
     m++;
     ch=fgetc(rp);
   }
   printf("m=%d\n",m); /*第一个序列的长度m*/
     rewind(rp);
/* 从文件中读出两个序列，并且算出两者的长度*/
x=(char*)malloc(m*sizeof(char));
z=(char*)malloc(m*sizeof(char));
for(i=0; i<m;i++){fscanf(rp,"%c",x+i);if(*(x+i)==' ')i--;}
for(i=0;i<m;i++)printf("%c",*(x+i));  /*在屏幕显示出第一个序列*/
printf("\n");
  ch=fgetc(rp);
  while(ch!='\n')ch=fgetc(rp);
   printf("\n");
     ch=fgetc(rp);
   while(ch!='\n'){
     n++;
     ch=fgetc(rp); }
   printf("n=%d\n",n); /*第二个序列长度n*/
   rewind(rp);
 y=(char*)malloc(n*sizeof(char));
  fseek(rp,(m+2)*sizeof(char),0);
 for(i=0;i<n;i++){fscanf(rp,"%c",y+i);if(*(y+i)==' ')i--;}
 for(i=0;i<n;i++)printf("%c",*(y+i)); /*在屏幕上显示出第二个序列*/
  /*为数组b,c分配空间 */
  c=(int*)malloc((m+1)*sizeof(int));
  for(i=0;i<=m;i++)
  *(c+i)=(int*)malloc((n+1)*sizeof(int));
  b=(int*)malloc((m+1)*sizeof(int));
  for(i=0;i<=m;i++)
  *(b+i)=(int*)malloc((n+1)*sizeof(int));
/* */
  fclose(rp);
  printf("\n");

 /*求得两个序列的最长公共子序列的长度*/
 /*初始化数组c和b*/
     for(i=0;i<=m;i++){*(*(c+i)+0)=0;*(*(b+i)+0)=0; }
     for(j=0;j<=n;j++){*(*(c+0)+j)=0; *(*(b+0)+j)=0; }

      for(i=1;i<=m;i++)
      for(j=1;j<=n;j++){
         if(*(x+i-1)==*(y+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;}}
 printf("\n");
 printf("the length of maxlongstring is:%d\n",*(*(c+m)+n)); /*最长公共子序列的长度*/
 /*输出c[i][j]*/
 printf("\n");
 for(i=0;i<=m;i++){
  for(j=0;j<=n;j++)
   printf("%2d",*(*(c+i)+j));
   printf("\n");}
   /*输出b[i][j]*/
 printf("\n");
 for(i=0;i<=m;i++){
  for(j=0;j<=n;j++)
   printf("%2d",*(*(b+i)+j));
   printf("\n");}
  /*输出最长公共子序列。这里的是非递归算法*/
   i=m;
   j=n;
   k=0;
   while(i!=0&&j!=0){
    if(*(*(b+i)+j)==1){*(z+k)=*(x+i-1);k++;i--;j--;}
        else if(*(*(b+i)+j)==2){i--;}
          else j--;

   }
   printf("the maxlongstring is:");
   for(i=k-1;i>=0;i--)printf("%c",*(z+i));  /*在屏幕上显示出最长的公共子序列*/
   /*输出到output.txt文件 */
   wp=fopen("output.txt","w+");
    for(i=k-1;i>=0;i--)fprintf(wp,"%c",*(z+i));
    fclose(wp);

    free(x);
    free(y);
    free(z);
    free(c);
    free(b);
  getch();
  return 0;
}