已知一个非纯集合B，试构造一个纯集合A，使得A中只包含B中所有值各不相同的数据元素。用c语言实现，写出代码，并计算时间复杂度

首先定义纯集合为元素互不相同的集合，非纯集合为元素可能重复的集合。

构造纯集合A的思路是遍历非纯集合B，将B中每个不同的元素添加到集合A中。这可以通过使用一个哈希表来实现。哈希表的键存储B中的元素，值为任意非NULL的指针。遍历B时，对于每个元素，将其作为键在哈希表中查找。如果键不存在，则将其添加到哈希表中，并将值设置为任意非NULL的指针。如果键已经存在，则跳过该元素。

以下是使用C语言实现的代码：

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

#define MAX_SIZE 100 // 假设B中最多有100个元素

typedef struct {
    int* keys[MAX_SIZE];
    void* values[MAX_SIZE];
    int size;
} HashSet;

void initializeHashSet(HashSet* set) {
    set->size = 0;
    memset(set->keys, 0, sizeof(set->keys));
    memset(set->values, 0, sizeof(set->values));
}

int hash(int key) {
    return abs(key) % MAX_SIZE;
}

void addToHashSet(HashSet* set, int key, void* value) {
    int index = hash(key);
    while (set->keys[index] != NULL) {
        if (*(set->keys[index]) == key) {
            return; // 键已存在，直接返回
        }
        index = (index + 1) % MAX_SIZE; // 线性探测下一个空槽
    }
    set->keys[index] = malloc(sizeof(int));
    *(set->keys[index]) = key;
    set->values[index] = value;
    set->size++;
}

void freeHashSet(HashSet* set) {
    for (int i = 0; i < MAX_SIZE; i++) {
        if (set->keys[i] != NULL) {
            free(set->keys[i]);
        }
    }
}

int main() {
    int B[MAX_SIZE] = {1, 2, 3, 2, 4, 1, 5}; // 非纯集合B
    HashSet A;
    initializeHashSet(&A);
    for (int i = 0; i < MAX_SIZE; i++) {
        if (B[i] == 0) {
            break;
        }
        addToHashSet(&A, B[i], NULL);
    }
    // 打印纯集合A中的元素
    printf("Pure set A: ");
    for (int i = 0; i < MAX_SIZE; i++) {
        if (A.keys[i] != NULL) {
            printf("%d ", *(A.keys[i]));
        }
    }
    printf("\n");
    freeHashSet(&A);
    return 0;
}

时间复杂度分析：对于每个元素，需要在哈希表中进行查找或添加操作，最坏情况下需要线性探测MAX_SIZE个槽位。因此，总时间复杂度为O(MAX_SIZE^2)。但是，我们可以通过调整哈希函数或使用更好的哈希表实现来优化时间复杂度。