第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; 删除该结点的前驱结点