数据结构之定义

数据结构的定义

什么是数据结构?

可以抽象的理解为两类结构逻辑结构存储结构的总称,逻辑结构是面向问题的,存储结构(也叫物理结构)是面向计算机的

 存储结构

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

顺序存储结构

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

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

链式存储结构

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

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

逻辑结构

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

线性结构

特点:数据元素之间 存在一对一的前后次序关系,每个元素(节点)最多有一个前件(头指针),最多有一个后件(尾指针)。

常见的线性结构

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

非线性结构

  • 集合结构

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

  • 树形结构

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

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

  • 图形结构

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