LCS.rar_visual c

#include "iostream.h" #include "stdio.h" #include "stdlib.h" static int e; //标志位 防止重复走走过的路径 int LCS(char *,char *); void ShowCS(int *,int,int,int,char *); void findplace(int *,int *,int,int,int,int,int,int,char *); void main() { char *A,*B,*p; char ch; int n,i,count; cout << endl; cout << " ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" <<endl; cout << " ◎---ＷＥＬＣＯＭＥ　ＴＯ　ＤＩＳＰＬＡＹ---◎" << endl; cout << " ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" <<endl; cout << endl; do { A=(char *)malloc(81); B=(char *)malloc(81); cout<<" 请选择手动输入（H）还是随机产生字符串（R）？"; cin>>ch; while(ch!='H' && ch!='h' && ch!='R' && ch!='r') { cout<<" 请选择手动输入（H）还是随机产生字符串（R）？"; cin>>ch; } if(ch=='H' || ch=='h') { cout<<" 请输入字符串A："; cin.get(); //吸收前面的回车键 cin.getline(A,81); cout<<" 请输入字符串B："; cin.getline(B,81); } else if(ch=='R' || ch=='r') { cout<<" 请输入要产生的字符串A的字符数：（<=80）"; cin>>n; for(i=0,p=A;i<n;i++,p++) { *p=char(rand()%26+65); } *p=0; cout<<" 请输入要产生的字符串B的字符数：（<=80）"; cin>>n; for(i=0,p=B;i<n;i++,p++) { *p=char(rand()%26+65); } *p=0; cout << " " ; for(p=A;*p!=0;p++) { cout<<*p; } cout<<endl; cout << " " ; for(p=B;*p!=0;p++) { cout<<*p; } cout<<endl; } cout<<" 它们的最长子序列有："<<endl; count=LCS(A,B); free(A); free(B); cout<<" 这两个字符串的最长子序列长为："<<count<<endl; cout << " ----------------------------------------------" << endl; cout<<" 是否继续比较其他字符串？（Y/N）"; cin>>ch; }while(ch=='Y' || ch=='y'); cout << " ---To Be End---" <<endl; } int LCS(char *A,char *B) { int n=0,m=0,i,j,lcs; char *p; int *L; p=A; while(*p!=0) { n++; p++; } p=B; while(*p!=0) { m++; p++; } L=(int *)malloc((n+1)*(m+1)*sizeof(int)); //用一维数组模拟二维数组 for(i=0;i<=n;i++) { *(L+i*(m+1))=0; } for(j=0;j<=m;j++) { *(L+j)=0; } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(*(A+i-1)==*(B+j-1)) *(L+i*(m+1)+j)=*(L+i*(m+1)+j-m-2)+1; else if(*(L+i*(m+1)+j-1)>*(L+i*(m+1)+j-m-1)) *(L+i*(m+1)+j)=*(L+i*(m+1)+j-1); else *(L+i*(m+1)+j)=*(L+i*(m+1)+j-m-1); } } lcs=*(L+n*m+n+m); ShowCS(L,n,m,lcs,A); free(L); return lcs; } void ShowCS(int *L,int n,int m,int count,char *A) { int *LCS; LCS=(int *)malloc(count*sizeof(int)); e=0; findplace(L,LCS,0,0,n,m,0,count,A); free(LCS); } void findplace(int *L,int *LCS,int i,int j,int n,int m,int num,int count,char *A) { int t=0; if(m-j>=count-num && n-i>=count-num && *(L+i*(m+1)+j)==*(L+i*(m+1)+j+1) && *(L+i*(m+1)+j)==*(L+(i+1)*(m+1)+j)) { if(*(L+i*(m+1)+j)+1==*(L+(i+1)*(m+1)+j+1)) { *(LCS+num)=i+1; t=1; num++; if(num==count) { cout << " " ; for(int p=0;p<count;p++) { cout<<*(A+*(LCS+p)-1); } cout<<endl; t=0; num--; } if(t==1) { e=0; i++; j++; findplace(L,LCS,i,j,n,m,num,count,A); } } else { if(e==0) findplace(L,LCS,i,j+1,n,m,num,count,A); e=1; findplace(L,LCS,i+1,j,n,m,num,count,A); } } }