建立网站地图,企业培训图片,软件开发 网站开发 不同,排名怎么优化快一、双链表
#xff08;一#xff09;双链表的定义
双链表是在单链表结点上增添了一个指针域prior#xff0c;指针域prior指向当前结点的前驱结点#xff0c;即此时链表的每个结点中都有两个指针域prior和next#xff0c;从而可以很容易通过后继结点找到前驱结点#x…一、双链表
一双链表的定义
双链表是在单链表结点上增添了一个指针域prior指针域prior指向当前结点的前驱结点即此时链表的每个结点中都有两个指针域prior和next从而可以很容易通过后继结点找到前驱结点故访问前驱和后继结点的时间复杂度都为O(1)。
二双链表的判空
一个带头结点L的双链表若L-nextNULL时则该双链表为空一个不带头结点的双链表若LNULL时则该双链表为空。
双链表判空条件带头结点L-nextNULL不带头结点LNULL
三双链表的插入操作
由于双链表可以很快地找到前驱结点所以双链表的插入、删除操作的时间复杂度都为O(1)。
双链表的插入操作可以概括为【先连后后连前】若在指针 *p 指向的结点之后插入结点 *q首先新结点q与原本 *p的指针域相连即下一个结点然后将结点q插入到结点p之后再将其prior和next域相连代码如下
q-nextp-next;
p-next-priorq;
q-priorp;
p-nextq;这里的代码插入不唯一插入操作必须保证的是不能断链即不能导致*p的后继结点的指针丢掉。 四双链表的删除操作
双链表的删除操作的代码如下
p-nextq-next;
q-next-priorp;
free(q);二、循环单链表
一循环单链表的定义
循环单链表可以实现从任一个结点访问链表中的任何结点遍历整个链表。
二循环单链表的判空
在带头结点L的循环单链表中若Lhead-next时循环单链表为空在不带头结点的循环单链表中若LNULL时循环单链表为空。
循环单链表判空条件带头结点Lhead-next不带头结点LNULL
三循环单链表的查找
在一个带头结点的循环单链表中 1、若只设置头指针L则查找表头结点的时间复杂度为O(1)查找表尾结点需要依次遍历整个链表即时间复杂度为O(n)而查找一个结点的前驱结点时的时间复杂度为O(n)。 2、若只设置尾指针R这样的好处是可以使查找链表的开始结点和终端结点很方便其查找时间都为O(1)而查找一个结点的前驱结点时的时间复杂度为O(n)。
四循环单链表的插入操作
循环单链表的插入操作与单链表类似也是【先连后再连前】若在指针 *p 指向的结点后插入结点 *p 步骤是首先将q的指针域与p结点原本的指向下一个结点的指针域相连即q-nextp-next然后再将q结点与p结点相连即p-nextq如下
q-nextp-next; //先连后
p-nextq; //再连前五循环单链表的删除操作
循环单链表的删除操作也与单链表类似删除的步骤可概括为【先定位后断开释放】将*q指针指向要删除的结点p为其前驱结点如下代码
qp-next; //先定位定位删除位置
p-nextq-next; //断开q与p的连接p与下一个结点连接
free(q); //free()函数释放结点三、循环双链表
一循环双链表的定义
循环双链表基于双链表头结点L的prior域指向表尾结点查找表头结点和表尾结点的时间复杂度均为O(1)查找一个结点的前驱结点时的时间复杂度也为O(1)。
二循环双链表的判空
一个带头结点L的循环双链表若L-priorLL-nextL时则该双链表为空。头结点的prior和next域都指向其本身时为空
循环双链表判空条件带头结点L-prior L L-next L不带头结点LNULL
三循环双链表的插入操作
若要在指针 *p 指向的结点后插入结点 *p其代码如下
q-nextp-next;
p-next-priorq;
q-priorp;
p-nextq;四循环双链表的删除操作
将*p指针指向要删除的结点其代码如下
p-next-priorp-prior;
p-prior-nextp-next;
free(p);
