📄 chapter3_2.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_1.htm";
var next = "chapter3_3.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3>表的指针实现</h3>
<p>实现表的另一种方法是用指针将存储表元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销。</p>
<p align="left" style="text-align:left;text-autospace:none">
为了将存储表元素的所有单元用指针串联起来，我们让每个单元包含一个元素域和一个指针域，其中的指针指向表中下一个元素所在的单元。例如，如果表是a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>
，那么含有元素a<sub>i</sub>的那个单元中的指针应指向含有元素a<sub>i+1</sub>的单元(i=1,2,…,n-1)。含有a<sub>n</sub>的那个单元中的指针是空指针nil。此外，通常我们还为每一个表设置一个表头单元header，其中的指针指向开始元素中所在的单元，但表头单元header中不含任何元素。设置表头单元的目的是为了使表运算中的一些边界条件更容易处理。这一点我们在后面可以看到。如果我们愿意单独地处理诸如在表的第一个位置上进行插人与删除操作等边界情况，也可以简单地用一个指向表的第一个单元的指针来代替表头单元。</p>
<p align="left" style="text-align:left;
text-autospace:none"> 上述这种用指针来表示表的结构通常称为<b>单链接表</b>，或简称为<b>单链表</b>或<b>链表<a name="def-chain"></a></b>。单链表的逻辑结构如图1所示。表示空表的单链表只有一个单元，即表头单元header，其中的指针是空指针nil。</p>
<blockquote>
<p align="center" style="text-autospace: none"><img border="0" src="images/img3.gif" width="439" height="96"></p>
</blockquote>
<p align="center" style="text-autospace: none">图1 单链表示意图</p>
<p align="left" style="text-align:left;
text-autospace:none"> 为了便于实现表的各种运算，在单链表中位置变量的意义与用数组实现的表不同。在单链表中位置i是一个指针，它所指向的单元是元素a<sub>i-1</sub>所在的单元，而不是元素a<sub>i</sub>所在的单元(i=2,3,…,n)。位置1是指向表头单元header的指针。位置End(L)是指向单链表L中最后一个单元的指针。这样做的目的是为了避免在修改单链表指针时需要找一个元素的前驱元素的麻烦，因为在单链表中只设置指向后继元素的指针，而没有设置指向前驱元素的指针。</p>
<p align="left" style="text-align:left;text-autospace:none">
在单链表中，表类型TList和位置类型TPosition一样，都是指向某一单元的指针。尤其可以是指向表头单元的指针。</p>
<p align="left" style="text-align:left;text-autospace:none">单链表结构的主要类型可形式地定义为:</p>
<pre>type
CellType=record
element:TElement;
next:^CellType;
end;
TList=^CellType;
TPosition=^CellType;</pre>
<p>在单链表中，函数End(L)可实现如下</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="4" height="190" cellspacing="0">
<tr>
<td width="100%" height="178">
<p align="left" style="text-align: left; text-autospace: none; margin-top: 0; margin-bottom: 2"><b>Function</b>
End(L:TList):TPosition;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 2; margin-bottom: 2">var</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 2; margin-bottom: 2">
q: TPosition;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 2; margin-bottom: 2">begin</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 2; margin-bottom: 2">
q:=L;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 2; margin-bottom: 2">
while q^.next<>nil do q:=q^.next;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 2; margin-bottom: 2">
return(q)</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 2; margin-bottom: 0"> end;
</td>
</tr>
</table>
</center>
</div>
<p>上述算法中的指针q指向需要检查的单元。由于检查要从header开始，而L是指向表头单元header的指针，所以q的初值为L。如果q所指的单元中的指针不是空指针，说明该单元不是表中的结束单元，因此要将q移向该单元的指针所指的下一单元，以便检查下一个单元。直到q所指的单元中的指针为nil时，那时的q值才是应返回的函数值。若表的长度为n,按这样计算End(L)需要扫描整个链表，因此需要<i>O</i>(n)时间，效率很低。如果需要频繁地调用函数End，我们可以采用下面的两种方法之一来提高效率。</p>
<ol>
<li>
<p align="left" style="text-align:left;text-autospace:none">在链表结构中多设一个指向链表结束单元的表尾指针。对此，通过表尾指针就可以在<i>O</i>(1)时间内实现End(L)。
</li>
<li>
<p align="left" style="text-align:left;text-autospace:none">尽可能避免调用End(L)。例如<a href="chapter2.htm#purge">Purge程序</a>的第(2)行中判断条件p<>End(L)应该用p.next<>nil来代替。
</li>
</ol>
<p>下面讨论单链表中Insert,Delete和Locate三种运算的实现。</p>
<div align="center">
<table border="1" width="90%" bordercolor="#FFFFFF" cellpadding="5" style="font-size: 10pt">
<center>
<tr>
<td width="100%" bgcolor="#E0E0E0"><b>函数</b> <font size="2">Insert(x,p)</font>
<p><b>功能</b></p>
<blockquote>
<p><font size="2">在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>，那么在执行Insert(x,p)后，表L变为a<sub>1</sub>,a<sub>2</sub>,…a<sub>p-1</sub>,x,a<sub>p</sub>,…,a<sub>n
</sub>。若p为End(L)，那么表L变为a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>,x
。若表L中没有位置p，则该运算无定义。</font></p>
</blockquote>
<p><b>实现</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>Procedure</b> Insert(x:TElement;p:TPosition);</p>
<p style="margin-top: 5; margin-bottom: 5">var</p>
<p style="margin-top: 5; margin-bottom: 5"> temp:TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> temp:=p^.next;</p>
<p style="margin-top: 5; margin-bottom: 5">
new(p^.next);</p>
<p style="margin-top: 5; margin-bottom: 5"> p^.next^.element:=x;</p>
<p style="margin-top: 5; margin-bottom: 5"> p^.next^.next:=temp;</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p><b>说明</b></p>
<blockquote>
<p align="left" style="text-align:left;text-autospace:none">上述算法中，链表指针的修改情况见图2。</p>
</blockquote>
<p align="center" style="text-autospace: none"><img border="0" src="images/img4.gif" width="435" height="84"></p>
<p align="center" style="text-autospace: none">(a)</p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -