函数内部的 C 问题，在另一个单词中搜索一个单词并返回位置

Question

下面的 C 问题在 s2 中搜索 s1 并返回 s1 在 s2 中找到的位置。我写了这段代码，它适用于像 s1: car s2: carnal 这样的值，但如果我有 s1:car 和 s2: cbrcarnal 我认为它进入了一个无限循环或 smth 但它什么也不会显示。你们能看到吗问题？它必须在我的职能范围内。哦，我不允许使用 strstr。

代码:

#include "stdafx.h"
#include "stdio.h"
#include "string.h"

int subsir(char s1[],char s2[],int k)
{    int n,m,i=0,j,poz=-1;
n=strlen(s1);
m=strlen(s2);
if(n>m)
return -1;
j=k;
while(j<=m-n)
if((s1[i]==s2[j])&&(s1[n-1]==s2[j+n-1]))
{
    poz=j;
    while(j+1<poz+n-1)
        if(s1[i+1]==s2[j+1])
            {i++;
            j++;
            }
        else
            return subsir(s1,s2,poz++);
}
else
j++;

if(poz!=-1)
    return poz;
else
    return -1;
}

int _tmain(int argc, _TCHAR* argv[])
{char s1[30],s2[30];
int n;
printf("introduceti sirul 1: ");
scanf("%s",&s1);
printf("introduceti sirul 2: ");
scanf("%s",&s2);
n=subsir(s1,s2,0);
if(n!=-1)
    printf("%s is found in %s, at: %d\n",s1,s2,n);
else
    printf("s %s is not found in %s\n",s1,s2);

}

Answer 1

这是您的代码的格式化版本。我所做的唯一更改是注释、大括号、空格、声明变量更接近它们的使用位置、将一个 while 循环更改为 for 循环以及删除无效的后增量。它与您的代码完全相同:

int subsir(char s1[], char s2[], int k) {
    // Return location of s1 in s2, starting at index k in s2.

    int n = strlen(s1);
    int m = strlen(s2);
    if (n > m)  // s1 cannot be in s2
        return -1;

    int poz = -1;
    for (int j = k, i = 0; j <= m - n;) {
        // if first and last character in s1 match corresponding locations in s2
        if((s1[i] == s2[j]) && (s1[n - 1] == s2[j + n - 1])) {
            // save current s2 location in poz
            poz = j;
            while (j + 1 < poz + n - 1) {
                if(s1[i + 1] == s2[j + 1]) {
                    i++;
                    j++;
                }
                else {
                    return subsir(s1, s2, poz);
                }
            }
        }
        else {
            j++;
        }
    }

    return poz;
}

有了这个版本，您应该更容易发现问题:

• 我知道您已经想到并明确地写在某个地方(或者您只是从作业描述中阅读)，但它总是有助于您的思维过程包括一个简短的句子关于功能的目的。这是第一条评论。

• 我通常不会在我的代码中包含第二条和第三条注释，但我写的对象与您不同。解释“为什么”(针对第二条评论)以及更复杂的表达式如何工作(针对第三条评论)应该对您有所帮助。

• 第四条评论是指定 poz 服务的角色的开始。类似于简短的函数描述，您应该能够对每个变量进行简短的介绍。通常，对于变量 n、m、k、j 和 i，您不必将其显式地放入代码中 — 但如果您感到困惑，请开始添加它们。例如，“k 是要搜索的起始索引”、“n 是 s1 的长度”、“j 和 i 分别是 s2 和 s1 中的‘当前’位置”，等等。

  <

• 我删除的后增量是在 return 语句中，但由于控制永远不会返回到此函数(因此永远不会再次使用 poz)，它没有影响。

• 您检查了 poz 是否为 -1，如果是，则返回 -1；否则返回poz。这和直接返回poz是一样的。

• 你修改了 i，但是如果控制从那个 while 循环中逃脱，你永远不会将它重置为零；因此，您永远不会从 s1 的开头开始搜索。

• 因为您在递归调用中从 poz(而不是 poz + 1)开始，所以您陷入了一个循环，不断地一遍又一遍地检查相同的位置。 (传递 poz + 1 可以解决这个问题。)

从这里继续，我会将您的内部循环重构为一个单独的函数，执行与 strncmp 等效的操作——或者如果可以的话，直接使用 strncmp。更大的模块化使问题更容易推理。

这里不需要递归，但以这种方式对问题进行建模很好:

• 如果s1在s2中从位置k开始，返回k
• else 调用 subsir(s1, s2, k + 1) 在下一个位置搜索
  • 这通常是在循环中而不是递归调用中完成的，但是通过尾调用优化，它是完全一样的