(36)--公共基础计算机二级Office高级应用.ppt

4.1.1算法与数据结构算法与数据结构一、算法（一、算法（algorithm）1、算法的基本概念、算法的基本概念n算法算法解题方案的准确而完整的描述解题方案的准确而完整的描述2、算法的特点、算法的特点n可行性可行性n确定性确定性n有穷性有穷性n拥有足够的情报（输入输入和输出输出）4.1.1算法与数据结构算法与数据结构3、算法的复杂度算法的复杂度n时间复杂度时间复杂度n时间复杂度时间复杂度指执行算法所需要的基本元算次数来度量n常用的度量方法：n最坏情况复杂性13 826381751344.1.1算法与数据结构算法与数据结构n空间复杂度空间复杂度n一般是指执行这个算法所需要的内存空间。n所需内存空间包括：n算法程序所占的空间、n输入的初始数据所占的存储空间n算法执行过程所需要的额外存储空间。4.1.1算法与数据结构算法与数据结构二、数据结构二、数据结构（Data Structure）1、数据结构分类、数据结构分类n数据的逻辑结构n数据的物理结构4.1.1算法与数据结构算法与数据结构2、数据的逻辑结构：、数据的逻辑结构：n指反映数据元素之间逻辑关系(前后件关系)的数据结构冬冬春春夏夏秋秋例例1：一年四季的逻辑结构：一年四季的逻辑结构 父亲父亲儿子儿子女儿女儿例2：家庭成员数据结构可表示成4.1.1算法与数据结构算法与数据结构3、数据的物理结构、数据的物理结构n数据的逻辑结构在计算机存储空间的存放形式称为数据的物理结构（也称为数据的存储结构）冬冬春春夏夏秋秋例例1：一年四季的逻辑结构：一年四季的逻辑结构 春夏秋冬301245春春冬夏秋3012454.1.1算法与数据结构算法与数据结构4、几个术语：n前件（或前驱）n后件（或后继）n根结点n叶子结点冬冬春春夏夏秋秋父亲父亲儿子儿子女儿女儿4.1.1算法与数据结构算法与数据结构5、数据结构分类n根据数据元素前后件关系的复杂程度分n线性结构线性结构n非线性结构非线性结构4.1.1算法与数据结构算法与数据结构6、线性结构与非线性结构：线性结构与非线性结构：n线性结构线性结构n有且只有一个根结点有且只有一个根结点n每一个结点最多有一个前件，也最多有一个后件。每一个结点最多有一个前件，也最多有一个后件。n注意：在线性结构中插入或删除任何一个结点后还应是线性注意：在线性结构中插入或删除任何一个结点后还应是线性的。的。n非线性结构：非线性结构：n线性以外的数据结构。线性以外的数据结构。D DA AB BC C 下课了。下课了。追求追求休息一会儿。休息一会儿。