《C语言学习：链表》19

写在前面：本笔记为个人学习各平台C语言系列课程所作，仅供交流学习，不得作他用。

1. 定义

（1）链表定义

整个链表里，第一个成员需要有一部分表示这是链表的头，最后一个成员需要有一部分表示这是链表的尾。除最后一个成员外，其他每个成员的结构都是一部分表示数据，一部分表示地址，该地址指向下一个成员。

把链表里每一个成员（数据+指针）叫做结点。头文件里通常定义结点结构：

这里node第二个成员实际上是一个指向同样类型变量的指针，这里不能省略struct，因为还没有定义完。

（2）主函数实现链表例子

尾插法实现单链表，这一段代码放在主函数里。

第一句表示初始化链表，找到头。head=null代表链表现在是空的，没有任何节点。

在循环里，不断读入数字直到number为-1，把每一个有效数字放入链表。这个过程被表示为：读入一个有效数，新建一个结点p，malloc分配给它对应内存，让其数值部分为读入有效数字、指针部分（p.NEXT）为NULL，因为默认没有后续结点。

判断部分：新建结点last=head。如果链表为空（对于else部分），新结点就是首个结点；如果链表非空（对应if成立，head不为NULL），循环走到末尾结点（last.next为NULL时就是末尾结点，跳出），再把新建的结点p挂在当前末尾结点last的尾部。

2. 链表函数add()

这个函数其实就是把上一节定义部分循环里的内容单独领出来整成一个函数，作用是往链表最后新加一个值。稍有不同的是，这里单独新定义了一个结构_list，里面只放了一个指针head。

这是因为在调用这个添加元素的函数时，我们需要知道新的head指向哪里，但如果只把head作为变量传入自定义函数，在自定义函数里修改的head对主函数head没有用，作为全局变量的话又不方便移植。但如果作为一种新的结构体，不仅解决了这一问题，还能够在这个新结构体里加上更多元素，实现其他功能，比如可以考虑加上元素末尾tail。

3. 链表搜索

这个函数实现了遍历链表并打印值的功能。这里p不一定要=p.next，可以根据具体情况具体安排。

这一段核心就在这个for循环。

4. 链表删除结点

链表删除当前结点，需要做两步：一是让前一个结点的next指向后一个结点，二是把当前结点的内存释放。实现这一步需要两个指针，一个指向当前结点，一个指向前一个结点。

这一段放在主函数就行。

这里循环的起始有两个值，但是结束条件只有p为NULL，所以q是一个不安全的指针，有可能出现q在循环时指向了最后一个结点的下一个（不存在！！！）

用一种机械的方式去判断循环或数组边界：当错误会发生在赋值的左边时，就有问题。

因此这里额外加了判断，在p.value=num的情况下（找到值），判断是否q存在（当p指向第一个结点时q无）：存在，则赋值q，使前一个结点跳过当前结点指向后一个结点；不存在，则赋值head，直接删去第一个结点。

5. 链表清除

链表使用完之后需要全部清除，每一个结点都是malloc出来的，需要释放。

挨个释放即可，放在主函数最后。