算法----------------------------链表

向右看齐 2022-07-15 00:21 133阅读 0赞

双向链表

循环单链表的出现， 虽然能够实现从任意节点出发沿着链能够找到其前驱结点，但时间耗费是O（n）。如果从表中快速确定某一个节点的前驱

，另一个解决办法就是在单链表的每个节点里面在增加一个指向其前驱的指针域prior。这样形成的链表就有两条方向不同的链，我们课称之为双向链表

（）。双向链表的结构定义如下：

typedef struct DNode

Elemtype data;

stuct DNode \*prior,\*next;

\}DNode, \*DoubleList;

双链表的结点结构如图2.14所示。

![E5_9B_BE2.14.JPG][]

与单链表类似，双链表一般也是有头指针唯一确定的，增加头结点也能使双链表的某些运算变得方便。同时双向链表也可以有循环表，称为双向循环链表，其结构如图2.15所示。

![E5_9B_BE2.15.JPG][]

由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中某一结点，则有下式成立：

<table style=""> 
 <tbody> 
 <tr> 
 <td> 
 <div> 
 P-&gt;prior-&gt;next=p=p-&gt;next-&gt;prior 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

在双向链表中，那些只涉及后继指针的[算法][Link 1]，如求表长度、取元素、元素定位等，与单链表中相应的算法相同，但对于前插和删除操作则涉及到前驱和后继两个方向的指针变化，因此与单链表中的算法不同。

**1.双向链表的前插操作**

**算法描述**：欲在双向链表第i个结点之前插入一个新的结点，则指针的变化情况如图2.16所示。

![E5_9B_BE2.16.JPG][]

<table style=""> 
 <tbody> 
 <tr> 
 <td> 
 <div> 
 int DlinkIns(DoubleList L,int i,ElemType e) 
 { 
 &nbsp;DNode *s,*p; 
 &nbsp;…/*先检查待插入的位置i是否合法（实现方法同单链表的前插操作）*/ 
 &nbsp;…/*若位置i合法，则让指针p指向它*/ 
 &nbsp;s=(DNode *)malloc(sizeof(DNode)); 
 &nbsp;if(s) 
 &nbsp;&nbsp; { 
 &nbsp;&nbsp;&nbsp; s-&gt;data=e; 
 &nbsp;&nbsp;&nbsp; s-&gt;prior=p-&gt;prior;p-&gt;prior-&gt;next=s; 
 &nbsp;&nbsp;&nbsp; s-&gt;next=p;p-&gt;prior=s; 
 &nbsp;&nbsp;&nbsp; return TRUE; 
 &nbsp;&nbsp; } 
 &nbsp;else 
 &nbsp;&nbsp;&nbsp; teturn fALSE; 
 } 
 算法&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;双向链表的插入操作 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

**2.双向链表的删除操作**

**算法描述**：欲删除双向链表中的第i个结点，则指针的变化情况如图2.17所示。

![E5_9B_BE2.17.JPG][]

int DlinkDel(DoubleList L,int i,ElemType \*e)

DNode \*p;

…/\*首先检查待插入的位置i是否合法（实现方法同单链表的删除操作）\*/

…/\*若位置i合法，则让指针p指向它\*/

\*e=p->prior->next=p->next;

p->next->prior->p=p->prior;

free(p);

return TRUE;

算法双向链表的删除操作

[E5_9B_BE2.14.JPG]: /images/20220715/fa80037973e248a9b36303c5fa77bce6.png
[E5_9B_BE2.15.JPG]: /images/20220715/c8e5ac2b7e464bc29e3d61ddf9beb178.png
[Link 1]: http://lib.csdn.net/base/datastructure
[E5_9B_BE2.16.JPG]: /images/20220715/3593623b77d5433f93ce3dfebdaf32f1.png
[E5_9B_BE2.17.JPG]: /images/20220715/b515fd310ecf4a0ba0f6c03f07bfe191.png