数据结构
为了编写一个“好”的程序，必须分析待处理的对象特性以及各处理对象之间存在的关系.这就需要学习“数据结构”。因此，简单地说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。在信息学奥赛中需要学习线性表、树、图三种数据结构，在后面我们将一一介绍.
4.1 栈
线性表是最常用且比较简单的一种数据结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项.例如我们前面所学过的数组是线性的数据结构.
下面介绍的栈是一种线性表，但是对它的插人和删除等操作都限制在表的同一端进行，即栈顶，而另一端则称为是栈底.打个形象地比喻，用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆.取走时，只能从上面一件一件取.堆和取都在顶部进行，底部一般是不动的.所以，栈也称为后进先出表(LIFO表).
通常栈可以用顺序的方式存储，分配一块连续的存储区域来存放栈中的数据项，即用定长为N的数组S来表示，并用一个变量TOP指向当前栈顶(如图4-1-1).若TOP=0，表示栈空，T0P=N时栈满.我们一般把插人操作称为进栈(PUSH)，此时TOP加1，删除操作则称为出栈(POP)，则TOP减1.当TOP<0时为下溢.
用Pascal语言来模拟栈的定义和操作. 1.栈的定义： CONST
N=栈数据项的上限 TYPE
stack=array[1..n]of stype； {styp代表数据项类型} s：stack；
2.进栈过程push(s，x，top)——往栈S中压人一个值为X的数据项 procedure push(var s：stack；x：stype；var top：integer)； BEGIN
if top=0 then write(’underflow’) else
VAR
1
BEGIN
top:=top+1； s[top]:=x； END； END；
3.出栈函数pop(s，top)——从栈中弹出一个数据项
function pop(var s：stack；var top：integer)：stype； BEGIN
if top=0 then writeln(’underflow’) else BEGIN
pop:=s[top]； top:=top-1； END； END；
4.读数函数stop(s，top)——读栈顶的数据项
function stop(var s:stack；t：integer)：stype； BEGIN
if top=0 then writeln(’stack empty’) else stop:=s[top]； END
栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈.
从历届初赛可以看出，栈也是属于比较容易出题的知识点，选择题、解答题等题型都有可能出现.
例、设输入元素为1、2、3、P和A，输人次序为123PA，如图4.1.2 所示，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？
高级语言变量名的定义规则：以字母开头，字母与数字的组合. 由于必须以字母开头，所以，第一个可能出现的字母是P，那么必 然要求123已经先后入栈，这样便可得到以P开头的、并且123按逆序排列的(即321)、同时A位于P后任一位置的变量名序列.此外，还需要考虑以A开头的可能情况，这只有一种情形:AP321.所以AP321，PA321，P3A21，P32A1，P321A可以作为高级语言的变量名.
2
例、 中缀表达式A-(B+C/D)*E的后缀形式是什么?
中缀形式：即一般情况下的表达方式，将运算符写于参与运算的操作数的中间，操作数依原序列排。后缀形式：式中不再引人括号，运算符放在参与运算的操作数之后，操作数的排列依原序列，所有计算按运算符出现的顺序，严格地由左而右进行(不再考虑运算符的优先规则).所以利用椎栈的特性，可以得出本题的答案是ABCD/+E*－。前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前，如－A*+B/CDE。 【练习题】单项选择题
1、设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a那么栈容量至少应该是（ ）。
A．6 B．5 C．4 D．3 E．2 2、一个栈的入栈序列为a，b，c，d，e，则栈的不可能输出序列为（ ） A、edcba B、decba C、dceab D、abcde
3.设栈的输人序列为1、2、3、??、n，输出序列为al、a2、??、an，若存在1<=k<=n使得ak=n，则当k<=i<=n时，ai为( ). A.n-i+1 B.n-(i-k) C.不确定
4、设栈的输入序列是(1、2、3、4)，则( )不可能是其出栈序列. A.1243 B.2134 C.1432 D.4312 E.3214
5、已知一算术表达式的中缀形式为A+B*C—D/E，其后缀形式为ABC*+DE/一，其前缀形式为( ).
A.-A+B*C/DE B.-A+B*CD/E C.-+*ABC/DE D.-+A*BC/DE 6、设栈的输入序列是1、2、?、n，若输出序列的第一个元素是n，则第i个输出元素是( )
A.不确定 B.n-i+l C.i D.n-i
4.2 队列
队列是限定在一端进行插入，另一端进行删除的特殊线性表。正像排队买东西，排在前面人买完东西后离开队伍(删除)，而后来的人总是排在队伍末尾(插入).通常把队列的删除和插分别称为出队和人队.允许出队的一端称为队首，允许人队的一端称为队尾.所有需要进队数据项，只能从队尾进人，队列中的数据项只能从队首离去.由于总是先入队的元素先出队(排队的人先买完东西)，这种
3
表也称为“先进先出\表.
队列可以用数组Q[1?m]来存储，数组的上界m即是队列所容许的最大容量.在队列的算中需设两个指针：
head：队首指针，指向实际队头元素的前一个位置 tail：队尾指针，指向实际队尾元素所在的位置
队列中拥有的元素个数为：L=tail—head.一般情况下，两个指针的初值设为O，这时队列为空，没有元素.
用Pascal语言模拟队列的定义和操作. 1.队列的定义 CONST
m=队列元素的上限； TYPE
equeue=array[1..m]of qtype； ｛队列的类型定义｝ VAR
q：equeue； ｛队列｝
head，tail：integer； ｛队首指针与队尾指针｝ 2.人队过程add(q，x，taxi)——在队列的尾端插入元素x
procedure add(var q：equeue；x：qtype；vat tail：integer)； BEGIN
if tail：m then writeln(’overflow’) ｛队列满上溢｝ else BEGIN
tail:=tail+l； q[tail]:=x； END END；
3.出队过程del(q，y，head，tail)——取出q队列的队首元素Y procedure del(var q：equeue；Var y：qtype；Var head，tail：integer)； BEGIN
if head=tail then writeln(’underflow’) ｛列表空下溢｝ else
4
BEGIN
head:=head+1; y:=q[head];
END END
对循环队列的操作要区别于一般队列：
(1)初始时队列空，队首指针和队尾指针均指向存储空间的最后一个位置，即head=tail：m.
(2)入队运算时，尾指针进一，即
tail:=tail+l；if tail=m+1 then tail:=1 这两条语句可用一条语句替代：tail:=tail mod m+1 (3)出队运算时，首指针进一，即
head:=head+1；if head=m+1 then head:=1 这两条语句可用一条语句替代：head:=head mod m+1 (4)队列空时，head=tail
(5)队列满时，head=tail mod m+1
为了区分队列空和队列满，改用“队尾指针追上队首指针’’这一特征作为队列满标志.这种处理方法的缺点是浪费队列空间的一个存储单元. 所以，我们重新得到另外两种循环队列的运算.
1.人队过程add(q，x，taxi)——在队列的尾端插入元素x
procedure add(vat q：equeue；x：qtype；var tajl：integer)； VAR t：integer； BEGIN
t:=tail mod m+1；
if t=head then writeln(’full’) else BEGIN
tail：=t； q[tail]:=x； END； END；
2.出队过程del(q，y，head，tail)——取出q队列的队首元素y procedure del(var q：equeue；var y：qtype；var head：integer)；
5