数据结构

b · 发表于 2004-5-29 04:22:32

<H2>栈的实现</H2><

>栈是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现栈。不过，栈的操作相对表来说比较简单，因此通常只用数组和链表两种方法实现栈。<UL><LI><a href="http://algorithm.myrice.com/datastructure/basic/stack/chapter3_1.htm" target="_blank" >栈的数组实现</A> <LI><a href="http://algorithm.myrice.com/datastructure/basic/stack/chapter3_2.htm" target="_blank" >栈的指针实</A></LI></UL>

b · 发表于 2004-5-29 04:22:52

<H3>栈的数组实现</H3><

>由于栈是一个特殊的表，我们可以用数组来实现栈。考虑到栈运算的特殊性，我们用一个数组elements[1..maxlength]来表示一个栈时，将栈底固定在数组的底部，即elements[1]为最早入栈的元素，并让栈向数组上方(下标增大的方向)扩展。同时，我们用一个游标top来指示当前栈顶元素所在的单元。当top=0时，表示这个栈为一个空栈。在一般情况下，elements中的元素序列elements[top],elements[top-1],..,elements[1]就构成了一个栈。这种结构如图2所示。<

align=center><img src="http://algorithm.myrice.com/datastructure/basic/stack/images/img2.gif"><

align=center>图2 用数组实现栈利用上述结构，我们可以形式地定义栈类型TStack如下：<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">Type TStack=Record top:integer; element:array[1..maxlength] of TElement; End;</TD></TR></TABLE></CENTER></DIV>在这种表示法下，栈的5种基本运算可实现如下。<DIV align=center><CENTER><TABLE 10pt" borderColor=#ffffff cellPadding=5 width="90%" border=1><TR><TD width="100%" bgColor=#e0e0e0>procedure MakeNull(Var S:TStack);begin S.top:=0;end;</TD></TR><TR><TD width="100%" bgColor=#e0e0e0>function Empty(var S:Stack):Boolean;begin return(S.top=0);end; </TD></TR><TR><TD width="100%" bgColor=#e0e0e0>finction Top(var S:TStack):TElement;begin if Empty(S) then Error('The stack is empty.') else return(S.element[S.top]);end; </TD></TR><TR><TD width="100%" bgColor=#e0e0e0>procedure Pop(var S:TStack);begin if Empty(S) then Error('The stack is empty.') else dec(S.top); {S.top减1}end; </TD></TR><TR><TD width="100%" bgColor=#e0e0e0>procedure Push(x:TElement;var S:TStack);begin if S.top=maxlength then Error('The stack is full.') else begin inc(S.top); {S.top增1} S.elements[S.top]:=x; end;end; </TD></TR></TABLE></CENTER></DIV>以上每种操作的复杂性为O(1)。在一些问题中，可能需要同时使用多个同类型的栈。为了使每个栈在算法运行过程中不会溢出，要为每个栈顶置一个较大的栈空间。这样做往往造成空间的浪费。实际上，在算法运行的过程中，各个栈一般不会同时满，很可能有的满而有的空。因此，如果我们让多个栈共享同一个数组，动态地互相调剂，将会提高空间的利用率，并减少发生栈上溢的可能性。假设我们让程序中的两个栈共享一个数组S[1..n]。利用栈底位置不变的特性，我们可以将两个栈的栈底分别设在数组S的两端，然后各自向中间伸展，如图3所示。这两个S栈的栈顶初值分别为0和n+1。只有当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以余缺互补，因此每个栈实际可用的最大空间往往大于n/2。<img src="http://algorithm.myrice.com/datastructure/basic/stack/images/img3.gif">图3 共享同一个数组的两个栈

b · 发表于 2004-5-29 04:23:29

<H3>栈的指针实现</H3><

>在算法中要用到多个栈时，最好用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3_2.htm#def-chain" target="_blank" >链表</A>作为栈的存储结构，即用指针来实现栈。用这种方式实现的栈也称为链栈，见图4。由于栈的插人和删除操作只在表头进行，因此用指针实现栈时没有必要像<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3_2.htm#def-chain" target="_blank" >单链表</A>那样设置一个表头单元。<

