c - 如何检查 C 中是否由完全相同的字符组成更多单词？

Question

我遇到以下问题:我需要输入直到 EOF 之前的单词以及之后的单词，以对由完全相同的字符(不一定是完全相同的字符数)组成的单词进行分组。

例如:

输入:

“abc”“acb”“abcabc”“cab”“de”“gh”“ab”“ed”“hg”“abcde”

输出:

"abc" "acb" "abcabc" "cab"
"de" "ed"
"gh" "hg"

我会记下我到目前为止所做的事情:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    char **groups, word[30], **store, n = 0, k = 0;
    store = malloc(1*sizeof(char *));
    if (store == NULL) exit(1);
    for (;;) {
        printf("Enter word: ");
        if (scanf("%s", word) == EOF) break;
        store[n] = malloc((strlen(word)+1)*sizeof(char));
        if (store[n] == NULL) exit(1);
        strcpy(store[n], word);
        n++;
        store = realloc(store, (n+1)*sizeof(char *));
        if (store == NULL) exit(1);
    }
    for (int i=0; i<n; i++) {
        printf("%s ", store[i]);
    }
    return 0;
}

问题是我真的不知道如何检查字符。你能帮我一下吗？

更新

我尝试按照@jarmod的建议进行操作:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    char **groups, word[30], **store, n = 0, k = 0, *aux;
    store = malloc(1*sizeof(char *));
    if (store == NULL) exit(1);
    for (;;) {
        printf("Enter word: ");
        if (scanf("%s", word) == EOF) break;
        store[n] = malloc((strlen(word)+1)*sizeof(char));
        if (store[n] == NULL) exit(1);
        strcpy(store[n], word);
        n++;
        store = realloc(store, (n+1)*sizeof(char *));
        if (store == NULL) exit(1);
    }
    for (int i=0; i<n; i++) {
        printf("%s ", store[i]);
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        for (int j=0; j<strlen(store[i])-1; j++) {
            for (int l=(j+1); l<strlen(store[i]); l++) {
                if (store[i][j] > store[i][l]) {
                    aux = store[i][j];
                    store[i][j] = store[i][l];
                    store[i][l] = aux;
                }
            }
        }
    }
    for (int i=0; i<n; i++) {
        printf("%s ", store[i]);
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        for (int j=0; j<strlen(store[i])-1; j++) {
                if (store[i][j] == store[i][j+1]) {
                    for (int l=j; l<strlen(store[i])-1; l++) {
                        store[i][l] = store[i][l+1];
                    }
                    j--;
                    store[i] = realloc(store[i], (strlen(store[i])-1)*sizeof(char));
                    if (store[i] == NULL) exit(1);
                }
        }

    }
    for (int i=0; i<n; i++) {
        printf("%s ", store[i]);
    }
    printf("\n");
    return 0;
}

Answer 1

有一种巧妙的方法可以确定单词属于哪一组。

我们必须创建一个方案，其中每个组都由一个数字唯一标识。我们如何定义和区分一个组:通过它包含的字母。重复的字母不算数(这是一组)。因此，我们需要一个公式来对一组字母进行编码。如果我们为每个字母分配一个数字(从 0 开始)，我们可以通过 2 的幂和获得 id(实际上可以选择任何基数，但 2 是计算的自然选择)。

例如:

"abdeae"这组字母是 {'a', 'b', 'd', 'e'} 。他们对应的号码是:{0, 1, 3, 4} ID 是 2^0 + 2^1 + 2^3 + 2^4 .

因为有26字母我们可以使用 32 位整数来编码 id。 2^i对应位i所以算法看起来像这样:

uint32_t letter_mask(char ch)
{
    assert(ch >= 'a' && ch <= 'z');

    return (uint32_t) 1u << (ch - 'a');
}

uint32_t word_group_id(const char * str)
{
    size_t len = strlen(str);

    uint32_t id = 0;

    for (size_t i = 0; i < len; ++i)
    {
        id |= letter_mask(str[i]);
    }

    return id;
}

<小时/>

现在我们有了一种简单的方法来确定单词组，您需要创建一个简化版本的 map 来放置单词。

这是我简单快速的实现。免责声明:未经测试。您还必须通过添加对 malloc 和 realloc 的检查来改进它。

typedef struct Word_map_bucket
{
    uint32_t id;
    char** words;
    size_t words_size;
} Word_map_bucket;

void init_word_map_bucket(Word_map_bucket* bucket, uint32_t id)
{
    bucket->id = id;
    bucket->words = NULL;
    bucket->words_size = 0;
}

typedef struct Word_map
{
    Word_map_bucket* buckets;
    size_t buckets_size;
} Word_map;

void init_word_map(Word_map* map)
{
    map->buckets = NULL;
    map->buckets_size = 0;
}

Word_map_bucket* find_bucket(Word_map map, uint32_t id)
{
    for (size_t i = 0; i < map.buckets_size; ++i)
    {
        if (map.buckets[i].id == id)
            return &map.buckets[i];
    }
    return NULL;
}


Word_map_bucket* add_new_bucket(Word_map* map, uint32_t id)
{
    map->buckets = realloc(map->buckets, map->buckets_size + 1);
    map->buckets_size += 1;

    Word_map_bucket* bucket = &map->buckets[map->buckets_size + 1];
    init_word_map_bucket(bucket, id);

    return bucket;
}

void add_word(Word_map* map, const char* word)
{
    // get to bucket
    uint32_t id = word_group_id(word);
    Word_map_bucket* bucket = find_bucket(*map, id);
    if (bucket == NULL)
        bucket = add_new_bucket(map, id);

    // increase bucket->words
    bucket->words = realloc(bucket->words, bucket->words_size + 1);
    bucket->words_size += 1;

    // push word into bucket
    bucket->words[bucket->words_size - 1] = malloc(strlen(word));
    strcpy(bucket->words[bucket->words_size - 1], word);
}