循环链表与双向链表

循环链表与双向链表乙

一、刖百J A线性表的顺序存储结构（例如数组），存储空间是连续的因此我们不用担心元素之间的逻辑关系，线性表最大优点在于可以快速的存取表中任一位置的元素线性表顺序存储的缺点在于插入和删除操作时需要移动大量元素时间复杂度为（）线性表的0n,长度也难以适应变化较大的情况，且线性表的扩容需要重新开辟出一块满足大小需求且连续的空间，这容易造成空间碎片我们学习链式存储结构的单链表，单链表可以很好的解决数组的这些问题，但是访问单链表的某一位置的元素，需要遍历整个单链表，且每次都要头开始进行单方向的遍历为了解决这些问题我们引用循环链表和双向链表

二、循环链表循环链表将单链表中最后一个结点的指针域指向头结点（带头结点的链表）或首元结点（不带头结点的链表），使整个单链表形成一个首尾相连的环循环链表带头结点的空表数据域next头指针head非空表:汨旨针head在判断单链表是否是最后一个结点时只需要判断是否为但是循环链表需要判断p-next NUII,p-是否等于头结点，若等于则说明是最后一个结点，否则不是当我们经常在链表尾部进行增查操作时，我们可以使用带尾指针的循环链表，将头指针换成尾指针指向链表最后一个结点即可void add_to_headint xe[idx]=x;ne[idx]=head;head=idx++;void add_to_afterint k,int xe[idx]=x;ne[idx]=ne[k];ne[k]=idx++;void move_afterint kne[k]=ne[ne[k]];int mainint m;cin»m;init;whilem-char op;int x;int k;cin»op;ifop==Hcin»x;add_to_headx;else ifop==Tcin»k»x;add_to_afterk-l,x;elsecin»k;if!k head=ne[head];else move_afterk-l;}forint i=head;i!=-l;i=ne[i]cout«e[i]«}cout«endl;return0;注意至于这儿为什么要传上面已经说过了

1.k-1,.在的这种情况中，要处理一下特殊情况，如果匕也就是删除头节点之后的节点的情况2D0,

3.在这儿也是要类比结构体实现单链表中一样理解，我们要打印单链表中的值，就要遍历他,通过这个数组来遍历，因为其中相当于存放了他们之间的连接关系，首先从开始,然后ne head从头往后遍历，之后最后遇到空节点停止ne[i]-1双向链表题目双链表的思路也是，同样需要类比之前用指针实现的双向循环链表的思路，这是博主之前的关于双向链表的文章双向循环链表注意这儿的双向链表并不是双向循环链表代码实现#includeiostreamusing namespacestd;const intN=100010;int e[N],l[N],r[N],idx;〃初始化表不左端点，表示右端点1void initr

[0]=l;1

[1]=0;idx=2;〃在节点的右边插入一个节点kvoid add_k__rightint kJnt xe[idx]=x;l[idx]=k;r[idx]=r[k];〃这两个顺序不能反，因为你要引用l[r[k]]=idx;r[k]r[k]=idx++;〃删除节点kvoid movekint k l[r[k]]=l[k];r[l[k]]=r[k];}int mainint m;cin»m;init;whilem-string op;cin»op;int x;int k;ifop==nL cin»x;add_k_rightO,x;else ifop==R cin»x;add_k_rightl[l],x;else ifop==D cin»k;〃注意这儿是从开始的，即第一个插入的元素为因为被左右端点占据了idx2idx2,0,1movekk+l;else ifop==IL〃注意这儿的顺序，写在前面，因为在函数传参时，先传的是有关cin»k;k的这个，所以的要写在前面k+1k cincin»x;add_k_rightl[k+l],x;else〃注意这儿的顺序，写在前面，因为在函数传参时，先传的是有关cin»k»x;k k+1的这个，所以的要写在前面k cinadd_k_rightk+l,x;}forint i=r[O];i!=l;i=r[i]cout«e[i]«cout«endl;return0;}注意.这儿只需要两个接口就可以实现个功能，我们实现的是在节点右边插入一个节点，如果15k要在它的左边插入一个节点，可以将问题转化为在的左节点的右边插入一个节点k.在双向链表中表示左端点，表示右端点，仅起标识作用，不存放值

