数据结构

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

<

>Function Locate(x:TElement;L:TList):TPosition;<

>Var<

> p:TPosition;begin p:=L; while p^.next<>nil do if p^.next^.element = x then return(p) else p:=p^.next; return(p);end;说明在单链表中实现LOCATE的过程与用数组实现表时的LOCATE过程是类似的。复杂性容易看出，在最坏情况下和平均情况下，LOCATE所需的时间均为O(n)。
 对于其他基本的表运算实现起来都比较简单，这里从略。至于时间复杂性，在最坏情况下，PrintList显然需要O(n)，而Previous由于单链表没有设置指向前驱的指针，得从头到尾扫描，因此也需要O(n)。

b · 发表于 2004-5-29 04:17:40

<

>表的游标实现
所谓游标就是指示数组单元地址的下标值，它属整数类型。我们可以用游标来模拟指针，将TElement类型的元素所组成的表用一个数组来实现，数组单元是记录类型，记录中包含一个表元素和一个作为游标的整数；具体说明如下:<

>Var
SPACE: array[1..maxlength] of
 record
 element:TElement;
 next:integer;
 end;
对于一个表L，我们用一个整型变量Lhead作为L的表头游标。SPACE[Lhead]就是L的表头单元，其中的elemnt域是空的，next域中的游标指示L的第一个元素在数组SPACE中的存储地址(数组下标值)。这样，我们就可以用游标来模拟指针，实现单链表中的各种运算。照此，我们虽然是用数组来存储表中的元素，但在作表的插人和删除运算时，不需要移动元素，只要修改游标，从而保持了用指针实现表的优点。因此，有时也将这种用游标实现的表称为静态链表。<

> 下面我们介绍用游标实现表的另一种方式。这种方式不用表头单元，因此在表的第一个位置进行插入或删除时，需要进行特殊处理。这与在单链表中不用表头单元的情形类似。设L是一个表。我们用Lhead指示L的第一个元素，即L的第一个元素存放于SPACE[Lhead].element中，而SPACE[Lhead].next为L的第二个元素所在单元的下标值。其后每个元素的后继元素所在单元以类似的方式给出。如果Lhead或者某单元中next域的值为0，则表示这是一个空指针，即该游标不指示任何单元。表L可以用它的表头变量Lhead来代表。由于表头变量是整型变量，所以表的类型为整型。位置变量类型TPosition也是整型。与单链表中位置变量的意义相类似。我们约定，当i>1时，表示第i个位置的位置变量pi的值是数组SPACE中存储表L的第i-1个元素的单元的下标值，即SPACE[pi].next是指示第i个元素在SPACE中的下标。当i=1时，pi=O。类型定义如下：Type
TList=integer;
TPosition=integer;

b · 发表于 2004-5-29 04:17:55

<DIV align=center><CENTER><TABLE height=217 width=313 border=0><TR><TD width=230></TD><TD vAlign=top width=72> SPACE</TD></TR><TR><TD width=230 height=213><img src="http://algorithm.myrice.com/datastructure/basic/list/images/img7.gif"></TD><TD vAlign=top width=72 height=213><TABLE borderColor=#000000 cellSpacing=0 cellPadding=0 width=70 border=1><TR><TD align=middle width="100%">d</TD><TD align=middle width="100%">7</TD></TR><TR><TD align=middle width="100%">　</TD><TD align=middle width="100%">4</TD></TR><TR><TD align=middle width="100%">c</TD><TD align=middle width="100%">0</TD></TR><TR><TD align=middle width="100%">　</TD><TD align=middle width="100%">6</TD></TR><TR><TD align=middle width="100%">a</TD><TD align=middle width="100%">8</TD></TR><TR><TD align=middle width="100%">　</TD><TD align=middle width="100%">0</TD></TR><TR><TD align=middle width="100%">e</TD><TD align=middle width="100%">0</TD></TR><TR><TD align=middle width="100%">b</TD><TD align=middle width="100%">3</TD></TR><TR><TD align=middle width="100%">　</TD><TD align=middle width="100%">10</TD></TR><TR><TD align=middle width="100%">　</TD><TD align=middle width="100%">2</TD></TR></TABLE></TD></TR></TABLE></CENTER></DIV><

