关于网友提出的“ 数据结构课程设计（求完整代码） 给定两个串X和Y，①求子串在主串中的所有位置 并记录②找出X和Y的一个最长公共子串。③置换①所定位的所有子串。”问题疑问，本网通过在网上对“ 数据结构课程设计（求完整代码） 给定两个串X和Y，①求子串在主串中的所有位置 并记录②找出X和Y的一个最长公共子串。③置换①所定位的所有子串。”有关的相关答案进行了整理，供用户进行参考，详细问题解答如下：
问题： 数据结构课程设计（求完整代码） 给定两个串X和Y，①求子串在主串中的所有位置 并记录②找出X和Y的一个最长公共子串。③置换①所定位的所有子串。描述:
数据结构课程设计（求完整代码） 给定两个串X和Y，①求子串在主串中的所有位置 并记录②找出X和Y的一个最长公共子串。③置换①所定位的所有子串。
解决方案1:
#include "stdio.h"解决方案2:
#include "string.h"
#include "stdlib.h"
const int n=200;
int c[n][n];
char str[n];
#define MaxSize 100
typedef struct
{
char data[MaxSize];
int length; //串长
}SqString;
void StrAssign(SqString &str,char cstr[]) //str为引用型参数
{
int i;
for (i=0;cstr[i]!='\0';i++)
str.data[i]=cstr[i];
str.data[i]='\0';
str.length=i;
}
void GetNextval(SqString t,int nextval[]) //由模式串t求出nextval值
{
int j=0,k=-1;
nextval[0]=-1;
while(j<>
{
if (k==-1 || t.data[j]==t.data[k])
{
j++;
k++;
if(t.data[j]!=t.data[k])
nextval[j]=k;
else
nextval[j]=nextval[k];
}
else k=nextval[k];
}
}
int KMPIndex1(SqString s,SqString t,int start) //修正的KMP算法，start变量保存每次匹配的起始位置
{
int nextval[MaxSize],i=0,j=0;
GetNextval(t,nextval);
i=start;
while(i<><>
{
if(j==-1 || s.data[i]==t.data[j])
{
i=i+1;
j++;
}
else
j=nextval[j];
}
if (j>=t.length)
return (i-t.length);
else
return -1;
}
int lcs_len(char a[],char b[],int c[][n])
{
int sa=strlen(a);
int sb=strlen(b);
int i,j;
for(i=0;i<=sa;i++)
c[i][0]=0;
for(j=0;j<=sb;j++)
c[0][j]=0;
for(i=1;i<=sa;i++)
{
for(j=1;j<=sb;j++)
{
if(a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else if(c[i][j-1]> c[i-1][j])
c[i][j]=c[i][j-1];
else c[i][j]=c[i-1][j];
}
}
return c[sa][sb];
}
char* bulid_lcs(char a[],char b[])
{
int k=0,i,j;
i=strlen(a);
j=strlen(b);
k=lcs_len(a,b,c);
str[k]= '\0 ';
while(k>0)
{
if(c[i][j]==c[i-1][j])
i--;
else if(c[i][j]==c[i][j-1])
j--;
else
{
str[--k]=a[i-1];
i--;
j--;
}
}
return str;
}
void main()
{
char a[n],b[n],change[n];
SqString s,t;
int p[n],m,i=1,j,k,h,start;
printf("Please enter two strings!\n");
printf("Please enter first string: ");
gets(a);
printf("Please enter second string: ");
gets(b);
printf("Please the new string: ");
gets(change);
StrAssign(s,a);
StrAssign(t,b);
start = 0,j=0;
bulid_lcs(a,b);
if(str[0]==' ')
printf("这两个字符串没有公共字符串！\n");
else
{
printf("The max length common subsequence is: ");
puts(str); //找出X和Y的一个最长公共子串
}
while(1) //求子串在主串中的所有位置，并记录
{
if(start>=s.length)
break;
m=KMPIndex1(s,t,start);
if(m!=-1)
{
printf("第%d次匹配的位置为:%d\n",i++,m);
p[j++]=m;
start = m+t.length;
}
else
{
printf("这两个字符串不匹配！\n");
break;
}
}
if(j==0)
printf("这两个字符串无法匹配，无法替换！\n");
else
{
for(i=0;i<>
{
h=p[i];
for(k=0;k<>
a[h++]=change[k];
}
printf("字符串a被替换后为：");
puts(a);
}
system("pause");
}
#include “stdio.h”
#define MAXNUM 200
void replace(char chString[],char chOldWord[],char chNewWord[])
{
int i,nStartPos=0,nLen1=0,nLen2=0,nLen3=0,nFound;
/*计算旧词和新词的长度*/
while(chOldWord[nLen2++]!='\0');
nLen2--;
while(chNewWord[nLen3++]!='\0');
nLen3--;
/* chString中可能有多个旧词，均要替换为新词；
利用循环向前拨动查找位置，逐次进行比较和替换*/
while(chString[nStartPos]!='\0')
{
/*从nStartPos位置开始，Len2长度的字符串是否和旧词相同？*/
nFound=1;
for(i=0;i<>
if(chString[nStartPos+i]!=chOldWord[i])
{
nFound=0;
break;
}
if(nFound==1)/*相同，这Len2个字符需要被替换掉*/
{
/*计算输入字串chString 的长度，注意在循环中每次计算chString
长度是必要的，因为完成一次替换后，chString的长度可能发生变化*/
while(chString[nLen1++]!='\0');
nLen1--;
/*新词、旧词长度可能不同，先将chString长度调至正确的位置，
chString中nStartPos 后的字符可能需要前移或后移若干位*/
if(nLen3-nLen2>=0)/*新词比旧词长，从后向前移动*/
{
for(i=nLen1-1;i>=nStartPos;i--)
chString[i+nLen3-nLen2]=chString[i];
}
else/*新词比旧词短，从前向后移动*/
{
for(i=nStartPos+nLen2;i<>
chString[i+nLen3-nLen2]=chString[i];
}
chString[nLen1+nLen3-nLen2]='\0';
/*将新词复制到chString，替换原来的旧词 */
for(i=0;i<>
chString[nStartPos+i]=chNewWord[i];
/*下一次检查的位置：从替换后新词后面的位置开始*/
nStartPos+=nLen3;
}
else/*不同，则从下一个字符开始，继续进行检查*/
nStartPos++;
}
}
main()
{
char chStr[MAXNUM],chOld[MAXNUM],chNew[MAXNUM];
/*输入原始字符串、被替换串和替换串*/
printf("\nPlease input the original string:\n");
gets(chStr);
printf("Please input the word to be replaced:\n");
gets(chOld);
printf("Please input the new word to replace:\n");
gets(chNew);
/*调用函数进行替换*/
replace(chStr,chOld,chNew);
/*输出结果*/
printf("The processed string = %s",chStr);
}
分析
程序运行结果如下：
Please input the original string:
Tom want to go to school, Tom's father said...
Please input the word to be replaced:
Tom
Please input the new word to replace:
Jimmy
The processed string = Jimmy want to go to school, Jimmy's father said...