21.正因为有左端点和右端点的存在，所以是从开始的，即第一个插入的元素的为30,1idx2idx所以在传第个插入元素的时候要传进去2,k k+1这儿要注意顺序，不能先写再写因为你函数传参时是先传的有关的参,所以要

4.cin»k»x x k,k先把写在前面k这两句代码写的时候要注意顺序，不然可能会对之后的代码造成影响

5.1[r[k]]=idx;r[k]=idx++;数组模拟单链表双链表静态链表单链表邻接表邻接表主要用于存储图和树，如最短路，最小生成树，最大流双链表优化用数组模拟单链表，首先需要定义表示的数组表示某个点的指针值的数组val e[N],next ne[N],e和之间用相同的下标关联，存储当前用到了哪个地址相当于开始指向第一个结点的指ne idx针,每次把指向的结点分配出去之后，向后移动一位，指向头结点idx idxhead初始化void inithead=-1;idx=0;把新结点插到头结点的位置x把的指针指向当前的头结点指向的结点;X head把指向结点head xvoid add_to_headint xne[idx]=head;head=idx;e[idx]=x;idx++;把新结点插到下标是的结点的后面xk把的指针指向的下一个结点的；X k k ne把的指针指向k xvoid addint k,int xne[idx]=ne[k];ne[k]=idx;e[idx]=x;idx++;将下标是的后面的点删除k把的指向的的k nek nenevoid removeint kne[k]=ne[ne[k]];}整个链表的遍历forint i=head;i!=-1;i=ne[i]cout«e[i]«循环链表解决约瑟夫环问题约瑟夫环问题即有个人围成一圈每个人编号为从第个人n1-n,k开始报号，报号为的人出圈，剩余的人继续重复此过程，直至所有人都出圈，输出出圈的先m后顺序约瑟夫环有两大难题如何循环重复出圈如歌判断循环结束而不会造成死循环第一个问题我们用环形的循环链表完美解决，出圈的人只需要删除此结点即可解决第二个问题有三种思路带头结点的循环链表这样可以通过判断是否只剩一个头结点实现，但是每次循环要判断结点是否为头结点然后跳过头结点这样显然是没有体现链式存储结构不连续不需要就删除的优点；如果不用头结点，只是循环判断条件为二这样最后剩余的一个结点会造成死循环p-next!null我们换一个思路，最后剩余的一个结点一定是最后出圈的，既然这样我们在循环结束之后再出圈也是可以的，那么只要最后一个结点的是自己就说明只剩一个结点了这个时候结束循next环，最后再单独让最后一个结点出圈#includestdio.h2#include stdlib.hint funint n,intm,intk5main{3int int n=0,m=0,k=0;4Bscanf,,%d%d%d,,n,m,kj funn,m,5,k;6return0j789L10B intfunintn,intm,intk{11//动态创建数组开辟内存12int*flags=int*mallocsizeofint*njint ij13//数组全初始化为14for i=0j inj i++{15H16flags[i]=0;17-}18int nowindex=k-lj count//当前下标19int=0;nowLength=nj//计数器int20//剩余人数while nowLength0{21Bif flags[nowindex]==0{22Hcount++j23if count==m{24Elcount=0;25flags[nowindex]=1j2627nowLength一-;28printfn%d”,nowindex+1；}29-30-nowindex++5if nowindex==n{nowindex=3132B}3334-35-我们可以另外用一个变量记录圈中剩余的人数，这样在剩余人数为时跳出循环即可0

