11
数据结构实战：用 C 手撸一遍
Linked List · Stack · Queue · Tree
C 没有现成的 list、map（那是 C++ STL、Python 标准库的事），所以数据结构得自己拿 struct + 指针 + malloc 拼。别嫌麻烦——这一遍拼下来，你才算真的懂了"链表是怎么连起来的"。下面给最核心的单链表。
单链表：节点 + 指针
每个节点装一个数据，外加一个指向下一个节点的指针。最后一个指向 NULL 表示"到头了"。
单链表：创建头节点、头插、遍历、释放
#include <stdio.h>
#include <stdlib.h>
// 一个链表节点
typedef struct Node {
int data;
struct Node *next; // 指向下一个节点，自己引用自己，必须用 struct Node*
} Node;
// 在链表头部插入一个新节点
Node *push_front(Node *head, int val) {
Node *n = (Node *)malloc(sizeof(Node));
n->data = val;
n->next = head; // 新节点指向原来的头
return n; // 新节点变成新的头，返回它
}
// 从头到尾遍历打印
void print_list(Node *head) {
for (Node *p = head; p != NULL; p = p->next) {
printf("%d -> ", p->data);
}
printf("NULL\n");
}
int main() {
Node *head = NULL; // 空链表
head = push_front(head, 30);
head = push_front(head, 20);
head = push_front(head, 10); // 链表：10->20->30
print_list(head); // 10 -> 20 -> 30 -> NULL
// 别忘了释放整段链表，否则全泄漏
while (head) {
Node *tmp = head->next;
free(head);
head = tmp;
}
return 0;
}
运行结果
10 -> 20 -> 30 -> NULL
栈、队列、二叉树：一句话思路
| 结构 | 怎么实现 |
|---|---|
| 栈 stack | "后进先出"。用数组 + 一个 top 下标：压栈 a[top++]=x，弹栈 x=a[--top]。 |
| 队列 queue | "先进先出"。用数组 + 头尾两个下标，或用链表。排队买票，先来的先走。 |
| 二叉树 | 每个节点有左、右两个孩子指针。前/中/后序遍历天然就是递归：visit(root->left)、visit(root)、visit(root->right)。 |
| 哈希表 | 用一个数组当"桶"，key 经过哈希函数算出桶号，同一个桶里挂一条链表（链地址法）。 |
二叉树的递归遍历（三行核心）
typedef struct TNode {
int val;
struct TNode *left, *right;
} TNode;
// 中序遍历：左 -> 根 -> 右
void inorder(TNode *root) {
if (root == NULL) return; // 终止条件：空树
inorder(root->left); // 先逛左子树
printf("%d ", root->val); // 再处理自己
inorder(root->right); // 最后逛右子树
}
二叉搜索树（BST）与二分查找
普通二叉树只是"能遍历"，二叉搜索树（BST）加了一条规矩：左子树所有值 < 根 < 右子树所有值。于是查找、插入都能每次砍掉一半，平均 O(log n)——比链表挨个找快得多。
BST 插入与查找：递归版，每次往左或右砍一半
BST 节点 + 查找 + 插入（递归核心）
typedef struct Node {
int val;
struct Node *left, *right;
} Node;
// 查找：在 root 这棵树里找 key
Node* search(Node *root, int key) {
if (root == NULL || root->val == key) return root; // 空 或 命中
if (key < root->val)
return search(root->left, key); // 比根小，去左子树
else
return search(root->right, key); // 比根大，去右子树
}
// 插入：递归找到空位置挂上去（返回新根）
Node* insert(Node *root, int key) {
if (root == NULL) { // 空位：建新节点
Node *n = malloc(sizeof(Node));
n->val = key; n->left = n->right = NULL;
return n;
}
if (key < root->val) root->left = insert(root->left, key);
else root->right = insert(root->right, key);
return root;
}
注意：BST 按顺序插入会退化成链表（1,2,3,4 串成一条），查找就变成 O(n)。工程上用平衡树（AVL、红黑树）防止它退化成链——Linux 内核、C++ map 都是红黑树。理解 BST 就理解了后面一切平衡树的基础。
配套：有序数组上的二分查找（BST 思想的数组版）
// 在升序数组 a[0..n-1] 里找 key，找到返回下标，否则 -1
int bsearch(int a[], int n, int key) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // 防 (lo+hi) 溢出
if (a[mid] == key) return mid;
else if (a[mid] < key) lo = mid + 1; // 去右半
else hi = mid - 1; // 去左半
}
return -1;
}