地址、指针以及一个链表的 C 语言实现
August 01, 2021

最令初学 C 语言的朋友犯难的,应该是指针了。下述内容绝大部分都可以在《深入理解计算机系统》一书中找到更细节的解释,但考虑到此书对初学者并不友好,因此我用更好懂的语言以及例子进行解释。有决心的读者应当在书中找到我所说的概念,验证学到的知识。

想要理解指针,需要先理解计算机中内存与地址的概念。

内存是计算机中存放运行时数据的地方。什么叫运行时数据呢?就是说程序正在运行的时候,需要的数据。当编译器把源代码编译为可执行文件的时候,这个文件是放在磁盘上的。在运行的时候,操作系统需要首先把这个可执行文件从磁盘里加载到内存中,然后才能执行。在执行过程中,程序需要对数据进行读写的操作,这些数据是存放在内存里的。

内存可以抽象地理解为一个无限长的格子序列,每个格子可以放一个字节的数据。我们称这样的一个格子为内存中的一个存储单元。

[ ] [ ] [ ] [ ] [ ] [ ] ...
^   ^   ^
|   |   |
0   1   2

同时,每个格子都有一个编号,这个编号我们称之为内存中的地址。从而,我们可以根据地址来找到存储单元,进一步地可以读取或者修改这个存储单元中的数据。

一般而言,你在 C 语言中声明的变量,都会存放在内存中的一段空间中。如果是一个 int 类型的变量,会占用连续的四个字节;一个数组则会占用连续的数组大小乘以每个元素大小的空间。注意,这里着重强调“连续”的概念。

举个例子,如果你在程序中声明了 int a[101]; 的数组,那么内存中就会有一段空间用来存放这个数组。这段空间的大小应该是 4×1014\times 101 个字节,因为每个 int 元素的大小为 4 个字节,而这个数组内总共有 101 个元素。

数组中第一个元素 a[0] 的地址,就是这段空间的地址。在 C 语言中,我们可以通过在变量前添加 & 来获取这个变量的地址,& 被称为取地址运算符。举例来说,如果数组 a 在内存空间中占用的地址区间是 [400, 804)(注意是左闭右开的区间),那么 &a[0] 作为一个表达式的值就是数组 a 中第一个元素的地址,即 400,而 &a[33] 的值则为 400+33×4=532400+33\times 4=532

当我们知道了某个变量在内存中存储的地址,我们希望能通过地址来读取或者修改这个变量的值。

首先我们需要明白的是,变量在内存中究竟是如何存储的。

用 int 来举例,int 的大小为 4 个字节。假设有一个 int 变量,值为 0x44332211 (这里用 16 进制表示,读者可以自行计算其十进制的值),那么从低位到高位,每个字节的值分别为 0x11, 0x22, 0x33, 0x44。假设这个变量存储在地址 [100, 104) 上,那么如果其摆放为 [0x11] [0x22] [0x33] [0x44] ,则称为小端表示法(little-endian),如果为 [0x44] [0x33] [0x22] [0x11] 则为大端表示法(big-endian),这摆放的顺序被称为字节序(endianness),不同的 CPU 架构可能会采用不同的字节序。CPU 在从内存中读取 int 的值时,会根据其认可的字节序来理解值。

对于复杂一些的结构体,例如 struct myStruct { int a; char b } s; 来说,我们定义了一个名为 s 的变量,其类型为 struct myStruct,包含了两个成员变量(field),分别为 int 和 char 两个类型。

首先一个问题是,s 会占用多少内存空间?单纯看成员变量,得出的结论是 4+1=54 + 1 = 5,然而有一个重要的规则要求,int 的变量只能从 4 的整倍数的地址上开始存储,即 int 变量能存储在 [104, 108) 这段地址上,但不能是 [102, 106) 这种地址。这个规则被称为地址对齐规则(alignment),类似地,对于 double 这种需要占用 8 个字节的变量,其地址需要按 8 的倍数对齐。因此,如果 s 占用 5 个字节的地址,那么在数组中连续摆放 struct myStruct 时,第二个结构体的 int 成员变量的地址将无法对齐。因此,s 需要占用 8 个字节,末尾的 3 个字节是浪费掉的。读者可以通过 https://godbolt.org/z/x8Kcvjh6s 查看编译器编译的结果,验证 myStruct 变量的确占用 8 个字节。

理解了对齐的规则,其实对结构体的存储表示就呼之欲出了。取决于是否允许对成员变量的摆放顺序进行重新排列,如果是按顺序摆放的话,需要对内部的每一个成员变量都执行对齐的规则,从最近的其大小整倍数的地址上开始摆放。

💡
这里可以出一个编程题,感兴趣的读者应当尝试实现。给定一个结构体的成员变量,计算在不重新排列成员变量的情况下该结构体的最小的内存占用大小。如果允许重新排列呢? 例如对于 struct myStruct { int a; char b; int c; char d } s; 来说,考察 s 占用的内存空间,如果不重新排列成员变量,那么基于上述的地址对齐规则,s 占用的内存是 4+4+4+4=164 + 4 + 4 + 4 = 16。如果可以重新排列成员变量,那么成员变量的顺序可以是struct myStruct { int a; int c; char; char d } s; 那么 s 占用的内存是 4+4+4=124 + 4 + 4 = 12

