指针与数据结构：从理论到工程实战

大家好，我是你们的老朋友。今天咱们来聊一个硬核话题——指针与数据结构。说实话，我见过太多工程师，写业务代码溜得很，一碰到指针操作数据结构就手抖。嗯，这很正常，因为指针这东西，说白了就是一把双刃剑。

我在项目中遇到过好几次，因为链表指针没处理好，导致线上服务内存泄漏，最后查了整整两天才定位到问题。从那以后，我养成了一个习惯：凡是涉及指针操作数据结构的代码，必须画图、写注释、做单元测试。今天我就把这些经验掰开揉碎了讲给你听。

栈与队列的指针实现

先说说栈和队列。这两个结构看着简单，但用指针实现时，坑其实不少。

链式栈：后进先出的指针艺术

栈的核心操作就两个：push 和 pop。用数组实现栈很简单，但用链表实现时，你得想清楚指针怎么指。

// 链式栈节点
typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

// 栈结构（带栈顶指针）
typedef struct {
    StackNode* top;  // 栈顶指针
    int size;
} LinkedStack;

// 入栈
void push(LinkedStack* s, int val) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    node->data = val;
    node->next = s->top;  // 新节点指向当前栈顶
    s->top = node;        // 更新栈顶指针
    s->size++;
}

// 出栈
int pop(LinkedStack* s) {
    if (s->top == NULL) return -1;  // 空栈检查
    StackNode* tmp = s->top;
    int val = tmp->data;
    s->top = tmp->next;  // 栈顶下移
    free(tmp);
    s->size--;
    return val;
}
我的习惯：每次写 push 操作时，我都会先画一下指针指向图。新节点的 next 指向当前 top，然后 top 再指向新节点——这个顺序不能乱。我曾经因为先更新了 top 再赋值 next，导致链表断链，排查了半天。

链式队列：两个指针的默契配合

队列比栈多了一个尾指针。front 负责出队，rear 负责入队。这两个指针配合好了，队列就稳了。

typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;  // 队头指针
    QueueNode* rear;   // 队尾指针
    int size;
} LinkedQueue;

// 入队（从队尾）
void enqueue(LinkedQueue* q, int val) {
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    node->data = val;
    node->next = NULL;
    
    if (q->rear == NULL) {  // 空队列
        q->front = q->rear = node;
    } else {
        q->rear->next = node;
        q->rear = node;
    }
    q->size++;
}
避坑指南：我曾经在队列出队时忘记处理空队列的情况，结果 front 指针变成了野指针。记住：出队前一定要检查 front 是否为 NULL，出队后如果队列变空，要把 rear 也置为 NULL。

二叉树的指针实现

二叉树是指针操作的重灾区。为什么？因为递归操作多，指针传递容易搞混。

遍历：递归与迭代的指针游戏

先来个前序遍历的递归实现，这是最直观的：

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

// 前序遍历（根-左-右）
void preorder(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

但递归有栈溢出的风险。我建议你掌握迭代版本，用栈模拟递归：

void preorder_iterative(TreeNode* root) {
    if (root == NULL) return;
    Stack* stack = createStack();
    push(stack, root);
    
    while (!isEmpty(stack)) {
        TreeNode* node = pop(stack);
        printf("%d ", node->data);
        
        // 先压右子树，再压左子树（因为栈是后进先出）
        if (node->right) push(stack, node->right);
        if (node->left) push(stack, node->left);
    }
}

插入与删除：指针的重新编织

二叉搜索树的插入相对简单，但删除操作就复杂了。删除一个节点时，有三种情况：

情况 处理方式 指针操作
叶子节点 直接删除 父节点指针置 NULL
只有一个子节点 子节点顶替 父节点指向子节点
有两个子节点 找中序后继 替换数据，删除后继节点 
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) return NULL;
    
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        // 找到了要删除的节点
        if (root->left == NULL) {
            TreeNode* tmp = root->right;
            free(root);
            return tmp;
        } else if (root->right == NULL) {
            TreeNode* tmp = root->left;
            free(root);
            return tmp;
        }
        // 有两个子节点：找右子树的最小节点
        TreeNode* minNode = findMin(root->right);
        root->data = minNode->data;
        root->right = deleteNode(root->right, minNode->data);
    }
    return root;
}
核心要点：删除操作中，最关键的是要理解「指针的重新连接」。你想想看，删除一个节点，本质上是把它的父节点指针重新指向它的子节点。这个逻辑想通了，二叉树的操作就通了。

