《数据结构》课程教学资源（PPT课件）第二章 线性表（2.4 循环单链表 2.5 双向链表 2.6 仿真链表）

第2章线性表2.1线性表2.2顺序表2.3单链表2.4循环单链表2.5双向链表2.6仿真链表

第2章 线性表 2.1 线性表 2.2 顺序表 2.3 单链表 2.4 循环单链表 2.5 双向链表 2.6 仿真链表

2.4循环单链表循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针不再是结束标记，而是指向整个链表的第一个结点，从而使单链表形成一个环。和单链表相比，循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时：适合于采用循环单链表。headhead(a)(b)

循环单链表是单链表的另一种形式，其结构特点是链 表中最后一个结点的指针不再是结束标记，而是指向整 个链表的第一个结点，从而使单链表形成一个环。 2.4 循环单链表 (a) head (b) a . head 0 a1 an-1 和单链表相比，循环单链表的长处是从链尾到链头比 较方便。当要处理的数据元素序列具有环型结构特点时， 适合于采用循环单链表

带头结点的循环单链表的操作实现方法和带头结点的单链表的操作实现方法类同，差别仅在于：（1）在构造函数中，要把初始时的带头结点的循环单链表设计成下图所示的状态。headNextLinListO(head=current=newNode(null):head.next-head;?

带头结点的循环单链表的操作实现方法和带头结点的单 链表的操作实现方法类同，差别仅在于： head Next LinList(){ head = current = new Node(null); head.next=head; } （1）在构造函数中，要把初始时的带头结点的循环单链表 设计成下图所示的状态

（2）index(i)函数，把循环结束判断条件current！=null改为current!=head。headNextcurrent = head.next;int j= O;while((current!=head) && j<i)current-current.next;j ++;7

（2）index(i)函数，把循环结束判断条件current != null改 为current != head。 a . head 0 a1 an-1 Next current = head.next; int j = 0; while((current != head) && j < i){ current=current.next; j ++; }

例叶点单链表只能从头结点开始遍历整个链表，而循环单链表则可以从表中任意结点开始遍历整个链表。如何寻找前驱结点？ao福ps-p;s指向该结点的前while(s.next.next!=p)驱结点的前驱结点s=s.next:删除该结点的前驱结点s.next=p

例：假设长度大于1的循环单链表中，既无头结点也无头指针， p指向该链表中某一结点，编写一个算法删除该结点的前驱结 点。 单链表只能从头结点开始遍历整个链表，而循环单链表则 可以从表中任意结点开始遍历整个链表。 a . a0 1 a2 an-1 p s=p; while(s.next.next!=p) s=s.next; 如何寻找前 驱结点？ s指向该结点的前 驱结点的前驱结点 s s.next=p; 删除该结点的前驱结点

思考：对于单链表而言，连接两个单链表应该如何实现？currentheadlhead2current.next-head2.next对于循环单链表呢？

思考：对于单链表而言，连接两个单链表应该如 何实现？ a . 0 head1 a1 an-1 ^ b . 0 head2 b1 bn-1 ^ current current.next=head2.next 对于循环单链表呢？

0head1head2p-head1.next;head1.next-head2.next.next:head2.next=p:head1head2

a . 0 head1 a1 an-1 b . 0 head2 b1 bn-1 p p=head1.next; head1.next=head2.next.next; head2.next=p; a . 0 head1 a1 an-1 b . 0 head2 b1 bn-1 p

2.5双向链表双向链表是每个结点除后继指针外还有一个前驱指针。在双向链表中，每个结点包括三个域，分别是element域、next域和prior域，其中element域为数据元素域，next域为指向后继结点的对象引用，prior域为指向前驱结点的对象引用。datapriornext

双向链表是每个结点除后继指针外还有一个前驱 指针。 2.5 双向链表 在双向链表中，每个结点包括三个域，分别是 element域、next域和prior域，其中element域为数据 元素域，next域为指向后继结点的对象引用，prior 域为指向前驱结点的对象引用。 prior data next

和单链表类同，双向链表也有带头结点结构和不带头结点结构两种，带头结点的双向链表更为常用；另外，双向链表也可以有循环和非循环两种结构，循环结构的双向链表更为常用

和单链表类同，双向链表也有带头结点 结构和不带头结点结构两种，带头结点的双 向链表更为常用；另外，双向链表也可以有 循环和非循环两种结构，循环结构的双向链 表更为常用

下图是带头结点的循环双向链表的图示结构。循环双向链表的next和prior各自构成自己已的循环单链表。headhead(b)带头结点的循环双向链表（a）空链表；（b）非空链表

下图是带头结点的循环双向链表的图示结构。循环双向 链表的next和prior各自构成自己的循环单链表。 带头结点的循环双向链表 （a）空链表；（b）非空链表 (a) (b) head a0 . head a1 an-1