📄 chapter3_3.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_2.htm";
var next = "chapter3_4.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"> 所谓游标就是指示数组单元地址的下标值，它属整数类型。我们可以用游标来模拟指针，将TElement类型的元素所组成的表用一个数组来实现，数组单元是记录类型，记录中包含一个表元素和一个作为游标的整数；具体说明如下:</p>
<pre>Var
SPACE: array[1..maxlength] of
record
element:TElement;
next:integer;
end;</pre>
<p style="text-autospace: none"> 对于一个表L，我们用一个整型变量Lhead作为L的表头游标。SPACE[Lhead]就是L的表头单元，其中的elemnt域是空的，next域中的游标指示L的第一个元素在数组SPACE中的存储地址(数组下标值)。这样，我们就可以用游标来模拟指针，实现单链表中的各种运算。<b>照此，我们虽然是用数组来存储表中的元素，但在作表的插人和删除运算时，不需要移动元素，只要修改游标，从而保持了用指针实现表的优点。</b>因此，有时也将这种用游标实现的表称为<b>静态链表</b>。</p>
<p style="text-autospace: none" align="left"> 下面我们介绍用游标实现表的另一种方式。这种方式不用表头单元，因此在表的第一个位置进行插入或删除时，需要进行特殊处理。这与在单链表中不用表头单元的情形类似。设L是一个表。我们用Lhead指示L的第一个元素，即L的第一个元素存放于SPACE[Lhead].element中，而SPACE[Lhead].next为L的第二个元素所在单元的下标值。其后每个元素的后继元素所在单元以类似的方式给出。如果Lhead或者某单元中next域的值为0，则表示这是一个空指针，即该游标不指示任何单元。表L可以用它的表头变量Lhead来代表。由于表头变量是整型变量，所以表的类型为整型。位置变量类型TPosition也是整型。与单链表中位置变量的意义相类似。我们约定，当i>1时，表示第i个位置的位置变量p<sub>i</sub>的值是数组SPACE中存储表L的第i-1个元素的单元的下标值，即SPACE[p<sub>i</sub>].next是指示第i个元素在SPACE中的下标。当i=1时，p<sub>i</sub>=O。</p>
<p style="text-autospace: none" align="left">类型定义如下：</p>
<pre>Type
TList=integer;
TPosition=integer;</pre>
<div align="center">
<center>
<table border="0" width="313" height="217">
<tr>
<td width="230"></td>
<td valign="top" width="72"> SPACE</td>
</tr>
<tr>
<td width="230" height="213"><img border="0" src="images/img7.gif" width="229" height="219"></td>
<td height="213" valign="top" width="72">
<table border="1" width="70" bordercolor="#000000" cellspacing="0" cellpadding="0">
<tr>
<td width="100%" align="center">d</td>
<td width="100%" align="center">7</td>
</tr>
<tr>
<td width="100%" align="center"> </td>
<td width="100%" align="center">4</td>
</tr>
<tr>
<td width="100%" align="center">c</td>
<td width="100%" align="center">0</td>
</tr>
<tr>
<td width="100%" align="center"> </td>
<td width="100%" align="center">6</td>
</tr>
<tr>
<td width="100%" align="center">a</td>
<td width="100%" align="center">8</td>
</tr>
<tr>
<td width="100%" align="center"> </td>
<td width="100%" align="center">0</td>
</tr>
<tr>
<td width="100%" align="center">e</td>
<td width="100%" align="center">0</td>
</tr>
<tr>
<td width="100%" align="center">b</td>
<td width="100%" align="center">3</td>
</tr>
<tr>
<td width="100%" align="center"> </td>
<td width="100%" align="center">10</td>
</tr>
<tr>
<td width="100%" align="center"> </td>
<td width="100%" align="center">2</td>
</tr>
</table>
</td>
</tr>
</table>
</center>
</div>
<p align="center" style="text-autospace: none">图4 用游标实现表</p>
<p style="text-autospace: none" align="left"> 在图4中，两个表L（包含元素依次为a,b,c）和M（包含元素依次为d,e）存放于同一数组SPACE中，其中的maxlength=10。数组SPACE中末被占用的所有单元组成了另一个表available，由这个表提供L和M的备用单元。当我们要在表L或M中插入一个元素时，所用的新单元就取自表available。反之，从两个表中删除的单元要回收(插入)到表available中备用。</p>
<p style="text-autospace: none" align="left"> 初始时，我们将数组SPACE中所有单元链接成表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>procedure</b>
Initialize;</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">
i: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">
for i:=maxlength-l downto 1 do SPACE[i].next:=i+l;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
available:=1;</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
{表available的第一个可用单元即表头在SPACE中的下标为1}</p>
<p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">
SPACE[maxlength].next:=0;</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，可将表available的第一个单元摘除，并将这个备用单元插入L的适当位置，再将这个新单元的element域赋值为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>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">begin</p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -