比较字符数组

Question

例如，如果我有一个字符数组：

A = [w, o, r, n, g, , w, o, r, d]

另一个数组例如：

B = [c, o, r, r, e, c, t, , w, o, r, d, .]

我需要将数组 A 中的单词（以空格分隔）与数组 B 进行比较，并且第一个数组中的任何单词是否存在于第二个数组，那么应该打印该单词。例如，由于“word”存在于第一个数组和第二个数组中，因此应该打印出“word”。

我该怎么办？

Answer 1

让我们看看我会怎么做：

您将需要一个函数，给定一个 char 数组，将其拆分为一个单词数组（并将它们放入 C 字符串中，请以 NUL 结尾:-)） 。我会将该数组的长度和该数组放入一个结构中

struct WordCollection
{
    size_t NumWords;
    char **Words;
}

...现在如何执行此功能？

假设我们“作弊”了一点，并决定我们的数组 A 和 B 以 NUL 终止（或者如果它们像 B 一样以 . 终止，然后将 . 替换为 NUL）。现在，这是 C 语言，您应该首先计算字符串中的空格数，分配一个足以包含 char* (WordCollection::Words) 的数组>n + 1 char* （并将此 n + 1 放入 WordCollection::NumWords 中）并使用 strtok “标记”字符串并放置您创建的数组中的单词。

那么你应该（可以）使用这个函数将 A 和 B 数组分割成单词。您将获得两个 WordCollection：A1 和 B1。

为了使其更快，我会 qsort B1。

然后，对于 A1 中的每个单词，您在 B1 中 bsearch 它（它不是这是一个坏词...它的意思是二分搜索，它是一种在有序数组中搜索某些内容的快速方法）

完成 :-)

如果这是您第一次使用 bsearch 和qsort，您最好查看周围可以找到的示例。它们的语法可能很“棘手”。

现在...我知道你不会看代码 :-) 所以我会把它放在这里

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

struct WordCollection
{
    size_t NumWords;
    char **Words;
};

void splitWord(char *str, struct WordCollection *wc)
{
    char *c;
    char **currentWord;

    c = str;

    wc->NumWords = 1;

    while (*c != '.')
    {
        if (*c == ' ')
        {
            wc->NumWords++;
        }

        c++;
    }

    *c = '\0';

    wc->Words = (char**)malloc(wc->NumWords * sizeof(char*));

    c = strtok(str, " ");

    currentWord = wc->Words;

    while (c)
    {
        *currentWord = c;
        currentWord++;

        c = strtok(NULL, " ");
    }
}

int myComp(const void *p1, const void *p2)
{
    return strcmp(*(const char**)p1, *(const char**)p2);
}

int main(void)
{
    char a[] = { 'w', 'o', 'r', 'n', 'g', ' ', 'w', 'o', 'r', 'd', '.' };
    char b[] = { 'c', 'o', 'r', 'r', 'e', 'c', 't', ' ', 'w', 'o', 'r', 'd', '.' };

    struct WordCollection a1, b1;
    struct WordCollection *pSmaller, *pBigger;

    size_t i;

    splitWord(a, &a1);
    splitWord(b, &b1);

    if (a1.NumWords <= b1.NumWords)
    {
        pSmaller = &a1;
        pBigger = &b1;
    }
    else
    {
        pSmaller = &b1;
        pBigger = &a1;
    }

    qsort(pBigger->Words, pBigger->NumWords, sizeof(char*), myComp);

    for (i = 0; i < pSmaller->NumWords; i++)
    {
        void *res = bsearch(&pSmaller->Words[i], pBigger->Words, pBigger->NumWords, sizeof(char*), myComp);
        if (res)
        {
            printf("Found: %s", pSmaller->Words[i]);
        }
    }

    free(a1.Words);
    free(b1.Words);

    return 0;
}

并放在 ideone

Answer 2

基本上，您需要以某种方式分离单词，然后迭代组合。有一百种方法可以做到这一点——它只需要编程。

Answer 3

您也可以这样做：

1. 将集合 A 中的所有单词插入集合 C 中，并带有后缀“A”。你会得到 =>
   worngA
wordA

2. 将集合 B 中的所有单词插入到集合 C 中，并带有后缀“B”。你会得到 =>
   rightB
wordB

3. 在集合C上运行排序算法，例如qsort。你会得到 =>
   correctB
wordA
wordB
worngA

4. 在集合C中循环，直到它尺寸-1。将 word[i] 与 word[i+1] 进行比较 - 如果它们除了最后一个字母之外都匹配 - 您发现重复的内容，您可以将其打印出来。

我不知道这个算法的复杂性，但它显然应该比暴力扫描所有单词组合更快:-)