📄 chapter3_5.htm
字号:
<html><!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" -->
<title>双链表</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
var previous = "chapter3_4.htm";
var next = "chapter4.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3 align="left">双链表</h3>
<p align="left" style="text-align:left;
text-autospace:none"> 在单循环链表中，虽然从任一单元出发，可以找到其前驱单元，但需要<i>O</i>(n)时间。如果我们希望能快速确定表中任一元素的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指针，一个指向后继，另一个指向前驱，形成图8所示的<b>双向链表</b>或简称为<b>双链表</b>。</p>
<p align="center" style="text-autospace: none"><img border="0" src="images/img12.gif" width="535" height="30"></p>
<p align="center" style="text-autospace: none">图8 双链表</p>
<p align="left" style="text-align:left;text-autospace:none">
由于在双链表中可以直接确定一个单元的前驱单元和后继单元，我们可以用一种更自然的方式表示元素的位置，即用指向双链表中第i个单元而不是指向其前一个单元的指针来表示表的第i个位置。</p>
<p align="left" style="text-align:left;text-autospace:none">双链表的单元类型定义如下。</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="5">
<tr>
<td width="100%">
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">type</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"> celltype=record</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
element:TElement;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
next，previous:celltype;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
end;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
TPosition=^celltype;
</td>
</tr>
</table>
</center>
</div>
<p align="left" style="text-align:left;
text-autospace:none"> 和单链的循环表类似，双链表也可以有相应的循环表。我们用一个表头单元将双链表首尾相接，即将表头单元中的previous指针指向表尾，并将表尾单元的next指针指向表头单元，构成如图9所示的双向循环链表。</p>
<p align="center" style="text-autospace: none"><img border="0" src="images/img13.gif" width="557" height="108"></p>
<p align="center" style="text-autospace: none">图9 双向循环链表</p>
<p align="left" style="text-align:left;text-autospace:none">
下面仅以双向循环链表为例给出三种基本运算的实现。</p>
<p align="left" style="text-align:left;text-autospace:none">(1)在双向循环链表L的位置p处插入一个新元素x的过程Insert可实现如下。</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="5">
<tr>
<td width="100%">
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"><b>procedure</b>
Insert(x:TElement;p:TPosition;var L:TList);</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">Var</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
q:TPosition;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">begin</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
new(q);</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
q^.element:=x;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
q^.previous:=p^.previous;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
q^.next:=p;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
p^.previous^.next:=q;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
p^.previous:=q;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
</table>
</center>
</div>
<p align="left" style="text-align:left;text-autospace:none">上述算法对链表指针的修改情况见图10。</p>
<p align="center" style="text-autospace: none"><img border="0" src="images/img14.gif" width="410" height="205"></p>
<p align="center" style="text-autospace: none">图10 在双向循环链表中插入一个元素</p>
<p align="left" style="text-align:left;text-autospace:none">
算法Insert中没有检查位置p的合法性，因此在调用Insert之前应保证位置p的合法性。由于插入通常是在表的头尾两端进行的，所以容易检查位置p的合法性。</p>
<p align="left" style="text-align:left;text-autospace:none">(2)从双向循环链表L中删除位置p处的元素可实现如下:</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="5">
<tr>
<td width="100%">
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"><b>procedure</b>
Delete(p:TPosition;var L:TList);</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">begin</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
if (p<>nil)and(p<>L) then</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
begin</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
p^.previous^.next:=p^.next;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
p^.next^.previous:=p^.previous;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
dispose(p^);</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
end;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
</table>
</center>
</div>
<p align="left" style="text-align:left;text-autospace:none">上述算法对链表指针的修改情况见图11。</p>
<p align="center" style="text-autospace: none"><img border="0" src="images/img15.gif" width="535" height="107"></p>
<p align="center" style="text-autospace: none">图11 从双向循环链表中删除一个元素</p>
<p align="left" style="text-align:left;text-autospace:none">
与单链表中的删除算法类似，上述算法是在已知要删除元素在链表中的位置p时，将该位置所指的单元删去。若要从一个表中删除一个元素x但不知道它在表中的位置，则应先用定位函数Locate(x,L)找出要删除元素的位置，然后再用Delete删除之。</p>
<p align="left" style="text-align:left;text-autospace:none">(3)在双向循环链表中，定位函数Locate可实现如下。</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="5">
<tr>
<td width="100%">
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"><b>function</b>
Locate(x:TElement;L:TList):TPosition;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">Var</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
p:TPosition;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">begin</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"> p:=L^.next;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"> while
p<>L do</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
if p^.element=x then return(p)</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
else
p:=p^.next;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"> return(nil);</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
</table>
</center>
</div>
<p align="left" style="text-align:left;text-autospace:none">
算法Locate在最坏情况下需要的时间显然为<i>O</i>(n)，n为表L的长度。算法Insert和Delete需要<i>O</i>(1)时间。在双向循环链表中，其他表的运算容易实现，这里就不一一说明了。另外，我们也可以用游标来模拟指针，从而实现双向链表和双向循环链表。</p>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -