数据结构-线性表|顺序表|链表(中)

回到正题，继上次出了数据结构线性表的内容上以后，这次又给大家更新啦。这次介绍的是单链表和静态链表的内容，话不多说，开始我们的正题。

【注：代码下载请移步留言区】

＊

内容提要：

＊预备知识

＊顺序表(Sequential List)

＊单链表(Singly Linked List )

＊静态链表(Static list )

＊循环链表(circular linked list)

＊双向链表(doubly linked list)

03 单链表(Singly Linked List )

3.1 什么是单链表？

单链表是一种链式存储的结构。它动态地为节点分配存储单元。当有节点插入时，系统动态的为结点分配空间。在结点删除时，应该及时释放相应的存储单元，以防止内存泄露。由于是链式存储，所以操作单链表时，必须知道头结点或者头指针的位置。并且，在查找第i个节点时，必须找到第i-1个节点。

3.2 单链表的存储结构代码描述

对于链式存储，通过上一节的讲解相信大家已经了解得够清楚了。如下图所示：

下面我们来看看单链表存储是如何用代码来实现的：

由上面的结构我们可以看出，一个节点由存放数据的数据域和存放地址的指针域组成。假如p指向了第i个节点，那么p->data就是该节点存放的数据，而p->pnext自然就是指向下一个节点的指针。如下图所示：

那么接下来我们看看单链表的各个操作具体实现吧。(只讲几个关键步骤)

备注：下面的代码基于这样的一个单链表：

1) 有一个头指针phead

2) 有一个头结点node

3) 头指针指向头结点，头结点位置记为0

3.3 单链表的读取

在拿到头指针以后，单链表的读取也并非一件难事。我们的做法是一开始设置一个计数变量，不断遍历链表，让计数器自增。找到合适的位置将数据读取出来。具体代码实现如下：

3.4 单链表的插入

01

3.4.1 指定位置后插

其实链表的插入和删除都是很简单的操作，初学者只要抓住指针指向的节点，并加以区分开来，就很easy了。如下图：

图中，假如此时p指向了我们要插入的节点的位置。那么，怎样把我们的S节点给插入到p指向的节点之后？在这里我们先不要惊动p以及p后面的节点：

1) 我们先让S节点指向p之后的节点(步骤①)

2) 之后我们切断p和p后面那个节点的关系(步骤②)

3) 最后让p节点的指针域指向s节点(步骤③)，搞定

算法描述：

1) 声明一个指针p指向链表头结点，向后遍历p=p->next，找到正确的位置。

2) 新建一个结点s。

3) s->next = p->next ①.

4) p->next = s ②③

具体代码如下：

3.4.1 指定位置前插

02

咳咳，聪明的小伙伴，用脑子想想。指定位置前插 == 指定位置的前一个位置进行后插。懂了吧？直接看具体代码：

3.5 单链表的删除

单链表的删除其实也是很简单。只要比如要删除p指向的节点，只需要让p之前的节点的指针域直接指向p之后的节点，再把p给free就OK了。如下图：

算法描述:

1) 声明一个指针p指向链表头结点，向后遍历p=p->next，找到要删除的节点位置。

2) q = p->next

3) p->next = q->next ①②

4) free(q) ③④

具体代码如下:

代码应该不难，相信大家都能很容易看懂。

3.6 单链表的完整代码

好了，前面介绍了几个重要的操作，接下来请大家看看完整的代码吧。小编为了使用方便，就用C++的class和template将整个链表封装到了一个类里面，通过模板实现泛型编程。

【注：代码下载请移步留言区】

04 静态链表(circular linked list)

4.1 什么是静态链表？

我们把线性表的元素存放在数组中，这些元素由两个域组成：

数据域data

指针域cur

数据域是存放数据的，而指针域，这里和链表不同是，它存的不再是指向下一个节点的内存地址。而是下一个节点在数组中的下标。我们就把这种用数组描述的链表称为静态表，该方法也称之为游标实现法。如下图所示：

由上图我们需要注意以下几点：

1) 我们对数组的第一个元素和最后一个元素做特殊处理，不存放数据。

2) 把未使用的数组元素称为备用链表。

3) 数组的第一个元素(下标为0)的cur域存放备用链表第一个节点的下标。

4) 数组的最后一个元素的cur域存放第一个有数据的节点的下标，相当于链表中头结点的存在。链表为空时，其值为0。

如下图：

引出的问题：数组的长度定义的问题，无法预支。所以，为了防止溢出，我们一般将静态表开得大一点。

4.2 静态链表存储的代码描述

基于上面的讲解，我们来看看代码是怎么描述这种存储结构的:

接下来我们讲解几个重要的操作实现。

4.3 静态链表的插入操作

前面我们讲动态链表的时候说过，增加和删除一个节点我们可以用malloc()和free()函数(C++可用new和delete)来实现。但是现在由于我们操作的是静态表，它可是用数组存的，可没有这种操作了。因此我们首先来自己实现一个静态表的malloc和free。

那么怎么辨别数组中哪些空间没有被使用呢？一个好的解决办法是，将所有未使用或者被删除的空间串成一个备用链表。插入节点时便可以从备用链表获取第一个未使用的空间的下标。因此我们在初始化的时候会做这样的工作：

分配内存

上面的代码应该是没有难度的。写完了这个函数，我们来看看静态表中具体如何插入：

注意几点：

1) 首先我们让k指向了要插入节点(记为X)的前一个位置(记为Y节点)，前插法。

2) 然后我们在静态表内申请空间，存放新的节点(记为N)。

3) 把数据放进新申请的节点里面。

4) 新节点N的cur域指向X节点，然后让Y节点指向N节点。

该过程不难理解。就不上图了……

4.4 静态链表的删除操作

删除同样需要自己实现free函数，我们来看看代码：

回收内存

删除以后记得把空间重新挂载到备用链表上以便下一次使用。下面我们实现删除的代码：

其实代码也很好理解了。假如X、Y、Z……等等排列，我们要删除Y。无非就是告诉X，你不要指向Y了，你直接指向Z，然后我们再把Y给free了。就直接变成了X、Z……简单吧。

4.5 静态链表的完整代码

【注：代码下载请移步留言区】

这次文章代码量有点大哈，希望同学们能耐心坚持看完。关键的几个操作，牢牢把握各个重要的概念，理解也不成问题的。代码链接请戳原文链接。

END