8双向链表、循环链表

8双向链表、循环链表 上次课介绍了单向链表。我们了解了单向链表在插入、删除数据时不需要移动其他元素。也了解了单向链表的缺点在于只能从链表头向链表尾单向遍历。为了克服这个缺点，使链表具有更大的灵活性，人们设计了循环链表、双向链表等形式。二、循环链表1、定义 循环链表是将链表的最后的一个结点的指针域指向该链表的头结点，由此整个链表形成一个环。2、特点 从循环链表的任一结点出发均可以找到其它结点头结点||||||||||||||||数据1数据2数据3数据n…3、循环链表的形态4、初始状态头结点|||||||||||||||||||即：Head->next=Head则以下语句可以判断循环链表是否为空：

if(Head->next==Head)

cout<<"链表为空"<<endl; else

cout<<"链表不空"<<endl;5、遍历循环链表

LinkNodep; p=Head->next;

while(p!=Head) {

cout<<p->data<<""; p=p->next; }||||尾指针TAHA||||尾指针TBHB6、循环链表的合并设立了尾指针，对于单循环链表的合并非常方便TA->next=HB->nextTB->next=HAdeleteHB三、双向链表1、定义：结点中不仅有指向后继的指针next，还有指向前驱的指针Prior。structnode{DataTypedata;node*prior;//指向前驱node*next;//指向后继};2、特点：由某个结点可方便地找到其前驱和后继。前驱数据后继3、形态结点形态双向链表形态：头结点^4、插入操作在结点p后面插入一个新结点s头结点^ps4、插入操作在结点p后面插入一个新结点s头结点^ps引入一个指针q4、插入操作在结点p后面插入一个新结点s头结点^ps引入一个指针qq=p->nextq4、插入操作在结点p后面插入一个新结点s头结点^ps引入一个指针qq=p->nexts->next=qq4、插入操作在结点p后面插入一个新结点s头结点^ps引入一个指针qq=p->nexts->next=qq->prior=sq4、插入操作在结点p后面插入一个新结点s头结点^ps引入一个指针qq=p->nexts->next=qq->prior=sp->next=sq4、插入操作在结点p后面插入一个新结点s头结点^ps引入一个指针qq=p->nexts->next=qq->prior=sp->next=ss->prior=pq4、插入操作在结点p后面插入一个新结点s头结点^ps引入一个指针qq=p->nexts->next=qq->prior=sp->next=ss->prior=pq在结点p后面插入一个新结点s（不准引入新指针）s->next=p->nextp->next->prior=s;p->next=s;s->prior=p或者s->prior=ps->next=p->nextp->next->prior=sp->next=s5、删除p后面的结点引入两个指针q、rq=p->next;r=q->next;deleteq;p->next=r;r->prior=p;不准引入其他指针p=p->nextp->prior->next=p->next;p->next->prior=p->prior;在前面我们介绍的list模板，在内部采取的就是双向循环链表。采用双向循环链表使得链表的倒置非常容易，只要把最后一个结点作为第一个结点就行了。总结：对于循环链表中插入、删除某个结点经常是考察的知识点，尤其是不允许加入新的指针变量。思考题：一、判断题1、双向链表从任何一个结点出发，都能访问到所有结点........()2、循环链表从任何一个结点出发，都能访问到所有结点........()二、程序设计题有15个人围成一圈，顺序从1到15编号。从第一个人开始报数，凡报到n的人退出圈子。用C语言写出程序，输入n(n>=1)的值，输出最后留在圈子里的人的编号解决方法：采取循环链表的方法解决。#include<iostream>usingnamespacestd;structnode{

intdata; node*next;};///int

main(int

argc,char*argv[]){ node*tail=newnode; tail->next=tail; tail->data=1;

intlength=15;

for(inti=2;i<=length;i++) {//生成约瑟夫环

node*temp=newnode; temp->data=i; temp->next=tail->next; tail->next=temp; tail=temp; }node*head=tail->next; node*p=head;

intcount=1;

intn;

cin>>n;while(head!=head->next) {

while(count<n-1) { count++; p=p->next; } //此时p指向出列者的前驱

//删除p的后继

node*q=p->next;

if(q==head)//如果出列的是第一个人，注意head指针的改变

head=head->next; p->