分类

线性表、栈、队列、字符（串）、数据、广义表、树、二叉树、图

逻辑结构 分类-1

线性结构

• 概念:
  集合中的元素成线性排列

• 特点：

  1. 集合中必存在唯一一个“第一个元素”
  2. 集合中必存在唯一一个“最后一个元素”
  3. 集合中其他元素只能存在一个唯一的后继，并且只能存在一个唯一的前驱

• 常见
  线性表，栈，队列，串

非线性结构

• 概念：
  集合中的元素为非线性排列
• 特点：
  1. 一个结点元素可能由多个直接前驱和多个直接后继
• 常见：
  树结构，图结构

逻辑结构 分类-2

集合结构

确定性、唯一性、无序性。该结构的数据元素之间的关系是同属于一个集合，无其他关系

线性结构

线性结构是指元素之间存在“一对一”的线性关系的数据结构

树状结构

除了第一个元素以外，其他元素有且仅有一个直接前驱，但是可以有多个直接后继，元素之间存在一对多的关系

网状结构

每个元素可以有多个直接前驱和多个直接后继，元素之间存在多对多的关系

存储结构

顺序存储

• 概念：
  把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言的数组来描述的。
• 优缺点：
  • 优点：
  1. 节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑数组的情况），结点之间的逻辑关系没有占用额外的存储空间
  2. 索引查找效率高，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址
  • 缺点：
  1. 插入和删除操作需要移动元素，效率较低

链式存储

• 概念：
  数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。每一结点是由数据和指针域组成。元素之间的逻辑关系通过存储结点之间的链接关系反映出来
• 优缺点：
  • 优点：
  1. 比顺序存储结构的存储密度小（每个结点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多）
  2. 插入、删除灵活（不必移动结点，只要改变结点中的指针）
  • 缺点：
  1. 查找结点时链式存储要比顺序存储慢

索引存储

• 概念：
  除建立存储结点信息外，还建立附加的索引表来标识结点的地址

散列存储

• 概念:
  根据结点的关键字直接计算出该结点的存储地址，一种神奇的结构，查询和添加速度快。