信息竞赛复习资料4--数据结构(NOIP).doc

(完整版)信息竞赛复习资料4--数据结构(NOIP)
第一章 什么是数据结构
1。1 基本概念和术语
 1.数据(data）：
  是对客观事物的符号的表示,是所有能输入到计算机中并被计算机程序处理的符号的总称.
 2.数据元素（data element）:
 是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个 数据项（data item）组成,数据  项是数据不可分割的最小单位。
3.数据结构(data structure）：
是相互之间存在一种或多种特定关系的数据元素的集合.数据结构是一个二元组,记为：
data_structure=(D,S)。其中D为数据元素的集合,S是D上关系的集合。
数据元素相互之间的关系称为结构（structure）。根据数据元素之间关系的不同特性,通常由下列四类基本结构：
（1)集合：数据元素间的关系是同属一个集合。(图1）
（2）线性结构：数据元素间存在一对一的关系。（图2）
(3）树形结构：结构中的元素间的关系是一对多的关系。（图3)
（4）图（网）状结构：结构中的元素间的关系是多对多的关系。（图4)

    图1                              图2

      图3                                           图4
1.2 数据的逻辑结构和物理结构
逻辑结构:数据元素之间存在的关系（逻辑关系）叫数据的逻辑结构。
物理结构:数据结构在计算机中的表示（映象）叫数据的物理结构。
一种逻辑结构可映象成不同的存储结构：顺序存储结构和非顺序存储结构（链式存储结构和散列结构）。

第二章 线性表
2.1 线性表的逻辑结构及基本运算
1。线性表简单的定义
n个数据元素的的有限序列其特点是除了表头和表尾外,表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。
2。线性表的基本运算
length(L）
返回表L的长度,即元素个数。
IsEmpty（L）
如果表L为空表(长度为0）则返回true，否则返回false.
next（L,p）
这是一个函数，函数值为表L中位置p的后继位置。如果p是L中结束元素的位置，则L.Next（p）=L.end。当L中没有位置p或p=L。end时，该运算无定义。
prev（L,p)
这是一个函数，函数值为表L中位置p的前驱位置。当L中没有位置p或p是L中开始元素的位置时，该运算无定义。
get（L，p)
这是一个函数，函数值为L中位置p处的元素。当p=L.end或L中没有位置p时,该运算无定义。
insert（L，x，p)
在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a1，a2，…，an，那么在执行insert(L，x，p）后,表L变为a1,a2,…ap-1，x，ap,…,an .若p为L.end，那么表L变为a1，a2,…,an,x 。若表L中没有位置p，则该运算无定义。
delete（L，p)
从表L中删除位置p处的元素.例如，当L为a1，a2,…，an时，执行delete(L,p)后，L变为a1，a2,…，ap-1，ap+1，…，an 。当L中没有位置p或p=L。end时，该运算无定义。
locate（L，x）
这是一个函数，函数值为元素x在L中的位置。若x在L中重复出现多次，则函数值为x第一次出现的位置。当x不在L中时，函数值为0
MakeEmpty(L)
这是一个将L变为空表的方法。
例1 假设两个线性表LA,LB分别代表两个集合A和B：求A=A U B
proc union(var la:linear_list;lb:linear_list）； 
begin
 n：=length（la）；
 for i:=1 to length(lb） do
   x：=get（lb,i)；
 k:=locate(la，x);
 if k=0 then begin insert（la,n+1,x）;n:=n+1 end；
end
例2 已知线性表la，lb中的数据元素按值非递减有序排列，现要求将la,lb归并为一个新的线性表lc且lc按值非递减.
proc merge(la,lb：linear_list;var lc:linear_list）；
begin
 i：=1;j:=1;k：=0;
 while （i<=length（la）） and (j〈=length（lb）) do
  if get（la,i）<=get（lb,j） then begin insert（lc,k+1，get(la,i））;k：=k+1;i：=i+1 end
                            else begin insert（lc,k+1，get（lb，j)）;k:=k+1；j：=j+1 end 
while i<=length（la） do
  begin insert(lc,k+1,get(la，i))；k：=k+1;i:=i+1； end
while j<=length(lb） do
  begin insert(lc，k+1，get(lb,j）)；k：=k+1;j：=j+1 end
end;
2。2 线性表的顺序存储结构
线性表的顺序存储即用一组地址连续的存储单元依次存储线性表中的元素。
设线性表中每个元素需占用r个存储单元则
   loc(ai+1 ）=loc（ai）+r
   loc（ai）=loc（a1）+(i-1）*r
这时可以这样定义线性表类型
type sqlist=record
   data：array［1。。maxlen] of datatype；
   last：0.。maxlen
end
在这种存储方式下，容易实现对表的遍历。要在表的尾部插入一个新元素，也很容易。但是要在表的中间位置插入一个新元素,就必须先将其后面的所有元素都后移一个单元，才能腾出新元素所需的位置。执行删除运算的情形类似。如果被删除的元素不是表中最后一个元素，则必须将它后面的所有元素前移一个位置，以填补由于删除所造成的空缺。这两种运算的时间复杂度均为O(n)n为表的长度.
2.3  线性表的链式存储结构
1。单链表
定义：实现表的另一种方法是用指针将存储表元素的那些单元依次串联在一起.这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时,不再需要移动元素来腾出空间或填补空缺.然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系,因而增加了额外的存储空间的开销.
为了将存储表元素的所有单元用指针串联起来，我们让每个单元包含一个元素域和一个指针域，其中的指针指向表中下一个元素所在的单元.例如,如果表是a1,a2，…,an ，那么含有元素ai的那个单元中的指针应指向含有元素ai+1的单元(i=1,2,…,n—1）。含有an的那个单元中的指针是空指针nil。此外，通常我们还为每一个表设置一个表头单元header，其中的指针指向开始元素中所在的单元，但表头单元header中不含任何元素。设置表头单元的目的是为了使表运算中的一些边界条件更容易处理。这一点我们在后面可以看到。如果我们愿意单独地处理诸如在表的第一个位置上进行插人与删除操作等边界情况，也可以简单地用一个指向表的第一个单元的指针来代替表头单元。
上述这种用指针来表示表的结构通常称为单链接表，或简称为单链表或链表。单链表的逻辑结构如图1所示。表示空表的单链表只有一个单元,即表头单元header,其中的指针是空指针nil。

图1 单链表示意图
为了便于实现表的各种运算,在单链表中位置变量的意义与用数组实现的表不同。在单链表中位置i是一个指针,它所指向的单元是元素ai—1所在的单元，而不是元素ai所在的单元(i=2,3,…,n）。位置1是指向表头单元header的指针。位置End(L）是指向单链表L中最后一个单元的指针。这样做的目的是为了避免在修改单链表指针时需要找一个元素的前驱元素的麻烦，因为在单链表中只设置指向后继元素的指针，而没有设置指向前驱元素的指针。
单链表结构的主要类型可形式地定义为：
type pointer=^nodetype
     nodetype=record
           data:datatype；
           next：pointer；
         end;
linklist=pointer；
基本运算的实现：
过程 Insert（x，p）
功能
在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a1,a2，…，an，那么在执行Insert（x,p)后,表L变为a1，a2，…ap-1，x，ap,…，an 。若p为End(L)，那么表L变为a1，a2，…,an，x 。若表L中没有位置p，则该运算无定义。
实现
Procedure Insert（x：datatype;p:pointer）;
var
   temp：integer;
begin
   new（temp);
   temp^。data:=x；
   temp^。next：= p^。next  
 p^。next：=temp;
end；
上述算法中，链表指针的修改情况见图2

图2(a）是执行Insert运算之前的情况。我们要在指针p所指的单元之后插入一个新元素x。图2（b)是执行Insert运算以后的结果，其中的虚线表示新的指针.
在上述Insert算法中，位置变量p指向单链表中一个合法位置，要插入的新元素x应紧接在p所指单元的后面。指针p的合法性应在执行Insert运算之前判定。往一个单链表中插入新元素通常在表头或表尾进行，因此p的合法性容易判定.Insert运算所需的时间显然为O（1）。
过程 Delete（p)
功能
从表L中删除位置p的下一元素。例如，当L为a1,a2,…,an时，执行Delete（p）后，L变为a1，a2，…，ap—1,ap+1，…，an 。当L中没有位置p或p=End(L)时,该运算无定义。
实现
Procedure Delete（p：pointer);
var
  q:integer
begin
    q:=p^。next；
      p^.next：=p^。next^。next；
   dispose(q）;
end;
说明
这个过程很简单，其指针的修改如图3所示。

若要从一个表中删除一个元素x，但不知道它在表中的位置，则应先用Locate(x,L)找出指示要删除的元素的位置，然后再用Delete删除该位置指示的元素。Delete过程所需的时间显然也为O(1)。
2.静态链表
静态链表：用游标指示数组单元地址的下标值，它属整数类型数组元素是记录类型，记录中包含一个表元素和一个作为游标的整数；具体说明如下:
type jid=record
data:datatype;
next:integer；
end；
var alist=array［0。。maxsize] of jid
游标就是.我们可以用游标来模拟指针, 对于一个表L，我们用一个整型变量Lhead（如Lhead=0）作为L的表头游标。。这样,我们就可以用游标来模拟指针，实现单链表中的各种运算。当i〉1时,表示第i个位置的位置变量pi的值是数组alist中存储表L的第i-1个元素next值，用p：=alist（p)。next后移.照此，我们虽然是用数组来存储表中的元素,但在作表的插人和删除运算时，不需要移动元素，只要修改游标，从而保持了用指针实现表的优点.因此，有时也将这种用游标实现的表称为静态链表。
3。循环链表
我们在用指针实现表时，表中最后一个元素所在单元的指针域(next）为空指针nil。如果将这个空指针改为指向表头单元的指针就使整个链表形成一个环。这种首尾相接的链表称为循环链表。在循环链表中,从任意一个单元出发可以找到表中其他单元.图6所示的是一个单链的循环链表或简称为单循环链表.
（a)非空表

(b)空表

图6单循环链表
在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。它们仅在循环终止条件上有所不同:前者是p或p^.next指向表头单元；后者是p或p^。next指向空（nil）。在单链表中我们用指向表头单元的指针表示一个表L，这样就可以在O(1)时间内找到表L中的第一个元素。然而要找到表L中最后一个元素就要花O(n)时间遍历整个链表。在单循环链表中,我们也可以用指向表头单元的指针表示一个表L。但是,如果我们用指向表尾的指针表示一个表L时，我们就可以在O(1）时间内找到表上中最后一个元素。同时通过表尾单元中指向表头单元的指针，我们也可以在O（1）时间内找到表L中的第一个元素。在许多情况下，用这种表示方法可以简化一些关于表的运算.
4。双链表
单循环链表中，虽然从任一单元出发，可以找到其前驱单元,但需要O(n)时间.如果我们希望能快速确定表中任一元素的前驱和后继元素所在的单元,可以在链表的每个单元中设置两个指针，一个指向后继，另一个指向前驱，形成图8所示的双向链表或简称为双链表。

图8 双链表
由于在双链表中可以直接确定一个单元的前驱单元和后继单元，我们可以用一种更自然的方式表示元素的位置,即用指向双链表中第i个单元而不是指向其前一个单元的指针来表示表的第i个位置。
双链表的单元类型定义如下。
type dupointer=^celltype
celltype=record
data：datatype;
next，previous:dupointer；
end；
dulist=dupointer；
和单链的循环表类似，双链表也可以有相应的循环表。我们用一个表头单元将双链表首尾相接,即将表头单元中的previous指针指向表尾,并将表尾单元的next指针指向表头单元，构成如图9所示的双向循环链表.

图9 双向循环链表
下面仅以双向循环链表为例给出三种基本运算的实现。
（1）在双向循环链表L的位置p处插入一个新元素x的过程Insert可实现如下。
procedure Insert（x：datatdata；p：pointer；var L：duList）；
Var
q：integer
begin
new（q)；
q^。data：=x；
q^.previous:=p^。previous；
q^。next:=p;
p^。previous^.next:=q;
p^。previous：=q；
end；

上述算法对链表指针的修改情况见图10。

图10 在双向循环链表中插入一个元素
算法Insert中没有检查位置p的合法性，因此在调用Insert之前应保证位置p的合法性。由于插入通常是在表的头尾两端进行的，所以容易检查位置p的合法性。
（2)从双向循环链表L中删除位置p处的元素可实现如下:
procedure Delete(p:integer；var L:duList）；
begin
if （p〈>nil)and(p<>L） then
begin
p^.previous^.next:=p^。next;
p^.next^。previous：=p^.previous;
dispose(p^）;
end;
end；
上述算法对链表指针的修改情况见图11。

图11 从双向循环链表中删除一个元素

5.链表的应用
  例1：求 （A—B)U(B-A)其中A，B代表两个集合（用静态链表）
program jtlb；
const maxsize=20；
type jid=record
       data:integer；
       next:integer；
      end;
jtlist=array[0.。maxsize] of jid；
var a:jtlist;
last，i，k，pre,x,m，n：integer；
begin
 for i:=0 to maxsize—1 do a[i］.next：=i+1;
 a[maxsize].next：=—1;
 readln（m,n)；
 for i:=1 to m do
  begin read(x)；a［i].data：=x； end;
 readln；
 last:=m;
 for i：=1 to n do
  begin
   read（x)；
   k:=1;pre：=0；
   while （a[k]。data〈>x) and (k<>a[last］.next） do
    begin
      pre：=k;k:=a［k].next;
    end;
   if k=a［last］.next then
     begin a［k]。data：=x;last:=k end
     else begin a［pre].next：=a［k]。next;if k=last then last:=pre end
  end；
 writeln；
 i:=0;
 repeat
  i:=a[i］.next;
  write（a［i］.data,' '）;
 until i=last;
end。
例2 求p1（x)+p2(x) （两个多项式的和)
program dxshi；
type link=^node;
 node=record
   coef:real;
   exp：integer;
   next：link
 end；
 poly=link;
