北大数据结构课节义7.ppt

第四章 栈和队列 4.1 栈 4.2 栈的顺序存储结构和操作实现 4.3 栈的链接存储结构和操作实现 4.4 栈的简单应用举例 4.5 算术表达式的计算 4.6 栈与递归 4.7 队列 4.1 栈 栈的定义 栈（stack）又称堆栈，是限定只在表尾进行插入或删除操作的线性表。栈 S = ( a1, a2, …，an ) 是按a1, a2, …，an次序进栈的，a1为栈底元素，an为栈顶元素。 在顺序队列中插入和删除，不需要比较和移动任何元素，只需修改队尾和队首指针，并向队尾写入元素或从队首取出元素 时间复杂度为：O(1) 若存储队列的数组的长度为N，则队列长度（即所含元素个数）为: (N+rear-front)%N 在链队中插入和删除，不需要比较和移动任何元素，只需修改个别相关指针和进行结点的动态分配或回收操作 时间复杂度为：O(1) 书面回答,请以纸面形式上交课代表,要求整洁清楚，时间期限:5月10日 [格式提头:学号/序号/姓名/第四章] 1、对于一个栈，如果输入项序列由A，B，C组成，给出全部可能和不可能的输出序列。 2、设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a6,a7,a5,a8,a4,a2,a1，则栈S的容量至少应该是多少？（即至少应该容纳多少个元素？） 3、设有算术表达式x+a*(y-b)-c/d，将其转换为后缀表达式。 4、有字符串序列为3*-y-a/y↑2,试利用栈给出将次序改变为3y-*ay2 ↑/-的操作步骤。（用X代表扫描字符串函数中顺序取一字符进栈的操作，S代表从栈中取出一个字符加入到新字符串尾的出栈操作。）例如，ABC变为BCA，则操作步骤为XXSXSS。 5、假设Q[0..10]是一个线性队列，初始状态为front=rear=0， 画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。（要求明确标出各元素在队列中的位置序号，头、尾指针） (a)d,e,b,g,h入队 (b)d,e出队 (c)i,j,k,l,m入队 (d)b出队 (e)n,o,p入队 第五章 树 5.1 树的概念 5.2 二叉树 5.3 二叉树的遍历 5.4 二叉树的其他运算 5.5 树的存储结构和运算 校长 5.1树的概念 5.1.1 树的定义 树Tree：是由n?0 个结点组成的有穷集合以及结点之间关系组成的集合构成的结构。 递归的数据结构 树的递归定义： （1）树由具有相同特性的数据元素（称为结点）组成，结点个数为0时，称为空树； （2）在一棵非空树中有且仅有一个根root结点，除根结点外，其余结点可分为m( m ≥0)个互不相交的子集，每个子集也是一棵树，称为子树SubTree。 tree = (K, R) K = {ki | 1≤i≤n, n≥0, ki ∈ElemType} R = {r} ElemType是具有相同特性的数据元素。 关系r满足： （1）有且仅有一个结点没有前驱，这个结点即树根； （2）除树根外，其余结点有且仅有一个前驱； （3）包括根结点在内的所有结点都可以有任意个(含0个)后继。 如上图： K = { A，B，C，D，E，F，G，H，I } r = {A,B, A,C, B,D, B,E, B,F, C,G, E,H, E,I} tree = (K, R) K = {ki | 1≤i≤n, n≥0, ki ∈ElemType} R = {r} 如上图： K = { A，B，C，D，E，F，G，H，I } r = {A,B, A,C, B,D, B,E, B,F, C,G, E,H, E,I} 换个说法 二叉链表：值域，左指针域，右指针域。 一 系 二 系 三 系 六 系 教 务 处 科 研 处 总 务 处 601 602 教 务 科 603 A B C D … … … … 张 三 李 四 王 五 … 例1 … 工 厂 (根目录) \ f1 f2 f3 fn d1 d2 dm … … … 例2 f11 f12 f1k d11 d12 … … … … 例3 例4 panda.cs.tsinghua.edu.cn au ee cn edu tsinghua cs panda buaa pku … … … … … … 一个数据元素 : 一个结点 A 数据元素(结点)之间的关系 : 分支 A B J I H G F E A C X B A的第1棵子树 A的第3棵子树