本质上说,内存只负责储存字节,需要程序来理解这些存储的字节数据的意义,指挥 CPU 对数据进行各种操作。而程序对数据的理解则来源于变量的类型。同样的 4 个字节,如果按照 int 理解,那么其值就是整数;如果按照 float 理解,那么其值就是浮点数。

💡
读者在后文了解指针后,可以尝试写一个程序,通过逐字节赋值,把 int 变量存储的内容复制到 float 变量中,来验证类型对数据的理解。

回到“通过地址来读取或者修改这个变量的值”的问题上来。

光有地址,我们只能更好地理解变量的表示,想要真正发挥其能力,还需要引入指针的概念。

本质上说,指针就是一个存储地址的变量,所有的指针都是。

因此,所有指针在内存中的大小都是固定的。在过去的 32 位 CPU 上,这个大小为 4 个字节;在现在,大部分 CPU 都是 64 位,这个大小为 8 个字节。32 位、64 位的意思本质上就是允许用来表示地址的值大小,32 位 CPU 可以读取的地址的值可以用 32 个 bit 来表示,一个 byte 等价于 8 个 bit,因此作为存储地址的指针需要 4 个字节;而 64 位 CPU 可以访问的地址的值需要 64 个 bit,则指针需要 8 个字节。计算机世界里,很多东西都是有迹可循、有理可依的,读者应当多问为什么、多探索这背后的机理。

一个 int 指针,定义为 int* intPtr; ,表示其值作为地址开始往后的四个字节,存储了一个 int。类似的,一个 char 指针 char* charPtr; 表示其值作为地址的那个字节存储了一个 char;或者 myStruct 指针 struct myStruct* myStructPtr; 定义了一个名为 myStructPtr 的指针变量,其值作为地址开始往后的 8 个字节,存储了一个 struct myStruct。形象地说,我们称某个类型的指针在内存中指向了一个具有某个类型的变量。这个形象的比喻其实是让初学者迷惑的主要原因。特别是当我们学习到指针的指针的时候。

如果我们想要访问指针指向的变量时,我们需要使用一个特殊的运算符 *,这个运算符被称为解引用(dereference)运算符。对于指针 intPtr 而言,*intPtr 就表示内存中 intPtr 所指向的 int。如果我们写 *intPtr = 3 ,就是在给这个 int 赋值;而如果我们写 printf("%d\n", (*intPtr) * 2),则是打印这个 int 与 2 乘的结果。请注意不要把解引用运算符和乘法运算,甚至是定义指针时所写的 * 搞混。

聪明的读者应该已经发现了,解引用运算和取地址运算互为逆操作。给定一个 int a = 520; 和一个 int* aPtr = &a;&a 获取了 a 这个变量的地址,于是 aPtr 存储了这个地址。因此,当我们写 *aPtr = 1314 的时候,a 这个变量的值就变成了 1314,而在任何我们需要 a 这个变量的值的时候,我们都可以写 *aPtr 来参与运算。

额外补充一下数组与指针的关系。数组本质上就是一个指针。例如 int arr[233]; 这样一个数组, arr 是可以当作一个指向数组在内存中第一个字节的地址的 int 指针来使用的。因此 *arr 等价于 a[0] 。得益于数组的元素在内存中是连续摆放的,C 语言还支持对指针进行加减法的运算,这被称为指针算术(pointer arithmatics)。不同于对数值的加减法运算,arr + 1 的值是 arr 的值加 4,因为指针的类型是 int。因此 *(arr + 1) 等价于 a[1]

只有光秃秃的地址,我们无法理解这个地址中存储的值所表示的意义,因此我想强调的是指针需要类型帮助我们理解地址中的值。

一个指针中存储的地址,在解引用时究竟意味着什么,完全取决于这个指针的类型。类型明确了变量在内存中占用空间的大小,也明确了程序应该如何理解数据。

所以,一个 int 类型的指针,其存储的地址在解引用的时候应该按照 int 来理解。臭名昭著的指针的指针,不过是一个具有指针类型的指针而已,解引用这个指针就得到了另一个指针。

在理解取地址、解引用之后,我们来看一个具体的链表的 C 语言实现的例子。

首先我们定义一个结构体。

struct ListNode {
	int val;
	struct ListNode* next;
};

这个结构体包含两个成员变量,val 表示链表中元素的值,而 next 则是一个指向下一个元素的指针。

程序在运行过程中,可以动态地向操作系统索要内存空间,使用 malloc 函数,可以获得内存中一段连续的空间用来存放数据。

struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));

