第一章：绪论

一篇关于数据结构思维导图，数据结构的基本概念、算法与算法评价等。希望对你有所帮助！

第一章：绪论

• 1.1数据结构的基本概念
  • 基本概念与术语
    • 1、数据
      • 所有能输入到计算机中并被计算机程序识别和处理的符号的集合
      • 所有的数据在计算机中都表现为二进制
    • 2、数据元素
      • 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理
    • 3、数据项
      • 数据元素由若干数据项组成，数据项是数据的不可分割的最小单位
    • 4、数据对象
      • 数据对象是具有相同性质的数据元素的集合
    • 5、数据类型
      • 数据类型是一个值的集合和定义在此集合上的一组操作的总程
      • 分类
        • 原子类型
          • 值不可再分割的数据类型
          • 例如：int
        • 结构类型
          • 值可以再分割的数据类型
          • 例如：结构体
        • 抽象数据类型（ADT）
          • D：数据对象
          • S：数据关系
          • P：基本操作
  • 数据结构的三要素
    • 1、数据的逻辑结构
      • 定义
        • 相互之间存在一种或多种特定关系的数据元素的集合
      • 分类
        • 线性结构
          • 一对一关系
          • 特点
            • 除第一个元素外，其他元素均存在唯一的一个“直接前驱”
            • 除最后一个元素外，其他元素均存在唯一的一个“直接后继”
        • 集合
          • 同属于一个集合
        • 树状结构
          • 一对多关系
          • 特点
            • 除根结点外，其余几点均存在唯一的一个“直接前驱”
            • 除叶子结点外，其余元素均存在若干“直接后继”
        • 网状结构 （图状结构）
          • 多对多关系
          • 特点
            • 对于任意一顶点均可存在若干“直接前驱”和“直接后继”
    • 2、数据的物理结构 （存储结构）
      • 定义
        • 存储结构是指数据结构在计算机中的表示（又称为映像），也称物理结构
      • 分类
        • 顺序存储结构
          • 定义
            • 将逻辑相邻的结点存储在物理位置上也相邻的存储单元中
            • 一般由数组表示
          • 优点
            • 可以实现随机存取
            • 每个元素占用最少的空间
          • 缺点
            • 只能使用相邻的一整块存储空间，容易产生碎片
          • 图示
        • 链式存储结构
          • 定义
            • 不要求逻辑上相邻的元素在物理位置上也相邻
            • 借助指针来表示元素之间的逻辑关系
          • 优点
            • 可以充分利用所有存储空间
          • 缺点
            • 只能顺序存取
            • 指针会占用额外的存储空间
          • 说明
            • 结点内存储单元地址：一定连续
            • 结点间存储单元地址：不一定连续
          • 图示
        • 索引存储结构
          • 定义
            • 在存储数据元素信息的同时，还建立索引表
            • 一般形式为：<关键字，地址>
          • 优点
            • 检索速度快
          • 缺点
            • 索引表占用额外的存储空间
            • 增、删数据时需要修改索引表
        • 散列存储结构
          • 定义
            • 根据关键字的大小直接计算出该数据元素的地址
            • 又称哈希存储
          • 优点
            • 检索、增加和删除节点的速度都很快
          • 缺点
            • 若散列函数不好，会出现存储冲突，解决冲突会增加时间和空间开销
        • 非顺序存储结构
    • 3、数据的运算
      • 定义
        • 施加在数据上的运算包括运算的定义和实现。
        • 运算的定义针对逻辑结构
        • 运算的实现针对物理结构
• 1.2算法与算法评价
  • 算法的基本概念
    • 沃思公式=数据结构+算法=程序
    • 1、算法的定义
      • 是对特定问题求解的步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作
    • 2、算法的描述方法
      • 自然语言
      • 流程图
      • 伪代码
      • 程序设计语言
    • 3、算法的五大特性
      • （1）有穷性
        • 在执行有穷步骤之后结束，且每一步都可在有穷时间内完成
        • 例如：死循环的程序代码
      • （2）确定性
        • 每一条指令必须有确切的含义，读者理解时不会产生二义性
        • 对于相同的输入只能得到相同的输出
      • （3）可行性
        • 算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现
      • （4）输入
        • 一个算法有零个或多个输入
      • （5）输出
        • 一个算法有一个或多个输出
    • 4、算法的评价
      • （1）正确性
        • 算法能正确地解决问题
        • “正确”的层次
          • a.程序不含语法错误
          • b.对于几组合法的输入数据能够产生满足要求的输出结果
          • c.对于非法的输入数据能够产生满足要求的输出结果
          • d.对于一切合法的输入数据能够产生满足要求的输出结果
      • （2）可读性
        • 有助于人对算法的理解
      • （3）健壮性
        • 当输入数据非法时，算法也能适当地做出反应或进行处理
      • （4）高效率与低存储量需求
        • 效率指的是算法执行的时间
        • 存储量需求指的是算法执行过程中所需要的最大存储空间
  • 算法的度量
    • 度量标准
      • 时间复杂度
      • 空间复杂度
    • 度量方法
      • 事后统计
        • 利用计算机计时器对程序上机运行时间进行计时
        • 缺点
          • （1）必须先运行依据算法编制的程序
          • （2）所得运行时间依赖于计算机的硬件、软件等环境因素
          • （3）程序运行的代价成本较高
      • 事前分析估算
        • 在计算机程序编制前，依据统计方法对算法进行估算
        • 运行所消耗时间取决于
          • （1）算法选用何种策略
          • （2）问题的规模
          • （3）书写程序的语言
          • （4）编译所产生的机器代码的质量
          • （5）机器执行指令的速度
        • 关注点
          • 撇开与计算机硬件、软件有关的因素，可以认为一个特定算法的“运行工作量”的大小，只依赖于问题的规模（n），或者说，它是关于问题规模的函数。
    • 时间复杂度
      • 计算方法
        • 语句频度
          • 最深层循环内的语句中原操作执行的次数
        • 函数表示
          • 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作T（n）=O（f(n)）(时间复杂度)
        • 关注点
          • 只看最高阶
          • 去掉常数项
          • 忽略系数
      • 常见O（n）的大小关系
      • 三种情况
        • 最好时间复杂度
        • 最坏时间复杂度
        • 平均时间复杂度
      • 影响因素
        • 数据的初始状态
        • 问题规模
    • 空间复杂度
      • 计算方法
        • 算法的空间复杂度记作S（n）=O（f(n)）
        • 关注点
          • 分析除输入和程序之外的额外空间