align=center><img src="http://algorithm.myrice.com/datastructure/basic/stack/images/img4.gif"><

align=center>图4 链栈栈的类型说明与单链表类似。<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">type TNode=record element:TElement; next:^TNpde; ent; TStack=^TNode </TD></TR></TABLE></CENTER></DIV>链栈的基本操作实现如下：<DIV align=center><CENTER><TABLE borderColor=#ffffff cellPadding=5 width="90%" border=1><TR><TD width="100%" bgColor=#e0e0e0>procedure MakeNull(Var S:TStack);var p:TStack;begin p:=S; while S<>nil do begin S:=S^.next; dispose(p); {释放该单元占用的内存空间} p:=S; end;end;</TD></TR><TR><TD width="100%" bgColor=#e0e0e0>function Empty(var S:Stack):Boolean;begin return(S=nil);end; </TD></TR><TR><TD width="100%" bgColor=#e0e0e0>finction Top(var S:TStack):TElement;begin if Empty(S) then Error('The stack is empty.') else return(S.element);end; </TD></TR><TR><TD width="100%" bgColor=#e0e0e0>procedure Pop(var S:TStack);var p:TStack;begin if Empty(S) then Error('The stack is empty.') else begin p:=S; S:=S^.next; dispose(p); end;end; </TD></TR><TR><TD width="100%" bgColor=#e0e0e0>procedure Push(x:TElement;var S:TStack);var p:TStack;begin new(p); p^.element:=x; p^.next:=S; S:=p;end; </TD></TR></TABLE></CENTER></DIV>显然，以上操作中只用MakeNull的复杂性为O(n)，其余的复杂性为O(1)。

b · 发表于 2004-5-29 04:23:44

<H2>队列的定义</H2><

>队列是一种特殊的<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter1.htm" target="_blank" >线性表</A>。对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(First In First Out)表，简称FIFO表。<H2>队列的数学性质</H2><

>假设队列为a1,a2,..,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,..,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,..,an-1都离开队列之后，an才能退出队列。图1是队列的示意图。<

align=center><img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img7.gif">图1 队列的先进先出示意图

b · 发表于 2004-5-29 04:24:07

<H2>ADT队列的操作</H2><

>作为一种抽象数据类型，队列的基本操作为：<DIV align=center><CENTER><TABLE 10pt" height=200 cellPadding=5 width="90%" border=0><TR><TD align=middle width="19%" bgColor=#e0e0e0 height=15>运算</TD><TD align=middle width="81%" bgColor=#e0e0e0 height=15>含义</TD></TR><TR><TD align=middle width="19%" bgColor=#e0e0e0 height=28>Front(Q)</TD><TD width="81%" bgColor=#e0e0e0 height=28>这是一个函数，函数值返回队列Q的队头元素。用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >一般的表运算</A>可将Front(Q)表示为Retrieve(First(Q),Q)。</TD></TR><TR><TD align=middle width="19%" bgColor=#e0e0e0 height=28>Enqueue(x,Q)</TD><TD width="81%" bgColor=#e0e0e0 height=28>将元素x插入队列Q的队尾。此运算也常简称为将元素x入队。也可用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >一般的表运算</A>将Enqueue(x,Q)表示为Insert(x,End(Q),Q)。</TD></TR><TR><TD align=middle width="19%" bgColor=#e0e0e0 height=27>Dequeue(Q)</TD><TD width="81%" bgColor=#e0e0e0 height=27>将Q的队头元素删除，简称为出队。用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >一般的表运算</A>可将Dequeue(Q)表示为Delete(First(Q),Q)。</TD></TR><TR><TD align=middle width="19%" bgColor=#e0e0e0 height=15>Empty(Q)</TD><TD width="81%" bgColor=#e0e0e0 height=15>这是一个函数，若Q是一个空队列，则函数值为true，否则为false。</TD></TR><TR><TD align=middle width="19%" bgColor=#e0e0e0 height=15>MakeNull(Q)</TD><TD width="81%" bgColor=#e0e0e0 height=15>使队列Q成为空队列。</TD></TR></TABLE></CENTER></DIV>

