《简单的数据结构》由会员分享，可在线阅读，更多相关《简单的数据结构（24页珍藏版）》请在金锄头文库上搜索。
1、数据结构为了编写一个“好”的程序，必须分析待处理的对象特性以及各处理对象之 间存在的关系.这就需要学习“数据结构”。因此，简单地说来，数据结构是一门 研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操 作等等的学科。在信息学奥赛中需要学习线性表、树、图三种数据结构，在后面 我们将一一介绍.4.1 栈线性表是最常用且比较简单的一种数据结构，它是由有限个数据元素组成的 有序集合，每个数据元素有一个数据项或者含多个数据项.例如我们前面所学过 的数组是线性的数据结构.下面介绍的栈是一种线性表，但是对它的插人和删除等操作都限制在表的同 一端进行，即栈顶，而另一端则称为是栈底.打个形象地
2、比喻，用桶堆积物品， 先堆进来的压在底下，随后一件一件往上堆.取走时，只能从上面一件一件取. 堆和取都在顶部进行，底部一般是不动的 .所以，栈也称为后进先出表 （LIFO 表）.通常栈可以用顺序的方式存储，分配一块连续的存储区域来存放栈中的数据 项，即用定长为 N 的数组 S 来表示，并用一个变量 TOP 指向当前栈顶（如图 4-1-1）.若TOP=0,表示栈空，T0P=N时栈满.我们一般把插人操作称为进栈 （PUSH），此时TOP加1,删除操作则称为出栈（POP），则TOP减1.当TOP0时为下溢.图 41-1用 Pascal 语言来模拟栈的定义和操作.1. 栈的定义：CONSTN栈数据项的
3、上限TYPEstack=array1.nof stype； styp 代表数据项 类型VARs： stack ；2. 进栈过程 push（s， x， top） 往栈 S 中压人一个值为 X 的数据项procedurepush(vars：stack；x：stype；vartop：integer) ；BEGINif top=0 then write(underflow) elseBEGINtop:=top+；1stop:=x；END；END；3 .出栈函数pop(s, top)从栈中弹出一个数据项function pop(var s：stack；var top：integer) ：stype； B
4、EGINif top=0 then writeln(underflow)elseBEGINpop:=stop； top:=top-1；END；END；4. 读数函数 stop(s, top) 读栈顶的数据项function stop(var s:stack；t：integer) ：stype；BEGINif top=0 then writeln(stack empty)else stop:=stop；END栈的用途极为广泛,在源程序编译中表达式的计算、过程的嵌套调用和递归 调用等都要用到栈.从历届初赛可以看出,栈也是属于比较容易出题的知识点,选择题、解答题 等题型都有可能出现.例、设输入元素为
5、1、2、3、P和A,输人次序为123PA,如图4.1.2 所示,元素经过栈后到达输出序列,当所有元素均到达输出序列后,有哪些 序列可以作为高级语言的变量名？高级语言变量名的定义规则：以字母开头,字母与数字的组合.由于必须以字母开头，所以，第一个可能出现的字母是P,那么必 然要求123 已经先后入栈,这样便可得到以 P 开头的、并且123 按逆序排列的(即321) 、同时 A 位于 P 后任一位置的变量名序列.此外，还需要考虑以 A 开头的 可能情况，这只有一种情形：AP321.所以AP321，PA321，P3A21，P32A1，P321A可以作为高级语言的变量名.例、 中缀表达式 A-（B+C
6、/D）*E 的后缀形式是什么?中缀形式：即一般情况下的表达方式，将运算符写于参与运算的操作数的中 间，操作数依原序列排。后缀形式：式中不再引人括号，运算符放在参与运算的 操作数之后，操作数的排列依原序列，所有计算按运算符出现的顺序，严格地由 左而右进行（不再考虑运算符的优先规则）.所以利用椎栈的特性，可以得出本题 的答案是ABCD/+E* 。前缀表达式：同后缀表达式一样，不包含括号，运算符 放在两个运算对象的前，如一A*+B/CDE。【练习题】单项选择题1、设栈 S 的初始状态为空，元素 a，b，c，d，e，f 依次入栈，出栈顺序为 b，d，c，f，e， a 那么栈容量至少应该是（ ）。A6B
7、5C4D3E22、一个栈的入栈序列为a，b，c，d，e,则栈的不可能输出序列为（）A、 edcbaB、 decbaC、 dceab D、 abcde3 .设栈的输人序列为1、2、3、n输出序列为al、a2、an，若存在 1=k=n 使得 ak=n,贝U当 k=i=n 时，ai 为（）.A.n-i + 1B.n-（i-k）C不确定4、设栈的输入序列是（1、 2、 3、 4） ，则（）不可能是其出栈序列.A.1243B.2134C.1432D.4312E.32145、已知一算术表达式的中缀形式为A+B*CD/E,其后缀形式为ABC* + DE/，其前缀形式为（）.A.-A+B*C/DE B.-A+
8、B*CD/E C.-+*ABC/DE D.-+A*BC/DE6、设栈的输入序列是1、2、n,若输出序列的第一个元素是n,则第i个输出元素是（）A不确定B.n-i + lC.iD.n-i4.2 队列队列是限定在一端进行插入，另一端进行删除的特殊线性表。正像排队买东 西，排在前面人买完东西后离开队伍（删除） ，而后来的人总是排在队伍末尾（插 入）. 通常把队列的删除和插分别称为出队和人队. 允许出队的一端称为队首，允 许人队的一端称为队尾. 所有需要进队数据项，只能从队尾进人，队列中的数据 项只能从队首离去. 由于总是先入队的元素先出队（排队的人先买完东西） ，这种表也称为“先进先出（FIFO）表
9、.队列可以用数组Q1m来存储，数组的上界m即是队列所容许的最大容 量. 在队列的算中需设两个指针：head队首指针，指向实际队头元素的前一个位置tail队尾指针，指向实际队尾元素所在的位置队列中拥有的元素个数为：L=tailhead. 一般情况下，两个指针的初值 设为O,这时队列为空，没有元素.用 Pascal 语言模拟队列的定义和操作.1. 队列的定义CONSTm=队列元素的上限;TYPE队列的类型定义equeue=array1.mof qtype；VAR队列队首指针与队尾指针q： equeue ；head， tail：integer；2. 人队过程 add（q， x， taxi） 在队列的
10、尾端插入元素 xprocedure add（var q：equeue；x：qtype；vat tail：integer） ；BEGIN队列满上溢if tail：m then writeln（overflow）elseBEGINtail:=tail+l qtail:=x；ENDEND；3. 出队过程 del（q， y， head， tail） 取出 q 队列的队首元素 Yprocedure del（var q：equeue；Var y：qtype；Var head， tail： integer） ；BEGINif head=tail then writeln（underflow）歹口表空下溢el
11、seBEGIN head:=head+1; y:=qhead;ENDEND对循环队列的操作要区别于一般队列：(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) 队歹U空时，head=tail(5) 队
12、列满时， head=tail mod m+1为了区分队歹空和队歹满，改用“队尾指针追上队首指针这一特征作为队 歹满标志.这种处理方法的缺点是浪费队歹空间的一个存储单元.所以，我们重新得到另外两种循环队歹的运算.1.人队过程add(q, x, taxi)在队列的尾端插入元素xprocedure add(vat q： equeue；x： qtype；var tajl： integer) ；VARt： integer；BEGINt:=tail mod m+1；if t=head then writeln(full)elseBEGINtai： l=t；qtail:=；xEN；DEND；2 .出队过程d
13、el(q, y, head, tail)取出q队列的队首元素yproceduredel(varq： equeue；var y： qtype；varhead： integer) ；BEGINif head=tail writeIn(empty)elseBEGINhead:=head mod m+1； y:=qhead；EN；DEND；【练习题】单项选择题：1. 若用一个大小为 6 的数组来实现循环队列，且当一和 front 的值分别为 0 和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 多少？A.1 和 5B.2和 4C.4 和 2D.和 1e6、e5、e1，则栈
14、S的容量至少应该是（）.2 .设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5和e6依次通 过栈S，一个元素出栈后即进入队列Q,若6个元素出队的序列是e2、e4、e3、B.4A.6C.3D.23. 如右图所示的循环队列中元素数目是（）.其中tail=32 指向队尾元素， head=15 指向队首元素的前 一个空位置，队列空间 m=60.A.42B.16C.17D.414.3 树前两节学习的栈和队列属于线性结构.在这种结构中，数据元素的逻辑位置 之间呈线性关系，每一个数据元素通常只有一个前件 （除第一个元素外）和一个 后件（除最后一个元素外）.在实际生活中，可以用线性结构描述数据元
15、素之间逻 辑关系的问题是很广泛的，但也有很多问题不能依靠线性结构来解决，例如家谱、 行政组织机构等都是非线性的数据结构.其中树就是一种非线性的数据结构.一）树的递归定义为树（Tree）是n（n$0）个结点的有限集T，T为空时称 为空树，否则它满足 如下两个条件：（1 有且仅有一个特定的称为根（Root）的结点；（2 其余的结点可分为m（m$O）个互不相交的子集，T1, T2,，Tm,其中每个子集本身又是一棵树，并称其为根的子树（Subtree）.比如在现实生活中，有如下血统关系的家族可用树形图（ 图 4-3-1） 表示张源有三个孩子张明、张亮和张丽；张明有两个孩子张林和张维；张亮有 三个孩子张平和张群；张丽有两个孩子张晶和张磊.以上表示很像一棵倒画的树.其中“树根”是张源，树的“分支点是张明 张亮
