逻辑结构 & 物理结构

一般从两个角度对数据进行描述，一个是逻辑结构，一个是物理结构

逻辑结构：描述的是数据与数据之间的逻辑关系
物理结构：描述的是数据在内存中存储的形式

逻辑结构

数据结构

• 线性结构：数据之间的关系是一对一的，所有符合一对一的都是线性结构

数组、链表 是线性结构
字符串 是 特殊线性结构，存储内容只能是字符串
队列、栈 是特殊线性结构，区别在于读取方式

1. 队列是先进先出，即FIFO
2. 栈是先进后出，即FILO

• 集合结构：集合中的所有元素除了同属于一个集合外，他们之间没有其他关系

• 树形结构：数据之间的存在一对多的层次关系
  

  树形结构

• 图形结构：数据之间存在多对多的关系

物理结构

数据的物理结构就是数据存储在磁盘中的方式，这里的磁盘指的是计算机的内存，主要研究的是数据结构在计算机中的实现方式，包括数据结构中的元素的表示及元素间关系的表示，有以下两种

顺序存储结构： 逻辑上相邻的数据元素，物理存储位置也相邻，顺序表的存储空间需要预先分配，且存储空间是一段的连续的内存，顺序存储结构如下图所示

• 优点
  方法简单，易实现，因为在各种高级语言中都有数组
  顺序存储结构具有随机访问的特点
• 缺点
  顺序表中做插入/删除 操作时，需要进行大量的数据移动，因此对n较大的顺序表效率低
  需要预先分配空间，如果空间预估过大，会导致顺序表后面的大部分空间闲置，浪费内存，如果预估过小，又会造成溢出

链式存储结构 ：逻辑上相邻的数据元素，其物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系，且链表的存储空间是动态分布的，链式存储结构如下图所示

• 优点：
  不需要提前开辟一段连续的空间，其空间是动态分配的
  插入、删除操作方便，只需要改变指针的指向，不需要移动数据元素
• 缺点
  链表不能随机存取元素，如果在链式存储中遍历，需要遍历所有的元素