b · 发表于 2004-5-29 04:24:30

<H2>队列的实现</H2><

>队列是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现队列。不过，队列的中的元素的个数通常不固定，因此常用循环数组和链表两种方法实现队列。<UL><LI><a href="http://algorithm.myrice.com/datastructure/basic/queue/chapter3_1.htm" target="_blank" >用循环数组实现队列</A> <LI><a href="http://algorithm.myrice.com/datastructure/basic/queue/chapter3_2.htm" target="_blank" >用指针实现队列</A></LI></UL>

b · 发表于 2004-5-29 04:24:51

<H3>用循环数组实现队列</H3><

>我们可以将队列<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3_1.htm" target="_blank" >当作一般的表用数组加以实现</A>，但这样做的效果并不好。尽管我们可以用一个游标last来指示队尾，使得Enqueue运算可在O(1)时间内完成，但是在执行Dequeue时，为了删除队头元素，必须将数组中其他所有元素都向前移动一个位置。这样，当队列中有n个元素时，执行Dequeue就需要O(n)时间。<

>为了提高运算的效率，我们用另一种方法来表达数组中各单元的位置关系。设想数组Q[1..MaxLength]中的单元不是排成一行，而是围成一个圆环，即Q[1]接在Q[MaxLength]的后面。这种意义下的数组称为循环数组，如图2所示。<BLOCKQUOTE><

align=center><img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img10.gif">图2 用循环数组实现队列</BLOCKQUOTE>用循环数组实现队列时，我们将队列中从队头到队尾的元素按顺时针方向存放在循环数组中一段连续的单元中。当需要将新元素入队时，可将队尾游标Q.rear按顺时针方向移一位，并在新的队尾游标指示的单元中存入新元素。出队操作也很简单，只要将队头游标Q.front依顺时针方向移一位即可。容易看出，用循环数组来实现队列可以在O(1)时间内完成Enqueue和Dequeue运算。执行一系列的入队与出队运算，将使整个队列在循环数组中按顺时针方向移动。在图2中，我们直接用队头游标Q.front指向队头元素所在的单元，用队尾游标Q.rear指向队尾元素所在的单元。另外，我们也可以用队头游标Q.front指向队头元素所在单元的前一个单元，或者用队尾游标Q.rear指向队尾元素所在单元的下一个单元的方法来表示队列在循环数组中的位置，如图3所示。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img9.gif"><img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img8.gif">　图3 循环数组中的队头与队尾游标</BLOCKQUOTE>在循环数组中，不论用哪一种方式来指示队头与队尾元素，我们都要解决一个细节问题，即如何表示满队列和空队列。图4给出一个例子，MaxLength=6，队列中已有3个元素。我们用上述3种方法来指示队头和队尾元素，分别如图4(a)、(b)和(c)所示。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img5.gif">(a)<img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img19.gif">(b)<img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img18.gif">(c)图4 循环数组中的队列</BLOCKQUOTE>现在，有3个元素a4,a5,a6相继入队，使队列呈"满"的状态，则如图5相应的(a),(b)和(c)所示。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img6.gif">(a)<img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img17.gif">(b)<img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img16.gif">(c)图5 队列满的情形</BLOCKQUOTE>如果在图4中，3个元素a1,a2,a3相继出队，使队列呈"空"的状态，则如图6相应的(a),(b)和(c)所示。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img4.gif">(a)<img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img15.gif">(b)<img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img14.gif">(c)图6 队列空的情形</BLOCKQUOTE>比较图5和图6我们看到，不论采用哪一种方式指示队头和队尾元素，都需要附加说明或约定才能区分满队列和空队列。通常有两种处理方法来解决这个问题。其一是另设一个布尔量来注明队列是空还是满。二是约定当循环数组中元素个数达到MaxLength-1时队列为“满”，使得队列满和队列空时的队头和队尾游标的相对位置不同，从而满队列和空队列得以区分。例如，在图4中，当元素a4和a5相继入队后，就便队列呈“满”的状态，如图7所示。比较图7和图6，显然只要测试头和队尾游标的相对位置便可区分出满队列和空队列。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img13.gif">(a)<img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img12.gif">(b)<img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img11.gif">(c)图7 改进后的队列满的情形</BLOCKQUOTE>为确定起见，这里采用图2的方式定义Q.front和Q.rear，另采用上述的第二种处理法区分满队列和空队列。这样，队列的类型QueueType说明为：<DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">typeTPosition=integer;QueueType = record Elements:array[1..MaxLength] of ElementType; front,rear:TPosition; end; </TD></TR></TABLE></CENTER></DIV><BLOCKQUOTE>那么，在用循环数组实现的队列中，队列的5种基本运算可实现如下。其中∧表示空元素，要根据不同的元素类型来确定。</BLOCKQUOTE><DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" border=0><TR><TD width="100%" bgColor=#e0e0e0>函数 Front(Q)功能<BLOCKQUOTE>这是一个函数，函数值返回队列Q的队头元素。用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >一般的表运算</A>可将Front(Q)表示为Retrieve(First(Q),Q)。如果队列为空则返回空元素∧。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Front(var Q

