《信息技术竞赛培训教程》由会员分享，可在线阅读，更多相关《信息技术竞赛培训教程（28页珍藏版）》请在金锄头文库上搜索。
1、信息技术竞赛培训教程目录第二部分 数据结构（一）栈（二）队列（三）链表（四）迭代与递推（五）递归（六）搜索与回溯（七）树与二叉树（八）排序算法（九）查找算法（十）图论基础知识l l 广度优先搜索l l 广度优先搜索第二部分 算法和数据结构（一）栈说到学习和掌握数据结构，很容易让人想到的就是其最本的数据结构模式：栈、队这一讲，我们就来谈谈“栈”。“栈”的应用很广泛，大家在PASCAL程序设计中，常遇的一种错误就是“栈”超界，那么，“栈”为何物呢？栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是
2、不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。一个栈可以用定长为的数组来表示，用一个栈指针TOP指向栈顶。若TOP0，表示栈空，TOP=N时栈满。进栈时TOP加。退栈时TOP减。当TOP0时为下溢。栈指针在运算中永远指向栈顶。1、进栈（PUSH）算法若TOP时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作）；置TOP=TOP+1（栈指针加，指向进栈地址）；S(TOP)=X，结束（X为新进栈的元素）；2、退栈（POP）算法若TOP0，则给
3、出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作)；X=S(SOP)，（退栈后的元素赋给X）；TOP=TOP-1，结束（栈指针减，指向栈顶）。进栈、出栈的Pascal实现过程程序：CONST n=100;TYPEstack=ARRAY1.n OF integer;PROCEDURE PUSH(VAR s:stack;VAR top,x:integer);入栈BEGINIF top=n THEN writeln(overflow) ELSE BEGINtop:=top+1;stop:=x;END;END;PROCEDURE POP(VAR s:stack;VAR y,top
4、:integer);出栈BEGINIF top=0 THEN writeln(underflow) ELSE BEGIN y:=stop;top:=top-1; ENDEND;对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的。对于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。堆栈的数组模拟十进制数N和其它d进制数的转换是实现计算的基本问题，解决方法很多，下面给出一中算法原理：N=(N div d)dN mod d （其中 div 为整除运算，mod为求余运算）。例如：(1348)10(25
5、04)8运算过程如下：NN div 8N mod 8134816841682102125202NN div 8N mod 894131、 1、 填空：(9413)10=( )8=( )16=( )22、下面的程序实现这个转换过程，请补充完整。数制转化程序【xoi00_07.pas】program xoi00_07;const size=100;var a:array1.size of integer; n,d,i,j:integer;begin writeln; write(Please enter a number(N) base 10:); readln(n); write(please
6、enter a number(d):); readln(d); i:=1; repeat ai:=n mod d; n:=n div d; inc(i); until n=0; for j:=i-1 downto 1 do write(aj:5);end.出站进站2、火车站列车调度示意图如下，假设调度站两侧的轨道为单向行驶轨道。1、 1、 如果进站的车厢序列为123，则可能的出战车厢序列是什么？2、 2、 如果进展进站的车厢序列为123456，问能否得到135426和435612的出站序列。栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈，下面以表达式计算为例
7、子加以说明。源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句X:4823; (式 11.1)其正确的计算结果应该是，但若在编译程序中简单地按自左向右扫描的原则进行计算，则为：X122324321这结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规则。通常采用运算符优先数法。一般表达式中会遇到操作数、运算符和语句结束符等，以算术运算符为例，对每种运算赋予一个优先数，如：运算符：优先数：（语句结束符“；”的优先数为零）在运算过程中，优先数高的运算符应先进行运算（但遇到括号时，应另作处理）。按这样的规定，对式
8、（11.1）自左向右进行运算时，其计算顺序就被唯一地确定下来了。计算顺序确定后，在对表达式进行编译时，一般设立两个栈，一个称为运算符栈（OPS），另一个称为操作数栈（OVS），以便分别存放表达式中的运算符和操作数。编译程序自左向右扫描表达式直至语句结束，其处理原则是：凡遇到操作数，一律进入操作数栈；当遇到运算符时，则将运算符的优先数与运算符栈中的栈顶元素的优先数相比较；若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在操作数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入操作数栈，然后继续比较该运算符与栈顶元素的优先数。例如式（11.1）中，当扫描到“”和“”时都要将运
9、算符入栈。接着扫描到“”号， 其优先数小于乘号所以乘号退栈，并执行，将结果再存入操作数栈。再将“”号的优先数与运算符栈的栈顶元素“”号的优先数相比较，两者相等，所以再将加号退栈，进行，结果为，再入栈，接着，由于运算栈已空，所以减号入栈。当扫描到“”时，操作数入栈。当扫描到“；”时，其优先数最低， 所以减号退栈并执行，结果为并入栈。因已扫描到语句结束符，所以表达式的求值结束，结果为。例题模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含、运算符，充许含括号），输出算术表达式的值。设输入的表达式串是合法的。分析:建立两个栈，一个是操作数栈（number），一个是运算符栈（symbol），
10、根据运算符的优先级对两个栈进行相应的操作。源程序program ex11_4;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,
11、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;begi
12、n write(String : ); readln(s); s := ( + s + ); i := 1; p := 0; while i = length(s) do begin while si = ( do 左括号处理 begin push; inc(i); end; j := i; repeat 取数入操作数栈 inc(i); until (si 9); t := copy(s, j, i - j); val(t, numberp, code); repeat if si = ) then 右括号处理 begin while symbolp ( do pop; dec(p); num
13、berp := numberp + 1; end else begin 根据标志函数值作运算符入栈或出栈运算处理 while can do pop; push; end; inc(i); until (i length(s) or (si - 1 ); end; write(Result=, number0); readln;end.练习题：1、读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。(句子末尾不一定用.结束) 如果含有其他的字符，则只要求输出错误信息及错误类型。含有大写字母 错误类型 error 1数字（0-9） 错误类型 error 2其他非法字符 错误类型 error 3如 输入： It is 1
