c 存储不重复的数据

在C语言中，存储不重复的数据通常需要使用数据结构来确保唯一性，常见的方法包括使用数组、链表、集合（通过散列表实现）或者二叉搜索树等，下面将介绍几种常用的方法来实现这一功能。

使用数组和线性搜索

这是最简单的方法，但效率较低，特别是当数据集较大时，基本思路是在添加新元素前，遍历整个数组检查该元素是否已存在。

#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
int data[MAX_SIZE];
int size = 0;
bool addData(int element) {
    for (int i = 0; i < size; i++) {
        if (data[i] == element) {
            return false; // 元素已存在
        }
    }
    if (size >= MAX_SIZE) {
        return false; // 数组已满
    }
    data[size++] = element;
    return true;
}
int main() {
    addData(10);
    addData(20);
    addData(10); // 尝试添加重复元素
    for (int i = 0; i < size; i++) {
        printf("%d ", data[i]);
    }
    return 0;
}

使用链表

链表允许动态内存分配，因此在插入新元素时不需要预先定义数组大小，同样，需要在插入前检查元素是否存在。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;
Node* head = NULL;
bool addData(int element) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == element) {
            return false; // 元素已存在
        }
        current = current->next;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        return false; // 内存分配失败
    }
    newNode->data = element;
    newNode->next = head;
    head = newNode;
    return true;
}
void printList() {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("
");
}
int main() {
    addData(10);
    addData(20);
    addData(10); // 尝试添加重复元素
    printList();
    return 0;
}

使用散列表（哈希表）

散列表提供了平均常数时间复杂度的查找性能，是存储不重复数据的高效方式，C语言标准库不直接支持散列表，但可以通过第三方库或自定义实现来达到目的。

使用二叉搜索树（BST）

二叉搜索树可以保持元素的排序顺序，同时提供高效的插入、删除和查找操作，每个节点都遵循左子节点小于父节点，右子节点大于父节点的规则。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;
TreeNode* insert(TreeNode* root, int data) {
    if (root == NULL) {
        TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
        node->data = data;
        node->left = node->right = NULL;
        return node;
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}
bool search(TreeNode* root, int data) {
    if (root == NULL) return false;
    if (root->data == data) return true;
    if (data < root->data) return search(root->left, data);
    return search(root->right, data);
}
void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}
int main() {
    TreeNode* root = NULL;
    root = insert(root, 20);
    root = insert(root, 10);
    root = insert(root, 30);
    root = insert(root, 20); // 尝试添加重复元素
    inorderTraversal(root);
    printf("
");
    return 0;
}

FAQs

Q1: 为什么在实际应用中不推荐使用数组来存储大量不重复的数据？

A1: 数组的大小是固定的，当数据量超过预设大小时，无法再添加新元素，每次插入新元素时都需要线性搜索整个数组，导致效率低下，对于大数据量的存储，更推荐使用链表、散列表或二叉搜索树等数据结构。

Q2: 散列表如何确保数据的唯一性？

A2: 散列表通过计算数据的哈希值来确定其存储位置，在插入新元素时，首先计算其哈希值，如果该位置为空，则直接插入；如果不为空，则比较存储在该位置的元素与新元素是否相同，如果相同，则说明元素已存在，不进行插入；如果不同，则发生哈希冲突，需要通过链地址法或开放地址法解决冲突后插入新元素，由于哈希函数的设计，使得不同元素产生相同哈希值的概率很低，从而保证了数据的唯一性。

小编有话说

选择哪种数据结构来存储不重复的数据，取决于具体的应用场景和需求，对于小规模数据，简单的数组或链表可能就足够用了，而对于大规模数据或需要频繁查找、插入和删除操作的应用，散列表或二叉搜索树则是更好的选择，希望本文能帮助你更好地理解如何在C语言中存储不重复的数据。