数据结构

数据结构思维导图（初学者的思想）

数据结构

• 逻辑结构
  • 从具体问题抽象出来的数学模型，与数据的存储无关独立于计算机
  • 线性结构
    • 有且仅有一个终端和始端，且所有元素只有一个前驱和一个后继是一个有序数据元素的集合
    • 线性表
      • 顺序表
        • 优点：模拟创建操作很简单，链表查询速度较快，时间复杂度O(logn)）缺点：维护十分麻烦，容易浪费空间
      • 链式表
        • 优点：十分灵活，不容易造成空间浪费，维护操作很简单缺点：模拟创建操作比较麻烦，对初学者不友好，查询时间为O(n)
      • 两者都能写出链表，队列，栈之类的结构
  • 非线性结构
    • 数据元素可以有多个前驱和后继
    • 集合结构
      • 多个元素在一个集合中
    • 树状结构
      • 元素只有一个前驱和多个后继
        • eg:二叉树等
    • 图状结构
      • 元素有多个前驱和多个后继（多向性）
        • eg:网络结构
• 物理结构（存储结构）
  • 数据元素及其关系在计算机的存储形式
  • 顺序映像
    • 借助元素在储存器中的相对位置来表示数据元素之间的关系
    • 顺序存储结构
      • 逻辑上相邻的数据元素在物理(实际)上也相邻的存储单元主要用于线性数据结构对于非线性数据结构也可以采取局部线性化的方法来实现顺序存储
  • 非顺序映象
    • 借助指针表示数据元素之间逻辑的关系
    • 链式存储结构
      • 每个元素增加至少一个的存放地址的指针域eg:单链表就有一个指针域指向后一个或者前一个元素eg:双链表就有两个指针域分别指向前一个和后一个元素优点：十分灵活，不容易造成空间浪费，维护操作很简单 缺点：模拟创建操作比较麻烦，对初学者不友好，查询时间为O(n)
    • 索引结构
      • 索引通过对表中标识按照从小到大排序构成索引表（每一个索引值必须唯一）优点：查询实践复杂度非常快O(1)缺点：创建时对空间和实践的浪费很大
    • 哈希/散列结构
      • 不用的数据通过哈希函数计算分配给元素相应的地址（哈希计算结果必须保持唯一性）优点：哈希平衡了数组和链表的优缺点（不过我也没学）缺点：要解决哈希冲突（对数据有一定的要求）