C语言searchprimarykey如何实现主键搜索？-C语言-盈思创科技

C语言本身没有内置的“数据库”或“表”的概念，因此它也没有“主键”这个内置数据类型或关键字，主键是关系型数据库中的一个核心概念，用于唯一标识表中的每一条记录。

（图片来源网络，侵删）

在C语言中实现“搜索主键”，本质上是使用C语言的数据结构和算法，来模拟和实现数据库中根据主键查找记录的功能。

下面我将从几个层面来解释如何实现这个功能：

概念理解：主键是什么？
简单实现：使用线性结构（数组和链表）
高效实现：使用非线性结构（哈希表、二叉搜索树）
实践案例：一个简单的学生信息管理系统
进阶方向：连接真实数据库

概念理解：主键是什么？

在数据库中,主键有以下特点：

唯一性：主键的值在表中必须是唯一的，不能有重复。
非空性：主键的值不能为 NULL。
稳定性：主键的值通常不应该被修改。

在C语言中,我们模拟主键，就是选择一个或多个字段，来确保我们存储的每一条“记录”都能被这个字段的值唯一地标识。

（图片来源网络，侵删）

简单实现：使用线性结构

这是最直观、最容易理解的方法，但效率较低，我们用一个结构体数组来存储记录。

数据结构定义

#include <stdio.h>
#include <string.h> // 用于 strcmp
// 定义学生记录结构体
// 假设学号是主键
typedef struct {
    int id;             // 主键
    char name[50];
    int age;
} Student;
// 定义一个“数据库”，就是一个结构体数组
Student database[100]; 
int current_size = 0; // 当前数据库中记录的数量

搜索算法：线性搜索

遍历数组,逐个比较主键值，直到找到匹配的记录。

// 根据主键 (id) 搜索学生
// 返回找到的记录在数组中的索引，如果没找到返回 -1
int searchByPrimaryKey_linear(int id) {
    for (int i = 0; i < current_size; i++) {
        if (database[i].id == id) {
            return i; // 找到，返回索引
        }
    }
    return -1; // 未找到
}
void printStudent(Student s) {
    printf("ID: %d, Name: %s, Age: %d\n", s.id, s.name, s.age);
}
int main() {
    // 添加一些测试数据
    database[0] = (Student){101, "Zhang San", 20};
    database[1] = (Student){102, "Li Si", 21};
    database[2] = (Student){103, "Wang Wu", 22};
    current_size = 3;
    int search_id = 102;
    int index = searchByPrimaryKey_linear(search_id);
    if (index != -1) {
        printf("Found student with ID %d:\n", search_id);
        printStudent(database[index]);
    } else {
        printf("Student with ID %d not found.\n", search_id);
    }
    return 0;
}

优点：

实现简单,逻辑清晰。
无需额外的数据结构。

缺点：

（图片来源网络，侵删）

效率低下：时间复杂度为 O(n)，当数据量很大时（比如百万条记录），搜索会非常慢。

高效实现：使用非线性结构

为了提高搜索效率,我们需要更复杂的数据结构，C语言标准库中没有直接提供这些结构，但我们可以自己实现或使用第三方库。

哈希表

哈希表是实现键值对存储和查找的绝佳选择,平均时间复杂度可以达到 O(1)。

原理：通过一个“哈希函数”，将主键（key）映射到一个数组索引（index），直接访问该位置获取数据，如果发生冲突（不同主键映射到同一索引），则需要用链地址法或开放地址法来解决。

C语言实现思路：

创建一个结构体 HashEntry，包含 key（主键）、value（记录）和一个指向下一个节点的指针（用于处理冲突）。
创建一个哈希表结构体 HashTable，包含一个 HashEntry 类型的指针数组。
实现哈希函数（id % table_size）。
实现插入和查找函数。

// (这是一个简化的哈希表示例，实际实现会更复杂)
#define HASH_TABLE_SIZE 100
typedef struct HashNode {
    int key; // 主键
    Student student;
    struct HashNode* next;
} HashNode;
HashNode* hashTable[HASH_TABLE_SIZE];
// 哈希函数
int hashFunction(int key) {
    return key % HASH_TABLE_SIZE;
}
// 插入学生
void insertStudent(Student s) {
    int index = hashFunction(s.id);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = s.id;
    newNode->student = s;
    newNode->next = hashTable[index]; // 头插法
    hashTable[index] = newNode;
}
// 根据主键搜索学生 (哈希表方式)
Student* searchByPrimaryKey_hash(int id) {
    int index = hashFunction(id);
    HashNode* node = hashTable[index];
    while (node != NULL) {
        if (node->key == id) {
            return &(node->student); // 找到，返回记录的指针
        }
        node = node->next;
    }
    return NULL; // 未找到
}
int main_hash_example() {
    // 初始化哈希表
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }
    Student s1 = {101, "Zhang San", 20};
    Student s2 = {102, "Li Si", 21};
    Student s3 = {103, "Wang Wu", 22};
    insertStudent(s1);
    insertStudent(s2);
    insertStudent(s3);
    int search_id = 102;
    Student* found = searchByPrimaryKey_hash(search_id);
    if (found != NULL) {
        printf("Found student with ID %d:\n", search_id);
        printStudent(*found);
    } else {
        printf("Student with ID %d not found.\n", search_id);
    }
    // ... 记得在程序结束时释放所有分配的内存 ...
    return 0;
}

优点：

查找速度极快，平均时间复杂度为 O(1)。

缺点：

实现比线性结构复杂。
需要处理哈希冲突。
内存占用相对较大。

二叉搜索树

二叉搜索树也是一种高效的数据结构,对于有序数据，其查找、插入、删除的平均时间复杂度为 O(log n)。

原理：对于树中的任意节点，其左子树中所有节点的值都小于该节点的值，其右子树中所有节点的值都大于该节点的值。

C语言实现思路：

定义一个 TreeNode 结构体，包含 key、value、left 和 right 指针。
实现插入函数,根据 BST 规则将新节点插入到正确的位置。
实现搜索函数,从根节点开始，根据比较结果向左或向右子树递归查找。

// (这是一个简化的BST示例)
typedef struct TreeNode {
    int key;
    Student student;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;
TreeNode* insertIntoBST(TreeNode* root, Student s) {
    if (root == NULL) {
        TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
        newNode->key = s.id;
        newNode->student = s;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if (s.id < root->key) {
        root->left = insertIntoBST(root->left, s);
    } else if (s.id > root->key) {
        root->right = insertIntoBST(root->right, s);
    }
    // 如果相等，可以选择不插入或更新，这里假设主键唯一，不插入重复项
    return root;
}
Student* searchInBST(TreeNode* root, int id) {
    if (root == NULL) {
        return NULL;
    }
    if (root->key == id) {
        return &(root->student);
    } else if (id < root->key) {
        return searchInBST(root->left, id);
    } else {
        return searchInBST(root->right, id);
    }

C语言searchprimarykey如何实现主键搜索？

概念理解：主键是什么？

简单实现：使用线性结构

数据结构定义

搜索算法：线性搜索

高效实现：使用非线性结构

哈希表

二叉搜索树

相关文章

目录[+]