哈希表的指针实现

哈希表用指针实现，主要是为了解决哈希冲突。链地址法是最常见的做法——每个桶里挂一个链表。

#define TABLE_SIZE 100

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

typedef struct {
    HashNode** buckets;  // 指针数组
    int size;
} HashTable;

// 插入
void insert(HashTable* ht, int key, int val) {
    int idx = hash(key) % TABLE_SIZE;
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->value = val;
    
    // 头插法
    node->next = ht->buckets[idx];
    ht->buckets[idx] = node;
    ht->size++;
}
我的经验：哈希表的扩容是个大坑。当负载因子超过 0.75 时，一定要扩容。我见过一个项目，哈希表装满了也不扩容，结果查找退化成 O(n)，性能直接崩了。扩容时要重新计算所有元素的哈希值，这个操作很耗时，但必须做。

图的邻接表与指针

图的邻接表实现，本质上是一个指针数组，每个指针指向一个链表。每个链表节点代表一条边。

typedef struct EdgeNode {
    int vertex;              // 邻接顶点
    int weight;              // 权重
    struct EdgeNode* next;   // 下一条边
} EdgeNode;

typedef struct {
    EdgeNode** adjList;  // 邻接表
    int numVertices;
    int numEdges;
} Graph;

// 添加边（无向图）
void addEdge(Graph* g, int u, int v, int w) {
    // u -> v
    EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    edge->vertex = v;
    edge->weight = w;
    edge->next = g->adjList[u];
    g->adjList[u] = edge;
    
    // v -> u（无向图需要加两条边）
    edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    edge->vertex = u;
    edge->weight = w;
    edge->next = g->adjList[v];
    g->adjList[v] = edge;
    
    g->numEdges++;
}

图的遍历（DFS、BFS）本质上就是指针的游走。DFS 用递归或栈，BFS 用队列。核心逻辑都一样：顺着指针往下走，走过的节点标记一下。

注意：图的邻接表实现中，释放内存是个大工程。每个顶点对应的链表都要遍历释放。我建议你写一个统一的销毁函数，否则很容易内存泄漏。

知识体系总览

下面这张图总结了本章的核心知识点，你可以把它当作一个思维导图来用：

指针与数据结构 栈与队列 链式栈：top指针 链式队列：front+rear 入栈/出栈指针操作 空队列处理 二叉树 递归/迭代遍历 插入：指针赋值 删除：三种情况 中序后继替换 哈希表 链地址法 头插法插入 负载因子与扩容 哈希冲突处理 图（邻接表） 指针数组+链表 DFS/BFS遍历 无向图双向添加 内存释放 核心思想 • 指针是数据结构的「粘合剂」——没有指针，动态结构无从谈起 • 画图！画图！画图！——指针操作前先画指向图 • 内存管理是基本功——malloc 和 free 必须成对出现

说实话，指针与数据结构这块，没有捷径可走。我当年学的时候，也是画图画到手酸，调试调到眼红。但只要你把每个指针的指向都搞清楚，把每个节点的生命周期都管理好，这些东西其实没那么可怕。

最后送你一句话：指针不是洪水猛兽，它是 C 语言给工程师的礼物。用好它，你的代码会变得优雅而高效；用不好，它就会变成噩梦。多练、多画图、多调试，你一定能掌握它。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →