第22章指针与查找算法

课程目录第22章指针与查找算法

22、指针与查找算法：二分查找的指针实现、指针与哈希表、指针与二叉搜索树

查找，是编程里最基础也最核心的操作之一。你想想看，我们写程序，本质上就是在处理数据——存进去，再找出来。而指针，恰恰是让查找变得高效的关键工具。

这一章，我会带你用指针的视角，重新审视三种经典的查找结构：二分查找、哈希表、二叉搜索树。说白了，就是看看指针在这些场景下，到底扮演了什么角色。

一、二分查找的指针实现

二分查找，大家都不陌生。但很多人写二分查找，用的是数组下标。我个人习惯用指针来写，因为指针操作更贴近底层，也更灵活。

先看一个标准实现：

int* binary_search(int* arr, int size, int target) {
    int* left = arr;
    int* right = arr + size - 1;
    
    while (left <= right) {
        int* mid = left + (right - left) / 2;
        
        if (*mid == target) {
            return mid;  // 返回指针，而不是下标
        } else if (*mid < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return NULL;  // 没找到
}

注意看，这里返回的是指针。为什么？因为指针携带了地址信息，你可以直接通过它访问元素，还能做指针运算。如果返回下标，你还得再算一次地址。

我的经验：在嵌入式开发中，我经常用这种返回指针的方式。比如在内存映射的寄存器表中查找某个配置项，返回指针后可以直接读写，省去了下标到地址的转换步骤。

这里有个细节：mid = left + (right - left) / 2。为什么不用 (left + right) / 2？因为指针相加是未定义行为！两个指针相减得到的是ptrdiff_t，是合法的；但相加就不行。嗯，这个坑我踩过。

避坑指南：我曾经在项目里写过 mid = (left + right) / 2，编译器没报错，但运行结果时对时错。后来查了C标准才知道，指针相加是未定义行为。从那以后，我写二分查找只用 left + (right - left) / 2。

二、指针与哈希表

哈希表，说白了就是「数组 + 链表」的组合。而指针，是连接这两者的桥梁。

看一个简单的哈希表节点定义：

typedef struct HashNode {
    int key;
    int value;
    struct HashNode* next;  // 拉链法，用指针串起来
} HashNode;

typedef struct HashTable {
    HashNode** buckets;  // 指针的指针，指向一个指针数组
    int size;
} HashTable;

这里 buckets 是二级指针。为什么？因为每个桶里存的是链表的头指针，而我们要动态分配这个指针数组。说白了，buckets 指向一个连续的指针数组，每个指针又指向一个链表节点。

插入操作的实现：

void hash_insert(HashTable* table, int key, int value) {
    int index = key % table->size;
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->value = value;
    
    // 头插法，用指针操作
    node->next = table->buckets[index];
    table->buckets[index] = node;
}

查找操作：

int* hash_find(HashTable* table, int key) {
    int index = key % table->size;
    HashNode* cur = table->buckets[index];
    
    while (cur != NULL) {
        if (cur->key == key) {
            return &(cur->value);  // 返回值的指针
        }
        cur = cur->next;  // 指针遍历链表
    }
    
    return NULL;
}

核心要点：哈希表的效率，取决于指针操作的速度。插入时是O(1)的指针操作，查找时是O(1)的哈希计算加上O(n)的链表遍历。但这里的n是单个桶里的节点数，理想情况下接近1。

我在项目中遇到过一个问题：哈希表的扩容。当负载因子超过阈值时，需要重新分配桶数组，重新计算所有节点的哈希值。这时候，二级指针就派上用场了——你可以直接操作 buckets 指针数组里的每个指针，而不需要移动节点本身的数据。

三、指针与二叉搜索树

二叉搜索树（BST），是链表结构的升级版。每个节点有两个指针，分别指向左子树和右子树。

节点定义：

typedef struct BSTNode {
    int data;
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

插入操作，用二级指针实现会更优雅：

void bst_insert(BSTNode** root, int value) {
    while (*root != NULL) {
        if (value < (*root)->data) {
            root = &((*root)->left);
        } else if (value > (*root)->data) {
            root = &((*root)->right);
        } else {
            return;  // 已存在，不插入
        }
    }
    
    *root = (BSTNode*)malloc(sizeof(BSTNode));
    (*root)->data = value;
    (*root)->left = NULL;
    (*root)->right = NULL;
}

注意看，这里用 BSTNode** 二级指针，直接修改了父节点中指向子节点的指针。不需要额外的父节点变量，也不需要递归。我个人觉得这种写法比递归更直观，也更高效。

查找操作：

BSTNode* bst_search(BSTNode* root, int target) {
    while (root != NULL) {
        if (target == root->data) {
            return root;
        } else if (target < root->data) {
            root = root->left;  // 指针向左移动
        } else {
            root = root->right; // 指针向右移动
        }
    }
    return NULL;
}

我的习惯：写BST查找时，我更喜欢用迭代而不是递归。原因很简单——嵌入式环境栈空间有限，递归容易爆栈。而且迭代版本的指针操作，性能上通常比递归好那么一点点。

删除操作稍微复杂些，但核心还是指针操作：

void bst_delete(BSTNode** root, int target) {
    BSTNode* cur = *root;
    BSTNode** parent_link = root;
    
    // 先找到要删除的节点
    while (cur != NULL && cur->data != target) {
        if (target < cur->data) {
            parent_link = &(cur->left);
            cur = cur->left;
        } else {
            parent_link = &(cur->right);
            cur = cur->right;
        }
    }
    
    if (cur == NULL) return;  // 没找到
    
    // 处理三种情况
    if (cur->left == NULL) {
        *parent_link = cur->right;  // 用右子树替代
        free(cur);
    } else if (cur->right == NULL) {
        *parent_link = cur->left;   // 用左子树替代
        free(cur);
    } else {
        // 左右子树都不为空，找右子树的最小节点
        BSTNode** min_parent = &(cur->right);
        BSTNode* min_node = cur->right;
        while (min_node->left != NULL) {
            min_parent = &(min_node->left);
            min_node = min_node->left;
        }
        
        // 用最小节点的值替换当前节点
        cur->data = min_node->data;
        
        // 删除最小节点
        *min_parent = min_node->right;
        free(min_node);
    }
}

避坑指南：我曾经在删除BST节点时，忘记更新父节点的指针，导致内存泄漏和野指针。后来我养成了一个习惯——删除节点前，先想清楚「谁指向它」，然后通过二级指针来修改那个指向关系。

四、三种查找结构的对比

结构	查找时间复杂度	插入时间复杂度	指针使用特点	适用场景
二分查找（有序数组）	O(log n)	O(n)	指针算术运算	静态数据，频繁查找
哈希表	O(1) 平均	O(1) 平均	二级指针、链表指针	动态数据，快速查找
二叉搜索树	O(log n) 平均	O(log n) 平均	左右子树指针、二级指针	需要有序遍历的数据

你想想看，这三种结构，本质上都是在用指针来组织数据。二分查找用指针做算术运算，哈希表用指针做链式存储，二叉搜索树用指针做树形结构。指针，就是这些数据结构的「骨架」。

总结一下：指针在查找算法中，不只是「指向数据」，更是「组织数据」的工具。掌握指针的灵活运用，你就能写出更高效、更优雅的查找代码。

嗯，这一章的内容就到这里。指针与查找算法的结合，说白了就是「用指针来组织数据，用算法来遍历指针」。你写代码的时候，多想想指针在其中的角色，慢慢就会形成自己的风格。

📚 课程目录

22、指针与查找算法：二分查找的指针实现、指针与哈希表、指针与二叉搜索树

一、二分查找的指针实现

二、指针与哈希表

三、指针与二叉搜索树

四、三种查找结构的对比