数据结构和算法绪论

数据结构和算法绪论思维导图大纲学习

数据结构和算法绪论

• 1.1基本概念和术语
  • 数据元素：数据的基本单位
  • 数据项：数据的不可分割的最小单位
  • 数据对象：性质相同的数据元素的集合，数据的一个子集
  • 数据：数字、字符、声音、图形、图像等的总称
• 1.2什么是数据结构
  • 数据结构：带结构的数据元素的集合
  • 数据结构形式定义：二元组(D,S)
    • D:数据元素的有限集
    • S：D上关系的有限集
• 1.3数据结构的研究内容
  • 逻辑结构：数据元素之间的逻辑关系
    • 集合：元素仅属于同一集体，没有其他关系
    • 线性结构：存在一对一关系，序列相邻，必须关系
    • 树型结构：存在一对多关系，层次关系
    • 图状结构(网状结构)：任何两个结点都可以领接
  • 物理结构(存储结构)：是逻辑结构到存储器的一个映射
    • 顺序存储：借助元素在存储器的相对位置来表示数据元素之间的逻辑关系
    • 链式存储：通过附加指针字段来表示数据元素间的逻辑关系
• 1.4抽象数据类型的表示与实现
  • 1.4.1引用(c++)
    • 引用的概念：变量的别名
    • 引用的格式：类型 &引用名 = 已定义的变量名：
    • 引用的说明：
      • 不单独分配存储单元
      • 必须立即进行初始化
      • 可以不书写间接运算符“*”
      • 引用运算符&与地址操作符&不一样，引用操作符&仅在声明引用时使用
    • 引用作为函数参数：不需要再分配空间
  • 1.4.2数据类型
    • 定义：具有相同性质的计算机数据的集合及定义在这个数据集合上的一组操作的总称
    • 抽象数据类型：
      • 定义：基于一个逻辑类型的数据模型以及定义在该模型上的一组操作
      • 描述：三元组(D,S,P)
        • D–数据元素的有限集
        • S–D上关系的有限集
        • P–对D的基本操作集
      • 定义格式
        • ADT抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT抽象的数据类型名 基本操作的定义格式： 基本操作名(参数表) 初始条件：<初始条件描述> 操作结束：<操作结束描述>
• 1.5算法和算法分析
  • 1.5.1算法与数据结构的关系
    • 算法的重要特性
      • 有穷性
      • 确定性
      • 0至多个输入
      • 1至多个输出
      • 有效性(可行性)
    • 算法：为了求解问题而给出的指令序列 程序：算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解
  • 1.5.2算法的要求和效率
    • 要求：1.正确性 2.可读性 3.健壮性(容错性) 4.效率与低储存量需求
    • 效率：一个算法如果能在所要求的资源限制内将问题解决好，则称这个算法是有效率的
    • 算法性能的评价
      • 评价标准：算法所需的计算时间；算法所需的存储空间；算大的简单性
      • 度量算法执行时间的方法
        • 事后统计法
        • 事前分析估算法✔
  • 1.5.3时间复杂度
    • 频度：该语句重复执行的次数
    • 时间复杂度
      • 定义：一般情况下，算法中基本操作重复执行的时间是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))——大O记法。它表示随问题规模的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。
      • 结论：1.f(n)为对数函数，幂函数，或它们的乘积时，算大的运行时间可接受，称这些算法是有效算法；f(n)为指数函数，阶乘函数时，算大的运行时间不可接受，称这些算法是无效算法。2.随n的增大，增长速度各不相同，n足够大时：对数函数<幂函数<指数函数
    • 示例_时间复杂度示例
      • O(1) ： 算法的时间复杂度为常数阶，记作T(n)=O(1)，程序段的执行时间是一个与问题规模无关的常熟 O(n^2)，O(n)，O(log2n)…
      • 例：小兔子问题 解决思路：1.递归(低效)；2.循环(✔)
  • 1.5.4空间复杂度
    • 1.存储算法本身所占用的空间 2.算法的输入/输出数据占用的空间 3.算法在运行过程中临时占用的辅助空间
    • 原地工作：若辅助空间相对于输入数据量是常数，则称此算法是原地工作
    • 注：若所占空间量依赖于特定的输入，按最坏的情况来分析