在 C 中创建 Set ADT 时无法删除重复值

Question

我尝试使用动态数组在 C 中创建一个简单的 Set 抽象数据类型，只是为了学习目的。我实现了一个名为 buildSet() 的函数，该函数将结构 Set 作为参数，即要导入的元素数 n，后跟 n 个元素参数。我的问题是，正如我们从数学中知道的那样，我不应该允许重复的值。但我的代码无法通过这个要求。我实现了 Set 结构，没有错误，但是当我打印我的集合时，我发现存在重复项。

考虑以下示例

在主文件中:

Set S;
buildSet(&S, 6, 5, 20, 2, 3, -8, -8);
for (int i = 0; i < S.size; ++i) {
    printf("%d ", S.elems[i]);
}

预期输出是

5 20 2 3 -8

实际输出是

5 20 2 3 -8 -8

波纹管是我使用的结构:

typedef struct {
    int *elems; /* Array contains our set elements. */
    size_t size; /* Number of elements exist in set. */
    long maxSize; /* Maximum allowed number of elements in set. */
    long sum; /* Sum of all elements in set. */
    int *min; /* The minimum element in set. */
    int *max; /* The maximum element in set. */
} Set;

我使用的函数原型(prototype):

/**
 * Creates a set structure S 
 * with n elements x1,x2, x3,….
 */
void buildSet(Set *S, size_t n, ...);

/**
 * Checks whether the value x is in the set S.
 */
int isElementOfSet(Set *S, int x);

下面是函数体:

void buildSet(Set *S, size_t n, ...) {
    /**
     * Pass each argument, representing a set element,
     * from our variadic function to variadic list.
     */
    va_list setElems; 

    /**
     * Get the number of elements we want to pass
     * to our set.
     */
    va_start(setElems, n);

    /**
     * The number of elements in set structure.
     */
     S->size = 0;

    /**
     * Using this function we don't restrict ourselves
     * of using any number of elements for our set, so
     * we "unset" maxSize member.
     */
     S->maxSize = -1;

     /**
     * We initialize the sum counter. This will
     * allow us to get the sum using sumOfSet()
     * in O(1) time.
     */
     S->sum = 0;

    /**
     * Allocates memory for our set.
     */
    S->elems = malloc(sizeof(int)*(S->size));

    /**
     * Pass each set element, to our set
     * and update the sum counter.
     */
    int elem;
    for (size_t i = 0; i < n; ++i) {
        elem = va_arg(setElems, int);
        if (!isElementOfSet(S, elem)) {
            ++(S->size);
            S->elems = realloc(S->elems, sizeof(int)*(S->size));
            S->elems[(S->size)-1] = elem;

            S->sum += elem;
        }
    }

    /**
     * Frees the variadic list.
     */
    va_end(setElems);
}

int isElementOfSet(Set *S, int x) {
    /**
     * We use binary search in our array-set
     * to find if x belongs to S.
     */
    int middle, left = 0, right = (S->size)-1;
    while (left < right) {
        middle = (left + right)/2;
        if (S->elems[middle] == x) {
            return 1;
        } else {
            if (S->elems[middle] > x) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
    }

    return 0;
}

Answer 1

您已在方法 isElementOfSet 中使用了二分搜索。 <强> Binary Search 仅当数组的元素已排序时才能应用于该数组。我没有看到您在任何地方应用了某种排序。因此，我建议您将方法 isElementOfSet 更改为线性搜索。

int isElementOfSet(Set *S, int x) {

    int i;
    for(i = 0;i < S->size;++i)
    {
     if(S->elems[i] == x)
       return 1;
    }
    return 0;
}