如果说学习过《计算导论与C语言基础》，你已经迈入了C语言的殿堂，那么《C程序设计进阶》将帮助你更上一层楼，理解“结构化程序设计的基本思想”，掌握“C程序设计的基本技巧”，养成“良好的编程习惯和编程风格”，编写出“真正具有生命力的计算机程序”。完成这门课的学习，你将能解释C程序设计语言的基本概念与知识，并且使用C语言编写计算机程序解决生活工作中的实际问题。
链表的操作
Loading...
来自 Peking University 的课程
C程序设计进阶
597 个评分
从本节课中
结构体与链表
这次课，我们将为大家讲解“结构体”的基本概念、定义方式和使用方式，结构体的使用将为某些程序的编写带来极大的便利：）在此基础上，我们还将介绍“链表”的基本概念和创建方法。需要说明的是，在我们的课程上，链表将不作为一个重点练习的内容，因为，在后续的课程中，它将被反复大量的讨论：）
与讲师见面
Ge Li 李戈, Ph.D.Associate Professor
School of Electronics Engineering and Computer Science
在完成链表的创建之后呢，我们再来看一下，对链表的操作。
那么在使用链表的过程中啊，有一些操作是我们经常需要进行的。
那么我们分别来看一下。首先呢，我们先来看一下链表的遍历。
所谓的遍历就是一个一个的去访问。啊，把这些值啊，都打印出来。比方说，在我们给出的左边的这个程序里头，
我们就使用了一个 while
循环。啊，也就是说呢，我们定义了一个临时的指针 pointer ，
让它指向链表的第一个元素。那么在访问完这个 元素以后呢，用
pointer 的 next 给 pointer 赋值，这样的话， 就使得 pointer
往后移动了一个结点。啊，那么一个一个结点移下去， 如果 pointer next 不等于 NULL ，我就一直移下去。
那么通过这种方式呢，我就可以完成对链表的遍历。
接下来呢，我们再来看一下，链表中结点的删除。那么要从一个链表中删除一个结点啊，
我们需要分不同的情况来讨论。首先我们来看一下这个情况。那么原来有一个完整的链表，
当我们想把链表中的第一个元素从链表中删除的时候，
我们应该怎么去操作？
要删除第一个结点是非常容易的。首先呢，我们用一个 temp 指针，找到这个要被删除的结点。
然后呢，如果它是第一个结点的话，我们就直接让这个 head
， 指向它的下一个结点就可以了。那么相应的程序呢，我们可以写成这样
： temp 就等于 head ，然后呢，我们直接把 head
→ next 赋给 head 就完成这个删除了。
当然，我们可以使用 delete 去释放掉这个结点所占用的内存空间。
这是删除第一个结点的情况。那如果我们要删除的是一个
中间结点呢？比方说，我们要删除第三个结点。
那在这种情况下，我们就需要两个辅助的指针来帮助我们完成这个删除。
那么既然我们要删除这个结点，那么删除的办法也很简单，
无非就是让它的前一个结点直接指向它的后一个结点。
那么要实现这个操作，就需要我们使用 temp
去寻找这个结点的同时， 找另外一个指针，跟在 temp 的后面，
因为我们要利用这一个指针对这个结点的 next
指针进行 赋值。那么相应的程序呢，可以写成这个样子。就是说，把
temp 的 next 赋给 follow 的 next。
啊，通过这种方式，我们就把这个结点给删除掉了。当然我们也可以使用 delete 把它释放掉。
那么相应的程序呢，我们就可以写成这样一个函数。那么假设呢，存在一个头为 head
的一个链表。 而且呢，我们要删除它的数据区为 n 的这么一个结点。那么就需要分情况来讨论。
啊，如果链表为空，应该怎么办？如果删除的是第一个结点，应该怎么办？
如果不是这两种情况呢，我们就寻找到要删除的这个结点。如果没有找到，应该怎么办？
最后，除此之外，我们就可以利用 follow → next = temp → next ，
通过这种方式完成结点的删除。
那么这是在链表中删除结点的情况。
那么接下来呢，我们再来讨论一下，如何在链表中插入一个结点。
跟删除的结点相类似，我们也需要分情况来讨论。比方说，
如果我们要在一个链表中所有结点的前面插入一个结点，
啊，那么我们应该怎么去操作呢？ 那么在这儿，我需要特别的提示大家，链表的插入啊，
要特别的小心，因为它的操作是有顺序的。
比方说对于这样一个链表，我们要在它所有的元素前面插入一个新的结点。
那么假设说呢，原来有一个指针将 unit 指向这个结点。那么现在呢，我们要把这个
unit 插入到第一个结点的最前面去。那么我们应该怎么去操作呢？
我们第一步能不能先让 Head 指向这个新的结点啊？可不可以啊？
不可以。为什么呢？因为如果第一步
我们就让 Head 指向这个新的结点， 那么就相当于我们切掉了
Head 这个结点跟任何后续结点的联系。
也就是说，我们再也没办法找到链表中剩下的这些结点了。
那么这些结点呢，就会被丢失掉了。
所以说当我们想在一个链表中插入一个结点的时候，我们的第一步一定是
先让这个新插入的结点指向它的后续结点，从而保证
后续的这些结点不会被丢失掉。所以说在这里插入一个结点的程序是这样的：
首先我们对要插入的这个结点 unit→next
的指针进行赋值，
然后呢，我们再让 Head 指向这个 unit。
啊，是这样的一个顺序。Ok ， 这是在所有的元素前面插入一个结点的情况。
Ok, 那么接下来我们再来讨论一下如何在一个链表的中间
插入一个新的结点。啊，比方说这是一个原来的链表。
我们现在呢，需要在 2 和 3 之间插入一个 0。
啊，这样的一个结点。怎么去操作呢？
那么跟刚才的操作相类似，要在一个链表的中间插入一个新的结点，
我们就需要两个辅助指针帮我们来做这个事情。 temp 在前面， follow
在后面。那么在这种情况下呢，就比刚才要灵活一些。 因为插入位置之前的这个结点由
follow 替你保存， 插入位置之后的这个结点呢，由
temp 帮你保存。啊，所以说在这个时候呢，赋值就会灵活一些。
那么我们可以用这样的程序来完成。 那么在这儿呢，我们首先也是先给 unit →next
的这些赋值。 也就是先建立这个指向关系。然后呢，我们再去给follow →next
的这些赋值，也是什么？ 建立这个指向关系。那么通过这两步就可以完成这个结点的插入了。
那么相应的呢，我们就可以把这个插入结点的程序再写成一个函数
insert。 那这个函数呢就能够帮助我们在一个以 head
为头的结点中 插入一个结点值为 n 的元素。
那么也是呢，需要分情况去讨论。那么感兴趣的同学啊，可以运行一下这个程序，试一下。 Ok,
那么到目前为止啊，我们前面讨论过的链表啊，都是单向链表。
也就是说在这样的链表中呢，每一个结点上只包含一个
指向它的后继结点的指针。
那么除了这种链表之外呢，还有一种非常常用的链表，叫做双向链表。
那么在双向链表中呢，每一个结点上啊，除了数据区以外，
还包含了两个指针。一个呢，是指向这个结点的
后继结点的指针。还有一个呢，是指向这个结点的前区结点的指针。那也就是说啊，
在这一种链表中，从任意一个结点出发都
可以到达链表上的任意其他的结点。
因为每个结点都有指示它向前走的指针，也有指示它
向后退的指针。啊，所以说，这一种链表的使用啊，非常非常的
灵活。只是啊，在这种链表中，想要删除
或者添加一个结点，比单向链表啊，稍微有一点麻烦。 我们来看一下。
首先我们来看一下，如何在这样的一个链表中删除一个结点。那么比方说，在
这样的一个双向链表中啊，我们想删除这个结点。那么如果要删除这个结点的话，我们必须要修改
它的前驱结点中指向后方的一个指针。
并且呢，要修改它的后继结点中，
指向前方的这个指针。啊，这是必须要修改的两个指针。
那么要完成这个修改呢，首先我们定义一个临时的指针变量， temp
，用它呢来指向待删除的这个结点。然后呢，首先啊，我们来修改它的前驱结点中的
next 的指针。temp→ahead→next 就等于temp 的→ next
。那么通过这样一句程序啊， 我们就修改了 temp 结点的前驱结点中,
next 它的指针，修改为指向 temp
的后继结点。那么接下来呢，再对这一个结点中的 ahead 的指针进行修改。
这个 ahead 的指针由原来指向 temp 修改成指向 temp 的前驱结点。
那么当这两句程序执行完毕以后呢， 这个
temp 结点就从双向链表中被删掉了。
那么通过这个分析啊，我们可以看到，虽然在双向链表中删除一个结点稍微有点复杂，
但是呢，思路是非常清楚的。Ok, 那么接下来呢我们再来看一下
如何在双向链表中啊插入一个新的结点。
那么现在呢我们要在这样的一个双向链表中插入一个新的结点， unit ，啊。
在这个位置。那么为了完成这个操作啊，我们仍然定义一个
临时的指针变量 temp ，让它指向待插入结点的前面一个结点。
那么接下来呢我们就来修改这个结点，这个结点和这个结点中指针的直向关系。
那这个过程呢可以描述成这样。首先呢我们来修改 unit
这个结点的 next 的指针。让 next 的指针呢，
等于 temp 的 next 的。于是呢， unit 的 next 的就指向呢，它的下一个结点。
再接下来呢，我们再对 unit 的 ahead 的结点，
也就是这个结点进行修改。那么它呢，就等于 temp 。于是呢，指向了它的前驱结点。
那接下来呢，我们再来修改后面这个结点中指向前面的这个
ahead 的指针，也就是说 temp→next →ahead，
那它等于 unit 。那么当执行完毕的时候呢，现在呢改为指向
unit。 那么最后呢，我们再对 temp→next 的指针进行修改。让 temp→
next 指向 unit。 啊，由此执行完毕之后呢， temp→next
就指向 unit 的结点。那么通过这样的一个修改，我们就完成了
unit 这个结点的插入。
那么通过这个分析我们可以看到，虽然这个过程看上去有点复杂，但是思路还是很清楚的。
其实啊，在很多的应用场景中，双向链表比单向链表啊更有用。
比方说，在这儿我们举一个小例子，约瑟夫问题。
约瑟夫问题啊，是一个非常经典的问题。这个问题是这样的。
编号为 1-N
的 N 个人围坐在一起形成一个圆圈，
啊，就像这样，N 个人围坐在一起形成一个圆圈。然后呢，
从第 P 个人开始，啊，比方说 P 等于 7 的话，我们从这儿开始，
依次按照顺时针的方向来报数。 那么数到第 M
的人出列，直到最后剩下一个人。那么这个游戏呢，就结束了。
那么现在希望你呢，写一个程序。对于给定的 N, P 和 M ，
计算并且打印出出列的人的序号。
当然，对于这样的一个问题啊，有非常非常多的解法。
那么在这儿啊，其实有一种非常直观的解法。那就是啊，
利用循环链表。
啊，那么在这儿呢，我就举出来一个程序的例子。在这个程序里头啊，我们定义了一个双向循环链表。
啊，利用一个双向循环链表来解决了
约瑟夫问题。那么在这个程序里头呢，我们定义了三个函数。 一个呢，是 create
，用来创建链表。一个呢，是 search ，用来在链表中啊寻找某一个确定的结点。
还有一个呢，是 release ，要把某一个特定的结点从链表中剔除掉。那么利用这三个函数，
我们就可以模拟约瑟夫问题的解的过程。那么限于时间的关系呢，在这儿我们就不做一一的介绍了。
那么有兴趣的同学呢，可以把这三个函数抄写下来运行一下。