ueueType):ElementType;begin if Empty(Q) then return(∧) else return(Q.Elements[Q.front]);end;</BLOCKQUOTE>说明<BLOCKQUOTE>显然</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Enqueue(x,Q)功能<BLOCKQUOTE>将元素x插入队列Q的队尾。此运算也常简称为将元素x入队。也可用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >一般的表运算</A>将Enqueue(x,Q)表示为Insert(x,End(Q),Q)。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure Enqueue(x:ElementType;var Q

ueueType);begin if Full(Q) then Error('The queue is full!') else begin Q.rear:=Q.rear mod MaxLength+1; Q.Elements[Q.rear]:=x; end;end;　Full是一个函数，若队列Q已满，则函数值为true，否则为false。　Function Full(var Q

ueueType):Boolean;begin Return((Q.front+MaxLength-Q.rear=2)or(Q.front-Q.rear=2));end;　</BLOCKQUOTE>说明<BLOCKQUOTE>注意在计算队尾的位置时，如果用Q.rear:=(Q.rear+1) mod MaxLength，当Q.rear=MaxLength-1时就会出错，因此应该用Q.rear:=Q.rear mod MaxLength+1。如图7(a)所示，队列满有两种情况，一种是Q.front>Q.rear且Q.front-Q.rear=2，一种是Q.front<Q.rear且Q.front+MaxLength-Q.rear=2，根据这点可以实现Full函数。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Dequeue(Q)功能<BLOCKQUOTE>将Q的队头元素删除，简称为出队。用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >一般的表运算</A>可将Dequeue(Q)表示为Delete(First(Q),Q)。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure Dequeue(var Q:QueueType);begin if Empty(Q) then Error('The queue is empty!') else Q.front:=Q.front mod MaxLength +1;end;</BLOCKQUOTE>说明<BLOCKQUOTE>显然。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Empty(Q)功能<BLOCKQUOTE>这是一个函数，若Q是一个空队列，则函数值为true，否则为false。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Empty(var Q:QueueType):Boolean;begin return((Q.front-Q.rear=1)or(Q.front+MaxLength-Q.rear=1));end;</BLOCKQUOTE>说明<BLOCKQUOTE>根据图6(a)知，队列空有两种情况，一种是Q.front>Q.rear且Q.front-Q.rear=1，一种是Q.front<Q.rear且Q.front+MaxLength-Q.rear=1。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 MakeNull(Q)功能<BLOCKQUOTE>使队列Q成为空队列。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure MakeNull(Q);begin Q.front:=2; Q.rear:=1;end;</BLOCKQUOTE>说明<BLOCKQUOTE>用这种循环数组实现队列，不需要回收内存空间，因此MakeNull实现起来很简单，只要利用队列空的条件，使Q.front-Q.rear=1即可。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR></TABLE></CENTER></DIV>

b · 发表于 2004-5-29 04:25:15

<H3>用指针实现队列</H3><

