1

这是我试图解决但无法找到更简单方法的问题：-

编写一个函数 squeez，删除 s1 中与字符串 s2 中的任何字符匹配的每个字符。

到目前为止我所做的是以下代码： -

#include<stdio.h>
#include<string.h>
char *mysqueeze(char *a, char *b);
int main(void)
{
    int j = 0;
    char s1[100] = "krishna";
    char s2[100] = "kareem";
    char real[100];
    char *t = mysqueeze(s1,s2);
    for (int i = 0; i <= strlen(t); i++)  //1
        if (t[i] != '*')
    real[j++] = t[i];
    real[j] = '\0';        //4

    printf("%s\n", real);
}

char *mysqueeze(char *a, char *b)
{
    int i = 0, k;
    do
    {
        k = 0;
        while (b[k] != '\0')
        {
            if (a[i] == b[k]) {
                a[i] = '*';
                break;
            }
            k++;
        }
        i++;
    }
    while (a[i]);
    return a;
}

如何改进此代码？如何将 1 到 4 移动到代码的循环部分？

4

2 回答 2

1

我希望这不是在回答家庭作业问题，但即使是这样，我想既然你已经有了一个可行的解决方案，我在技术上不会为他们做任何人的家庭作业。

我下面的两个解决方案都实现了原地崩溃算法，如果适用于该问题，这肯定是最有效的方法。如果问题需要崩溃到另一个缓冲区的解决方案，则所需的修改将是最小的。正如 Paul Griffiths 在他的解决方案中提到的，最有效的解决方案（对于大型干草堆）涉及预先计算针布尔值的查找表。我在mysqueeze3()下面实现了这样的解决方案。请注意，如果要重复使用同一组针，最好将函数拆分为两个单独的函数，一个用于初始化针数组，然后mysqueeze实现将采用指向针数组查找表的指针而不是指向字符串的指针。

在实施任何解决方案时，您都需要验证它是否正确处理重复的针字符。为了测试这一点，我将您的 haystack 字符串扩展为四个相同字母的序列。您原始帖子的解决方案正确处理了这种情况。我的两个解决方案也都能正确处理这种情况。

可能应该注意，虽然mysqueeze3()比 更有效mysqueeze2()，但前者不是通用解决方案，而后者是。查找表解决方案取决于char大小为 8 位（或更小）；即，最多有 256 个针值。如果char系统上的 a 为 9 位或更大，则需要相应地修改该解决方案。如果char您系统上的 a 是 16 位或更大（可能是 unicode！），那么查找表解决方案就变得不切实际了。

#include<stdio.h>
#include<string.h>
typedef enum {false=0, true=1} bool;
char *mysqueeze(char *a, char *b);
char *mysqueeze2(char *haystack, const char *needles);
char *mysqueeze3(char *haystack, const char *needles);
void mysqueeze_griffiths(const char * first, const char * second, char * result);

int main(void)
{
    int j = 0;
    char s1[100] = "kkkkrrrriiiisssshhhhnnnnaaaa";
    char s2[100] = "kareem";
    char real[100];
    char *t = mysqueeze(s1,s2);
    for (int i = 0; i <= strlen(t); i++)  //1
        if (t[i] != '*')
           real[j++] = t[i];
    real[j] = '\0';        //4

    printf("mysqueeze:           %s\n", real);

    char s3[100] = "kkkkrrrriiiisssshhhhnnnnaaaa";
    char s4[100] = "kareem";
    printf("mysqueeze2:          %s\n", mysqueeze2(s3,s4));

    char s5[100] = "kkkkrrrriiiisssshhhhnnnnaaaa";
    char s6[100] = "kareem";
    printf("mysqueeze3:          %s\n", mysqueeze3(s5,s6));

    char s7[100] = "kkkkrrrriiiisssshhhhnnnnaaaa";
    char s8[100] = "kareem";
    char result[100];
    mysqueeze_griffiths(s7,s8, result);
    printf("mysqueeze_griffiths: %s\n", result);

}

char *mysqueeze(char *a, char *b)
{
    int i = 0, k;
    do
    {
        k = 0;
        while (b[k] != '\0')
        {
            if (a[i] == b[k]) {
                a[i] = '*';
                break;
            }
            k++;
        }
        i++;
    }
    while (a[i]);
    return a;
}

void mysqueeze_griffiths(const char * first, const char * second, char * result) {
    while ( *first ) {
        bool found = false;
        while ( *second ) {
            if ( *first == *second++ ) {
                found = true;
                break;
            }
        }
        if ( !found ) {
            *result++ = *first;
        }
        ++first;
    }

    *result = '\0';
}

char *mysqueeze2(char *haystack, const char *needles)
{
    char *dest=haystack, *src=haystack;
    while (*src)
    {
        const char* n;
        for (n=needles; *n; ++n)
        {
            if (*n==*src)
            {
                ++src;
                break;
            }
        }
        if (!*n)
           *dest++ = *src++;
    }
    *dest = '\0';
    return haystack;
}

char *mysqueeze3(char *haystack, const char *needles)
{
    char *dest=haystack, *src=haystack;
    bool needleArray[256];
    memset(needleArray,0,sizeof(needleArray));
    for (const char* n=needles; *n; ++n)
        needleArray[(unsigned char)*n] = true;
    while (*src)
    {
        if (needleArray[(unsigned char)*src])
            ++src;
        else
           *dest++ = *src++;
    }
    *dest = '\0';
    return haystack;
}
于 2013-09-17T18:10:55.503 回答
0

要真正回答您的问题，将 1 到 4 移动到函数中的最明显方法是real作为第三个参数传递。但是，将其中的字符替换为a然后'*'复制其他字符是不必要的步骤。像这样更好：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void mysqueeze(const char * first, const char * second, char * result);

int main(void) {
    char first[] = "krishna";
    char second[] = "kareem";
    char result[100];

    mysqueeze(first, second, result);

    printf("Result: %s\n", result);

    return EXIT_SUCCESS;
}

void mysqueeze(const char * first, const char * second, char * result) {
    while ( *first ) {
        const char * t_second = second;
        bool found = false;
        while ( *t_second ) {
            if ( *first == *t_second++ ) {
                found = true;
                break;
            }
        }
        if ( !found ) {
            *result++ = *first;
        }
        ++first;
    }

    *result = '\0';
}

实现该算法有更省时的方法，例如，通过第二个字符串并在数组中为每个存在的字符设置一个标志，因此与第一个字符串的每次比较都可以在单个常量中完成 -时间查询。

已编辑：添加变量t_second以响应 phonetagger 的评论。

于 2013-09-17T17:31:13.767 回答