align=center>图4 用游标实现表<

align=left> 在图4中，两个表L（包含元素依次为a,b,c）和M（包含元素依次为d,e）存放于同一数组SPACE中，其中的maxlength=10。数组SPACE中末被占用的所有单元组成了另一个表available，由这个表提供L和M的备用单元。当我们要在表L或M中插入一个元素时，所用的新单元就取自表available。反之，从两个表中删除的单元要回收(插入)到表available中备用。<

align=left> 初始时，我们将数组SPACE中所有单元链接成表available备用。这个过程可实现如下。

b · 发表于 2004-5-29 04:18:12

<

>procedure Initialize;<

>Var<

> i:Integer;begin for i:=maxlength-l downto 1 do SPACE.next:=i+l; available:=1; {表available的第一个可用单元即表头在SPACE中的下标为1} SPACE[maxlength].next:=0;end;
 要在表L中插入一个元素x，可将表available的第一个单元摘除，并将这个备用单元插入L的适当位置，再将这个新单元的element域赋值为x。procedure Insert(x:TElement;p:TPosition;var L:TLIST);begin if p=O then (在第一个位置插入) begin if move(available,L) then SPACE[L].element:=x else error; end else {不在第一个位置插入} if move(available,SPACE[p].next) then SPACE[SPACE[p].next].element:=x else errorend;
 由于我们没有使用表头单元，所以必须单独处理在第一个位置插入的情形。另外，上述过程中用到了一个函数move(p,q)，其功能是从某一链表中将游标p所指的单元C摘除，并将这个单元C插入到另一链表中游标q所指的单元之前，成功则返回true。我们可以先将q改为指向单元C，然后再将p改为指向单元C的下一单元，最后再将C中的游标改为指向q原来所指的单元即可。这个游标的修改过程如图5所示。

b · 发表于 2004-5-29 04:18:55

。<BLOCKQUOTE><

align=center><img src="http://algorithm.myrice.com/datastructure/basic/list/images/img8.gif"></BLOCKQUOTE><

align=center>图5 两个链表之间的单元转移<

align=left> 图5中的实线和虚线分别表示单元转移前后的游标。当单元C存在时，函数move取值为true，并施行单元C的转移;当单元C不存在时，函数move取值为false。<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">function move(var p,q;integer):boolean;var temp:integer;begin if p=0 then return(false) e1se begin temp:=q; q:=p; p:=SPACE[p].next; SPACE[q].next:=temp; return(true); endend; </TD></TR></TABLE></CENTER></DIV> 要从表中删除位置p的元素，可以将L中位置p所指示的那个单元摘除，并将它插入表available的头一个位置备用。<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">procedrue Delete(p:TPosition;var L:TList);beginif p=O then move(L，available) else move(SPACE[p]^.next，available)end; </TD></TR></TABLE></CENTER></DIV> 与单链表中的情形类似，为要删除表L中的一个元素x，先要找到x在表L中的位置。这可以用下面的函数Locate来实现。在表L中找到第一个与x相同的元素时，Locate返回x所在单元的位置，否则返回表尾位置。<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">function Locate (x:TElement;L:TList):TPosition;Var p:TPosition;begin p:=L; if p=0 then error('List is empty.'); if SPACE[p].element=x then return(0); while SPACE[P].next<>0 do if SPACE[SPACE[P].next].element=x then return(p) else p:=SPACE[P].next; return(p);end; </TD></TR></TABLE></CENTER></DIV> 由于我们是用游标来模拟指针的，上述各运算的复杂性分析与单链表中的情形是类似的。另外，上述程序中都省略了检查错误的语句。

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