>与<a href="http://algorithm.myrice.com/datastructure/basic/stack/chapter1.htm" target="_blank" >栈</A>的情形相同，任何一种<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3.htm" target="_blank" >实现表的方法</A>都可以用于实现队列。用指针实现队列得到的实际上是一个单链表。由于入队在队尾进行，所以用一个指针来指示队尾可以使入队操作不必从头到尾检查整个表，从而提高运算的效率。另外，指向队头的指针对于Front和Dequeue运算也是必要的。为了便于表示空队列，我们仍使用一个表头单元，将队头指针指向表头单元。当队头和队尾指针都指向表头单元时，表示队列为一个空队列。<

>用指针实现队列时，单元类型及队列类型可说明如下:<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%"><

5px; MARGIN-BOTTOM: 5px">typeTPosition=^NodeType;NodeType=record Element:ElementType; next:TPosition; end;QueueType=record front,rear:TPosition; end; </TD></TR></TABLE></CENTER></DIV>其中front为队头指针，rear为队尾指针。图8是用指针表示队列的示意图。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img1.gif">图8 用指针实现队列</BLOCKQUOTE>下面我们来讨论队列的5种基本运算。<DIV align=center><TABLE 10pt" cellPadding=5 width="90%" border=0><CENTER><TR><TD width="100%" bgColor=#e0e0e0>函数 Front(Q)功能<BLOCKQUOTE>这是一个函数，函数值返回队列Q的队头元素。用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >一般的表运算</A>可将Front(Q)表示为Retrieve(First(Q),Q)。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Front(var Q

ueueType):ElementType;begin if Empty(Q) then error('The queue is empty!') else return(Q.front^.next^.Element);end;</BLOCKQUOTE>说明<BLOCKQUOTE>显然。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Enqueue(x,Q)功能<BLOCKQUOTE>将元素x插入队列Q的队尾。此运算也常简称为将元素x入队。也可用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >一般的表运算</A>将Enqueue(x,Q)表示为Insert(x,End(Q),Q)。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure Enqueue(x:ElementType;var Q

ueueType);begin new(Q.rear^.next); Q.rear:=Q.rear^.next; Q.rear^.Element:=x; Q.rear^.next:=nil;end;</BLOCKQUOTE>说明<BLOCKQUOTE>图9是该操作修改指针的示意图。<img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img2.gif">图9 入队操作</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR></CENTER><TR><TD width="100%" bgColor=#e0e0e0><CENTER>函数 Dequeue(Q)功能<BLOCKQUOTE>将Q的队头元素删除，简称为出队。用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >一般的表运算</A>可将Dequeue(Q)表示为Delete(First(Q),Q)。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure Dequeue(var Q

ueueType);varp:TPosition;begin if Empty(Q) then Error('The queue is empty!') else begin p:=Q.front; Q.front:=Q.front^.next; dispose(p); end;end;</BLOCKQUOTE>说明</CENTER><BLOCKQUOTE>图10是该操作修改指针的示意图。<CENTER><img src="http://algorithm.myrice.com/datastructure/basic/queue/images/img3.gif">图10 出队操作</CENTER></BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Empty(Q)功能<BLOCKQUOTE>这是一个函数，若Q是一个空队列，则函数值为true，否则为false。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Empty(var Q:QueueType):Boolean;begin return(Q.front=Q.rear);end;</BLOCKQUOTE>说明<BLOCKQUOTE>当Q.front与Q.rear指向同一个结点单元时队列为空。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 MakeNull(Q)功能<BLOCKQUOTE>使队列Q成为空队列。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure MakeNull(var Q:QueueType);begin Q.rear:=Q.front; while Q.front<>nil do begin Q.front:=Q.front^.next; dispose(Q.rear); Q.rear:=Q.front; end; new(Q.front); Q.front^.next:=nil; Q.rear:=Q.front; end;</BLOCKQUOTE>说明<BLOCKQUOTE>首先将Q中所有的结点内存释放，然后重新生成一个结点作为标头单元，并使Q.rear:=Q.front。</BLOCKQUOTE>复杂性<BLOCKQUOTE>若输入的队列Q中有n个结点，则复杂性为O(n)。</BLOCKQUOTE></TD></TR></TABLE></DIV>

