什么是数据结构？

可以抽象的理解为两类结构逻辑结构与存储结构的总称，逻辑结构是面向问题的，存储结构（也叫物理结构）是面向计算机的。

　存储结构

主要分为顺序存储结构与链式存储结构。

顺序存储结构

概念：把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于数组来描述的。

  • 优点：节省空间，可以实现随机存取；
  • 缺点：插入、删除时需要移动元素，效率低。

链式存储结构

概念：在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

特点：元素在物理上可以不相邻，所以每个数据元素包括了一个数据域和一个指针域，数据域用来存放数据，而指针域用来指向其后继结点的位置。

逻辑结构

主要分为线性结构与非线性结构，用于描述数据之间的相互关系。

线性结构

特点：数据元素之间 存在一对一的前后次序关系，每个元素（节点）最多有一个前件（头指针），最多有一个后件（尾指针）。

常见的线性结构：

  • 数组
  • 链表
  • 线性表
  • 栈
  • 队列

非线性结构

  • 集合结构

    特点：数据元素之间的关系是属于同一个集合

  • 树形结构

    特点：数据元素之间 存在一对多的关系

    常见的如：二叉树、红黑树、B树、B+树

  • 图形结构

    特点：数据元素之间 存在多对多的关系