数据结构 第一节

这是一篇关于数据结构第一节的思维导图，主要内容有数据、数据元素(节点、记录)、数据项(域)、数据对象、数据结构、抽象数据类型(ADT)。

数据结构第一节

• 基础知识
  • 数据
    • 能够输入计算机中描述客观世界的符号：图像、文本、声音、符号等
  • 数据元素(节点、记录)
    • 数据的基本单位，如表的某一行
  • 数据项(域)
    • 有独立意义的数据最小单位，若干数据项构成数据元素，
  • 数据对象
    • 相同特性的数据元素的集合，是数据的子集
  • 数据结构
    • 相互之间存在一种或多种特定关系(结构)的数据元素的集合。研究的问题是把带关系的数据存在计算机中，并进行相关操作。
    • 逻辑结构
      • 集合(鸡圈和鸡圈内的鸡)
      • 线性结构
        • 线性表
          • 由n个相同类型的数据元素构成的有限序列，是最基本和最常用的一种线性结构。
          • 前驱、后继
          • 顺序、链式2种存储方式
        • 队列
        • 栈
        • 数组
        • 广义表
        • 一对一
      • 树形结构
        • 二叉树
        • 满二叉树
        • 树
        • 一对多
      • 图形结构
        • 多对多
      • 数据元素之间抽象的关系
        • 独立于计算机，与存储无关，从具体问题抽象出的数学模型
    • 存储结构
      • 数据元素及关系在计算机中的存储方式
        • A和B是表亲关系(逻辑)，教室中的位置是存储关系，存储关系改变不影响逻辑关系
      • 顺序存储
        • 逻辑上相邻的元素存储(使用一段连续的空间)位置也相邻。插入删除需要移动大量元素 
      • 链式存储(铁链)
        • 逻辑上相邻在存储上不一定相邻，包括数据域和指针域 
        • 单链表
        • 双链表
        • 循环链表
        • 双向链表
        • 双向循环链表
      • 散列存储(哈希存储)
        • 由节点的关键码值决定节点存储位置，使用散列函数  
      • 索引存储
        • 除建立存储节点信息外，建立附加的索引表来标识节点位置，索引表有若干索引项。  索引表分为稠密索引(每个节点在索引表中都有索引项)和稀疏索引(一组节点在索引表中只对应一个索引项)。 索引项的一般形式为关键字、地址。
        • 倒排索引
          • 在搜索引擎中，使用属性反搜记录。带有倒排索引的文件称为倒排索引文件(倒排文件)。
    • 运算
      • 初始化、取值、增删改查
  • 抽象数据类型(ADT)
    • 将数据对象、数据对象的关系、数据对象的基本操作封装在一起。 实现数据封装和信息隐藏，分离实现和使用。
    • 三元组ADT=（D，S，P）表示法
      • ①D：数据对象 S：数据对象关系 P：D上的操作集 ②ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT 抽象数据类型名
• 算法复杂度
  • 特点
    • 有穷性
    • 确定性
    • 可行性
    • 输入和输出
  • ”好“算法
    • 正确性
    • 易读性
    • 健壮性
    • 高效性
      • 时间复杂度
        • 常数阶O(1)
        • 多项式阶：O(n)、O(n²)、O(n³)
        • 指数阶：O(2^n)、O(n!)、O(n^n)
        • 对数阶：O(logn)、O(nlogn)
        • O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2^n)<O(n!)<O(n^n)
    • 低存储性
      • 空间复杂度
        • 递归算法的空间复杂度要计算递归使用的栈空间
        • 计算辅助空间