大学计算机基础课件_第7章.ppt

  1. 1、本文档共75页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
*/77 栈的顺序存储 栈顺序存储结构是用一块连续存储区域存放栈中元素。连续区域的低地址一端作为栈底,栈底固定不变。 设用变量top表示栈顶位置,用n表示栈中最多能容纳元素的个数。 */77 入栈运算 a1 a2 a3 bottom top a4 S1:如果top=n,则栈已满,提示入栈失败(栈“上溢”错误),并结束入栈; S2:top+1 ? top; S3:将新元素放在当前栈顶位置(top)上。 */77 出栈运算 a3 top a1 a2 bottom S1:如果top=0,则栈为空,提示出栈失败(栈“下溢”错误),并结束出栈; S2:将当前栈顶(top)元素赋给一个变量; S3:top - 1 ? top。 */77 例如,容量为6的栈中已有3个元素,如图所示: 1 2 3 4 5 6 A C B bottom top X、Y两个元素先后入栈 X Y 元素Y出栈 */77 7.3.3 队 列 允许在一端进行插入、而在另一端进行删除的线性表,允许插入的一端称为队尾,允许删除的一端称为队头。 入队 退队 队尾 a b c 队头 */77 队列的基本运算 初始化队列 空队列判断 入队运算 出队运算 读队头元素 队列长度 创建一个空队列 判断队列是否为空 在队尾插入一个元素 在队头删除一个元素 读取队头元素赋给一个指定变量,不删除队头元素 求队列中元素个数 */77 队列顺序存储及其常用运算 队列的特点: 先进先出 入队和出队运算时队头和队尾位置要发生变化 队头 — front(指向第一个元素的前一个单元位置) 队尾 — rear(指向最后一个元素的位置) 队列中容纳元素 的个数为n */77 创建一个空队列,并令 front=rear=-1 front -1 2 0 1 rear 1.初始化队列 */77 2.入队运算 front rear -1 2 0 1 A B C S1:如果rear=n-1,则队列已满,入队失败(“上溢”错误),并结束入队 S2:rear+1 ?rear S3:将新元素放在当前队列位置(rear)上 */77 3.退队运算 front rear -1 2 0 1 A B C S1:如front=rear,则队列已空, 退队失败(“下溢”错误),并结束退队; S2:front+1?front; S3:取front所指元素 此时虽然队列有空位置,但也不能插入新结点。 假溢出现象 */77 7.4.2 二叉树 二叉树是另一种树形结构,每个结点最多只有两个后件(即最大度为2)。 特点: 非空二叉树有且只有一个根结点; 每个结点最多有两棵子树, 且有左右之分 A T X C Z Y B P */77 二叉树有五种基本形态 空二叉树 只有根结点 只有左子树 有左和右子树 只有右子树 */77 二叉树基本性质 性质一: 在二叉树的第i层上,最多有2i-1个结点(i≥1). 性质二: 深度为k的二叉树最多有2k-1个结点(k≥1). 性质三: 对于任意一棵二叉树,度为0的结点(即叶子结点)总比度为2的结点多一个. */77 满二叉树 如果一个深度为k的二叉树拥有2k-1个结点,则称它为满二叉树。 每一层的结点数都达到最大值, 叶子结点都在最下面的同一层上 完全二叉树 一棵深度为k的二叉树, 如果第一层到第k-1层是一棵满二叉树, 第k层上的结点数没有达到最大值2k-1, 但这些结点都满放在该层最左边, 则称此二叉树为完全二叉树。 如果某个结点没有左子树,则它一定没有右子树 */77 注:满二叉树是完全二叉树,但完全二叉树不一定是满二叉树。 A T X C E M B P 15个结点的满二叉树 S D N F R Y Q */77 完全二叉树性质: 12个结点的完全二叉树 A T X C R B P S E G F Y 性质一: 具有n个结点的完全二叉树的深度为 ?log2n」+1。其中,?log2n」 表示取log2n的整数部分。 */77 完全二叉树性质: 性质二: 在有n个结点的完全二叉树中, 将所有结点按从上到下, 从左到右的顺序用自然数1, 2, …, n进行编号, 则对于编号为k的结点有如下结论: ?k=1时, 该结点为根结点。 ?k1时, 该结点的父结点编号为int(k/2)。 ?2k=n时, 编号为k的结点的左子结点编号为2k, 否则无左子结点。 ?2k+1=n时, 编号为k的结点的右子结点编号为 2k+1, 否则无右子结点。 A T X C R B P S E Q F Y 1 2 3 4 5 6 7

文档评论(0)

00625 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档