信息技术竞赛培训教程.doc

信息技术竞赛培训教程 目录 第二部分数据结构 (一)――栈(二)――队列(三)――链表(四)――迭代与递推(五)――递归(六)――搜索与回溯(七)――树与二叉树(八)――排序算法(九)――查找算法(十)――图论基础知识l        广度优先搜索l        广度优先搜索第二部分算法和数据结构 (一)――栈 说到学****和掌握数据结构,很容易让人想到的就是其最本的数据结构模式:栈、队这一讲,我们就来谈谈“栈”。“栈”的应用很广泛,大家在PASCAL程序设计中,常遇的一种错误就是“栈”超界,那么,“栈”为何物呢?栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品,先堆进来的压在底下,随后一件一件往堆。取走时,只能从上面一件一件取。堆和取都在顶部进行,底部一般是不动的。栈就是一种类似桶堆积物品的数据结构,进行删除和插入的一端称栈顶,另一堆称栈底。插入一般称为进栈(PUSH),删除则称为退栈(POP)。栈也称为后进先出表(LIFO表)。一个栈可以用定长为N的数组S来表示,用一个栈指针TOP指向栈顶。若TOP=0,表示栈空,TOP=N时栈满。进栈时TOP加1。退栈时TOP减1。当TOP<0时为下溢。栈指针在运算中永远指向栈顶。1、进栈(PUSH)算法①若TOP≥n时,则给出溢出信息,作出错处理(进栈前首先检查栈是否已满,满则溢出;不满则作②);②置TOP=TOP+1(栈指针加1,指向进栈地址);③S(TOP)=X,结束(X为新进栈的元素);2、退栈(POP)算法①若TOP≤0,则给出下溢信息,作出错处理(退栈前先检查是否已为空栈,空则下溢;不空则作②); ②X=S(SOP),(退栈后的元素赋给X); ③TOP=TOP-1,结束(栈指针减1,指向栈顶)。进栈、出栈的Pascal实现过程程序:CONSTn=100;TYPEstack=ARRAY[1..n]OFinteger;PROCEDUREPUSH(VARs:stack;VARtop,x:integer);{入栈}BEGINIFtop=nTHENwriteln('overflow')ELSEBEGINtop:=top+1;s[top]:=x;END;END;PROCEDUREPOP(VARs:stack;VARy,top:integer);{出栈}BEGINIFtop=0THENwriteln('underflow')ELSEBEGINy:=s[top];top:=top-1;ENDEND;对于出栈运算中的“下溢”,程序中仅给出了一个标志信息,而在实际应用中,下溢可用来作为控制程序转移的判断标志,是十分有用的。对于入栈运算中的“上溢”,则是一种致命的错误,将使程序无法继续运行,所以要设法避免。堆栈的数组模拟十进制数N和其它d进制数的转换是实现计算的基本问题,解决方法很多,下面给出一中算法原理:N=(Ndivd)×d+Nmodd(其中div为整除运算,mod为求余运算)。例如:(1348)10=(2504)8运算过程如下:NNdiv8Nmod8134816841682102125202NNdiv8Nmod89413            1、 填空:(9413)10=()8=()16=()22、下面的程序实现这个转换过程,请补充完整。'数制转化程序【】programxoi00_07;constsize=100;vara:array[1..size]ofinteger;n,d,i,j:integer;beginwriteln;write('Pleaseenteranumber(N)base10:');readln(n);write('pleaseenteranumber(d):');readln(d);i:=1;repeata[i]:=nmodd;n:=ndivd;inc(i);untiln=0;forj:=i-1downto1dowrite(a[j]:5);、火车站列车调度示意图如下,假设调度站两侧的轨道为单向行驶轨道。1、 如果进站的车厢序列为123,则可能的出战车厢序列是什么?2、 如果进展进站的车厢序列为123456,问能否得到135426和435612的出站序列。  栈的用途极为广泛,在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈,下面以表达式计算为例子加以说明。源程序编译中,若要把一个含有表达式的赋值语句翻译成正确求值的机器语言,首先应正确地解释表达式。例如,对赋值语句 X:=4+8×2-3;()其正确的计算结果应该是17,但若在编译程序中简单地按自左向右扫描的原则进行计算,则为:X=12×2-3=24-3=21这结果显然是错误的。因此,为了使编译程序能够正确地求值,必须事先规定求值的顺序和规则。通常