📄 chapter2.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>表——ADT表的操作</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
previous = "chapter1.htm";
next = "chapter3.htm";
topic="表 LIST";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h2>ADT表的操作<a name="opt"></a></h2>
<p>表是一种非常简便的结构，我们可以根据需要改变表的长度，也可以在表中任何位置对元素进行访问、插人或删除等操作。我们还可以将两个表连接成一个表，或把一个表拆成几个表。表的结构在信息检索，程序设计语言的编译等许多方面有广泛的应用。</p>
<p>在表的数学模型上，我们还要定义一组运算，才能使这一数学模型成为一个抽象数据类型表即ADT表。下面我们将给出一组典型的表运算。其中L是由类型为 TElement
的元素组成的一个表。x表示一个元素，p表示元素在表中的位置，其类型为TPosition。<b>在表的不同实现方式下，TPosition可能有不同的类型定义，作为位置变量的p也可能有不同的含义</b>。但是TPosition必须是一个偏序集，即任何两个TPosition类型的变量x,y之间可以进行比较运算，且结果只有x>y,x<y,x=y,x>=y,x<=y五种。</p>
<p>下面我们将ADT表看作一个抽象类TList，L是该类的一个实体，ADT表的操作将定义成L的属性和方法。</p>
<p align="center"><b>ADT表的基本运算</b></p>
<div align="center">
<center>
<table border="1" width="90%" cellspacing="0" cellpadding="5" height="198" bordercolor="#FFFFFF">
<tr>
<th width="25%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">运算</font></th>
<th width="75%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">含义</font></th>
</tr>
<tr>
<td width="25%" align="center" height="15" bgcolor="#E0E0E0"><font size="2">L.end</font></td>
<td width="75%" height="15" bgcolor="#E0E0E0"><font size="2">为了方便，我们假定表L的结束元素a<sub>n</sub>之后还有一个位置，用属性end的值来表示这个位置。该属性的值为TPosition类型。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="15" bgcolor="#E0E0E0"><font size="2">L.piquet</font></td>
<td width="75%" height="15" bgcolor="#E0E0E0"><font size="2">为了方便，我们假定表L的开始元素a<sub>1</sub>之前还有一个位置，该为值称为哨兵位置，该位置上的元素称为哨兵元素，用属性Piquet的值来表示这个位置。该属性的值为TPosition类型。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">L.first</font></td>
<td width="75%" height="16" bgcolor="#E0E0E0"><font size="2">这是一个属性，其值为表L中第一个元素的位置。当L为空表时，值为L.end。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="15" bgcolor="#E0E0E0"><font size="2">L.last</font></td>
<td width="75%" height="15" bgcolor="#E0E0E0"><font size="2">这是一个属性，其值为表L中最后一个元素的位置。当L为空表时，值为L.end。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="15" bgcolor="#E0E0E0"><font size="2">L.length</font></td>
<td width="75%" height="15" bgcolor="#E0E0E0"><font size="2">返回表L的长度，即元素个数。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="15" bgcolor="#E0E0E0"><font size="2">L.IsEmpty()</font></td>
<td width="75%" height="15" bgcolor="#E0E0E0"><font size="2">如果表L为空表(长度为0)则返回true，否则返回false。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">L.next(p)</font></td>
<td width="75%" height="16" bgcolor="#E0E0E0"><font size="2">这是一个函数，函数值为表L中位置p的后继位置。如果p是L中结束元素的位置，则L.Next(p)=L.end。当L中没有位置p或p=L.end时，该运算无定义。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">L.prev(p)</font></td>
<td width="75%" height="16" bgcolor="#E0E0E0"><font size="2">这是一个函数，函数值为表L中位置p的前驱位置。当L中没有位置p或p是L中开始元素的位置时，该运算无定义。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">L.get(p)</font></td>
<td width="75%" height="16" bgcolor="#E0E0E0"><font size="2">这是一个函数，函数值为L中位置p处的元素。当p=L.end或L中没有位置p时，该运算无定义。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="15" bgcolor="#E0E0E0"><font size="2">L.put(x,p)</font></td>
<td width="75%" height="15" bgcolor="#E0E0E0"><font size="2">该方法将元素x放置到表L的位置p处，如果位置p处已有元素，则用x取代该元素；如果p=L.end或者L中没有位置p，则该运算无定义。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">L.insert(x,p)</font></td>
<td width="75%" height="16" bgcolor="#E0E0E0"><font size="2">在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>，那么在执行L.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为L.end，那么表L变为a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>,x 。若表L中没有位置p，则该运算无定义。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">L.delete(p)</font></td>
<td width="75%" height="16" bgcolor="#E0E0E0"><font size="2">从表L中删除位置p处的元素。例如，当L为a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>时，执行L.delete(p)后，L变为a<sub>1</sub>,a<sub>2</sub>,…,a<sub>p-1</sub>,a<sub>p+1</sub>,…,a<sub>n</sub>
。当L中没有位置p或p=L.end时，该运算无定义。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">L.locate(x)</font></td>
<td width="75%" height="16" bgcolor="#E0E0E0"><font size="2">这是一个函数，函数值为元素x在L中的位置。若x在L中重复出现多次，则函数值为x第一次出现的位置。当x不在L中时，函数值为L.end。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">L.MakeEmpty</font></td>
<td width="75%" height="16" bgcolor="#E0E0E0"><font size="2">这是一个将L变为空表的方法。</font></td>
</tr>
<tr>
<td width="25%" align="center" height="16" bgcolor="#E0E0E0"><font size="2">L.print</font></td>
<td width="75%" height="16" bgcolor="#E0E0E0"><font size="2">将表L中所有元素按位置的先后次序打印输出。</font></td>
</tr>
</table>
</center>
</div>
<p>在表的数学模型上，定义了上述运算后，我们就定义了抽象数据类型（抽象类）TList。当然，并非任何时候都需要同时执行以上运算。在有些问题中只需要上述的一部分运算，因此也可以用上述运算的其中几个来定义适合特殊目的的抽象数据类型。上述表的运算是一些最基本的运算，对于实际问题中涉及的关于表的更复杂的运算，可以用这些基本运算的组合来实现。</p>
<p><a name="purge"></a>例如，我们可以利用上述基本运算写一个过程Purge，来清除一个表L中重复出现的元素。其中 p,q为TPosition类型的变量。</p>
<p class="comment">================下面是Pascal语言描述的代码================</p>
<pre><code class="pascal">
Procedure Purge(var L:TList)
var
p,q:TPosition;
begin
1 p:=L.first;
2 while p<>L.end do
begin
3 q:=L.next(p);
4 while q<>L.end do
5 if Equal(L.get(p),L.get(q)) then L.delete(q)
6 else q:=L.next(q);
7 p:=L.next(p);
end
end;
</code></pre>
<p class="comment">================下面是C++语言描述的代码================</p>
<pre><code class="c++">
void Purge(TList& L)
{
TPosition p,q;
1. p=L.first();
2. while (p!=L.end())
{
3. q=L.next(p);
4. while (q!=L.end())
{
5. if (Equal(L.get(p),L.get(q))) L.delete(q);
6. else q=L.next(q);
}
7. p=L.next(p);
}
}
</code></pre>
<p>上述过程的参数是一个表L，其元素类型为TElement。过程中用到的函数Equal(x,y)的两个自变量均为TElement类型的元素。若x与y相同，则函数值为true，否则为false。这里所说的相同的含义要根据具体元素的类型来确定。例如，当TElement为实型时，当且仅当x=y时Equal(x,y)=true。但是如果TElement是一个有用户帐号、姓名及地址等多个域的记录，如:</p>
<p class="comment">================下面是Pascal语言描述的代码================</p>
<pre><code class="pascal">
type
TElement=record
ID: integer;
Name: string[20];
Address: string[50];
end;
</code></pre>
<p class="comment">================下面是C++语言描述的代码================</p>
<pre><code class="c++">
typedef struct TElement
{
int ID;
char Name[20];
char Address[50];
};</code></pre>
<p>这时我们可以规定，Equal(x,y)=true当且仅当x.ID=y.ID，即x与y的帐号相同时成立；也可以规定3个域的值都相同时Equal(x,y)=true。</p>
<p>在Purge过程中，变量p与q是表L的两个位置变量，第2-7行是关于变量p的循环。在循环中逐个检查位置p后面的每一个位置q，如果这两个位置上的元素相同，则将位置q的元素从表L中删去。当q遍历了p后面的所有位置之后，p变为下一个位置，再开始新的循环。在过程的第4-6行的内循环中，有一点值得注意：当执行到第5行删除了位置q的元素以后，表中原来在位置q+l,q+2，…的各元素都要向前移动一个位置。特别地，如果q恰好是结束元素的位置，那么在第5行删除了位置q的元素后，q值将变为L.end。因此内循环体第5和第6行的语句必须并行而不能串行，不然，可能会出现无定义的语句q=L.next(L.end)（即第6行的语句不用else而单独作为一个语句会出错）。在后文中，我们要给出TList和TPosition的适当类型说明，并讨论实现表运算的方法。</p>
<p>下面我们用抽象类来定义ADT表。</p>
<p class="comment">================下面是C++语言描述的代码================</p>
<pre><code class="c++">
template < class TElement >
class TLiearList {
public:
virtual bool IsEmpty() const = 0;
virtual int length() const = 0;
virtual bool locate(int k, T& x) const = 0;
//return the k'th element of list in variable x
virtual int Search(const T& x) const = 0;
//return position of x
virtual AbstractList<T>& Delete(int k, T& x) = 0;
//delete k'th element of list and return in x
virtual AbstractList<T>&
Insert(int k, const T& x) = 0;
//insert x just after k'th element
virtual void Output(ostream& out) const = 0;
};
</code></pre>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -