chapter2.htm

介绍各种数据结构的讲义

  <tr> 
    <td width="85"> 
      <div align="center"> <font size="2">a<sub>9</sub>&lt;a<sub>4</sub></font> 
      </div>
    </td>
  </tr>
  <tr> 
    <td width="85"> 
      <div align="center"> <font size="2">a<sub>9</sub>&lt;a<sub>10</sub></font> 
      </div>
    </td>
  </tr>
</table>
<p align="center"><font size="2">表1-3 S={a<sub>1</sub>,a<sub>2,</sub>...,a<sub>10</sub>}中的部分序</font></p>
<p>在数据模型Digraph和Queue的基础上，容易拟定出算法高层的宏观运算步骤，我们称之为算法的主干部分，并用非形式的自然语言表述如下：</p>
<blockquote> 
    <p style="margin-top: 0; margin-bottom: 0">1.φ-&gt;Q;</p>
    <p style="margin-top: 0; margin-bottom: 0">2.检测G。</p>

  <p style="margin-top: 0; margin-bottom: 0">(1)当G≠φ时;</p>
  <blockquote> 
      <p style="margin-top: 0; margin-bottom: 0">①在G中出任意一个无前驱的结点，记为a；</p>
      <p style="margin-top: 0; margin-bottom: 0">②将a加到Q的末尾;</p>
      <p style="margin-top: 0; margin-bottom: 0">③在G中删去结点a以及以a为起点的所有有向边;</p>
      <p style="margin-top: 0; margin-bottom: 0">④转向2。</p>
  </blockquote>
  <p style="margin-top: 0; margin-bottom: 0">(2)当C=φ时，算法结束，问题的解在Q中。</p>
</blockquote>
<p>用高级语言中的控制结构语句成分，替换上述主干算法中自然语言的控制转移术语，则主干算法可用自然语言和高级语言的混合语言改述如下:</p>
<pre><code>φ-&gt;Q;
while G≠φ do
 begin
  a:=G中任意一个无前驱的顶点; 
  将a加到Q的末尾; 从G中删去结点a以及以a为起点的所有有向边; 
 end;</code></pre>
<p>我们看到，其中那些还未能用高级语言表达的语句或语句成分，正是算法需要定义在数据 模型Digraph和Queue上的运算。现分别将它们列出。</p>
<p>对于Digraph中的G:</p>
<blockquote> 
  <ol>
    <li>检测G是否非空图;</li>
    <li>在G中找任意一个无前驱的结点;</li>
    <li>在G中删去一个无前驱的结点，以及以该结点为起点的所有有向边。</li>
  </ol>
</blockquote>
<p>对于Queue中的Q:</p>
<blockquote> 
  <ol>
    <li>初始化Q为空队列;</li>
    <li>将一个结点加到Q的末尾。</li>
  </ol>
</blockquote>
<p>如果还考虑到已知G的初始状态如何由输入形成和Q的结果状态的输出，那么，对于Digraph和Queue还需要补充定义若干有关的运算。为了简单，这里从略。</p>
<p>由于高级语言为抽象数据类型的定义提供了很好的环境和工具，再复杂的数据模型都可 以通过构造数据类型来表达，再复杂的运算都可以借助过程或函数来描述。因此，上述由数据模型和数据模型上定义的运算综合起来的抽象数据类型很容易用高级语言来定义。</p>
<p>对于抽象数据类型mgraph，定义如下三个运算:</p>
<dl> 
  <dd>(l)function G_empty(G:Digraph):boolean;</dd>
  <dd>{检测图G是否非空。如果G=φ，则函数返回true，否则返回false}</dd>
  <dd>(2)function G_front(G:Digraph):nodetype；</dd>
  <dd>{在有向图G中找一个无前驱的结点。nodetype是结点类型名，它有待用户定义，下同}</dd>
  <dd>(3)Procedure delete_G_front(var G:Digraph;a:nodetype);</dd>
  <dd>{在G中删去结点a以及以a为起点的所有有向边}</dd>
</dl>
<p>对抽象数据类型Queue，定义如下两个运算:</p>
<dl> 
  <dd>(l)Procedure init_Q(var Q:Queue); {初始化队列Q为空队列}</dd>
  <dd>(2)Procedure add_Q_rear(a:nodetype;var Q:Queue) {将结点a加到队列Q的末尾}</dd>
</dl>
<p>这样，我们便定义了ADT Digraph和ADT Queue。</p>
<p>有了抽象数据类型Digraph和Queue的上述定义，拓扑排序问题的主干算法即可完全由高级语言表达成主程序。</p>
<pre><code>Program topsort(input，ouput);
type
 nodetype=…
 Digraph=…
 Queue=…
 
Function G_empty(G:Digraph):boolean;
          ...
          
Function G_front(G:Dlgraph):nodetype;
          ...
          
Procedure delete_G_front(var G:Digraph;a:nodetype);
          ...
          
Procedure init_Q(var Q:Queue);
          ...
          
Procedure add_Q_rear(a:nodetype;var Q:Queue);
          ...

var
a:nodetype;
G:Digraph;
Q:Queue;

begin
 …       {输入并形成G的初始状态即拓扑排序前的状态}
 init_Q(Q);
 while not G_empty(G) do
  begin
   a:=G_front(G);
   add_Q_rear(a，Q);
   delete_G_front(G，a);
  end;
 …
{输出Q中的结果}
end;</code></pre>
<p>为了简明，我们在其中略去了输入、拓扑排序前G的状态的形成和结果输出三个部分。至于构造数据类型nodetype，Digraph和Queue的表示，函数G_empty，G_front，过程delete_G_front，init_Q和add_Q_rear等的实现，则留待算法的底层设计去完成。需要指出的是，nodetype通常用记录表示，而Digraph和Queue都有多种表示方式。因而G_empty，G_front，delete_G_front，init_Q和add_Q_rear也有多种的实现方式。</p>
<p>但是，只要抽象数据类型Digraph和Queue的定义不变，不管上述构造数据类型的表示和过程与函数的实现如何改变，主程序的表达都不会改变;反过来，不管主程序在哪里调用抽象数据类型上的函数或过程，上述构造数据类型的表示和过程与函数的实现都不必改变。算法顶层的设计与底层的设计之间的这种独立性，显然得益于抽象数据类型的引人。而这种独立性给算法和程序设计带来了许多好处。</p>

<!-- #EndEditable --> 
</div>
<script src='../../lib/footer.js'>
</script> 
</body> 
<!-- #EndTemplate --></html>