如何检查一个字符串是否存在于一个字符数组的数组中

Question

我正在寻找一种方法来检查一个特定的字符串是否存在于一个大型字符串数组中。这个数组是多维的：all_strings[strings][chars];。因此，这个数组实际上是一个字符数组的数组。每个字符数组以'\0'结尾。

给定另一个字符数组，我需要检查这些字符是否已经在all_strings中，类似于Python的in关键字。

我不太确定如何做到这一点，我知道strcmp可能有帮助，但我不确定如何实现它。

- JavascriptLoser

---

只需遍历您的all_strings列表，逐个字符串执行strcmp与您要比较的字符串（其他字符数组）进行比较。 - lurker

Answer 1

如lurker所建议的，朴素的方法是简单地在字符串数组上循环调用strcmp。他的string_in函数由于对sizeof(string_list)的误解而不幸失效，应该像这样：

。

#include <string.h>
int string_in(char *needle, char **haystack, size_t haystack_size) {
    for (size_t x = 0; x < haystack_size; x++) {
         if (strcmp(needle, haystack[x]) == 0) {
             return 1;
         }
    }
    return 0;
}

这种方法效率相对较低。如果您只偶尔使用它，特别是在一个小的字符串集合上使用它，那么这样做就可以了。但是，如果您正在寻找一种有效的方法来执行搜索，并且需要为每个搜索更改搜索查询，那么我考虑的两个选项是：

• 如果all_strings相对静态，则可以像这样对数组进行排序：qsort(all_strings, strings, chars, strcmp);…然后当您想确定单词是否存在时，可以使用bsearch执行二分查找，如下所示：char *result = bsearch(search_query, all_strings, strings, chars, strcmp);。请注意，当all_strings发生更改时，您需要再次对其进行排序。
• 如果all_strings更改得太频繁，您可能会从使用其他数据结构（例如trie或哈希表）中受益。

- autistic

Answer 2

使用for循环。C语言没有像Python中的in一样的内置函数：

int i;

for ( i = 0; i < NUM_STRINGS; i++ )
    if ( strcmp(all_strings[i], my_other_string) == 0 )
        break;

// Here, i is the index of the matched string in all_strings.
//   If i == NUM_STRINGS, then the string wasn't found

如果你希望它像Python中的in一样运行，你可以将其制作为一个函数：

// Assumes C99
#include <string.h>
#include <stdbool.h>

bool string_in(char *my_str, char *string_list[], size_t num_strings)
{
    for ( int i = 0; i < num_strings; i++ )
        if (strcmp(my_str, string_list[i]) == 0 )
            return true;

    return false;
}

- lurker

---

事实上，C++11有范围循环，类似于Python的in。 - user4098326

@user4098326 确实如此。但问题限制在C语言范围内。 - lurker

你的 string_in 函数是错误的... 请考虑 sizeof string_list 的值。 - autistic

@undefinedbehaviour 谢谢你指出这个问题。这就是我在感冒发烧期间回答 Stack Overflow 问题的后果。我已经纠正了它，因为我无法删除一个被接受的答案。 - lurker

Answer 3

你可以简单地检查一个字符串是否存在于一个字符串数组中。更好的解决方案可能是实际返回该字符串：

/*
 * haystack: The array of strings to search.
 * needle: The string to find.
 * max: The number of strings to search in "haystack".
 */
char *
string_find(char **haystack, char *needle, size_t max)
{
    char **end = haystack + max;
    for (; haystack != end; ++haystack)
        if (strcmp(*haystack, needle) == 0)
            return *haystack;
    return NULL;
}

如果您希望数组中的所有字符串都是唯一的，就可以将其视为一个集合来使用：

typedef struct set_strings {
    char **s_arr;
    size_t count;
    size_t max;
} StringSet;
.
.
.
int
StringSet_add(StringSet *set, const char *str)
{
    // If string exists already, the add operation is "successful".
    if (string_find(set->s_arr, str, set->count))
        return 1;

    // Add string to set and return success if possible.
    /*
     * Code to add string to StringSet would go here.
     */
    return 1;
}

如果您想实际操作字符串，也可以使用这种方式：

/*
 * Reverse the characters of a string.
 *
 * str: The string to reverse.
 * n: The number of characters to reverse.
 */
void
reverse_str(char *str, size_t n)
{
    char c;
    char *end;

    for (end = str + n; str < --end; ++str) {
        c = *str;
        *str = *end;
        *end = c;
    }
}
.
.
.
    char *found = string_find(words, word, word_count);
    if (found)
        reverse_str(found, strlen(found));

作为一个通用算法，它是相当有用的，甚至可以根据需要应用于其他数据类型（当然需要一些重新调整）。正如undefined behaviour's answer所指出的那样，它在大量字符串上不会很快，但对于简单和小型的东西来说已经足够好了。

如果您需要更快的东西，那个答案中给出的建议是很好的。如果您自己编写代码，并且能够保持事物排序，那么这是一个好主意。这使您能够使用比线性搜索更好的搜索算法。标准的bsearch很棒，但如果您想要适合快速插入的搜索例程，则可能需要一个搜索例程，该例程将为您提供插入新项的位置，以避免在bsearch返回NULL后搜索位置。换句话说，既然可以一次搜索并完成相同的事情，为什么要搜索两次呢？

- user539810

---

我很喜欢你适应了我的代码，使它从表格中返回字符串。这是朝着从集合中删除字符串的方向迈出的好步骤。我也很喜欢你引入的接口，使得更改StringSet_add使用其他集合变得非常简单。你通常开发关联数组数据结构和算法吗？如果你有GitHub资料，我很想关注一下。 - autistic

@undefinedbehaviour，老实说我没有Github个人资料。我也不常开发这样的结构和相关算法，但我发现当我这样做时，我的代码中的一个常见模式类似于我上面发布的内容。 - user539810

我发现当需要快速插入（或删除，或任何其他变化）时，其他数据结构更加适合。我倾向于偏爱PATRICIA，因为如你所提到的，可以返回要插入的位置（尽管插入过程需要更多信息，因此比简单地直接插入更复杂）。不过我很好奇... reverse_str 是什么意思呢？如果遇到回文会发生什么？ - autistic

@undefinedbehaviour 关于你的好奇心，除了我使用str != --end而不是str < --end这一事实之外，我不确定你指的是什么，如果使用偶数个字节进行交换，那将会导致可怕的结果。不过现在已经修复了。如果你问的是效率问题（为什么我没有在循环内部添加if (*str == *end)条件？），那是因为在我的机器上和其他机器上，无条件交换更快，而且分支指令相对于其他指令（尤其是数据移动指令）来说速度较慢。 - user539810