b · 发表于 2004-5-29 04:25:34

<H2>树的定义</H2><

> 树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。我们可以形式地给出树的递归定义如下:<OL><LI>单个结点是一棵树，树根就是该结点本身。 <LI>设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的儿子结点。我们还称n1,n2,..,nk为结点n的子树。 </LI></OL><

>空集合也是树，称为空树。空树中没有结点。<

>一棵典型的树如图1所示：<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img4.gif">图1 树的层次结构</BLOCKQUOTE>由图1可以看出树的形状就像一棵现实中的树，只不过是倒过来的。

b · 发表于 2004-5-29 04:26:19

<H2>树的相关术语</H2><OL><LI><

10px; MARGIN-BOTTOM: 10px">一个结点的儿子结点的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。 <LI><

10px; MARGIN-BOTTOM: 10px">树中度为零的结点称为叶结点或终端结点。 <LI><

10px; MARGIN-BOTTOM: 10px">树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。例如在图1中，结点A，B和E的度分别为3，2，0。其中A为根结点,B为内部结点，E为叶结点，树的度为3。 <LI>如果存在树中的一个结点序列K1,K2,..,Kj，使得结点Ki是结点Ki+1的父结点(1≤i≤j)，则称该结点序列是树中从结点K1到结点Kj的一条路径或道路。我们称这条路径的长度为j-1，它是该路径所经过的边(即连接两个结点的线段)的数目。树中任一结点有一条到其自身的长度为零的路径。例如，在图1中，结点A到结点I有一条路径ABFI，它的长度为3。 <LI>如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的祖先，也称结点M是结点K的子孙或后裔。例如在图1中，结点F的祖先有A，B和F自己，而它的子孙包括它自己和I,J。注意，任一结点既是它自己的祖先也是它自己的子孙。 <LI>我们将树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子孙。在一棵树中，树根是唯一没有真祖先的结点。叶结点是那些没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。 <LI>树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。例如图1中的结点B，C和D的高度分别为2，0和1，而树的高度与结点A的高度相同为3。 <LI>从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点n的深度或层数。根结点的深度为0，其余结点的深度为其父结点的深度加1。深度相同的结点属于同一层。例如，在图1中，结点A的深度为0；结点B，C和D的深度为1；结点E，F，G，H的深度为2；结点I和J的深度为3。在树的第二层的结点有E，F，J和H，树的第0层只有一个根结点A。 <LI>树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为祖先子孙关系。但是树中的许多结点之间仍然没有这种关系。例如兄弟结点之间就没有祖先子孙关系。如果我们在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵有序树；否则称为无序树。设结点n的所有儿子按其从左到右的次序排列为n1,n2,..,nk，则我们称n1是n的最左儿子，或简称左儿子，并称ni是ni-1的右邻兄弟，或简称右兄弟(i=2,3,..k)。图2中的两棵树作为无序树是相同的，但作为有序树是不同的，因为结点a的两个儿子在两棵树中的左右次序是不同的。后面，我们只关心有序树，因为无序树总可能转化为有序树加以研究。<img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img1.gif">图2 两棵不同的有序树我们还可以将兄弟结点之间的左右次序关系加以延拓：如果a与b是兄弟，并且a在b的左边，则认为a的任一子孙都在b的任一子孙的左边。 <LI>森林是m(m>0)棵互不相交的树的集合。如果我们删去一棵树的树根，留下的子树就构成了一个森林。当我们删去的是一棵有序树的树根时，留下的子树也是有序的，这些树组成一个树表。在这种情况下，称这些树组成的森林为有序森林或果园。 <LI>在讨论表的时候，我们对表的每一位置的元素赋予一个元素值。这里，我们也用树的结点来存储元素，即对于树中的每一个结点赋予一个标号，这个标号并不是该结点的名称，而是存储于该结点的一个值。结点的名称总是不变的，而它的标号是可以改变的。我们可以做这样的类比：树：表 = 标号：元素 = 结点：位置</LI></OL>

		自动登录	找回密码
密码			注-册-帐-号