C语言链表

链表

什么是链表

数据结构→数据存放的思想

数组数据的集合
数组是在内存连续的一段空间存放数据
结构体
大小和数组不一样，可以放很多数据

数组和结构体的缺点：地址连续，增加删除元素困难，删除一个空间后把后面的所有数据往前移动，运算量大

链表解决了上述问题
C语言链表

A指针变量存放b的地址，b存放c的地址
给整个数据的存储添加很多的灵活性
比如说要删除b，只需把a的地址指向c即可

例子
C语言链表

此时的数组是一串连续的数据
而这三个结构体是互相没有联系的三个地址中存放了数据
若要他们有联系，那么需要在他们中引入地址
C语言链表

指针存放的是地址，所以需要取址符
输出
C语言链表

这样输出也可以
C语言链表

有了结构体的next指针
可以将三个离散的地址联系起来，并且相较于数组，删改更方便
可以通过链表头——t1，就可以遍历整个链表

链表的遍历

提到数组的缺点
C语言链表

这个数组只有三个空间，如果还要加一个空间，就造成了数组溢出
而链表就非常简单，只要在后面链接一个就可以了
C语言链表

遍历链表的函数体
C语言链表

形式参数为一个结构体指针
这个指针作为链表的头，用point指针控制输出
用point指针先将链表头中的数据输出，
然后将point赋值为链表头中的next地址，即下一个链的地址
由此反复，直到下一个为初始值设置的NULL结束
这里要传递的实际参数是链表头的地址，如果穿链表头的next，就相当于传了第二个地址，那么链表头的数据data就没有输出
全代码
C语言链表

复杂的业务场景需要很多的数据类型，就像学生成绩实例一样。所以需要用到结构体
链表就是在结构体的基础上多了一个存放下个地址的指针。

链表的查找

链表的个数只需要设置一个num来记录head的地址变化的次数即可
函数体如下
C语言链表

Num初始值设为0，第一次地址变化成第二个链的地址，记1
第二次地址变化成第三个链的地址，记2
第三次地址变化成第四个链的地址，记3
第四次地址变化成第四个链中存放的NULL地址，记4

通过链表遍历来一个个对比数据，如果数据对了就返回1，没找到就返回0，然后在主函数中判断
函数体
C语言链表

主函数中判断部分
C语言链表

结果
C语言链表

链表的插入

比如要在第三个链的后面插入一个数据
那么只要先找到3
再把3所在链存放的地址指向要加的那个数据的地址
然后把所加数据中的指针指向原来第三个链后面的链的地址
函数体部分
C语言链表

在实际编写中遇到几个问题
在while循环中，是用来遍历整个链表，如果把没有找到就退出编写一个else语句放在if后面while的里面，就会造成，程序只找一次，只对链表头里面的数据进行判断
C语言链表

如果先把找到3，3链的next地址给要插入的链，那么此时这个next的地址就是要插入链的地址，可以看到结果最后无限输出插入的10
C语言链表

如果想指向next地址存放的next,
此时的head->next已经被赋值成要插入的point的next，就是说找到的数据后面一个链是要插入的那个链的地址
插入链的next是初始化的值NULL
那么在编写的遍历输出函数中，遇到null就停止输出
C语言链表

最后一个值就没有输出来
所以正确的做法是先将找到的3所在链中的next，把这个next给到要插入的链的next
再把找到的3所在链中的next赋值成要插入的链的地址

于是在最开始所述的插入的流程有些许错误
插入的流程应为
先找在哪一个数据后面插入
把找到的数据所在的链中存放的next地址给到要插入的链中存放的next地址
最后再把找到的数据所在的链存放的next地址赋值成要插入的地址
全代码
C语言链表

在指定节点前方插入数据

在前方插入需要考虑是不是在链表头的前面插入，如果在，那么新的链表头变成插入的那个数
函数体
C语言链表

结果
C语言链表

在实际情况中需要进行判断，判断是不是头节点

插入函数代码
C语言链表

形式参数有一个会在他前面插东西的数据，头节点的地址，要插入的节点的地址
先保存头节点的位置
判断这个节点是不是头节点，头节点和其他情况不同
若不是头节点，则遍历找到前面要插新节点的数据（这里的数据用前面一个节点存放的next指针指向的数据来判断，这样就可以插在前面一个数据的后面，比较简单）
先把找到的数据的前一个节点存放的next指针赋值给新节点的next，再变动找到的数据的前一个节点存放的next指针，把他赋值为新节点的地址
返回head的原始地址，因为在遍历的时候head会变化，如果直接返回head，就会使找到的数据的前一个节点变为头节点，这个新头节点的前几项会消失
C语言链表