c语言 - 我可以使用动态内存分配来减小 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;

如果您想知道唯一单词的数量以及它们在数组中重复的次数，可以使用不相交集数据结构的简化版本和计数数组。

我们的想法是，我们有两个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.