上面这一行代码调用了 malloc 函数申请了一端用来存放 struct ListNode 的内存空间。malloc 接受一个表示所需内存空间大小的值,这里我们使用 sizeof 运算,得到一个 struct ListNode 的大小。在上面了解了对齐规则后,我们知道,这个大小应该是 16。而 malloc 函数的返回值为开辟出的内存的首字节的地址。注意,malloc 函数返回的地址是没有类型的(没有类型的指针用void* 类型表示),因为 malloc 函数的参数只告知了内存大小,而没有告知数据类型,因此需要进行一次强制类型转换。malloc 函数前的 (struct ListNode*) 表示将这个地址理解为一个 struct ListNode 的指针,这和我们为 newNode 变量声明的类型是一致的。

我们来看一段构建链表的代码。

struct ListNode* constructList(int* vals, int len) {
	struct ListNode* head = NULL;
	struct ListNode* last = NULL;
	for (int i = 0; i < len; ++i) {
		struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
		newNode->val = vals[i];
		if (last == NULL) {
			head = newNode;
			last = head;
		} else {
			last->next = newNode;
			last = newNode;
		}
	}
	last->next = NULL;
	return head;
}

这段代码的逻辑应当是好理解的。head 表示链表的第一个元素,last 表示最后一个元素,在插入元素的时候,如果 head 是空,则初始化 head 和 last 都为这个元素;否则我们把这个元素接到 last 后面,然后更新 last 为新的元素。

这样写的代码的唯一的问题是,给定的 if 判断其实是冗余的,只要我们愿意使用指针的指针,这段代码可以更简洁地写作

struct ListNode* constructList(int* vals, int len) {
	struct ListNode** head = (struct ListNode*)malloc(sizeof(struct ListNode*));
	struct ListNode** cur = head;
	for (int i = 0; i < len; ++i) {
		struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
		newNode->val = vals[i];
		*cur = newNode;
		cur = &(newNode->next);
	}
	*cur = NULL;
	return *head;
}

我个人更倾向于后一种写法,只要正确、深刻地理解指针的概念,后面这种写法所表现出来的简洁性更加具有美感。

我们可以逐行地进行分析。

前两行代码定义了两个可以指向类型为 struct ListNode* 的变量的指针,换言之就是指针的指针。head 初始化为了一个通过 malloc 申请的 struct ListNode* 的地址,而 cur 也同样指向这个 struct ListNode* 的空间。见下图,head 本身占用 8 字节的空间,地址为 [302, 310),其存储的地址为 1000,指向 malloc 返回的地址。因为 malloc 申请的 struct ListNode* 也是一个指针,所以其大小也为 8 个字节。cur 的地址为 [310, 318) 同样指向这个指针。

head: [302, 310) ---> [1000, 1008)
                      ^
cur: [310,  318) -----|

随后,对于每一个链表中的元素,我们都通过 malloc 在内存中申请一个 struct ListNode 的空间,并为其 val 赋值。随后的

		*cur = newNode;
		cur = &(newNode->next);

是这个实现中最关键的地方。

newNode 的值是 malloc 返回的 struct ListNode 在内存中的地址,malloc 申请的空间的大小为 16 个字节(因为对齐规则)。所以 *cur = newNode 等价于把 malloc 返回的新节点的地址复制到 [1000, 1008) 所表示的内存空间上去。

head: [302, 310) ---> [1000, 1008) ---> newNode: [2000, 2016)
                      ^
cur: [310,  318) -----|

假设 newNode 的地址为 [2000, 2016),那么 newNode→next 的地址则为 [2008, 2016),所以而后的 cur = &(newNode→next) 则让 cur 指向了 [2008, 2016)

head: [302, 310) ---> [1000, 1008) ---> newNode: [2000, 2008, 2016)
                                                 [val,  next)
                                                        ^
cur: [310,  318) ---------------------------------------|

随后的迭代中,我们每次修改 *cur 就相当于让尾部节点的 next 等于新的节点,然后修改 cur 则相当于让 cur 指向新节点的 next 指针。

head: [302, 310) ---> [1000, 1008) ---> [2000, 2008, 2016)
                                        [val,  next)
																							 |
                                               ---> newNode: [3000, 3008, 3016)
                                                             [val,  next)
                                                                    ^
cur: [310,  318) ---------------------------------------------------|

最后的 *cur = NULL 让最后一个节点的 next 置为 NULL,表示链表的终结。

head: [302, 310) ---> [1000, 1008) ---> [2000, 2008, 2016)
                                        [val,  next)
																							 |
                                               ---> newNode: [3000, 3008, 3016)
                                                             [val,  next) ---> NULL
                                                                    ^
cur: [310,  318) ---------------------------------------------------|

而最开始的 head 指向的指针正是第一个节点的指针,所以返回 *head 即可。

到这里,读者应该理解了上述实现。事实上 Linux 的创始人 Linus 推崇下面这种写法,并称之为 good taste(好的品味)。

感兴趣的读者应当阅读 https://github.com/mkirchner/linked-list-good-taste 并理解其中通过指针的指针来删除节点的做法,它用到的知识就是本文所谈论的。

希望读者在这篇文章之后彻底理解指针的概念,并善于利用指针写出更优雅的代码。