c - 在这种情况下我应该使用什么样的数据结构？

Question

我有一个函数，它在循环内调用，它可以为每个循环生成一组整数，例如:

循环 1 的结果:{1 1 1 2}
循环 2 的结果:{1 1 1 3}
循环 3 的结果:{2 1 1 3}
循环 4 的结果:{3 1 3 2}

并且该函数可能会产生重复的结果，例如结果2和结果3是相同的。我需要将这些结果放入一个数据结构中，但不能放入重复项，如果结果2与结果3相同，则只保留其中一个，如何在C中实现？

Answer 1

如果项目范围足够小，可以使用位图作为枚举的手段。例如。如果要表示 1 到 32 范围内的整数集，所需的只是用作位图的 32 位整数:

00000001 00000001 00000000 00000000    - for set {8,16}
       ^        ^
       8        16

等等

如果范围较大，则使用字节数组，其中每个位代表该位置的值是否存在于集合中:

#define MAXVAL 1024

typedef unsigned char bitmap_t[];
byte bitmap[1 + MAXVAL / CHAR_BIT] = { 0 };
// CHAR_BIT is defined in limit.h and is equal to count of bits in a byte

void insert(bitmap_t bitmap, unsigned val) {
  assert(val < MAXVAL);
  bitmap[val / CHAR_BIT] |= (1 << (val % CHAR_BIT);
}

int is_present(bitmap_t bitmap, unsigned val) {
  assert(val < MAXVAL);
  return bitmap[ val / CHAR_BIT ] & (1 << (val % CHAR_BIT));
}