常用数据结构

这篇是整个教程中最重要的一篇。算法题的本质就是对数据结构进行操作，如果你不熟悉 C 语言中这些数据结构的用法，看算法代码就会一头雾水。

C 语言的标准库比较简陋，没有现成的动态数组、哈希表等容器。但好消息是，算法题中绝大多数场景用数组就能搞定，栈和队列也可以用数组简单模拟。哈希表等复杂数据结构，力扣平台内置了 GLib 库可以直接使用。

¶数组

前面 C 基础语法 中已经介绍了数组的声明和访问。这里补充一些算法题中常用的数组操作。

¶二维数组

二维数组就是「数组的数组」，常用来表示矩阵或网格：

¶数组的增删操作

C 语言的数组大小固定，没有内置的增删方法，需要手动搬移元素。算法题中最常用的是尾部增删，效率很高；中间插入删除需要搬移数据，效率低，应尽量避免。

¶字符串

C 语言没有独立的字符串类型，字符串就是以 \0（空字符）结尾的字符数组。这个 \0 是字符串结束的标志，所有字符串函数都靠它来判断字符串在哪里结束。

¶常用字符串函数

这些函数都在 <string.h> 中：

¶字符串与数字转换

¶字符判断与转换

<ctype.h> 提供了一组判断和转换单个字符的函数：

¶结构体

结构体（struct）让你把多个不同类型的数据组合在一起，形成一个新的类型。

¶定义与使用

¶typedef 简化类型名

每次都写 struct Student 太啰嗦，用 typedef 可以给类型起个短名字：

在算法题中，typedef 最常见的用途就是简化结构体声明和 long long 的类型名。

¶结构体指针与箭头操作符

当你有一个指向结构体的指针时，用 -> 来访问成员（等价于先解引用再用 .）：

-> 在链表、树等数据结构的代码中会大量出现，看到 node->val 就知道是"通过指针访问结构体成员"。

¶栈和队列

C 语言的标准库没有提供栈和队列这样的数据结构，需要自己实现。关于栈和队列的底层原理和多种实现方式，后面的 队列/栈基本原理 会详细介绍。这里先讲最简单也是刷题中最常用的方式，用数组模拟。

¶栈（数组模拟）

栈是一种后进先出（LIFO，Last In First Out）的数据结构：

核心就三个操作：stk[++top] = x（入栈）、top--（出栈）、stk[top]（看栈顶）。

¶队列（数组模拟）

队列是一种先进先出（FIFO，First In First Out）的数据结构，同样用数组模拟：

这种数组模拟队列的方式，front 只往前移动不会回退，已出队的空间不会复用。所以数组大小按"总共入队多少次"来开，而不是按"同时在队列中的最大元素数"。比如 BFS 遍历 n 个节点，每个节点最多入队一次，数组开 n + 1 就够了。

¶哈希表（GLib GHashTable）

C 语言标准库没有哈希表，但力扣平台内置了 GLib 库，可以直接 #include <glib.h> 使用 GHashTable。关于哈希表的底层原理，后面的 哈希表核心原理 会详细讲解。

当 key 的范围较小且已知时（比如 ASCII 字符、0~10^5 的整数），直接用 int arr[N] 比哈希表更快更简洁。只有 key 范围大或不确定时才需要用哈希表。

使用 GHashTable 存取 int 值时，需要用 GINT_TO_POINTER 和 GPOINTER_TO_INT 宏进行转换。这是因为 GHashTable 内部用 void* 指针存储数据，而 int 不是指针类型，需要用这两个宏在 int 和 void* 之间转换。当作固定写法记住就行。

注意：g_hash_table_lookup 在 key 不存在时返回 NULL（即 GPOINTER_TO_INT(NULL) == 0）。如果 0 也是合法的 value，需要先用 g_hash_table_contains 判断 key 是否存在。

¶哈希集合（用 GHashTable 模拟）

C 语言没有哈希集合，但可以用 GHashTable 模拟——value 固定为一个非 NULL 值即可：

¶小结

把这篇的数据结构和核心操作汇总一下：

不需要一次记住所有方法，用多了自然就熟了。下一篇会讲一些算法题中的实用技巧，比如排序、数学操作、宏定义等。