如何完成 K&R 练习 2-4？

Question

我正在学习如何使用 k&r 书（《C 编程语言》）用 C 语言编写程序，但其中一个练习有问题。 它要求我检测并删除字符串 s1 中的一个字符，该字符与字符串 s2 中的任何字符匹配。

所以，说 s1 = "A";

s2 =“AABAACAADAAE”

我希望它返回“BCDE”

我知道我走在正确的道路上，我只是不知道如何很好地设计程序，你能给我任何额外的提示吗？ 我尝试阅读有关二叉搜索树算法的内容，但觉得它对于这个平凡的任务来说有点太先进了。

感谢大家！

/* An alternate version of squeeze(s1, s2) that deletes each character in
 * s1 that matches any character in the string s2
 *
 * [email protected]
 */

#include <stdio.h>
#include <string.h>

void squeeze(char s[], char t[]);

char string[] = "BAD";
char sstring[] = "ABC";

int
main(void)
{
    squeeze(string, sstring);
    return 0;
}

void
squeeze(char s[], char t[])
{
    int i, j, d;

    d = 0;
    if(strstr(s, t) == NULL)
        printf("%c", s[i]);
    s[j] = '\0';
}

Answer 1

很棒的书。 如果我是你，我会按照第 2.8 节中的挤压（）进行操作，但不是直接比较（s[i]！= c），我会编写并利用一个函数，

 int contains(char s[], int c)

如果字符串 s 包含 c，则该函数返回 1 , 否则为 0。 从简单的方法开始； 当它起作用时，您可以使用更复杂的解决方案来提高性能（二分搜索，但请注意，该问题不需要 s2 中的字符按特定顺序排列）。

Answer 2

二进制搜索对此来说太过分了。 您需要三个索引。 一个索引 (i) 用于遍历 s，一个索引 (k) 用于遍历 t，还有一个索引 (k) 用于遍历 t索引 (j) 来跟踪您在 s 中的位置，查找需要保留的字符，因为它们不在 t 中。 因此，对于 s 中的每个字符，检查它是否在 t 中。 如果不是，请将其保留在 s 中。

void squeeze(char *s, char *t) {
    int i, j, k;
    int found = 0;

    for(i = j = 0; s[i] != '\0'; i++) {
        found = 0;
        for(k = 0; t[k] != '\0' && (found == 0); k++) {
            if(t[k] == s[i]) {
                found = 1;
            }
        }

        if(found == 0) {
            s[j++] = s[i];
        }

    }

    s[j] = '\0';
}

Answer 3

这是我非常清晰和简单的答案，并有一些合乎逻辑的解释。

#include<stdio.h>
void squeeze();

在 main 中，我们输入测试的字符串和 wantbedelete 字符串，其中包含我们要从 yourstring 中删除的字符。

int main() 
{

    char yourstring[] = "AABAACAADAAE";
    char wantbedelete[] = "A";

    squeeze(yourstring, wantbedelete);
    printf("%s", yourstring);

    return 0;
}

挤压函数内部的逻辑如下，

• 然后在wantbedelete内部逐个字符循环
• ，对于wantbedelete<中找到的任何字符/em> 我们循环遍历整个 yourstring
• 然后，我们比较两个找到的字符是否不匹配，我们从 更新（保存）该字符yourstring 到 yourstring 所以基本上这里我们只是定义一个新索引（k）来跟踪和更新 现在只需要字符，
• 这里的技巧是，每次我们再次返回到循环遍历我们打算删除的每个字符的外循环时，我们都希望重置索引，以便最终得到唯一想要的字符串。

我强烈建议使用调试器并跟踪挤压函数内的每一行，以便您能够更清楚地理解逻辑。

void squeeze(char s1[], char s2[]) 
{
    int i, j, k;

    k = 0;
    for (i = 0 ; s2[i] != '\0' ; i++) /* loop for each char we want to delete with index i */
    {
        for (j = 0 ; s1[j] != '\0'; j++) /* loop for each char we want to keep with index j */
        {
            if (s2[i] != s1[j]) /* if the two chars do not match */
            {
                s1[k++] = s1[j]; /* update s1 with the char that we want to keep using index k */
            }
        }
        s1[k] = '\0'; /* since we update all char that we want to keep, the last char of index k must be empty */
        k = 0; /* reset index k so we will be ready for the next char that we want to delete from s1 */
    }
}

Answer 4

您不需要花哨的二分搜索来完成这项工作。 您需要的是一个双 for 循环，用于检查一个字符串中每个字符在另一个字符串中的出现情况，并将未出现的字符复制到第三个字符数组中（这是您的结果）。

代码可以如下所示（未经测试！）：

char *s1, *s2, *result; /* original strings and the result string */
int len1, len2; /* lengths of the strings */
for (i = 0; i < len1; i++) {
   for (j = 0; j < len2; j++) {
     if (s1[i] == s2[j]) {
       break;
     }
   }
   if (j == len2) {  /* s1[i] is not found in s2 */
     *result = s1[i]; 
     result++; /* assuming your result array is long enough */
   }
}

Answer 5

void squeeze(char s1[], char s2[])
{
    int i,j,k;
    char c;
    for(i=0;s2[i]!='\0';i++)
    {
        c=s2[i];
        for(j=k=0;s1[j]!='\0';j++)
            if(s1[j]!=c)
                s1[k++]=s1[j];
            s1[k]='\0';
    }
}

Answer 6

这是我的功能：

void squeeze(char s1[],char s2[])
{
int i,j,p;
int found;

p=0;
for(i=0;s1[i]!='\0';i++)
{
    for(j=0;s2[j]!='\0';j++)
        if(s1[i]==s2[j])
            found=YES;
        else
            found=NO;
    if(found==NO)
        s1[p++]=s1[i];
     }
    s1[p]='\0';
}