Сравнить массивы символов - PullRequest
Новая
       15

Сравнить массивы символов

2 голосов
/ 23 октября 2011

Если бы у меня был массив символов, например: 

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

И другой массив, например: 

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

Мне нужно сравнить слова в массиве A (которые разделенычерез пробел) в массив B, и если любое из слов в первом массиве существует во втором массиве, то это слово должно быть напечатано.Так, например, поскольку «слово» существует в первом массиве и во втором массиве, то «слово» должно быть распечатано.

Как мне поступить?

Ответы [ 3 ]

4 голосов
/ 23 октября 2011

Посмотрим, как бы я это сделал:

Вам понадобится функция, которая, учитывая массив 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 вы bsearch оно в B1 (это не плохое слово ... Это означает бинарный поиск, и это быстрый метод поиска чего-либо в упорядоченном массиве)

Готово: -)

Я добавлю, что, если вы впервые используете 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

1 голос
/ 23 октября 2011

В основном вам нужно как-то разделить слова, а затем перебирать комбинации.Есть сотни способов сделать это - просто требуется программирование.

0 голосов
/ 24 октября 2011

Вы также можете сделать это так:

  1. Вставьте все слова из набора A в набор C с суффиксом «A». Вы получите =>
    worngA
    wordA

  2. Вставьте все слова из набора B в набор C с суффиксом «B». Вы получите =>
    correctB
    wordB

  3. Запуск алгоритма сортировки на множестве C, например qsort. Вы получите =>
    correctB
    wordA
    wordB
    worngA

  4. Цикл в наборе C, пока он не станет размером 1. Сравните word[i] с word[i+1] - если они совпадают, кроме последней буквы - вы нашли дубликат и можете распечатать его.

Я не знаю, насколько сложен этот алгоритм, но он явно должен быть быстрее, чем простое сканирование всех словосочетаний: -)

...