<H3 align=left>循环链表</H3><

left" align=left> 我们在用指针实现表时，表中最后一个元素所在单元的指针域(next)为空指针nil。如果将这个空指针改为指向表头单元的指针就使整个链表形成一个环。这种首尾相接的链表称为循环链表。在循环链表中，从任意一个单元出发可以找到表中其他单元。图6所示的是一个单链的循环链表或简称为单循环链表。

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

。
<DIV align=center>
<CENTER>
<TABLE border=0>

<TR>
<TD width="50%"><IMG src="http://algorithm.myrice.com/datastructure/basic/list/images/img9.gif"></TD>
<TD width="50%"><IMG src="http://algorithm.myrice.com/datastructure/basic/list/images/img10.gif"></TD></TR>
<TR>
<TD width="50%">
<

align=center>(a)非空表 </TD>
<TD width="50%">
<

align=center>(b)空表 </TD></TR></TABLE></CENTER></DIV>
<BLOCKQUOTE>
<

align=center>图6单循环链表</BLOCKQUOTE>
 在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。它们仅在循环终止条件上有所不同:前者是p或p^.next指向表头单元；后者是p或p^.next指向空(nil)。
 在单链表中我们用指向表头单元的指针表示一个表L，这样就可以在O(1)时间内找到表L中的第一个元素。然而要找到表L中最后一个元素就要花O(n)时间遍历整个链表。在单循环链表中，我们也可以用指向表头单元的指针表示一个表L。但是，如果我们用指向表尾的指针表示一个表L时，我们就可以在O(1)时间内找到表上中最后一个元素。同时通过表尾单元中指向表头单元的指针，我们也可以在O(1)时间内找到表L中的第一个元素。在许多情况下，用这种表示方法可以简化一些关于表的运算。例如要将图7(a)中两个表L1和L2合并成一个表时，只要修改两个指针值即可，运算时间为O(1)。合并后的表如图7(b)所示。
<BLOCKQUOTE>
<IMG src="http://algorithm.myrice.com/datastructure/basic/list/images/img11.gif">
图7 两个单循环链表的合并</BLOCKQUOTE>

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

<H3 align=left>双链表</H3><

left" align=left> 在单循环链表中，虽然从任一单元出发，可以找到其前驱单元，但需要O(n)时间。如果我们希望能快速确定表中任一元素的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指针，一个指向后继，另一个指向前驱，形成图8所示的双向链表或简称为双链表。<

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

