📄 chapter3_3.htm
字号:
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"> if
p=O 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">
if move(available,L) then SPACE[L].element:=x</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
else error;</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">
else {不在第一个位置插入}</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
if move(available,SPACE[p].next)</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
then SPACE[SPACE[p].next].element:=x</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
else error</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
</table>
</center>
</div>
<blockquote>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"> </p>
</blockquote>
<p style="text-autospace: none" align="left"> 由于我们没有使用表头单元，所以必须单独处理在第一个位置插入的情形。另外，上述过程中用到了一个函数move(p,q)，其功能是从某一链表中将游标p所指的单元C摘除，并将这个单元C插入到另一链表中游标q所指的单元之前，成功则返回true。我们可以先将q改为指向单元C，然后再将p改为指向单元C的下一单元，最后再将C中的游标改为指向q原来所指的单元即可。这个游标的修改过程如图5所示。</p>
<blockquote>
<p style="text-autospace: none" align="center"><img border="0" src="images/img8.gif" width="453" height="237"></p>
</blockquote>
<p style="text-autospace: none" align="center">图5 两个链表之间的单元转移</p>
<p style="text-autospace: none" align="left"> 图5中的实线和虚线分别表示单元转移前后的游标。当单元C存在时，函数move取值为true，并施行单元C的转移;当单元C不存在时，函数move取值为false。</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>
move(var p,q;integer):boolean;</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">
temp:integer;</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=0 then return(false)</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
e1se</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">
temp:=q;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
q:=p;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
p:=SPACE[p].next;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
SPACE[q].next:=temp;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
return(true);</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; margin-top: 5; margin-bottom: 5">
要从表中删除位置p的元素，可以将L中位置p所指示的那个单元摘除，并将它插入表available的头一个位置备用。</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>procedrue</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=O then move(L，available)</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
else move(SPACE[p]^.next，available)</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
</table>
</center>
</div>
<p style="text-autospace: none" align="left"> 与单链表中的情形类似，为要删除表L中的一个元素x，先要找到x在表L中的位置。这可以用下面的函数Locate来实现。在表L中找到第一个与x相同的元素时，Locate返回x所在单元的位置，否则返回表尾位置。</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;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
if p=0 then error('List is empty.');</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
if SPACE[p].element=x then return(0);</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
while SPACE[P].next<>0 do</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
if SPACE[SPACE[P].next].element=x then return(p)</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
else
p:=SPACE[P].next;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"> return(p);</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"> 由于我们是用游标来模拟指针的，上述各运算的复杂性分析与单链表中的情形是类似的。另外，上述程序中都省略了检查错误的语句。</p>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -