LCS.rar_LCS_lcs dynamic

/* 标准文档模板 */ #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; }