align=center>图8 双链表 由于在双链表中可以直接确定一个单元的前驱单元和后继单元，我们可以用一种更自然的方式表示元素的位置，即用指向双链表中第i个单元而不是指向其前一个单元的指针来表示表的第i个位置。双链表的单元类型定义如下。<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">type celltype=record element:TElement; next，previous:celltype; end; TPosition=^celltype; </TD></TR></TABLE></CENTER></DIV> 和单链的循环表类似，双链表也可以有相应的循环表。我们用一个表头单元将双链表首尾相接，即将表头单元中的previous指针指向表尾，并将表尾单元的next指针指向表头单元，构成如图9所示的双向循环链表。<img src="http://algorithm.myrice.com/datastructure/basic/list/images/img13.gif">图9 双向循环链表 下面仅以双向循环链表为例给出三种基本运算的实现。(1)在双向循环链表L的位置p处插入一个新元素x的过程Insert可实现如下。<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">procedure Insert(x:TElement;p:TPosition;var L:TList);Var q:TPosition;begin new(q); q^.element:=x; q^.previous:=p^.previous; q^.next:=p; p^.previous^.next:=q; p^.previous:=q;end; </TD></TR></TABLE></CENTER></DIV>上述算法对链表指针的修改情况见图10。<img src="http://algorithm.myrice.com/datastructure/basic/list/images/img14.gif">图10 在双向循环链表中插入一个元素 算法Insert中没有检查位置p的合法性，因此在调用Insert之前应保证位置p的合法性。由于插入通常是在表的头尾两端进行的，所以容易检查位置p的合法性。(2)从双向循环链表L中删除位置p处的元素可实现如下:<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">procedure Delete(p:TPosition;var L:TList);begin if (p<>nil)and(p<>L) then begin p^.previous^.next:=p^.next; p^.next^.previous:=p^.previous; dispose(p^); end;end; </TD></TR></TABLE></CENTER></DIV>上述算法对链表指针的修改情况见图11。<img src="http://algorithm.myrice.com/datastructure/basic/list/images/img15.gif">图11 从双向循环链表中删除一个元素 与单链表中的删除算法类似，上述算法是在已知要删除元素在链表中的位置p时，将该位置所指的单元删去。若要从一个表中删除一个元素x但不知道它在表中的位置，则应先用定位函数Locate(x,L)找出要删除元素的位置，然后再用Delete删除之。(3)在双向循环链表中，定位函数Locate可实现如下。<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">function Locate(x:TElement;L:TList):TPosition;Var p:TPosition;begin p:=L^.next; while p<>L do if p^.element=x then return(p) else p:=p^.next; return(nil);end; </TD></TR></TABLE></CENTER></DIV> 算法Locate在最坏情况下需要的时间显然为O(n)，n为表L的长度。算法Insert和Delete需要O(1)时间。在双向循环链表中，其他表的运算容易实现，这里就不一一说明了。另外，我们也可以用游标来模拟指针，从而实现双向链表和双向循环链表

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

<H2>栈的定义</H2>
<

> 栈是一种特殊的<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter1.htm" target="_blank" >表</A>，这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。
<

>　
<H2>栈的数学性质</H2>
<

>假设一个栈S中的元素为an,an-1,..,a1，则称a1为栈底元素，an为栈顶元素。栈中的元素按a ,a2,..,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出(Last In First Out)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈。
<BLOCKQUOTE>
<IMG src="http://algorithm.myrice.com/datastructure/basic/stack/images/img1.gif">
图1 栈的后进先出示意图</BLOCKQUOTE>

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

<H2>ADT栈的操作</H2><

>作为一种抽象数据类型，常用的栈运算有:<DIV align=center><CENTER><TABLE 10pt" borderColor=#ffffff cellPadding=5 width="90%" border=1><TR><TD align=middle width="27%" bgColor=#e0e0e0>运算</TD><TD align=middle width="73%" bgColor=#e0e0e0>含义</TD></TR><TR><TD align=middle width="27%" bgColor=#e0e0e0>MakeNull(S)</TD><TD width="73%" bgColor=#e0e0e0>使S成为一个空栈。</TD></TR><TR><TD align=middle width="27%" bgColor=#e0e0e0>Top(S)</TD><TD width="73%" bgColor=#e0e0e0>这是一个函数，函数值为S中的栈顶元素。用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >表运算</A>可将Top(S)表示为Retrieve(First(S),S)。</TD></TR><TR><TD align=middle width="27%" bgColor=#e0e0e0>

op(S)</TD><TD width="73%" bgColor=#e0e0e0>从栈S中删除栈顶元素，简称为抛栈。这个运算等价于<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >表运算</A>的Delete (First(S),S)运算。</TD></TR><TR><TD align=middle width="27%" bgColor=#e0e0e0>

ush(x,S)</TD><TD width="73%" bgColor=#e0e0e0>在S的栈顶插入元素x，简称为将元素x入栈。用<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter2.htm" target="_blank" >表运算</A>可将 Push(x,S)表示为Insert(x,FIRST(S),S)。</TD></TR><TR><TD align=middle width="27%" bgColor=#e0e0e0>Empty(S)</TD><TD width="73%" bgColor=#e0e0e0>这是一个函数。当S为空栈时，函数值为true，否则函数值为false。</TD></TR></TABLE></CENTER></DIV>

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