数据结构-绪论

这是一篇关于数据结构与算法绪论的思维导图，详细介绍了相关概念和要点，主要内容包括：数据结构的基本概念，数据结构的3要素，算法。

数据结构与算法绪论

• 数据结构的基本概念
  • 数据
    • 能输入到计算机中并被计算机程序处理的符号的集合
  • 数据元素
    • 数据的基本单位，通常作为一个整体进行考虑和处理
      • 在有些情况下，数据元素也称为元素、记录、节点、顶点等
    • 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着：
      • 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
  • 数据项
    • 一个数据元素可以由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位
  • 数据 数据元素 数据项的关系
    • 数据>数据元素>数据项
      • 数据由数据元素组成，数据元素由数据项组成
  • 数据对象
    • 是性质相同的数据元素的集合，是数据的一个子集
  • 数据结构
    • 不同数据元素之间不是独立的，而是存在特定的关系，将这些关系称为结构
    • 数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合
    • 数据结构是带"结构"的数据元素的集合
  • 抽象数据类型
    • 由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称
    • 具体包括3个部分:数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合
• 数据结构的3要素
  • 逻辑结构
    • 定义
      • 是从具体问题中抽象出的数学模型，从逻辑关系上描述数据，与数据的存储无关
    • 分类
      • 线性结构
        • 数据元素之间存在一对一的关系
          • 普通线性表
            • 不能说 链表/顺序表 因为它们是存储结构
          • 受限线性表
            • 栈
            • 队列
          • 推广线性表
            • 数组
      • 非线性结构
        • 集合结构
          • 收据元素之间除了“属于同一集合”的关系外，别无其他关系
        • 树结构
          • 数据元素之间存在一对多的关系
        • 图结构或网状结构
          • 数据元素之间存在多对多的关系
  • 存储结构/物理结构
    • 定义
      • 数据对象在计算机中的存储表示称为数据的存储结构
    • 分类
      • (1)顺序存储
        • 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系
      • (2)链式存储
        • 无须占用一整块存储空间
        • 需要给每个节点附加指针字段，用于存放后继元素的存储地址
      • (3)索引存储
        • 在存储元素信息的同时，还建立附加的索引表
      • (4)散列存储
        • 根据元素的关键字直接计算出该元素的存储地址，又称哈希 (hash) 存储
  • 区分
  • 运算
• 算法
  • 特点
    • 有穷
    • 确定
    • 可行
    • 输出
      • 1个或多个
    • 输入
      • 0个或多个，前4个必须满足，输入不一定有
  • 算法复杂度
    • 时间
    • 空间
      • 分析除了输入和程序之外的额外空间