前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

资料获取

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linkedlist)。

循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表的全部结点。

为了使空链表与非空链表处理一致，我们通常设-一个头结点，当然，这并不是说，循环链表一定要头结点，这需要注意。

非空的循环链表：

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p -> next不等于头结点，则循环未结束。

在单链表中，有了头结点时，可以用0(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要0(n)时间，因为我们需要将单链表全部扫描一遍。有没有可能用0(1)的时间由链表指针访问到最后一个结点呢? 当然可以。不过需要改造一下这个循环链表， 不用头指针，而是用指向终端结点的尾指针来表示循环链表

终端结点用尾指针rear（后）指示，则查找终端结点是o(1)

举个程序的例子，要将两个循环链表合并成一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是rearA和rearB

要想把它们合并，只需要如下的操作即可，

p=rearA->next; 保存A表的头结点，即①

rearA->next=rearB->next->next; 将本是指向B表的第一个结点(不是头结点) 賦值給reaA->next,即②

rearB->next=p; 将原A表的头结点赋值给rearB->next,即③ free (p) ; 释放p

双向链表

书中的故事很精彩，有时间一定看一遍

为了克服单向性这一缺点， 老科学家们，设计出了双向链表。双向链表(double linked list) 是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

arduino

复制代码

typedef struct DulNode
 {
 ElemType data;
 struct DuLNode *prior;  /*直接前驱指针*/
 struct DuLNode *next;   /*直接后继指针*/
 }DulNode, *DuLinkList;

既然单链表也可以有循环链表，那么双向链表当然也可以是循环表。

双向链表的循环带头结点的空链表如下：

非空的循环的带头结点的双向链表

由于这是双向链表，那么对于链表中的某一个结点p，它的后继的前驱是谁?当然还是它自己。它的前驱的后继自然也是它自己，即:

p->next->prior = p = p->prior- >next

就像人生一样，想享乐就得先努力，欲收获就得付代价。 双向链表既然是比单链表多了如可以反向遍历查找等数据结构，那么也就需要付出一-些小的代价:在插入和删除时，需要更改两个指针变量。

插入操作时，其实并不复杂，不过顺序很重要，千万不能写反了。我们现在假设存储元素e的结点为s，要实现将结点s插入到结点p和p -> next之间需要下面几步、

这里的prior值的是s结点的前指针，next指的是s结点的后指针

s->prior = p; 把p赋值给s的前驱，如图中① s -> next= P -> next; 把p->next赋值给s的后继，如图中② P -> next-> prior = s; 把s赋值给p->next的前驱，如图中③ P->next = s; 把s赋值给p的后继，如图中④

上面写的代码一定认真看，很好理解~~~

双向链表的删除就比较好理解了，类似链表的删除

p->prior->next=p->next; 把p->next赋值给p->prior的后继，如图中① p->next->prior=p->prior; 把p->prior赋值给p->next的前驱，如图中②

上面写的代码一定认真看，很好理解~~~

简单总结一下，双向链表相对于单链表来说，要更复杂- -些，毕竟它多了prior指针，对于插入和删除时，需要格外小心。另外它由于每个结点都需要记录两份指针，所以在空间上是要占用略多-些的。 不过,由于它良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。说白了，就是用空间来换时间。

总结回顾

这一章主要是学的线性表

知道了它的定义，线性表是零个或多个具有相同类型的数据元素的有限序列。然后说了抽象数据类型，和一些基本操作

之后说顺序存储结构和链式存储结构，顺序存储指的是用一段地址连续的存储单元依次存储线性表的数据元素，通常用数组来实现这一结构

之后说链式存储，它不受固定的存储空间限制，能快速插入和删除

之后说了单链表，循环链表，双向链表和不使用指针如何处理链表结构的静态链表

以上，基础中的基础。对后面又很重要的作用

\