Question

所谓单向链表，就是每个节点的指针域中只含有一个指向其后继节点指针的链表，如图 8.2 所示。

图 8.2　单向链表

在单向链表中，只能从头节点开始，不断地通过指向后继节点的指针，来逐个地向后访问遍历其他链表节点，最后一个节点的指针域为一个空指针，表示其没有后继节点了。

为了使用单向链表，必须定义相应的节点类型，由于节点具有数据域和指针域两个部分，因此，应该选用结构体来进行定义。例如：

定义了结构体 node，它有两个成员：int 类型的成员 data 和 struct node*类型的成员 next。初次看到这样的成员，可能会很茫然。成员 next 的类型和结构体 node 的类型怎么如此的相似呢？仔细看，在“struct node”和“next”之间有个星号，表示所定义出的成员 next 是 struct node 类型的指针。这是允许的，因为 C 语言中，所有类型的指针的大小是固定的，并不会随着指针的类型不同而改变。反之，如果在“struct node”和“next”之间没有这个星号就是错误，C 语言中，不允许在结构体的定义中，出现和结构体相同类型的成员，因为要想得知结构体的大小，就得知道其所有成员的大小，而成员的类型又和结构类型相同，那么若想知道成员的大小，就必须得先知道结构体的大小。这就出现了死锁现象，变成了无限的递归定义，就好像遇见那道“世界上是先有鸡，还是先有蛋”的亘古难题。

可以将结构体 node 看成是一个链表的节点类型，数据域部分是成员 data，而指针域部分是成员 next。为了方便，定义一个创建节点的函数 createNode，代码如下：

createNode 函数只有一个 int 类型的参数 val，用于表示新创建节点数据域部分的值，函数返回值为指向新创建节点的指针。在函数体中，首先通过 malloc 函数在堆中申请分配一块节点大小的内存空间，并让指针 pnode 指向这块内存。然后通过 if 语句判断申请分配内存是否成功，若成功则将这块内存作为新创建节点的存储区域，并通过指针 pnode 来给节点的数据域和指针域部分赋值，即将参数 val 赋值给成员 data，由于此时所创建的是一个单独的节点，并不知道是否会有后继节点，因此，将成员 next 的值赋为 NULL。最后，通过 return 语句返回指向堆中所创建的节点的指针。

下面定义将节点加到链表的函数 addNode，代码如下：

addNode 函数有两个参数，其中参数 pheadptr 是一个二级指针，表示指向链表头节点指针的指针，使用二级指针的目的，是为了能在函数中修改实参，而这个实参应为指向链表头节点的指针。另一个参数 val 是所添加节点的值，即节点的数据域部分。函数的返回值为 int 类型，值为 1 表示添加节点成功，值为 0 表示添加节点失败。

在函数体中，首先以 val 作为参数，调用 createNode 函数在堆中创建新节点，并由指针 p 指向该节点；然后，通过 if 语句检查新节点是否创建成功，若指针 p 为空指针，则表示节点创建失败，通过 return 语句返回 0，表示向链表添加节点失败；接着，再通过 if…else 语句判断指向头节点的指针是否为空指针，由于 pheadptr 是一个二级指针，因此，对它进行解引用即可访问到实参指针（即指向链表头节点的指针，简称头指针）。若实参指针是空指针，则表示此时的链表是一个空链表，就会将指针 p 赋值给实参指针，即将新节点作为链表的头节点，并让实参指针指向这个新节点。若实参指针不是空指针，则表示此时的链表并非空链表，就会执行 else 部分，定义一个临时指针 ptmp，并让它指向链表头节点，然后通过 while 循环语句找到链表的尾节点（即成员 next 的值为 NULL 的节点），再将尾节点的成员 next 赋值为指针 p，即表示将原来尾节点作为新创建节点的前驱节点，而新创建节点则成为链表的尾节点了。需要注意的是，在 while 循环的条件判断处，是通过检查指针 ptmp 所指向节点的成员 next 的值是否为空来决定是否执行循环体的，如果指针 ptmp 所指向节点的成员 next 的值为空，则表示指针 ptmp 已经指向了链表的尾节点，此时会终止 while 循环。如果指针 ptmp 所指向节点的成员 next 的值不为空，则会将其成员 next 的值重新赋值给指针 ptmp，即让指针 ptmp 指向原先节点的后继节点（即下一个节点），并再次执行下轮循环，直到指针 ptmp 所指向节点的成员 next 的值为空时止。由于指针 ptmp 是一个临时指针，因此，在 while 循环中，对指针 ptmp 的修改是不会影响到实参指针的，所以要注意它和 if 部分的指针使用方式的区别；最后，函数通过 return 语句返回 1，表示向链表添加节点成功。由此可见，每次调用 addNode 函数，都是将新创建的节点添加到链表的尾部。

为了能够方便了解当前链表中节点的个数，还可以定义一个专门用于统计链表节点数量的 countOfNodes 函数，代码如下：

countOfNodes 函数只有一个参数 headptr，它是指向链表头节点的指针，这里没有使用二级指针，是因为在函数中不需要去修改实参的值，实参应为指向链表头节点的指针。函数返回值被定义为 unsigned 类型，因为链表节点的数量不可能是一个负数。

