strcmp的实现

Question

我尝试实现strcmp：

int strCmp(char string1[], char string2[])
{
    int i = 0, flag = 0;    
    while (flag == 0) {
        if (string1[i] > string2[i]) {
            flag = 1;
        } else
        if (string1[i] < string2[i]) {
            flag = -1;
        } else {
            i++;
        }
    }
    return flag;
}

但是我遇到了一个问题，用户会输入相同的字符串，因为这个函数使用了1和-1，但是它不返回0。有人可以帮忙吗？请不要使用指针！

- blackFish

---

可能是优化的strcmp实现的重复。 - Box Box Box Box

Answer 1

呃...太复杂了。选这个吧：

int strCmp(const char* s1, const char* s2)
{
    while(*s1 && (*s1 == *s2))
    {
        s1++;
        s2++;
    }
    return *(const unsigned char*)s1 - *(const unsigned char*)s2;
}

它按预期返回小于0、等于0或大于0

如果不使用指针是无法完成的。在C语言中，对数组进行索引实际上就是使用指针。

也许您想避免使用 * 操作符？:-)

- Gianluca Ghettini

Answer 2

首先，标准C函数strcmp将字符串元素视为unsigned char类型进行比较。

其次，参数应该是指向常量字符串的指针，以便对常量字符串进行比较。

可以按照以下方式编写该函数：

int strCmp( const char *s1, const char *s2 )
{
    const unsigned char *p1 = ( const unsigned char * )s1;
    const unsigned char *p2 = ( const unsigned char * )s2;

    while ( *p1 && *p1 == *p2 ) ++p1, ++p2;

    return ( *p1 > *p2 ) - ( *p2  > *p1 );
}

- Vlad from Moscow

---

我个人更喜欢 while ( *p1 && *p1 == *p2 ) {++p1, ++p2}，不过其他方面都很好。 - Superlokkus

@Superlokkus 循环可以像这样编写：for ( const unsigned char *p1 = ( const unsigned char * )s1, *p2 = ( const unsigned char * )s2; *p1 && *p1 == *p2; ++p1, ++p2 ); 正如您所看到的，循环没有主体（语句）。它还有另一个问题：指针 p1 和 p2 在循环外部是需要的。 - Vlad from Moscow

@Superlokkus 为了使循环体，只需将表达式作为表达式语句放置在循环外部。在这种情况下，它看起来像 char *p1 = ( const unsigned char * )s1, *p2 = ( const unsigned char * )s2; while (; *p1 && *p1 == *p2 ) ++p1, ++p2 ;; 因此，我们有相同的原始循环，但循环的初始化部分和表达式部分都像一个语句一样放置在循环外部。 - Vlad from Moscow

我想我们在这里遇到了一个定义问题：在我看来，循环的主体，或者至少是while循环的主体，是在每次循环迭代中执行的语句，但不是条件语句。因此，我的建议只是将while(COND) BODY;转换为while(COND) {BODY}。 - Superlokkus

@Superlokkus 对不起，我觉得我们可能无法彼此交流出新的东西。:) - Vlad from Moscow

Answer 3

看起来您想避免指针算术运算，这很可惜，因为它可以使解决方案更简短，但您的问题仅仅是因为扫描超出了字符串的结尾。添加一个明确的中断语句就可以解决问题。以下是稍作修改的程序:

int strCmp(char string1[], char string2[] )
{
    int i = 0;
    int flag = 0;    
    while (flag == 0)
    {
        if (string1[i] > string2[i])
        {
            flag = 1;
        }
        else if (string1[i] < string2[i])
        {
            flag = -1;
        }

        if (string1[i] == '\0')
        {
            break;
        }

        i++;
    }
    return flag;
}

简化版：

int strCmp(char string1[], char string2[] )
{
    for (int i = 0; ; i++)
    {
        if (string1[i] != string2[i])
        {
            return string1[i] < string2[i] ? -1 : 1;
        }

        if (string1[i] == '\0')
        {
            return 0;
        }
    }
}

- Daniel B.

Answer 4

这是一个使用10个操作码实现的strcmp函数（假设使用GCC编译器）

int strcmp_refactored(const char *s1, const char *s2)
{
    while (1)
    {
        int res = ((*s1 == 0) || (*s1 != *s2));
        if  (__builtin_expect((res),0))
        {
            break;
        }
        ++s1;
        ++s2;
    }
    return (*s1 - *s2);
}

您可以尝试此实现并与其他实现进行比较：https://godbolt.org/g/ZbMmYM

- Larytet

Answer 5

我的实现