三、双向链表双向链表链表中每个结点有两个指针域，一个指向直接前趋，一个指向后继，构成一个双向的链表〃链表结点定义typedef struct node{〃数据域int data;〃直接前趋struct node*next;〃直接后继struct node*prior;}Node;双向链表带头结点的空表删除结点操作为待删除结点//P q=p-prior;q-next=p-next;p-next-prior=q;freep;La3a4a5a3a4a5q p的前驱指向p-prior=q;//p q的直接后继结点的前驱指向q-next-prior=p;//q p的后继指向的直接后继结点p-next=q-next;//p q的后继指向q-next=p;//q pqq-nextq-nextPqP双向链表的创建、遍历、删除某一个结点qftinclude stdio.hftinclude stdlib.htypedef struct node{int data;structnode*next;structnode*prior;}Node;Node*createNode*head,intn〃创建头结点head=Node*mallocsizeofNode;head-next=NULL;head-prior=NULL;head-data=O;int a;Node*p=NULL,*q=head;〃初始化双向链表forint i=O;in;i++〃初始化新的结点pp=Node*mallocsizeofNode;p-next=NULL;p-prior=NULL;，scanf%da;p-data=a;〃移动指针，指向最后一个结点qq-next=p;p-prior=q;q=q-next;}return head;〃遍历双向链表，前后两种遍历void displayNode*head Node*pr=head-next,*p=NULL;whilepr{％printf“5cT/pr-data;；P=pr pr=pr-next;printf\n;whilep-prior printf%5cT,p-data;p=p-prior;printf\n;Node*delNode*head,int numNode*p=head-next,*q=NULL;ifhead==NULLprintfempty list\n;return NULL;whilep-data!=nump=p-next;if p==NULL{printfnot find\n;为待删除结点//pq=p-prior;q-next=p-next;p-next-prior=q;freep;return head;〃在链表尾部加入一个结点Node*addNode*headJnt numNode*p=NULL,*pr=head;p=Node*mallocsizeofNode;ifp==NULL{printfmemory outuse\nH;return NULL;p-data=num;〃遍历得到最后一个结点whilepr-next{pr=pr-next;〃增加一个结点pr-next=p;p-prior=pr;p-next=NULL;return head;int mainintn,m,k;scanf%d,n;Node*head=NULL;head=createhead,n;displayhead;printf,,please inputa deletenumber:\n;〃删除一个数k，scanf”%d k;head=delhead,k;displayhead;printf,,please inputa addnumber:\n;〃增加一个数mscanf%d,m;head=addhead,m;displayhead;return0;

四、总结不管是循环链表还是双向链表本质都是线性链式存储的链表，不同的是改变链表的指针指向

1.和数量使得链表能够更加方便进行某一场景的使用在解决链表问题中为了使插入和删除任何位置都能一致操作，通常会加入一个头结点，头结

2.点不是第一个结点，头结点也称为哑结点，其数据域没有意义当然头结点并不是必须的，只是方便操作引用的一个结点,链表的增删操作结合图形更方便写代码和理解过程3算法基础一一用数组模拟实现单链表和双向链表结构体形成单链表玩的好好的，为什么要用数组来玩了？其实这就要涉及到效率的问题了，如果用之前的方法，在中我们每创建一个节点，就要一下，如果单链表很长，那么会很C++new消耗时间，有的题中甚至会超时，因为消耗的时间太多了new基本思想用数组实现单链表的基本思想就是用两个数组:一个存放值,一个存放下一个节点的下标在结构体的写法中，就相当于存放下一个节点的地址在这个过程中我们要用到一个变量来记idx录当前可用节点的下标这个算法说起来很抽象，不容器理解，下面我们来看代码以及结合之前结构体形成链表的方法来理解，就很容器理解了初始化void inithead=-l;idx=0;一开始链表中为空，为下标的位置就是空节点，为说明当前为个可用节点-1idx0,0向头节点插入这种方法其实在结构体形成链表中也就是头插法voidadd_to_headint xe[idx]=x;ne[idx]=head;head=idx++;.首先给这个位置赋值为一开始我们就说了，为当前可用位置的下标所以代码为1x,idxe[idx]=Xo.当前位置的口数组代替指向头，然后让这个位置变为头节点所以相应代码为2next nene[idx]=head;；head=idx.这样就完成了头插操作,此时当前位置已经用过了，所以3idx++下面的几个函数接口也是采用同样的类比方法来理解，这儿就不在赘述在任意节点之后插入一个xvoid add_to_3fterint kJnt xe[idx]=x;ne[idx]=ne[k];ne[k]=idx++;删除任意位置之后的一个节点void move_afterint kne[k]=ne[ne[k]];单链表题目这儿要注意的一个点是要理解第个插入的数的含义，我们来举例看看以结构体形成单链表中而言，第一个数插入k之后，其下标为第二个插入之后其下标为那么第个插入的数其下标则为0,1,kk-l代码实现#includeiostreamusing namespacestd;const intN=100010;int e[N],ne[N],idx,head;void inithead=-l;idx=0;。