[算法]写了一个最长公共字符串算法，关于里面一个死循环的体会

dskongenius 发表于 2008/11/9 22:42:21

vc9.0下面编译通过，写了半个小时，调试了四个小时，原来递归时产生了一个死循环，后来终于找到错误所在，看来以前没有理解递归的真正用法。 #include <iostream>#include <string> using namespace std; //此结构体用于存储两个字符串的相交点,第一个整数为公共字符在第一个串的位置，第二个整数为同样的公共字符在第二个串中的位置struct disjoint{ int x; int y;}; //比较三个整数，返回最大的整数int max(int a,int b,int c){ int maxNum=a; if(maxNum<b)  maxNum=b; if(maxNum<c)  maxNum=c; return maxNum;} //此函数对两个字符串计算最大公共子序列，返回最大子序列的长度int lcs(string a,string b,int **pStr){ for(int i=0;i<=b.length();++i)  pStr[0][i]=0; for(int i=0;i<=a.length();++i)  pStr[i][0]=0; for(int i=1;i<=a.length();++i)  for(int j=1;j<=b.length();++j)  {   if(a[i-1]==b[j-1])    pStr[i][j]=max(pStr[i][j-1],pStr[i-1][j],pStr[i-1][j-1]+1);   else    pStr[i][j]=max(pStr[i][j-1],pStr[i-1][j],pStr[i-1][j-1]);  }  return pStr[a.length()][b.length()];} //递归核心void comStr(string a,string b,int **pStr,int current,char *cs,disjoint *pdj,int row,int col,int length){ if(current>=0)//此处形成一个死循环，形成原因值得注意，很隐蔽的一个死循环      //如果把if(current>=0)改为while(current>=0)那么就是一个死循环      //具体原因如下：假设输入字符串为"abacd"和"ad"，那么程序的执行路径为      //(3)->(2)->(2)->(2)->(3)->(2)->(3)->(2)->(3)->(2)->(3)……      //可以看出，已经形成了一个死循环(2)->(3) {  if(pStr[row][col]==pStr[row][col-1])                           //(1)   comStr(a,b,pStr,current,cs,pdj,row,col-1,length);          //(2)  if(pStr[row][col]==pStr[row-1][col])   comStr(a,b,pStr,current,cs,pdj,row-1,col,length);  if(a[row-1]==b[col-1]&&pStr[row][col]==pStr[row-1][col-1]+1)   //(3)  {   cs[current]=a[row-1];   pdj[current].x=row-1;   pdj[current].y=col-1;   comStr(a,b,pStr,current-1,cs,pdj,row-1,col-1,length);  }  } else  if(current == -1)  {   for(int i = 0;i<length;++i)    cout<<"("<<cs[i]<<" "<<pdj[i].x<<","<<pdj[i].y<<")";   cout<<endl;  }} //此函数为递归驱动器，求出所有的公共字符串，并且输出到标准输出void findComStr(string a,string b,int **pStr,int length){ //初始化工作 char *cs=new char[length]; disjoint *pdj=new disjoint[length]; int current = length-1; int row=a.length(),col=b.length();  //调用递归核心 comStr(a,b,pStr,current,cs,pdj,row,col,length);  //释放动态申请的空间 delete []cs; delete []pdj;} int main(){ //从标准输入读入两个字符串 string a; cout<<"Please input the first string:"<<endl; cin>>a; string b; cout<<"Please input the second string:"<<endl; cin>>b;  //动态申请一个二维数组，行和列分别比两个字符串的长度大1，用于动态规划 int lenOfa = a.length(); int lenOfb = b.length(); int **pStr = new int*[lenOfa+1]; for(int i=0;i<=lenOfa;++i)  pStr[i] = new int[lenOfb+1];  //求出公共字符的个数 int lenCS=lcs(a,b,pStr); cout<<endl; cout<<endl; cout<<"输出结果："<<endl; cout<<"总共有"<<lenCS<<"个公共字符"<<endl;  //求出所有的公共字符串 cout<<"所有的公共字符串列表如下（每行为一个公共字符串，字母为公共字符，第一个数字"<<endl; cout<<"为该字符在第一个字符串中的位置，第二个数字为该字符在第二个字符串中的位置。）："<<endl; findComStr(a,b,pStr,lenCS);   //释放动态申请的数组空间 for(int i=0;i<=lenOfa;++i)  delete []pStr[i]; delete []pStr; return 0;}