在函数体中，首先定义了一个 unsigned 类型的变量 c 并初始化其值为 0，用于统计链表中节点的个数；在 while 循环中，通过检查形参指针 headptr 是否为空来决定是否执行循环体，初始指针 headptr 是指向链表头节点的，若为空，则说明是空链表，循环终止，若不为空，则说明链表中有节点，则执行循环体。在循环体中，会对变量 c 进行自增运算，并修改形参指针 headptr 的指向，将指针 headptr 所指向节点的成员 next 的值重新赋值给指针 headptr，即让指针 headptr 指向头节点的后继节点（下一个节点）。然后再次执行下轮 while 循环，并重新检查指针 headptr，以此类推，直至指针 headptr 为空指针时循环终止；最后通过 return 语句返回变量 c 的值。

同样地，countOfNodes 函数中的形式参数 headptr 只是一个普通指针，因此，在 while 循环的循环体中，对指针 headptr 的修改不会影响到实参指针。

知道了如何统计节点数量，那么想要遍历并打印链表节点就很容易了，可以定义专门用于遍历打印链表节点的函数 printAllNodes，代码如下：

和 countOfNodes 函数的不同之处在于 while 循环中将变量自增换成了 printf 函数调用，将指针 headptr 所指向节点的数据域部分打印输出，并在所有节点打印完毕之后，进行一个换行的操作。

对于节点的删除，算是链表中最为复杂的操作之一了。因为链表的节点可能是分散存储于内存的不同地方，靠着节点的指针域来进行节点间的联系，稍不小心，就可能会使链表的整体或部分断裂，造成数据的丢失和内存的泄漏。因此，在删除链表节点的同时，要精心地维护好节点间的关系。

对链表节点进行删除时，分以下两种情况。

1．头节点的删除

由于头指针是指向链表头节点的，因此，想要删除头节点，应该先用一个临时指针指向头节点，然后将头指针修改为指向链表第二个节点，最后再通过临时指针将原头节点所占用的内存空间释放回收即可，如图 8.3 所示。

图 8.3　头节点的删除

删除 1 号节点步骤：①用临时指针指向 1 号节点；②使头指针指向 2 号节点；③通过临时指针释放回收 1 号节点的内存空间。

2．非头节点的删除

对于非头节点的删除，首先要找到欲删除节点的前驱节点，将其成员 next 的指针指向欲删除节点的后继节点，然后再将节点删除并释放回收内存空间，如图 8.4 所示。

图 8.4　非头节点的删除

删除 2 号节点步骤：①用临时指针指向 2 号节点；②使 1 号节点的 next 指针指向 3 号节点；③通过临时指针释放回收 2 号节点内存空间。

删除链表节点的函数 deleteNode 的代码如下：

deleteNode 函数有两个参数，由于在头节点的删除中需要修改头指针，因此，参数 pheadptr 被定义为二级指针，即一个指向头指针的指针，参数 loc 是 unsigned 类型的变量，它用来表示欲删除节点的位置，即删除链表中的哪一个节点。函数返回值为 int 类型，如果节点删除成功返回 1，节点删除失败返回 0。

在函数体中，首先调用 countOfNodes 函数获取当前链表中的节点数量，并将节点数量保存至变量 c 中；然后通过 if 语句检查参数 loc 的值是否合法，如果 loc 的值大于链表节点数量，则直接通过 return 语句返回 0，表示删除节点失败；接着定义一个指针 p 并让其指向链表头节点；再通过 if 语句检查要删除的节点是否头节点，若 loc 的值等于 1，则表示对链表头节点的删除，执行 if 部分，即让头指针指向头节点的后继节点，并调用 free 函数对原头节点的内存进行释放回收。若 loc 的值不等于 1，则表示对链表非头节点的删除，会执行 else 部分，即通过 for 循环让指针 p 指向欲删除节点的前驱节点，其中循环变量 i 是从 2 开始循环的，例如想删除链表中第 2 个节点，则该循环的循环体不会被执行，指针 p 还是指向链表头节点的，而第 2 个节点的前驱节点就是头节点。接下来再定义一个指针 pdel，用来指向欲删除的节点，随后让欲删除节点的前驱结点的 next 指针指向欲删除节点的后继节点，即将欲删除的节点从链表中脱离，并让其前驱节点和后继节点建立联系；最后再调用 free 函数，释放、回收被删除节点的内存空间；函数体的最后，通过 return 语句返回 1，表示删除节点成功。

有了删除某一位置节点的 deleteNode 函数后，就可以通过它来实现链表所有节点的删除，例如定义一个删除链表所有节点的函数 deleteAllNodes，代码如下：

deleteAllNodes 函数没有返回值，只有一个参数 pheadptr，由于需要修改头指针，因此，也被定义为一个二级指针。在函数体中只有一个 while 循环，并将调用 countOfNodes 函数的结果作为循环的条件，即链表中节点数量不为 0 时执行循环体，为 0 时终止循环。在循环体中通过调用 deleteNode 函数，并将整数 1 作为其第 2 个参数，这表示将链表中的头节点删除。该函数会依次将链表中的头节点删除，直至成为空链表。

最后在主函数中测试这些函数，检查链表节点的创建、添加、统计和删除是否正确。相关代码如下：

编译运行程序，结果如下：

The number of linked list nodes is:5
10 20 30 40 50
Delete the node at location 2.
The number of linked list nodes is:4
10 30 40 50