linux c 不重复数据结构

在Linux C编程中，确保数据结构中的元素不重复是一个常见的需求。以下是一些基础概念和相关的数据结构类型，以及它们的优势、应用场景和可能的解决方案。

基础概念

哈希表（Hash Table）：一种通过哈希函数将键映射到值的数据结构，提供快速的插入、删除和查找操作。
集合（Set）：一种不允许重复元素的数据结构。
红黑树（Red-Black Tree）：一种自平衡二叉查找树，用于维护有序的数据集合。

数据结构类型及其优势

1. 哈希表

优势：

平均时间复杂度为O(1)的插入、删除和查找操作。
适用于需要快速访问和修改的场景。

应用场景：

实现字典、映射等功能。
缓存数据以提高访问速度。

示例代码：

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

typedef struct HashNode {
    int key;
    int value;
    struct HashNode* next;
} HashNode;

typedef struct {
    HashNode** table;
    int size;
} HashTable;

HashTable* createHashTable(int size) {
    HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));
    hashTable->table = (HashNode**)malloc(sizeof(HashNode*) * size);
    for (int i = 0; i < size; i++) {
        hashTable->table[i] = NULL;
    }
    hashTable->size = size;
    return hashTable;
}

unsigned int hashFunction(int key, int size) {
    return abs(key) % size;
}

void insert(HashTable* hashTable, int key, int value) {
    unsigned int index = hashFunction(key, hashTable->size);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashTable->table[index];
    hashTable->table[index] = newNode;
}

int search(HashTable* hashTable, int key) {
    unsigned int index = hashFunction(key, hashTable->size);
    HashNode* node = hashTable->table[index];
    while (node != NULL) {
        if (node->key == key) {
            return node->value;
        }
        node = node->next;
    }
    return -1; // Not found
}

void delete(HashTable* hashTable, int key) {
    unsigned int index = hashFunction(key, hashTable->size);
    HashNode* node = hashTable->table[index];
    HashNode* prev = NULL;
    while (node != NULL && node->key != key) {
        prev = node;
        node = node->next;
    }
    if (node == NULL) return; // Not found
    if (prev == NULL) {
        hashTable->table[index] = node->next;
    } else {
        prev->next = node->next;
    }
    free(node);
}

int main() {
    HashTable* hashTable = createHashTable(10);
    insert(hashTable, 1, 100);
    insert(hashTable, 2, 200);
    printf("Value for key 1: %d\n", search(hashTable, 1));
    delete(hashTable, 1);
    printf("Value for key 1 after deletion: %d\n", search(hashTable, 1));
    return 0;
}

2. 集合（Set）

优势：

自动处理重复元素。
提供高效的成员检查和插入操作。

应用场景：

需要确保元素唯一性的场景。
实现集合运算（并集、交集、差集）。

示例代码：

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

typedef struct SetNode {
    int value;
    struct SetNode* next;
} SetNode;

typedef struct {
    SetNode* head;
} Set;

Set* createSet() {
    Set* set = (Set*)malloc(sizeof(Set));
    set->head = NULL;
    return set;
}

void insertSet(Set* set, int value) {
    if (searchSet(set, value)) return; // Avoid duplicates
    SetNode* newNode = (SetNode*)malloc(sizeof(SetNode));
    newNode->value = value;
    newNode->next = set->head;
    set->head = newNode;
}

int searchSet(Set* set, int value) {
    SetNode* node = set->head;
    while (node != NULL) {
        if (node->value == value) {
            return 1; // Found
        }
        node = node->next;
    }
    return 0; // Not found
}

void deleteSet(Set* set, int value) {
    SetNode* node = set->head;
    SetNode* prev = NULL;
    while (node != NULL && node->value != value) {
        prev = node;
        node = node->next;
    }
    if (node == NULL) return; // Not found
    if (prev == NULL) {
        set->head = node->next;
    } else {
        prev->next = node->next;
    }
    free(node);
}

int main() {
    Set* set = createSet();
    insertSet(set, 1);
    insertSet(set, 2);
    insertSet(set, 1); // Duplicate, will be ignored
    printf("Contains 1: %d\n", searchSet(set, 1));
    deleteSet(set, 1);
    printf("Contains 1 after deletion: %d\n", searchSet(set, 1));
    return 0;
}

3. 红黑树

优势：

自平衡的特性保证了树的高度大致为log(n)，从而保证了操作的时间复杂度为O(log n)。
适用于需要有序数据集合的场景。

应用场景：

实现有序的数据存储和检索。
需要频繁插入、删除和查找操作的场景。

示例代码：

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

typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    int value;
    Color color;
    struct RBNode* left;
    struct RBNode* right;
    struct RBNode* parent;
} RBNode;

typedef struct {
    RBNode* root;
    RBNode* nil; // Sentinel node
} RBTree;

RBTree* createRBTree() {
    RBTree* tree = (RBTree*)malloc(sizeof(RBTree));
    tree->nil = (RBNode*)malloc(sizeof(RBNode));
    tree->nil->color = BLACK;
    tree->root = tree->nil;
    return tree;
}

void leftRotate(RBTree* tree, RBNode* x) {
    RBNode* y = x->right;
    x->right = y->left;
    if (y->left != tree->nil) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == tree->nil) {
        tree->root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

void rightRotate(RBTree* tree, RBNode* y) {
    RBNode* x = y->left;
    y->left = x->right;
    if (x->right != tree->nil) {
        x->right->parent = y;
    }
    x->parent = y->parent;
    if (y->parent == tree->nil) {
        tree->root = x;
    } else if (y == y->parent->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }
    x->right = y;
    y->parent = x;
}

void insertFixup(RBTree* tree, RBNode* z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBNode* y = z->parent->parent->right;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(tree, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(tree, z->parent->parent);
            }
        } else {
            RBNode* y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(tree, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(tree, z->parent->parent);
            }
        }
    }
    tree->root->color = BLACK;
}

void insertRBTree(RBTree* tree, int value) {
    RBNode* z = (RBNode*)malloc(sizeof(RBNode));
    z->value = value;
    z->color = RED;
    z->left = tree->nil;
    z->right = tree->nil;
    RBNode* y = tree->nil;
    RBNode* x = tree->root;
    while (x != tree->nil) {
        y = x;
        if (z->value < x->value) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->parent = y;
    if (y == tree->nil) {
        tree->root = z;
    } else if (z->value < y->value) {
        y->left = z;
    } else {
        y->right = z;
    }
    insertFixup(tree, z);
}

int main() {
    RBTree* tree = createRBTree();
    insertRBTree(tree, 10);
    insertRBTree(tree, 20);
    insertRBTree(tree, 5);
    // Additional functions for search and delete can be implemented similarly
    return 0;
}