2

我有两个清单。

char *name[] =  {"RGS", "O", "NRGY", "SIG", "BML-O", "BHI", "KSU", "ORN"};
char *name_to_remove[] =  {"RGS", "O", "NRGY"};

有没有一种有效的方法来获取项目列表并将其从另一个列表中删除？我已经实现了自己的版本，但我认为它的效率很低。它基本上是复制名称列表，然后使用嵌套的 for 循环遍历重复的名称和 name_to_remove 列表并将任何重复的项目标记为“删除”。最后，我浏览列表并复制所有项目，但值为“删除”的项目除外。它非常丑陋，我怀疑效率低下。我遇到的一个问题（以前没有处理过）是我不确定如果数组在内存中的大小是固定的，是否可以从数组中删除一个项目，所以我最初试图改变值，然后将值添加到新数组中（与原始数组大小相同 - 我要删除的项目数组的大小）。

我看不到更好的方法，memcmp 似乎很有希望，因为它可以比较两个列表，但我无法弄清楚它是如何适合的。我知道 C 不是 python，但这是我在 python 中干净利落的方法：

for item in name_to_remove:
    name_copy.remove(item)

也许在幕后，python 命令正在执行与我一样多的循环，但我想我会问。

4

6 回答 6

2

答案是使用适当的数据结构。Python 列表绝对不是作为纯 C 字符串数组实现的（只是因为您可以在 Python 列表中存储不同类型的对象）。因此，您要查找的数据结构可能是链表或哈希表。

于 2012-06-03T02:39:57.260 回答
1

它基本上是复制名称列表，然后使用嵌套的 for 循环遍历重复的名称和 name_to_remove 列表并将任何重复的项目标记为“删除”。最后，我浏览列表并复制所有项目，但值为“删除”的项目除外。

无需标记任何内容，您可以只复制您在其中找到的任何不存在的项目name并将其存储name_to_remove在新数组中，然后丢弃旧name数组。

于 2012-06-03T02:40:59.170 回答
1

如果字符串的顺序无关紧要，您可以对两个数组进行排序以查找重复项，如下所示：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARR_SIZE(array) sizeof(array)/sizeof(const char *)

int compare (const void * a, const void * b) {
    return strcmp(*((const char**)a), *((const char**)b));
}

int main(void) {
    const char *name[] =  {"RGS", "O", "NRGY", "SIG", "BML-O", "BHI", "KSU", "ORN"};
    const char *name_to_remove[] =  {"RGS", "O", "NRGY"};
    int i = 0, j = 0;
    qsort(name, ARR_SIZE(name), sizeof(const char*), compare);
    qsort(name_to_remove, ARR_SIZE(name_to_remove), sizeof(const char*), compare);
    while (i != ARR_SIZE(name) && j != ARR_SIZE(name_to_remove)) {
            int diff = strcmp(name[i], name_to_remove[j]);
            if (diff == 0) {
                    name[i] = NULL;
                    i++;
                    j++;
            } else if (diff < 0) {
                    i++;
            } else {
                    j++;
            }
    }
    for (i = 0 ; i != ARR_SIZE(name) ; i++)
            if (name[i])
                    printf("%s\n", name[i]);
    return 0;
}
于 2012-06-03T03:19:39.510 回答
0

我想python版本并不比你的代码效率高。

也就是说，您当然可以改进您的实施。请记住，C 数组实际上只是一块内存，带有一堆指向字符串开头的指针。由于您没有创建新字符串，因此您始终可以重用字符串指针。

从概念上讲，循环遍历您的数组，如果值在要删除的列表中，则将指针设置为 null。然后使用 malloc() 创建一个适当大小的新数组。遍历旧数组，将非空指针复制到新数组。

这样你就有了 2 次循环迭代和一个 malloc。

于 2012-06-03T02:40:57.113 回答
0

如果您在编译时分配第一个数组，那么它的大小是固定的，我相信随后不可能通过“删除”选定的元素来回收任何内存。我建议要么实现一个您可以动态分配的链表，然后free()在您希望删除项目时实现部分，或者更好的是，实现一个更有效的数据结构，例如二叉搜索树。

于 2012-06-03T02:44:17.743 回答
0

您可以制作一个哈希映射，然后遍历一个数组并通过测试mapOfRemovableWords.contains(words[i])并使用它来决定是否应该将元素复制到一个新数组（或自身的前面）。

您还可以对两个数组进行排序，然后同时遍历它们。使用这样一个事实，即如果您处于某个单词大于另一个列表中的当前单词的位置，那么它不在另一个列表中。你迭代一个，然后决定是否需要迭代另一个，然后重复，直到你完全完成了两个。

于 2012-06-03T02:40:51.253 回答