我可以使用动态内存分配，以减少一个int数组的大小，然后重新分配内存？

Question

我创建了一个程序，计算有多少次在列表中string已经发现，并在屏幕上的这个数字，并在int *arr保存它。然而，当存在两个相同strings，所述count结果显然是印刷＆在输出/存储列表两次。我的问题是：我可以检查一个字已被发现两次，如果是这样，那么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阵列，你首先初始化两个数组，以“所有的字都是唯一的，出现一次”的状态：

    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和1仅迭代），其是已知的是重复的单词。这也加速了后来词根内循环，因为我们仅对比候选词，而不是那些我们已经找到了一个词根的单词。

让我们来看看在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.