好久没看数据结构，昨天一个简单的单链表写了 1 个小时。期间还出了一个 bug，关于链表表头传参。

为了创建表头，当时我在 main 函数中声明了临时变量 part* head = NULL，我想通过函数来改变 main 函数中 head 存放的 NULL，来完成链表的创建。事实证明，这样的方法是十分愚蠢的，错误详细代码在 “2 向函数传递二级指针”部分。

0. 使用全局变量

答案上表头是使用全局变量定义的：

#include<stdlib.h>
#include<stdio.h>

typedef struct part {
	int number;
	struct part* next;
}part;

part* head = NULL; // 定义全局变量

void add() {

	part* node = (part*)malloc(sizeof(part));
	if (node == NULL) {
		printf("full\n");
		exit(EXIT_SUCCESS);
	}
	node->next = NULL;

	printf("Enter number of part: ");
	scanf("%d", &node->number);

	if (head == NULL) {
		head = node;
	}
	else {
		part* cur = head;
		while (cur->next != NULL)
			cur = cur->next;
		cur->next = node;
	}
}

void print() {

	for (part* cur = head; cur != NULL; cur = cur->next)
		printf("%d\n", cur->number);

}

int main(void) {

	add();
	add();
	add();
	print();

	return 0;
}

观察这个程序发现，因为使用的是全局变量，所以函数都是不带参数的。

数据段存储的全局变量作用域是从定义处到文件末

1. 使用“哨兵”结点

这个思路是表头也是 malloc 得来的，但是表头不存储有用信息。遍历链表从head->next开始。

#include<stdlib.h>
#include<stdio.h>

typedef struct part {
	int number;
	struct part* next;
}part;


void add(part* head) {
	
	part* node = (part*)malloc(sizeof(part));
	if (node == NULL) {
		printf("full\n");
		exit(EXIT_SUCCESS);
	}
	node->next = NULL;

	printf("Enter number of part: ");
	scanf("%d", &node->number);

	if (head->next == NULL) {
		head->next = node;
	}
	else {
		part* cur = head;
		while (cur->next != NULL)
			cur = cur->next;
		cur->next = node;
	}
}

void print(part* head) {

	for (part* cur = head->next; cur != NULL; cur = cur->next)
		printf("%d\n", cur->number);
		
}

int main(void) {
	
	part* head = (part*)malloc(sizeof(part));
	if (head == NULL) {
		printf("表头创建失败！");
		exit(EXIT_SUCCESS);
	}
	head->next = NULL;

	add(head);
	add(head);
	add(head);
	print(head);

	return 0;
}

可以发现，表头是在 main 函数中 malloc 得来的，调用函数需要传参。

2. 向函数传递二级指针

这个方法是通过在 main 函数中创建一个指针作为表头（不是 malloc 来的）

为什么要使用二级指针？我们先来测试一下不使用二级指针直接传参会发生什么：

这个程序和上面使用哨兵的程序整体差不多，只需要在 main 函数中删除 malloc 部分，然后将遍历链表改为直接从head开始即可：

#include<stdlib.h>
#include<stdio.h>

typedef struct part {
	int number;
	struct part* next;
}part;


void add(part* head) {
	
	part* node = (part*)malloc(sizeof(part));
	if (node == NULL) {
		printf("full\n");
		exit(EXIT_SUCCESS);
	}
	node->next = NULL;

	printf("Enter number of part: ");
	scanf("%d", &node->number);

	if (head == NULL) {
		head = node;
	}
	else {
		part* cur = head;
		while (cur->next != NULL)
			cur = cur->next;
		cur->next = node;
	}
}

void print(part* head) {

	for (part* cur = head; cur != NULL; cur = cur->next)
		printf("%d\n", cur->number);
		
}

int main(void) {
	
	part* head = NULL;

	add(head);
	add(head);
	add(head);
	print(head);

	return 0;
}

我们输入：

121
122
123

程序没有任何输出。调试发现，第一次离开 add 函数后 head 就变回了 NULL，为什么会这样？请看下图：

传递二级指针：

#include<stdlib.h>
#include<stdio.h>

typedef struct part {
	int number;
	struct part* next;
}part;


void add(part** head) {
	
	part* node = (part*)malloc(sizeof(part));
	if (node == NULL) {
		printf("full\n");
		exit(EXIT_SUCCESS);
	}
	node->next = NULL;

	printf("Enter number of part: ");
	scanf("%d", &node->number);

	if (*head == NULL) {
		*head = node;
	}
	else {
		part* cur = *head;
		while (cur->next != NULL)
			cur = cur->next;
		cur->next = node;
	}
}

void print(part** head) {

	for (part* cur = *head; cur != NULL; cur = cur->next)
		printf("%d\n", cur->number);
		
}

int main(void) {
	
	part* head = NULL;

	add(&head);
	add(&head);
	add(&head);
	print(&head);

	return 0;
}

可以发现，向函数传递的是指针变量 head 的地址。所以在函数中修改或使用 head 指向的链表的首指针时需要先解引用。