我正在尝试创建一个ADT。
它是有限元素的动态集合。它必须使用数组和链接列表来实现。
某些操作包括add(set, x)和remove(set, x)。
我知道我首先需要创建一个数组实现和链表实现都通用的接口。
但是，我不确定该数据类型的结构。我应该包括什么？
struct test {
int x;
char y;
};
像那样的东西？或者说我使集合不包含整数，数据结构将涉及什么？
帮助将不胜感激。谢谢！
最佳答案
由于这是上学的时间，因此我不会为您提供实施方案，但会为您指明正确的方向。使用数组和列表会尖叫“哈希表”。有关一些好的信息，请参见this answer。
为简单起见，我们假设它是一组整数。
本质上，您需要N个“存储桶”（即列表）的数组hash_table。要添加元素x，请执行hash_table[hash(x) % N]以获取（列表），应将x放入其中，如果尚未在列表中，则将其添加到该列表中。
要删除x，请执行hash_table[hash(x) % N]来获取存储桶，并删除x（如果有）。
如果可以实现这些功能，则search(set, x)是微不足道的。您也可以尝试实现union(setA, setB)，intersect(setA, setB)，difference(setA, setB)，isSubset(setA, setB)等。您可能还想细读the Wikipedia article on the Set ADT，并检查The Algorithm Design Manual中的条目，其中包括指向实现的链接。底部。
祝您好运，编码愉快。如果您遇到困难，可以随时在此处询问，下次再发布代码即可。 :)