计算机软件技术之算法基础和数据结构基础.ppt

第14讲算法基础和数据结构基础 计算机基础科学系2007 08 第7章计算机软件技术 计算机基础科学系 主要教学内容 计算机基础科学系 学习目标 计算机基础科学系 重点与难点 算法的概念 特征与设计原则 算法的描述与常用算法的实现思想为本讲的重点 数据结构的基本知识为本讲的难点 计算机基础科学系 1 算法基础 计算机基础科学系 算法的特征 算法中的每个步骤都能在有限时间内完成 算法中的所有运算都是基本的 都可以通过基本运算有限次实现之 算法的每一种运算有确定的意义 执行何种动作无二义性 目的明确 1 1算法的概念 计算机基础科学系 1 1算法的概念 算法执行时间的增长率和f n 的增长率相同 记作 T n O f n a x x 1 b fori 1tondox x 1 c forj 1tondofork 1tondox x 1基本操作 加法操作时间复杂度 a O 1 b O n c O n2 算法的复杂度 计算机基础科学系 算法设计的原则 当输入的数据非法时 算法应当恰当地作出反映或进行相应处理 程序对于精心选择的 典型 苛刻且带有刁难性的几组输入数据能够得出满足要求的结果 计算机基础科学系 1 2算法的三种基本结构 分支结构包括简单分支与选择分支结构 选择分支结构可以根据设定的条件 判断应该选择哪一条分支来执行 顺序结构是指按程序语句行的编写顺序 逐条执行 循环结构是指按照一定的条件反复执行某一或某些处理步骤的结构 有两种循环语句 一种是先判断条件再执行循环体的结构称为当型循环结构 另一种是先执行循环体后判断条件的结构称为直到型循环结构 计算机基础科学系 1 2算法的三种基本结构 输入 输出框 处理框 条件框 起止框 计算机基础科学系 1 2算法的三种基本结构 图1算法c a b的流程图 计算机基础科学系 1 2算法的三种基本结构 图2简单分支 图3选择分支 图4把两个数由大到小输出的算法描述 例 计算机基础科学系 1 2算法的三种基本结构 图5当型循环 图6计算1 3 5 7 99的当型循环 例 计算机基础科学系 1 2算法的三种基本结构 图7直到型循环 图8计算1 3 5 7 99的直到型循环 例 计算机基础科学系 1 3常见算法介绍 i 1 a 1 23 a 4 8 23 j 4 a 1 与a 4 交换 i 2 a 2 78 a 3 45 78 j 3 a 4 23 45 k 4 a 2 与a 4 交换 i 4 a 4 78 a 5 45 78 j 5 a 4 与a 5 交换 i 5 a 5 78 a 6 56 78 j 6 a 3 与a 5 交换 i 3 a 3 45 a 5 32 45 j 5 a 3 与a 5 交换 选择排序 1 排序算法 计算机基础科学系 1 3常见算法介绍 第一步 从最后一个数开始与前面的数比较56 32 32 8 位置不变 8 45 两者交换位置 8 78 交换位置 8 23 交换位置 得出最小值为8 其它同理 冒泡排序 计算机基础科学系 1 3常见算法介绍 3 插入排序插入排序是最常用的排序技术之一 经常在扑克牌游戏中使用 游戏人员将每张拿到的牌插入到手中合适的位置 以便手中的牌以一定的顺序排列 计算机基础科学系 1 3常见算法介绍 2 查找算法 顺序查找 计算机基础科学系 1 3常见算法介绍 折半查找 计算机基础科学系 1 3常见算法介绍 3 递归算法 计算机基础科学系 2 数据结构基础 数据 数据元素 数据项 数据结构是在整个计算机科学与技术领域上被广泛使用的术语 它被用来反映一个数据的内部构成 即一个数据由哪些成分数据构成 以什么方式构成 呈什么结构 数据结构有逻辑结构和物理结构之分 逻辑上的数据结构反映成分数据之间的逻辑关系 而物理上的数据结构反映成分数据在计算机内部的存储安排 它是数据结构的实现形式 数据结构作为一门学科 研究的内容主要包括数据的逻辑结构 数据的物理存储结构及对数据的操作 或算法 三个方面 计算机基础科学系 2 1线性列表 线性表是一个含有n 0个结点 数据元素 的有限序列 其中的结点 有且仅有一个开始结点和一个终端结点 其他结点有且仅有一个前驱和一个后继结点 线性表可分为广义线性表与限制线性表 广义线性表 可以在任何位置插入与删除数据 限制线性表 只能在列表两端增加与删除数据 如堆栈 队列 计算机基础科学系 2 2堆栈 图10出栈操作 栈的操作有很多 基本操作有 入栈 出栈和空三种 图9入栈操作 堆栈是一种执行 后进先出 算法的数据结构 计算机基础科学系 2 3队列 队列只允许在数据表的前端进行删除操作 而在数据列表的后端进行插入操作 图11计算机队列 计算机基础科学系 2 3队列 队列的操作也很多 基本操作有 入列 出列和空三种 图12入列操作 图13出列操作 计算机基础科学系 2 4树 树的基本概念 二叉树 根结点 父结点 子结点 叶子结点 兄弟 结点的度 树的高 深 度 计算机基础科学系 2 4树 A 是根结点 同时是B C D结点的父结点或双亲结点B 是E F的父结点 E F是B的子结点或孩子结点J K L F G I 是叶子节点 B的子孙为E F J K B C D互为兄弟 结点A的层次 1结点L的层次 4 树的高度 4 计算机基础科学系 2 4树 树的种类有很多 如无序树 有序树 二叉树和完全二叉树等 1 二叉树的概念二叉树是每个结点最多有两个子树的有序树 这两个子树分别称为左子树和右子树 而每一棵子树又是二叉树 2 二叉树的特点每个结点至多只有二棵子树 二叉树的子树有左 右之分 且其次序不能颠倒 二叉树的五种基本形态 计算机基础科学系 2 4树 3 二叉树的性质性质1 二叉树的第i层上至多有2i 1 i 1 个结点 证明 根据二叉树的特点 结论是显然的 用归纳法证明 性质2 深度为H的二叉树中至多2H 1个结点 性质3 具有n个结点的二叉树的最小高度H为 log2n 1 计算机基础科学系 2 4树 1 前序遍历 NLR 2 中序遍历 LNR 3 后序遍历 LRN 访问根结点按照前序遍历顺序访问根结点的左子树按照前序遍历顺序访问根结点的右子树 按中序遍历顺序访问根结点的左子树访问根结点按中序遍历顺序访问根结点的右子树 按后序遍历顺序访问根结点的左子树按后序遍历顺序访问根结点的右子树访问根结点 4 二叉树的遍历 计算机基础科学系 2 4树 前序遍历 根左右 中序遍历 左根右 后序遍历 左右根 ABCDEF CBDAEF CDBFEA