信息竞赛复习资料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中时，函数值为0MakeEmpty(L)这是一个将L变为空表的方法。例1 假设两个线性表LA,LB分别代表两个集合A和B：求A=A U Bproc union(var la:linear_list;lb:linear_list）；beginn：=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）；begini：=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 endwhile i=length（la） do begin insert(lc,k+1,get(la，i)；k：=k+1;i:=i+1； endwhile jnil)and(pL） then begin p.previous.next:=p。next; p.next。previous：=p.previous; dispose(p）; end;end； 上述算法对链表指针的修改情况见图11。图11 从双向循环链表中删除一个元素5.链表的应用 例1：求 （AB)U(B-A)其中A，B代表两个集合（用静态链表）program jtlb；const maxsize=20；type jid=record data:integer； next:integer； end;jtlist=array0.。maxsize of jid；var a:jtlist;last，i，k，pre,x,m，n：integer；beginfor i:=0 to maxsize1 do ai.next：=i+1;amaxsize.next：=1;readln（m,n)；for i:=1 to m do begin read(x)；ai.data：=x； end;readln；last:=m;for i：=1 to n do begin read（x)； k:=1;pre：=0； while （ak。datax) and (kalast.next） do begin pre：=k;k:=ak.next; end; if k=alast.next then begin ak。data：=x;last:=k end else begin apre.next：=ak。next;if k=last then last:=pre end end；writeln；i:=0;repeat i:=ai.next; write（ai.data, ）;until i=last;end。例2 求p1（x)+p2(x) （两个多项式的和)program dxshi；type link=node;node=record coef:real; exp：integer; next：linkend；poly=link;var p， pa，pb：poly；procedure jl(var a:poly)；var p，q：poly; co：real;ex:integer;beginp：=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；beginp:=a。next;q：=b。next；pre：=a；while （pnil) and (qq。exp then begin pre:=p；p:=p.next end else if p.exp=q。exp then begin x:=p。coef+q。coef; if x0 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 qnil do begin writeln(p.coef:8：2，p.exp：5）; p:=p。next; endend.练习题: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 栈的存储与实现栈的数组实现：由于栈是一个特殊的表，我们可以用数组来实现栈。考虑到栈运算的特殊性，我们用一个数组elements1。.maxlength来表示一个栈时，将栈底固定在数组的底部,即elements1为最早入栈的元素，并让栈向数组上方（下标增大的方向)扩展。同时，我们用一个游标top来指示当前栈顶元素所在的单元。当top=0时，表示这个栈为一个空栈.在一般情况下，elements中的元素序列elementstop,elementstop1,。，elements1就构成了一个栈。这种结构如图2所示。 图 2利用上述结构,我们可以形式地定义栈类型TStack如下:TypeTStack=Record top:integer; element：array1.。maxlength of TElement； End;在这种表示法下，栈的5种基本运算可实现如下.procedure inistack（Var S:TStack)；beginS。top:=0;end;function Empty(var S：Stack）：Boolean;beginreturn(S。top=0);end；finction Top（var S:TStack)：TElement；beginif Empty(S） then Error(The stack is empty。） else return(S。elementS。top）;end；procedure Pop（var S：TStack)；beginif Empty(S） then Error（The stack is empty。） else dec(S.top)； S.top减1end；procedure Push（var S:TStack;x：TElement;）;beginif S.top=maxlength then Error（The stack is full。） else begin inc(S。top）; S.top增1 S。elementsS。top：=x; end;end；以上每种操作的复杂性为O(1)。在一些问题中,可能需要同时使用多个同类型的栈。为了使每个栈在算法运行过程中不会溢出， 要为每个栈顶置一个较大的栈空间.这样做往往造成空间的浪费.实际上，在算法运行的过程中，各个栈一般不会同时满，很可能有的满而有的空。因此，如果我们让多个栈共享同一个数组，动态地互相调剂，将会提高空间的利用率，并减少发生栈上溢的可能性。 假设我们让程序中的两个栈共享一个数组S1。.n.利用栈底位置不变的特性，我们可以将两个栈的栈底分别设在数组S的两端，然后各自向中间伸展，如图3所示.这两个S栈的栈顶初值分别为0和n+1.只有当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以余缺互补,因此每个栈实际可用的最大空间往往大于n/2。图33。3 栈的应用 1.表达式的求值 问题:能否设计算法，编制一个程序，让计算机扫描如下表达式，并将其值打印出来.# 3 * ( 4 + 8 ) / 2 -5 注：给表达式设置,标志扫描的开始和结束。提示算法：设两个栈，一个是操作数栈，用来存放操作数，如3、4、8等，另一个是运算符栈，用来存放运算符。首先将标志“#”进运算符栈的栈底。然后依次扫描,按照栈的后进先出原则进行:(1）遇到操作数，进操作数栈；（2）遇到运算符时，则需将此运算符的优先级与栈顶运算符的优先级比较，若若高于栈顶元素则进栈，继续扫描下一符号，否则，将运算符栈的栈顶元素退栈，形成一个操作码Q，同时操作数栈的栈顶元素两次退栈，形成两个操作数a、b，让计算机对操作数与操作码完成一次运算操作，即aQb，并将其运算结果存放在操作数栈中 模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含、运算符，充许含括号），输出算术表达式的值。设输入的表达式串是合法的。 附源程序：program exsj_1；const max=100；var number:array0。.max of integer; symbol：array1.max of char； s，t：string； i,p,j，code：integer;procedure push；算符入栈运算begin inc(p);symbolp:=si；end;procedure pop；运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算begin dec（p); case symbolp+1 of +:inc(numberp,numberp+1）； :dec（numberp，numberp+1）； *:numberp：=numberp*numberp+1; /：numberp：=numberp div numberp+1； end；end;function can:boolean；判断运算符的优先级别,建立标志函数begin can:=true; if (si in +，） and （symbolp() then exit； if (si in *，/） and （symbolp in ，/) then exit； can：=false；end;begin write(String ： ); readln(s）； s:=（+s+); i:=1； p：=0； while i9）; t：=copy(s，j，ij）； val（t,numberp，code）； repeat if si=） then 右括号处理begin while symbolp（ do pop; dec(p）; numberp：=numberp+1；end elsebegin 根据标志函数值作运算符入栈或出栈运算处理 while can do pop; push；end;inc(i）; until （ilength(s）) or （si1)； end; write(Result=,number0)； readln;end。2。背包问题 问题:假设有n件质量分配为w1，w2，。.。，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+.。+wik=T。若能,则背包问题有解，否则无解。算法思想：首先将n件物品排成一列，依次选取;若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满.若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈）,然后在未装入的物品中挑选，重复此过程，直至装满背包(有解）,或无物品可选（无解）为止。具体实现：设用数组weight1。N，stack1，N分别存放物品重量和已经装入背包（栈)的物品序号，MaxW表示背包的最大装载量.每进栈一个物品，就从MaxW中减去该物品的质量，设i为待选物品序号，若MaxW-weighti=0，则该物品可选；若MaxW-weighti n，则需退栈，若此时栈空，则说明无解。用Pascal实现的参考函数: Function knapstack(n，MaxW,weight）；begin top:=0; i：=1; i为待选物品序号 while (MaxW0） and （ i =0） and （ i = n ） thenbegin top:=top+1； stacktop：=i;MaxW=MaxW-weighti end；第i件物品装入背包 if MaxW=0 then return（true）else beginif (i=n) and （top0) then 背包内有不合适物品 begin 取栈顶物品，恢复MaxW的值 i：=stacktop; top:=top-1;MaxW=MaxW+weighti； if top0 then begini：=stacktop; top：=top1；MaxW=MaxW+weighti;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运算也是必要的。为了便于表示空队列，我们仍使用一个表头单元，将队头指针指向表头单元。当队头和队尾指针都指向表头单元时,表示队列为一个空队列。用指针实现队列时，单元类型及队列类型可说明如下:typequeueptr=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）: