什么是数据结构?
可以抽象的理解为两类结构逻辑结构与存储结构的总称,逻辑结构是面向问题的,存储结构(也叫物理结构)是面向计算机的。
存储结构
主要分为顺序存储结构与链式存储结构。
顺序存储结构
概念:把逻辑上相邻的节点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构,通常顺序存储结构是借助于数组来描述的。
- 优点:节省空间,可以实现随机存取;
- 缺点:插入、删除时需要移动元素,效率低。
链式存储结构
概念:在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。
特点:元素在物理上可以不相邻,所以每个数据元素包括了一个数据域和一个指针域,数据域用来存放数据,而指针域用来指向其后继结点的位置。
逻辑结构
主要分为线性结构与非线性结构,用于描述数据之间的相互关系。
线性结构
特点:数据元素之间 存在一对一的前后次序关系,每个元素(节点)最多有一个前件(头指针),最多有一个后件(尾指针)。
常见的线性结构:
- 数组
- 链表
- 线性表
- 栈
- 队列
非线性结构
集合结构
特点:数据元素之间的关系是属于同一个集合
树形结构
特点:数据元素之间 存在一对多的关系
常见的如:二叉树、红黑树、B树、B+树
图形结构
特点:数据元素之间 存在多对多的关系