一个简单的C语言库用于一组整数集合是什么?

8
我需要修改一份C程序,其中需要包含一组无符号整数集。也就是说,我有数百万个整数集(每个整数集包含3到100个整数),我需要将它们存储在某种结构中,我们称之为目录,以便可以在对数时间内告诉我是否已经存在给定的整数集。目录上唯一需要定义的操作是查找和插入。
在具有内置支持有用数据结构的语言中,这将很容易,但我对C是外行,并且在Google上寻找(令人惊讶地)没有令我满意的答案。这个项目看起来很合适:http://uthash.sourceforge.net/,但我需要自己设计哈希键生成器。
这是一个标准、简单的问题,因此我希望有一个标准、简单的解决方案。
4个回答

3
这取决于您要对数据做什么。但是也许tsearch已经满足了您的需求。您也可以为每个集合构建一个排序数组,并使用bsearch查找值,尽管在插入过程中性能可能会受到影响。
编辑:如果您正在寻找(外部)库,则可以在这里找到一些C和C++哈希表实现的比较。文章作者编写了一个通用头文件实现,称为khash。因此,您编译后的二进制文件不需要任何其他依赖项。

1
tsearch非常适合管理通用元素的二叉树。它不会重复添加元素,因此我们可以将其用于集合。 - iomartin

0

编辑:抱歉,我开始回答时以为是C语言而不是C++。那么你应该自己找到哈希函数并编写代码。既然你已经知道了集合的平均维度,那么选择一个好的哈希函数就不难了!但如果你想检查目录是否已经存在,你需要将整个集合编码成一个数字。

你可以尝试迭代地对集合中的单个数字进行哈希:

int hashcode = initvalue
for (int i = 0; i < 0; ++i)
  hashcode = calc_code(hashcode, number_set[i], i);

以一种方式,哈希函数取决于其先前的值、当前的数字和当前的索引。

那STL集合呢?

#include <set>

int nums[6] = {1,6,34,2,67,41};
set<int> numbers;

for( int i = 0; i < 6; ++i ) numbers.insert(nums[i]);

for( set<int>::const_iterator iter = numbers.begin(); iter != numbers.end(); ++iter )
  cout << *iter << ' ';

使用这个数据结构,您可以轻松地存储所有集合,但您还需要一种方法来检查目录中是否已经包含了一个集合。不清楚:您想知道目录中是否已经存在一个具有完全相同元素的集合吗?
您可以通过手动检查所有元素来完成,但由于您有数百万个元素,因此应找到一种方法将集合的元素哈希为唯一数字,并使用映射集合的映射表。

OP 问了一个关于 C 程序的问题,而 STL 是纯粹的 C++。 - David Thornley
STL是用于C++的,这个问题被标记为“C”。 - Remo.D
是的,抱歉,我编辑了它 :) 刚醒来..还有点迷糊。 - Jack

0

如果我理解正确的话,您想要表示一组整数集合,这并不是特别简单的。

第一点是要表示一组整数。最简单的方法是使用可变大小数组,如下所示:

typedef struct { 
  int size;
  int elems[1];
} intset;

你可以使用以下代码创建一个包含固定元素数量的新集合:

intset *newset(int size) 
{ 
  intset *set;
  set = malloc(sizeof(intset) + sizeof(int)*(size-1));
  if (set) set->size = size;
  return set;
}

并将元素存储在set->elems[0]=i1; ...中。

另一个选择是使用位数组,但实现取决于要存储的整数的性质(例如,它们是否在固定范围内?它们通常以集合形式出现吗?)。

一旦您拥有整数集,您将需要一个比较函数(用于确定两个集合是否具有相同的元素)。如果您选择使用数组表示集合并保持该数组排序,则很容易检查两个集合是否相同;如果是位图,则取决于您如何实现它。

现在,对于集合的集合,您可以选择(排序的)向量,在插入元素时可能需要不时调整大小,或哈希表。在后一种情况下,您将需要为整数集编写哈希函数(可能使用现有函数!)。

正如我所说,这对我来说似乎并不简单,我不惊讶谷歌没有帮助。

虽然不是非常复杂,但在继续之前,您只需做出一些决策即可。


我很惊讶地听到这不是微不足道的,因为在其他语言中(甚至是类似的C++和其STL),这将是微不足道的。整数值是无符号的,并且在某个固定范围内(即在运行时而非编译时已知范围),在大多数情况下在0到1000万之间,尽管在某些情况下在0到1亿之间。如果我使用哈希表,是否有任何哈希函数适用?Zoborist哈希是否适用于此处? - conradlee

-4

自己实现一个简单的哈希表,这将使你成为一个更好的程序员。知道如何独立完成一个哈希表的实现,将对你的编程技能有所帮助。

http://en.wikipedia.org/wiki/Hash_table


6
尽管亲手实现可能会让我成为一名更好的程序员,但这并不是一个很好的答案。如果我仅仅想成为一名更好的程序员,可能有更好的练习可以让我花时间去做。此外,我不太可能实现出最优解,并且实现高性能的解决方案可能需要花费大量时间。我觉得奇怪的是,没有像 C++ 的 STL 那样的库可以给我一个简单的解决方案,而我需要重新发明(或重新实现)轮子。 - conradlee
1
你并没有真正回答这个问题。 - Jaco Pretorius

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接