我可以使用动态内存分配来减小 int 数组的大小然后重新分配内存吗？

Question

我创建了一个程序，它计算列表中 string 被找到的次数，并将该数字打印在屏幕上并将其保存在 int *arr 中。但是，当有两个相同的 strings 时， count 结果显然在 output/list 中打印并存储了两次。我的问题是：我可以检查一个词是否被找到两次，如果是，那么 free 那个内存块并使用 realloc() 为整个 int *arr 重新分配内存？这是我的 sortedCount() 方法，它执行我上面所说的到目前为止：

void sortedCount(int N) {
    int *wordCount;
    int i = 0;
    wordCount = malloc(N * sizeof(int));
    for(i = 0; i < N; i++) {
        wordCount[i] = count(N,wordList[i],1);
    }
    /* free mem */
    free(wordCount);
    return;
}

Answer 1

假设您有一个包含 words 个单词的动态分配数组：

char  **word;
size_t  words;

如果您想知道唯一单词的数量，以及它们在数组中重复的次数，您可以使用简化版本的 disjoint-set data structure 和计数数组。

想法是我们有两个数组，每个数组包含 words 个元素：

size_t *rootword;
size_t *occurrences;

rootword 数组包含该词第一次出现的索引，occurrences 数组包含每个词第一次出现的次数。

例如，如果 words = 5 和 word = { "foo", "bar", "foo", "foo", "bar" }，则 rootword = { 0, 1, 0, 0, 1 } 和 occurrences = { 3, 2, 0, 0, 0 }。

要填充 rootword 和 occurrences 数组，首先将两个数组初始化为 "all words are unique and occur exactly once" 状态：

    for (i = 0; i < words; i++) {
        rootword[i] = i;
        occurrences[i] = 1;
    }

接下来，您使用双循环。外层循环遍历独特的单词，跳过重复的单词。我们通过将 occurrence 计数设置为零来检测重复项。内部循环遍历我们不知道是否唯一的单词，并挑选出当前唯一单词的重复项：

    for (i = 0; i < words; i++) {

        if (occurrences[i] < 1)
            continue;

        for (j = i + 1; j < words; j++)
            if (occurrences[j] == 1 && strcmp(word[i], word[j]) == 0) {
                /* word[j] is a duplicate of word[i]. */
                occurrences[i]++;
                rootword[j] = i;
                occurrences[j] = 0;
            }
    }

在内循环中，我们显然忽略了已知重复的单词（并且 j 仅迭代 occurrences[j] 只能是 0 或 [=29 的单词=]).这也加快了后面词根的内循环，因为我们只比较候选词，而不是那些我们已经找到词根的词。

让我们看看在 word = { "foo", "bar", "foo", "foo", "bar" } 输入的循环中发生了什么。

 i ╷ j ╷ rootword  ╷ occurrences ╷ description
───┼───┼───────────┼─────────────┼──────────────────
   │   │ 0 1 2 3 4 │ 1 1 1 1 1   │ initial values
───┼───┼───────────┼─────────────┼──────────────────
 0 │ 1 │           │             │ "foo" != "bar".
 0 │ 2 │     0     │ 2   0       │ "foo" == "foo".
 0 │ 3 │       0   │ 3     0     │ "foo" == "foo".
 0 │ 4 │           │             │ "foo" != "bar".
───┼───┼───────────┼─────────────┼──────────────────
 1 │ 2 │           │             │ occurrences[2] == 0.
 1 │ 3 │           │             │ occurrences[3] == 0.
 1 │ 4 │         1 │   2     0   │ "bar" == "bar".
───┼───┼───────────┼─────────────┼──────────────────
 2 │   │           │             │ j loop skipped, occurrences[2] == 0.
───┼───┼───────────┼─────────────┼──────────────────
 3 │   │           │             │ j loop skipped, occurrences[3] == 0.
───┼───┼───────────┼─────────────┼──────────────────
 4 │   │           │             │ j loop skipped, occurrences[4] == 0.
───┼───┼───────────┼─────────────┼──────────────────
   │   │ 0 1 0 0 1 │ 3 2 0 0 0   │ final state after loops.

我可以使用动态内存分配来减小 int 数组的大小然后重新分配内存吗？

Can i use dynamic memory allocation to reduce an int array's size and then reallocate memory?

c

malloc

pointers

realloc