第一章（2）数据结构

这是一个关于第一章（2）数据结构的思维导图，①数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科。②数据结构是相互之间存在一种或多种特定关系的，具有相同构成的数据元素的有限集合。③通常记作DS=（D，R），其中D是数据元素的有限集合，R是D上关系的有限集合。

数据结构

• 概念
  • ①数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科。②数据结构是相互之间存在一种或多种特定关系的，具有相同构成的数据元素的有限集合。③通常记作DS=（D，R），其中D是数据元素的有限集合，R是D上关系的有限集合。
• 三要素
  • 逻辑结构
    • 概念
      • 数据元素之间的逻辑关系称为数据的逻辑结构。与数据的存储无关，独立于计算机。
    • 分类
      • 第一种分类法
        • 线性结构
          • 概念
            • 线性结构指有且仅有一个开始和一个终端节点，并且所有节点都最多只有一个直接前驱和一个直接后继。
          • 种类
            • 线性表
            • 栈
            • 队列
            • 字符串
            • 数组
        • 非线性结构
          • 概念
            • 一个结点可能有多个直接前驱和直接后继。
          • 种类
            • 树型结构
            • 网状结构
      • 第二种分类法
        • 数据结构四种基本类型／基本形态
          • 集合
            • 数据结构中的数据元素之间，除了同属于一个集合的关系外，无其他关系。
          • 线性结构
            • 数据结构中的数据元素之间存在一对一的关系。
          • 树形结构
            • 数据结构中的数据元素之间存在一对多的关系。
          • 网状结构／图形结构
            • 数据结构中的数据元素之间存在多对多的关系。
  • 物理结构／存储结构
    • 概念
      • 数据元素及其关系在计算机中的表示称为数据的存储结构。
    • 分类
      • 顺序存储
        • 概念
          • 用一组连续的存储单元依次存储数据元素。C语言用数组实现顺序存储结构。
        • 优点
          • ①可以实现随机存取②每个元素占用最少的存储空间。
        • 缺点
          • 只能使用相邻的一整块的存储单元，因此可能造成较多的外部碎片。
      • 链式存储
        • 概念
          • 用一组任意的存储单元存储数据元素。C语言用指针实现链式存储结构。
        • 优点
          • 不会产生碎片，充分利用了存储单元。
        • 缺点
          • ①不支持随机存取，只能顺序存储②每个元素因为存储指针而占用了额外的存储空间。
      • 索引存储
        • 概念
          • 根据节点索引号来确定结点存储地址。
        • 优点
          • 检索结点速度快
        • 缺点
          • 额外增加了索引表，会占用较多存储空间。同时，在增加删除结点时，需要更改索引表，也会占用更多时间。
      • 散列存储
        • 概念
          • 根据结点的关键字，计算出结点值，从而确定结点存储地址。
        • 优点
          • 检索、增加、删除结点操作很快
        • 缺点
          • 采用不好的散列函数可能造成节点存储单元的冲突，为了解决冲突可能会增加更多时间和空间。
  • 数据运算的定义和实现
    • 概念
      • 数据运算的定义和实现指对数据元素在逻辑结构上定义的可以施加的操作，以及这些操作在相应的存储结构上的实现。
    • 注意
      • 定义
        • 逻辑结构上
      • 实现
        • 物理结构上
    • 种类
      • 插入
        • 在指定位置前添加一个新结点。
      • 删除
        • 删除指定位置上的结点。
      • 更改
        • 修改某结点的值。
      • 查找
        • 寻找满足指定条件的结点及其位置。
      • 排序
        • 按指定的顺序给结点重新排列。
• 抽象数据类型
  • 抽象数据类型是一个数据结构以及定义在这个结构上的一组操作的总称，具体包括三部分：数据对象，数据对象上关系的集合和对数据对象的基本操作的集合。记作ADT=＜D，R，P＞，其中d代表数据，R代表关系，P代表操作。
• 实现
• 抽象