【蓝因子教育】 单链表/双向链表的建立/遍历/插入/删除！

给同学们的C语言课程设计练习作业一下难了不止一个档次，很多小伙伴第一次接触到了C语言的框架开发，了解了View（界面层）、Service（业务逻辑层）、Persistence（持久化层）的分离和耦合，一种面向过程的MVC的感觉。

而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出......

一、链表结构和静态/动态链表

二、单链表的建立与遍历

三、单链表的插入与删除

四、双向链表的概念

五、双向链表的建立与遍历

六、双向链表的元素查找

七、循环链表的概念

八、合并两个链表的实例

九、链表实战

拓展思维、拉到最后去看看 (•̀ᴗ•́) ̑̑

一、链表结构和静态/动态链表

链表是一种常见的数据结构——与数组不同的是：

1.数组首先需要在定义时声明数组大小，如果像这个数组中加入的元素个数超过了数组的长度时，便不能正确保存所有内容；链表可以根据大小需要进行拓展。

2.其次数组是同一数据类型的元素集合，在内存中是按一定顺序连续排列存放的；链表常用malloc等函数动态随机分配空间，用指针相连。

链表结构示意图如下所示：

在链表中，每一个元素包含两个部分；数据部分和指针部分。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表示指向的地址为空。整体用结构体来定义，指针部分定义为指向本结构体类型的指针类型。

静态链表需要数组来实现，即把线性表的元素存放在数组中。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在数组单元的下标。这些元素可能在物理上是连续存放的，也有可能是不连续的，它们之间通过逻辑关系来连接——这就要涉及到数组长度定义的问题，实现无法预知定义多大的数组，动态链表随即出现。

动态链表指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相连的关系。

二、单链表的建立与遍历

单链表中，每个结点只有一个指针，所有结点都是单线联系，除了末位结点指针为空外，每个结点的指针都指向下一个结点，一环一环形成一条线性链。

链表的创建过程：

接下来在源码中建立并遍历输出一个单链表。

三、单链表的插入与删除

在本实例中，插入时根据传递来的学号，插入到其后。

删除时根据其所在链表的位置，删除并释放该空间。

主函数增加如下：

插入函数：

删除函数：

四、双向链表的概念

双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。

在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域；一个存储直接前驱结点地址，一般称之为左链域。

双向链表结构示意图：

五、双向链表的建立与遍历

双向链表的源码实战和单链表类似，只是多了第二个指针域的控制，这里直接贴上没有注释的源代码。

六、双向链表的元素查找

查找函数 STUD *search(STUD *,char *);

七、循环链表的概念

类似于单链表，循环链表也是一种链式的存储结构，由单链表演化而来。

单链表的最后一个结点的指针指向NULL，而循环链表的最后一个结点的指针指向链表头结点。

这样头尾相连，形成了一个环形的数据链。

循环链表的建立不需要专门的头结点。

判断循环链表是否为尾结点时，只需判断该节点的指针域是否指向链表头节点。

八、合并两个链表的实例

建立两个带头节点的学生链表，每个节点包含学号、姓名和成绩，链表都按学号升序排列，将它们合并为一个链表仍按学号升序排列。

算法分析：

合并链表用merge()函数实现。函数中定义3个工作指针a、b、c，其中a、b分别指向La链表、Lb链表的当前结点，C指向合并后的链表尾结点。合并后链表的头结点共用La链表的头结点。

①合并前，先让a和b分别指向两个链表的第一个结点，c指向La链表的头结点。

②合并时应该分3种情况讨论，即La和Lb都没有处理完；La没处理完，但Lb处理完毕；Lb没处理完，但La处理完毕。

③合并过程中应始终将La和Lb链表中较小的一个链接在Lc中，方能保持有序。

九、实战

拓展思维、(•̀ᴗ•́) ̑̑

既然双向链表可以多出一个指针域用来指向前一个结点，用llink和rlink区分这两个指针域；

那么有没有可能再多几个指针域来放ulink和dlink呢（指向上面的结点和指向下面的结点）？

这样就构成了形象的二维链表而不是一维链表了。

当然，在物理内存上这些链表依然是线性关系。

理论可以实现，那么三维链表呢？