信息技术竞赛培训课件教程数据结构

《信息技术竞赛培训课件教程数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、信息技术竞赛培训教程 目录 第二部分数据结构 （一）――栈（二）――队列（三）――链表（四）――迭代与递推（五）――递归（六）――搜索与回溯（七）――树与二叉树（八）――排序算法（九）――查找算法（十）――图论基础知识ll        广度优先搜索ll        广度优先搜索第二部分算法和数据结构 （一）――栈 说到学习和掌握数据结构，很容易让人想到的就是其最本的数据结构模式：栈、队这一讲，我们就来谈谈“栈”。“栈”的应用很广泛，大家在PASCAL程序设计中，常遇的一种错误就是“栈”超界，那么，“栈”为何物呢？矚慫润厲钐瘗睞枥庑赖。栈是只能在某一端插入和删除

2、的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。　　栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO表）。　　一个栈可以用定长为Ｎ的数组Ｓ来表示，用一个栈指针TOP指向栈顶。若TOP＝0，表示栈空，TOP=N时栈满。进栈时TOP加１。退栈时TOP减１。当TOP<0时为下溢。栈指针在运算中永远指向栈顶。聞創沟燴鐺險爱氇谴净。1、进栈（PUSH）算法①若TOP≥ｎ时，则给出溢

3、出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；②置TOP=TOP+1（栈指针加１，指向进栈地址）；③S(TOP)=X，结束（X为新进栈的元素）；2、退栈（POP）算法①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈，空则下溢；不空则作②)；②X=S(SOP)，（退栈后的元素赋给X）；③TOP=TOP-1，结束（栈指针减１，指向栈顶）。　　进栈、出栈的Pascal实现过程程序：CONSTn=100;TYPE残骛楼諍锩瀨濟溆塹籟。stack=ARRAY[1..n]OFinteger;PROCEDUREPUSH(VARs:stac

4、k;VARtop,x:integer);{入栈}BEGINIFtop=nTHENwriteln('overflow')ELSEBEGINtop:=top+1;s[top]:=x;END;END;PROCEDUREPOP(VARs:stack;VARy,top:integer);{出栈}BEGIN酽锕极額閉镇桧猪訣锥。IFtop=0THENwriteln('underflow')ELSEBEGINy:=s[top];top:=top-1;ENDEND;对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的

5、。对于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。彈贸摄尔霁毙攬砖卤庑。堆栈的数组模拟十进制数N和其它d进制数的转换是实现计算的基本问题，解决方法很多，下面给出一中算法原理：N=(Ndivd)×d＋Nmodd（其中div为整除运算，mod为求余运算）。謀荞抟箧飆鐸怼类蒋薔。例如：(1348)10＝(2504)8运算过程如下：NNdiv8Nmod8134816841682102125202NNdiv8Nmod89413            1、1、 填空：(9413)10=()8=()16=()22、下面的程序实现这个转换过程，请补

6、充完整。'数制转化程序【xoi00_07.pas】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);end.

7、出站进站2、火车站列车调度示意图如下，假设调度站两侧的轨道为单向行驶轨道。1、1、 如果进站的车厢序列为123，则可能的出战车厢序列是什么？2、2、 如果进展进站的车厢序列为123456，问能否得到135426和435612的出站序列。  栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈，下面以表达式计算为例子加以说明。　　源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句X:＝4＋8×2－3;(式11.1)其正确的计算结果应该是１７，但若在编译程序中简单地