var p， pa，pb：poly；
procedure jl(var a:poly)；
var p，q：poly;
    co：real;ex:integer;
begin
 p：=nil；
 repeat
  read（co，ex）；
  new(q);q^.coef：=co；q^.exp:=ex;q^.next：=p；p:=q；
 until （ex=—1） and （co=-1)；
 a:=p；readln；
end;
procedure add_poly（var a:poly;b：poly）；
var p，q,u，pre:poly；
    x:real；
begin
 p:=a^。next;q：=b^。next；
 pre：=a；
 while （p<〉nil) and (q<〉nil） do
   if p^.exp>q^。exp then begin pre:=p；p:=p^.next end
        else if p^.exp=q^。exp then begin
               x:=p^。coef+q^。coef;
               if x〈>0 then begin p^。coef:=x；pre：=p；end
                       else begin pre^。next：=p^。next; dispose(p） end；
               p:=pre^.next;u：=q；q:=q^。next;dispose(u）;
                end
               else begin
               u:=q^。next;q^.next：=p;pre^。next：=q；pre：=q；q：=u
               end;
 if q<〉nil then pre^。next：=q;
 dispose(b);
 end;
 begin
  jl(pa)；jl（pb）;
  add_poly(pa,pb);
  p:=pa;p：=p^。next；
  while  p〈>nil do
  begin
   writeln(p^.coef:8：2，p^.exp：5）;
   p:=p^。next;
  end
 end.
练习题:
1.约瑟夫问题:
有M个猴子围成一圈，每个有一个编号，编号从1到M。打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一个开始,每隔N个，数到的猴子出圈,最后剩下来的就是大王。
要求：从键盘输入M，N，编程计算哪一个编号的猴子成为大王.（程序）
2。求多项式的减与乘法。(程序）
3。http://ace。delos。com/usacogate(题1。1。2.1珍珠项链）（程序）

第三章 栈
3。1 栈的概念及运算
栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地,表尾称为栈底。不含任何元素的栈称为空栈。
栈的逻辑结构：假设一个栈S中的元素为an,an-1，。.,a1，则称a1为栈底元素，an为栈顶元 素。栈中的元素按a1 ,a2，..，an-1，an的次序进栈。在任何时候,出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出(Last In First Out）表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈。

              图1
栈的运算:为一种抽象数据类型，常用的栈运算有：
运算
含义
inistack（S)
使S成为一个空栈。
getTop(S)
这是一个函数，函数值为S中的栈顶元素.
Pop（S）
从栈S中删除栈顶元素，简称为抛栈。
Push(S，x)
在S的栈顶插入元素x，简称为将元素x入栈。
Empty(S）
这是一个函数.当S为空栈时，函数值为true，否则函数值为false。
3。2 栈的存储与实现
栈的数组实现：由于栈是一个特殊的表，我们可以用数组来实现栈。考虑到栈运算的特殊性，我们用一个数组elements[1。.maxlength］来表示一个栈时，将栈底固定在数组的底部,即elements［1]为最早入栈的元素，并让栈向数组上方（下标增大的方向)扩展。同时，我们用一个游标top来指示当前栈顶元素所在的单元。当top=0时，表示这个栈为一个空栈.在一般情况下，elements中的元素序列elements［top］,elements[top—1],。。，elements［1］就构成了一个栈。这种结构如图2所示。

        图 2
利用上述结构,我们可以形式地定义栈类型TStack如下:
Type
 TStack=Record
         top:integer;
         element：array[1.。maxlength] of TElement；
        End;
在这种表示法下，栈的5种基本运算可实现如下.
procedure inistack（Var S:TStack)；
begin
 S。top:=0;
end;
function Empty(var S：Stack）：Boolean;
begin
 return(S。top=0);
end；
finction Top（var S:TStack)：TElement；
begin
 if Empty(S） then Error(’The stack is empty。'）
             else return(S。element[S。top]）;
end；
procedure Pop（var S：TStack)；
begin
 if Empty(S） then Error（'The stack is empty。'）
             else dec(S.top)； ｛S.top减1｝
end；
procedure Push（var S:TStack;x：TElement;）;
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；
以上每种操作的复杂性为O(1)。
在一些问题中,可能需要同时使用多个同类型的栈。为了使每个栈在算法运行过程中不会溢出， 要为每个栈顶置一个较大的栈空间.这样做往往造成空间的浪费.实际上，在算法运行的过程中，各个栈一般不会同时满，很可能有的满而有的空。因此，如果我们让多个栈共享同一个数组，动态地互相调剂，将会提高空间的利用率，并减少发生栈上溢的可能性。 假设我们让程序中的两个栈共享一个数组S[1。.n].利用栈底位置不变的特性，我们可以将两个栈的栈底分别设在数组S的两端，然后各自向中间伸展，如图3所示.这两个S栈的栈顶初值分别为0和n+1.只有当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以余缺互补,因此每个栈实际可用的最大空间往往大于n/2。

图3
 3。3 栈的应用
1.表达式的求值
问题:能否设计算法，编制一个程序，让计算机扫描如下表达式，并将其值打印出来.
　　# 3 * ( 4 + 8 ) / 2 -5 ＃
　　注：给表达式设置＃,标志扫描的开始和结束。
　　提示算法：设两个栈，一个是操作数栈，用来存放操作数，如3、4、8等，另一个是运算符栈，用来存放运算符。
　　首先将标志“#”进运算符栈的栈底。
　　然后依次扫描,按照栈的后进先出原则进行:
　　(1）遇到操作数，进操作数栈；
　　（2）遇到运算符时，则需将此运算符的优先级与栈顶运算符的优先级比较，
　　若若高于栈顶元素则进栈，继续扫描下一符号，
　　否则，将运算符栈的栈顶元素退栈，形成一个操作码Q，同时操作数栈的栈顶元素两次退栈，形成两个操作数a、b，让计算机对操作数与操作码完成一次运算操作，即aQb，并将其运算结果存放在操作数栈中……
模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含＋、－、×、÷运算符，充许含括号），输出算术表达式的值。设输入的表达式串是合法的。
附源程序：
program exsj_1；
const
  max=100；
var
  number:array[0。.max] of integer;
  symbol：array［1..max] of char；
  s，t：string；
  i,p,j，code：integer;
procedure push；{算符入栈运算}
begin
  inc(p);symbol[p]:=s[i］；
end;

procedure pop；{运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算｝
begin
  dec（p);
  case symbol[p+1] of
   '+':inc(number［p],number[p+1］）；
   '—’:dec（number[p］，number[p+1]）；
   '*’:number[p]：=number[p］*number[p+1］;
   ’/’：number［p]：=number［p］ div number[p+1]；
  end；
end;

function can:boolean；｛判断运算符的优先级别,建立标志函数｝
begin
  can:=true;
  if (s[i] in ［’+'，’—’]） and （symbol[p]<〉'(') then exit；
  if (s[i] in ［'*’，’/']） and （symbol[p］ in [’＊'，'/'］) then exit；
  can：=false；
end;

begin
  write('String ： ’); readln(s）； s:='（'+s+’)’; i:=1； p：=0；
  while i<=length(s) do
    begin
      while s[i]=’（' do ｛左括号处理]
begin
  push; inc(i）;
end；
    j：=i;
    repeat {取数入操作数栈}
      inc(i）；
    until （s［i]〈'0') or (s[i]>’9’）;
    t：=copy(s，j，i—j）； val（t,number［p］，code）；
    repeat
      if s[i]='）' then {右括号处理｝ 
begin
  while symbol［p］<>’（' do pop;
  dec(p）; number［p］：=number［p+1］；
end
      else
begin {根据标志函数值作运算符入栈或出栈运算处理}
  while can do pop;
  push；
end;
inc(i）;
    until （i>length(s）) or （s［i—1]<〉')’)；
    end;
  write(’Result=',number[0])；
  readln;
end。
2。背包问题
问题:假设有n件质量分配为w1，w2，。.。，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+..。+wik=T。若能,则背包问题有解，否则无解。
　　算法思想：首先将n件物品排成一列，依次选取;若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满.
　　若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈）,然后在未装入的物品中挑选，重复此过程，直至装满背包(有解）,或无物品可选（无解）为止。
　　具体实现：设用数组weight[1。。N]，stack[1，N］分别存放物品重量和已经装入背包（栈)的物品序号，MaxW表示背包的最大装载量.每进栈一个物品，就从MaxW中减去该物品的质量，设i为待选物品序号，若MaxW-weight[i］〉=0，则该物品可选；若MaxW-weight[i] < 0，则该物品不可选，且若i>n，则需退栈，若此时栈空，则说明无解。
　　用Pascal实现的参考函数:
Function knapstack(n，MaxW,weight）；
begin
  top:=0; i：=1; {i为待选物品序号}
  while (MaxW>0） and （ i < = n ） do
    begin
      if （MaxW—weight[i]>=0） and  （ i < = n ） then
begin top:=top+1； stack[top]：=i;MaxW=MaxW-weight［i] end；
｛第i件物品装入背包}
      if MaxW=0 then return（true）
else begin
if (i=n) and （top〉0) then ｛背包内有不合适物品｝
  begin  {取栈顶物品，恢复MaxW的值}
    i：=stack[top］; top:=top-1;MaxW=MaxW+weight［i］；
    if top〉0 then begin
i：=stack［top］; top：=top—1；MaxW=MaxW+weight[i];
end；
  end；
i：=i+1；
     end;
    end;
  return(false) {问题无解}
end;
练习:完整完成背包问题
第四章 队列
4.1 队列的概念及运算
队列的定义：
队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头）进行，插入操作只在表尾（称为队尾)进行.队列的修改是按先进先出的原则进行的,所以队列又称为先进先出（First In First Out)表,简称FIFO表。
队列的数学性质:
假设队列为a1，a2，。。，an，那么a1就是队头元素，an为队尾元素.队列中的元素是按a1，a2，..，an的顺序进入的,退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,.。,an-1都离开队列之后,an才能退出队列。图1是队列的示意图。

              图1
队列的运算：
为一种抽象数据类型，常用的队列运算有：
运算
含义
Gethead(Q）
这是一个函数，函数值返回队列Q的队头元素。
Enqueue(Q,x)
将元素x插入队列Q的队尾。此运算也常简称为将元素x入队。
Dlqueue(Q)
将Q的队头元素删除，简称为出队.
Empty（Q)
这是一个函数，若Q是一个空队列，则函数值为true,否则为false。
Clear（Q)
使队列Q成为空队列。

4。2 队列的存储与实现
队列是一种特殊的表,因此凡是可以用来实现表的数据结构都可以用来实现队列.不过,队列的中的元素的个数通常不固定,因此常用循环数组和链表两种方法实现队列。
链队列：
用指针实现队列得到的实际上是一个单链表。由于入队在队尾进行，所以用一个指针来指示队尾可以使入队操作不必从头到尾检查整个表，从而提高运算的效率。另外，指向队头的指针对于Gethead和Dequeue运算也是必要的。为了便于表示空队列，我们仍使用一个表头单元，将队头指针指向表头单元。当队头和队尾指针都指向表头单元时,表示队列为一个空队列。
用指针实现队列时，单元类型及队列类型可说明如下:
type
queueptr=^queuenode;
queuenode=record
          data:elemtp；
          next:queueptr;
         end；
linkedquetp=record
           front,rear：queueptr；
          end；
其中front为队头指针，rear为队尾指针.图2是用指针表示队列的示意图。
图2
面我们来讨论队列的5种基本运算。
函数 Gethead（Q）
功能
这是一个函数，函数值返回队列Q的队头元素。
实现
Function Gethead(var Q:linkedquetp）: