《北大数据结构课讲义7.ppt》由会员分享，可在线阅读，更多相关《北大数据结构课讲义7.ppt（65页珍藏版）》请在金锄头文库上搜索。
1、第四章栈和队列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为栈顶元素 栈与递归递归可使问题及求解步骤的描述变得简洁而清晰 特别是对于复杂问题 用递归方法分析描述 比较自然 利于理解 递归包括递归步骤和终止出口 递归问题转化为非递归往往要用栈来实现 把在递归中用到的变量入栈出栈 如书上 习题4 4 之9 10 4 7队列队列是一种先进先
2、出 FIFO 线性表 只允许在其一端删除元素 即队头 front 只允许在其另一端插入元素 即队尾 rear 图4 10顺序队列的插入和删除操作 入队时需先修改入队指针 队尾指针 rear rear 1 QueueMaxSize 出队时需要修改队头指针front front 1 QueueMaxSize 初始时 队列为空 有front 0rear 0 测试队列为空的条件是front rear a d front指出实际队头元素所在位置的前一个位置 队列的静态数组一般是循环使用的 为了判别队列满和队列空的指针状况 令front指向队首元素的前一个位置 入队时需先修改入队指针 队尾指针 rear
3、rear 1 QueueMaxSize然后判断队列满的条件 rear 1 QueueMaxSize front最后将元素入队 出队时先判断队列空的条件front rear然后修改队头指针front front 1 QueueMaxSize最后将元素出队 在顺序队列中插入和删除 不需要比较和移动任何元素 只需修改队尾和队首指针 并向队尾写入元素或从队首取出元素时间复杂度为 O 1 若存储队列的数组的长度为N 则队列长度 即所含元素个数 为 N rear front N 2 队列的链式存储结构structLinkQueue LNode front LNode rear structLNode El
4、meTypedata LNode next 在链队中插入和删除 不需要比较和移动任何元素 只需修改个别相关指针和进行结点的动态分配或回收操作时间复杂度为 O 1 4 4 4队列运算的实现1 队列运算在顺序存储结构上的实现 1 初始化队列voidInitQueue Queue 2 将队列清空 并释放动态存储空间voidClearQueue Queue 3 检查队列是否为空intQueueEmpty Queue 5 向队列插入新元素 1voidEnQueue Queue 5 向队列插入新元素 2voidEnQueue queue 把原队列尾部内容后移MaxSize个位置if Q rear Q Ma
5、xSize 1 for inti 0 i q rear i Q queur i Q MaxSize Q queur i Q rear Q MaxSize Q MaxSize 2 Q MaxSize 求出队尾的下一个位置Q rear Q rear 1 Q MaxSize 把item的值赋给新的队尾位置Q queue Q rear item 6 从队列中删除元素ElemTypeOutQueue Queue 2 队列运算在链接存储结构上的实现 1 初始化链队voidInitQueue LinkQueue 3 判断链队是否为空intQueueEmpty LinkQueue 5 向链队中插入一个元素vo
6、idEnQueue LinkQueue 不妨与书上P78的算法9 ppt4 算法9 向单链表的末尾插入一个元素 相对照学习 思考与书上P137的算法2 ppt6 算法5 向链栈中插入一个元素 的不同 6 从队列中删除一个元素ElemTypeOutQueue LinkQueue 不妨与书上P79的算法10 ppt4 算法12 从单链表中删除表头元素 相对照学习 也可对照书上P137的算法3 ppt6 算法6 从链栈中删除一个元素 4 4 6队列应用简介第一 解决主机与外设之间速度不匹配的问题如 打印输出 设置一个打印数据缓冲区 用队列存储待输出的数据 解决主机与外设速度不匹配的问题 第二 解决多
7、用户引起的资源竞争问题如 多用户CPU资源竞争 操作系统通常按照每个请求在时间上的先后顺序 把它们排成一个队列 1 熟悉栈的含义 掌握基本概念 存储结构和运算的实现 2 熟悉队列的含义 掌握基本概念 存储结构和运算的实现 本章学习要点 本章习题 第173 177页 4 1 1 4 1 4请独立完成该题4个问题 4 2请独立完成该题 4 3课外思考该题 4 4 1 2 7能在书上程序的基础上编写程序实现 4 4 3 6 8 11有兴趣者课外思考 书面回答 请以纸面形式上交课代表 要求整洁清楚 时间期限 5月10日 格式提头 学号 序号 姓名 第四章 1 对于一个栈 如果输入项序列由A B C组成
8、 给出全部可能和不可能的输出序列 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
9、 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入队 课后作业第四章 约定 进栈X 出栈S 4个元素依次进栈 任何时候都可以出栈 请写出所有可能的出栈序列 XXXXSSSSXXXSXSSSXXXSSXSSXXXSSSXSXXSXXSSSXXSXSXSSXXSXSSXSXXSSXSXSXXSSXXSSXSXSXSXSXSXXXSSSXSXXSXSSX
10、SXXSSXSXSXSXXSS 方法提示 第五章树5 1树的概念5 2二叉树5 3二叉树的遍历5 4二叉树的其他运算5 5树的存储结构和运算 退出 校长 一系 二系 三系 六系 教务处 科研处 总务处 601 602 教务科 603 A B C D 例1 工厂 例3 例4 一个数据元素 一个结点 A 数据元素 结点 之间的关系 分支 5 1树的概念5 1 1树的定义树Tree 是由n 0个结点组成的有穷集合以及结点之间关系组成的集合构成的结构 递归的数据结构树的递归定义 1 树由具有相同特性的数据元素 称为结点 组成 结点个数为0时 称为空树 2 在一棵非空树中有且仅有一个根root结点 除根
11、结点外 其余结点可分为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 1 有且仅有一个结点没有前驱结点 该结点为树的根结点 2 除了根结点外 每个结点有且仅有一个直接前驱结点 3 包括根结点在内 每个结点可以有多个后继结点 5 1 2树的表示树
12、有五种表示方式 1 树形表示 2 二元组表示 3 集合图表示 4 凹入表表示 5 广义表表示 1 树形表示法 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 2 二元组表示法 1 结点的度 2 树的度 3 叶结点 4 分支结点 5 层次的定义 该结点拥有的子树的数目 树中结点度的最大值 度为0的结点 度非0的结点 根结点为第一层 若某结点在第i层 则其孩子结点 若存在 为第i 1层 7 树林 森林 m 0棵不相交的树组成的树的集合 8 树的有序性 6 树的深度 树中结点所处的最大层次数 若树中结点的子树的相对位
13、置不能随意改变 则称该树为有序树 否则称该树为无序树 5 1 4树的性质性质1树中结点个数等于所有结点的度数加1 性质2度为k的树中第i层上至多有ki 1个结点 i 1 性质3深度为h的k叉树中至多有 kh 1 k 1 结点 满k叉树 结点个数等于 kh 1 k 1 的k叉树 性质4具有n个结点的k叉树的最小深度为 logk n k 1 1 5 2二叉树5 2 1二叉树的定义二叉树为度为2的有序树 递归定义 或者是一棵空树 或者是一棵由根结点和两棵互不相交的左 右子树组成的非空树 左 右子树同样也是二叉树 左孩子leftchild 左子树的根结点 右孩子rightchild 右子树的根结点 二
14、叉树的基本形态 空 a 空二叉树 b 仅有一个根结点的二叉树 c 右子树为空的二叉树 d 左右子树均非空的二叉树 e 左子树为空的二叉树 两种特殊形态的二叉树 1 一棵非空二叉树的第i层最多有2i 1个结点 i 1 证明 采用归纳法 1 当i 1时 结论显然正确 非空二叉树的第1层有且仅有一个结点 即树的根结点 2 假设对于第j层 1 j i 1 结论也正确 即第j层最多有2j 1个结点 3 有定义可知 二叉树中每个结点最多只能有两个孩子结点 若第i 1层的每个结点都有两棵非空子树 则第i层的结点数目达到最大 而第i 1层最多有2i 2个结点已由假设证明 于是 应有2 2i 2 2i 1 证毕
15、 2 深度为h的非空二叉树最多有2h 1个结点 证明 由性质1可知 若深度为h的二叉树的每一层的结点数目都达到各自所在层的最大值 则二叉树的结点总数一定达到最大 即有20 21 22 2i 1 2h 1 2h 1 证毕 3 若非空二叉树有n0个叶结点 有n2个度为2的结点 则n0 n2 1 证明 设该二叉树有n1个度为1的结点 结点总数为n 有n n0 n1 n2 1 设二叉树的分支数目为B 有B n 1 2 这些分支来自度于为1的结点与度度为2结点 即B n1 2n2 3 联列关系 1 2 与 3 可得到n0 n2 1 证毕 4 具有n个结点的完全二叉树的深度h log2n 1 证明 略 推
16、论 n0 n2 2n3 3n4 m 1 nm 1 5 若对具有n个结点的完全二叉树按照层次从上到下 每层从左到右的顺序进行编号 则编号为i的结点具有以下性质 1 若编号为i的结点有左孩子 则左孩子结点的编号为2i 若编号为i的结点有右孩子 则右孩子结点的编号为2i 1 2 除树根结点外 若一个结点的标号为i 则它的双亲结点的编号为i 2 也就是说 当i为偶数时 其双亲结点的编号为i 2 它是双亲结点的左孩子 当i为奇数时 其双亲结点的编号为 i 1 2 它是双亲结点的右孩子 3 若i n 2 即2i n 则编号为i的结点为分支结点 否则为叶子结点 4 若n为奇数 则每个分支结点都既有左孩子 又有右孩子 若n为偶数 则编号最大的分支结点 编号为n 2 只有左孩子 没有右孩子 其余分支结点左 右孩子都有 换个说法 5 若对具有n个结点的完全二叉树按照层次从上到下 每层从左到右的顺序进行编号 则编号为i的结点具有以下性质 1 当i 1 则编号为i的结点为二叉树的根结点 若i 1 则编号为i的结点的双亲结点的编号为 i 2 2 若2i n 则编号为i的结点无左子树 若2i n 则编号为i的结点
