1.建立空的双向循环链表
对于双向链表，一般采用带头结点的双向循环链表。在双向非循环链表中，头结点的前驱指针（prior）为<br />空（NULL）；尾部结点的后继指针（next）为空（NULL）。在双向循环链表中，头结点的前驱指（prior）<br />指向尾部结点；尾部结点的后继指针（next）指向头结点。
建立一个带头节点的空的双向循环链表，示意图如下图所示：
<br /> 建立空双向循环链表的过程：<br /> （1）产生一个头结点，分配一个空的双向链表空间<br /> DLinkList *L;<br /> L=(DLinkList *) malloc (sizeof (DNode));<br /> （2）将链表设置为空链表<br /> L->next=L;<br /> L->prior=L;
2.结点的插入操作
在双向链表中L中的第i个结点位置插入一个数据元素e，此时需要同时修改两个方向上的指针，如图所示。
**<br />** 插入操作实现的完整过程：**<br /> （1）定义一个双向链表结点类型的指针p，并指向<br /> DNode *p;<br /> p=L;<br /> （2）将指针p移动到第i个结点<br /> int j=0;<br /> while (p -> next != NULL && j < i )<br /> {<br /> p = p -> next;<br /> j ++;<br /> }<br /> （3）生成新的的结点s<br /> DNode *s;<br /> s = (DNode *) malloc (sizeof (DNode));<br /> s->data=e;<br /> （4）将新的结点s插入到链表的第i个结点位置（注意下面各操作的先后顺序）<br /> ① s -> prior = p -> prior; //新结点的前驱指向p结点的前驱<br /> ② p -> prior -> next = s; //p结点前驱的后继指向新结点<br /> ③ s -> next = p; //新结点的后继指向p结点<br /> ④ p -> prior = s; //p结点的前驱指向新结点
_**在插入新结点是的关键问题：因为指针p指向第i个结点，必须最后修改第i个结点i的prior域！**_
_ **问题思考：如果指针p指向第i-1个结点，该如何实现新结点的插入操作？**_<br />_**插入操作实现的算法：**<br /> Status DListInsert (DLinkList *L,int i, ElemType e)<br /> { //在双向循环链表L中的第i个位置插入一个数据元素e<br /> DNode *s, *p;<br /> p=L;<br /> int j=0;<br /> while (p -> next != NULL && j < i )<br /> {<br /> p = p -> next;<br /> j ++;<br /> }<br /> s = (DNode *) malloc (sizeof (DNode)) ; //生成新结点<br /> if (! s) return FALSE;<br /> s -> data = e; //将e赋给新结点的数据域<br /> s -> prior = p -> prior; //新结点的前驱指向p结点的前驱<br /> p -> prior -> next = s; //p结点前驱的后继指向新结点<br /> s -> next = p; //新结点的后继指向p结点<br /> p -> prior = s; //p结点的前驱指向新结点<br /> return TRUE; <br /> }
3.结点的删除操作
删除如下图所示的链表中指针p所指向的第i个位置的结点：<br /> <br /> <br /> 删除操作指针变化示意图如下：<br /> <br />** **<br />** 删除操作实现的完整过程：**<br /> （1）设置结点指针p，从链表的头结点移动到待删除的结点（方法与结点插入操作类似）；<br /> （2）修改待删除结点的前驱结点及后继结点的相关指针；<br /> （3）保存待删除结点的数据，释放要删除的结点的内存空间<br /> *e=p->data;<br /> free(p);
_ 问题思考：在上述指针的修改过程中，对两个指针的修改顺序是否可以改变？_
删除操作实现的算法：
Status DListDelete (DLinkList L,int i, ElemType e)
{ //删除双向链表L中的第i个结点
DNode p
p=L;
int j=0;
while (p -> next != NULL && j < i )
{
p = p -> next;
j ++;
}
p -> prior -> next = p -> next; //要删除结点前驱的后继指向其后继
p -> next -> prior = p -> prior; //要删除结点后继的前驱指向其前驱
e = p -> data; //将要删除结点的值赋给e
free (p); //释放p结点
return TRUE;
}
若有收获，就点个赞吧
0 人点赞
