第三章软件技术基础.ppt

程序是人们为了解决实际问题要求计算机执行的动作和操作；程序是一组计算机能操作的命令。 不要求的课后习题：一、填空题：1二、选择题：1、7、10补充习题：有改动一、填空题：1-20 栈的运算 栈的基本运算三种：入栈、退栈与读栈顶元素 入栈运算: 是指在栈顶位置插入一个新元素 退栈运算: 是指取出栈顶元素并赋给一个指定变量 读栈顶元素: 读栈顶元素是指将栈顶元素赋给一个指 定的变量. 3.3.3 栈和队列 队列的定义 队列: 是只能在一端进行插入运算、在另一端进行删除运算的线性表. 允许进行插入的一端称为队尾，允许进行删除的一端称为队首. 按照“后进后出”或“先进先出”的原则. 3.3.3 栈和队列 队列的顺序存储 用一维数组作为栈的顺序存储空间 队列的主要运算有：入队和退队运算 入队运算: 是指在在队尾插入一个新元素 退队运算: 是指取出队首元素并赋给一个指定的变量 3.3.3 栈和队列 树的定义 树是由n（n≥0）个结点组成的有限集合（记为T），其中： 如果n=0，它是一棵空树，这是树的特例； 如果n0，这n个结点中存在（有仅存在）以个结点作为树的根结点，简称根，其余结点可分为m（m0）个互不相交的有限集T1，T2，…，Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根的子树 3.3.4 树与二叉树 树是一种简单的非线性结构。在树的数据结构中，所有数据元素之间的关系具有明显的层次特性。如图所示。 举例说明树的数据结构 树的特点和术语 1. 在树结构中，每一个结点只有一个前驱，称为父结点，没有前驱的结点只有一个，称为树的根结点. 2. 在树结构中，每一个结点可以有多个后继，它们都称为该结点的子结点。没有后继的结点称为叶子结点. 3. 在树结构中，一个结点所拥有的后继个数称为该结点的度. 4. 树结构具有明显的层次关系，技术是一种层次结构。 5. 在树结构中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。 3.3.4 树与二叉树 二叉树的定义 二叉树是有限的结点集合，该集合由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成 二叉树的特点 二叉树具有以下两个特点： 1. 非空二叉树只有一个根结点； 2. 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 3.3.4 树与二叉树 二叉树遍历的定义 二叉树的遍历是指按照一定次序访问树中所有结点，并且每个结点仅被访问一次的过程。 二叉树的遍历种类 二叉树的遍历为三种： 前序遍历、中序遍历、后序遍历 3.3.4 树与二叉树 举例说明二叉树遍历 前序遍历二叉树的过程：① 访问根结点；② 前序遍历左子树；③ 前序遍历右子树。 注意：在遍历左右子树时仍然采用前序遍历的方法。 例如，图3.25（a）的二叉树的前序遍历序列为FCADEGB。 3.3.4 树与二叉树 举例说明二叉树遍历 中序遍历二叉树的过程：① 中序遍历左子树；② 访问根结点；③ 中序遍历右子树。 注意：在遍历左右子树时仍然采用中序遍历的方法。 例如，图3.25（a）的二叉树的中序遍历序列为ACDFEBG。 3.3.4 树与二叉树 举例说明二叉树遍历 后序遍历二叉树的过程：① 后序遍历左子树；② 后序遍历右子树；③ 访问根结点。 注意：在遍历左右子树时仍然采用后序遍历的方法。 例如，3.25（a）的二叉树的后序遍历序列为ADCBGEF。 3.3.4 树与二叉树 查找又称为检索，指在某种数据结构中找出满足 给定条件的元素。 查找 顺序查找 顺序查找：是指在线性表中查找指定的元素， 基本方法：从线性表的第一个元素开始，依次将 线性表中的元素与被查找元素进行比较，若相等则 表示查找成功；若线性表中所有的元素都与被查找 元素进行了比较但都不相等，则表示线性表中查找 失败。 3.3.5 查找和排序 二分法查找 二分法查找：又称折半查找，二分查找要求线性表 是有序表，即线性表中的元素按递增（或递减） 顺序排序。二分法是一种效率较高的查找方法。 二分法查找过程： ① 将x与线性表的中间项进行比较： ② 若中间项的值等于x，则说明查到，查找结束； ③ 若x小于中间项的值，则在线性表的前半部分 以①②相同的方法进行查找； ④ 若x大于中间项的值，则在线性表的后半部分 以①②相同的方法进布查找。 3.3.5 查找和排序 使用二分查找法查找出70 原始表 第一个子表 第二个子表 23 ? ? 34 ? ? 45 ? ? 46 ? ? 56 ? ? 57 ? ? 65 ? ? 66 ? ? 69 69 69 70