int strcmp(const char * s1, const char * s2)
{
    while (*s1 == *s2 && *s1++ | *s2++);
    int i = *s1 - *s2;
    return i < 0 ? -1 : i > 0 ? 1 : 0;
}

返回值

-1 // <0
1  // >0
0  // ==0

最后一个三元操作是可选的。

当您只返回“* s1- * s2”时，该函数仍符合“strcmp”的规则。

- Beyondo

---

你正在比较空元素。例如：strcmp("foobar\0b", "foobar\0a") 返回1，但实际上应该返回0（标准库中的strcmp也是如此）。请尝试使用以下代码：while (*s1 && *s1 == *s2) {s1++; s2++;} - damisan

Answer 6

你的问题在于没有检测字符串的结尾，因此如果在检测到任何差异之前两个字符串都已经结束，则不会返回零。

你可以通过在循环条件中进行检查来简单地解决这个问题：

while( flag==0 && (string1[i] != 0 | string2[i] != 0 ) )

请注意，两个字符串都会被检查，因为如果只有一个字符串在末尾，那么字符串就不相等，循环内的比较应该能够检测到这一点。

请注意，字符比较可能不会产生您期望的结果。首先，未定义char是有符号还是无符号，因此您应该将其转换为unsigned char进行比较。

也许更清晰的解决方案是在检测到差异时立即返回，即不是flag = -1而是直接返回-1。但这更多是一个观点问题。

- skyking

---

&& 是多余的，因为你已经知道在这个阶段 string1[i] == string2[i]。 - zakinster

如果string1为零且string2不为零，则继续while会导致未定义的行为。 - Peter Miehle

在这种情况下，如果 string1[i]<string2[i] 为真，则您将停止返回 -1。 - zakinster

@zakinster 很好的建议，我决定跳过那个解决方案，而是在循环条件中进行检查。 - skyking

@zakinster 不完全是这样，你知道如果有的话，string1[i]在上一次迭代中等于string2[i]。然而，在while语句中的第二个测试检查我们是否到达了任何一个字符串的结尾，因此它仍然是必需的——字符串"a\0z"和"a\0y"应该相等。 - skyking

如果你指的是string1为NULL，那么这不是问题。据我所知，如果任何参数为NULL，则strcmp具有未定义的行为（然后一个具有未定义行为的实现是可以接受的）。 - skyking

Answer 7

从这里获取的内容。

#include<stdio.h>
#include<string.h>
 
//using arrays , need to move the string using index
int strcmp_arry(char *src1, char *src2)
{
    int i=0;
    while((src1[i]!='\0') || (src2[i]!='\0'))
    {
        if(src1[i] > src2[i])
            return 1;
        if(src1[i] < src2[i])
            return -1;
        i++;
    }
 
    return 0;
}
//using pointers, need to move the position of the pointer
int strcmp_ptr(char *src1, char *src2)
{
    int i=0;
    while((*src1!='\0') || (*src2!='\0'))
    {
        if(*src1 > *src2)
            return 1;
        if(*src1 < *src2)
            return -1;
        src1++;
        src2++;
    }
    return 0;
}
 
int main(void)
{
    char amessage[] = "string";
    char bmessage[] = "string1";
    printf(" value is %d\n",strcmp_arry(amessage,bmessage));
    printf(" value is %d\n",strcmp_ptr(amessage,bmessage));
}

我做了一些更改，使其像strcmp一样工作。

- Box Box Box Box

---

你复制错了，漏掉了负号。 - technosaurus

Answer 8

另一种优雅（但不是最“干净”的代码）的实现方式，使用指针。

int a_strcmp(char* t, char* s)
{
    for( ; *t == *s ; *s++ , *t++)
        if(*t == '\0')
            return 0;
    return *t - *s;
}

不使用指针的版本。

int b_strcmp(char t[], char s[])
{
    int i;
    for(i = 0; s[i] == t[i]; ++i)
        if(t[i] == '\0')
            return 0;
    return t[i] - s[i];
}

- Anton K

---

你跳过了字符串的第一个字符，因此 strcmp("a", "b") 会比较相等。 - Olaf Dietsche

修改了帖子，Olaf，发现得好，谢谢！ - Anton K

不要在while条件内递增。例如，第一个“i++”将返回零/假，导致相等的结果，即使字符串不同strcmp（“abc”，“abd”）。对于第一种实现也是如此。考虑 strcmp("\0a", "")，这将在第一个字符后中断并比较不相等，尽管它应该返回零。请使用多个输入测试两种实现，并验证它们是否按预期工作。 - Olaf Dietsche

再次感谢，已经改用for循环实现，其中增量更加直观。 - Anton K

在 *s++ , *t++ 中，你不需要星号。 - Lover of Structure