第1章：指针与数据结构——链表、栈、队列的指针实现、二叉树与指针

大家好，我是你们的老朋友。今天咱们来聊聊指针与数据结构这个话题。

说实话，我刚开始学C语言那会儿，觉得指针就是个地址，没啥大不了的。直到我在一个嵌入式项目中，需要用指针实现一个动态内存管理的链表……嗯，那次差点把我整崩溃了。从那以后，我才真正意识到：指针和数据结构的结合，才是C语言的灵魂所在。

1.1 为什么数据结构离不开指针？

你想想看，数组是静态的，大小固定。但实际项目中，数据量往往是动态变化的。比如一个传感器采集系统，你不知道下一秒会来多少数据。这时候，静态数组就捉襟见肘了。

指针的妙处在于：它让你能在运行时动态分配内存，然后把这些零散的内存块串起来。说白了，指针就是数据结构的“胶水”。

1.2 链表的指针实现

链表是最基础、也是最常用的动态数据结构。我个人的习惯是，先画图再写代码。链表的结构其实很简单：每个节点包含数据域和指针域，指针指向下一个节点。

// 单链表节点定义
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域，指向下一个节点
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

这里有个细节我要强调一下：为什么插入头部要用二级指针？因为我们要修改头指针本身的值。如果你只传一级指针，函数内部修改的是指针的副本，外部头指针不会变。我曾经在这个坑里摔过好几次，后来养成了习惯：凡是可能修改指针本身的，一律用二级指针。

1.3 栈的指针实现

栈是一种“后进先出”的结构。用指针实现栈，其实就是在链表的基础上加一个限制：只能在栈顶操作。

// 栈节点定义（复用链表节点）
typedef Node StackNode;

// 栈结构
typedef struct {
    StackNode* top;  // 栈顶指针
    int size;        // 栈大小
} Stack;

// 入栈
void push(Stack* stack, int data) {
    StackNode* newNode = createNode(data);
    newNode->next = stack->top;
    stack->top = newNode;
    stack->size++;
}

// 出栈
int pop(Stack* stack) {
    if (stack->top == NULL) {
        printf("栈已空！\n");
        return -1;
    }
    StackNode* temp = stack->top;
    int data = temp->data;
    stack->top = temp->next;
    free(temp);
    stack->size--;
    return data;
}

你看，栈的实现其实就是链表的简化版。我建议初学者先掌握链表，栈和队列自然就通了。

1.4 队列的指针实现

队列是“先进先出”的结构。用指针实现队列，需要维护两个指针：队头指针和队尾指针。

// 队列结构
typedef struct {
    Node* front;  // 队头指针
    Node* rear;   // 队尾指针
    int size;
} Queue;

// 入队
void enqueue(Queue* queue, int data) {
    Node* newNode = createNode(data);
    if (queue->rear == NULL) {
        // 队列为空
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    queue->size++;
}

// 出队
int dequeue(Queue* queue) {
    if (queue->front == NULL) {
        printf("队列已空！\n");
        return -1;
    }
    Node* temp = queue->front;
    int data = temp->data;
    queue->front = temp->next;
    if (queue->front == NULL) {
        queue->rear = NULL;  // 队列变空
    }
    free(temp);
    queue->size--;
    return data;
}

1.5 二叉树与指针

二叉树是更复杂的数据结构，每个节点有两个指针：左孩子和右孩子。指针在这里的作用更加明显——它构建了树形结构。

// 二叉树节点定义
typedef struct TreeNode {
    int data;
    struct TreeNode* left;   // 左子树指针
    struct TreeNode* right;  // 右子树指针
} TreeNode;

// 创建二叉树节点
TreeNode* createTreeNode(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

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

// 插入节点（简单二叉搜索树）
void insert(TreeNode** root, int data) {
    if (*root == NULL) {
        *root = createTreeNode(data);
        return;
    }
    if (data < (*root)->data) {
        insert(&((*root)->left), data);
    } else {
        insert(&((*root)->right), data);
    }
}

二叉树的递归遍历，说白了就是指针的递归传递。每个节点通过指针找到它的孩子，孩子再找孙子……这种链式结构，用指针表达最自然不过了。

1.6 指针实现数据结构的核心思维

我总结了一下，用指针实现数据结构，核心就三点：

1. 动态分配：用malloc在堆上创建节点，运行时按需分配内存
2. 指针链接：用指针把零散的节点串成链、树等结构
3. 指针操作：插入、删除、遍历都靠修改指针指向

说白了，指针就是数据结构的“骨架”。你把节点当成积木，指针就是连接积木的卡扣。卡扣怎么连，结构就怎么变。

1.7 本章知识体系图

下面这张图展示了指针与数据结构的关系，我画了很久，希望能帮你理清思路：

1.8 避坑指南

最后，我把自己这些年踩过的坑分享给你：

• 野指针：节点释放后，记得把指针置为NULL。我曾经在链表删除操作中忘了这一步，结果程序跑着跑着就崩了，查了两天才发现是野指针在作怪。
• 内存泄漏：每次malloc都要对应一个free。我习惯在写代码时就写好free，避免后面忘记。
• 空指针检查：访问指针前，先判断是不是NULL。这个习惯救了我无数次。
• 二级指针：需要修改指针本身的值时，用二级指针。比如链表的插入头部、二叉树的插入节点。

好了，这一章就到这里。指针与数据结构的关系，说白了就是“工具”与“建筑”的关系。指针是工具，数据结构是建筑。工具用好了，什么建筑都能搭出来。

---

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