01什么是数据结构

什么是数据结构?

数据结构.jpg

数据结构=逻辑结构 + 物理结构

1. 逻辑结构：数据元素间抽象化的相互关系。

2. 物理结构：在计算机存储器中的存储形式。

一、 逻辑结构

1.1对于非空的线性表和线性结构,其特点如下:

• 存在唯⼀一的⼀一个被称作”第⼀一个”的数据元素;
• 存在唯⼀一的⼀一个被称作”最后⼀一个"的数据元素
• 除了了第⼀一个之外,结构中的每个数据元素均有⼀一个前驱
• 除了了最后⼀一个之外,结构中的每个数据元素都有⼀一个后继.

举例：

线性结构.jpg

1.2 非线性结构

各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系
集合结构、树形结构、图形结构
集合结构: 元素之间没有特殊的关系，只是属于一个集合
树形结构: 一对多的关系，比如二叉树，红黑树等
图形结构: 多对多的关系，如矩阵表等

举例：

Jietu20200411-174038.jpg

二、 存储结构

2.1顺序存储结构

• 顺序存储结构: 数据元素存放在一组存储地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的

  
  image.png

2.2链式存储结构

• 链式存储结构: 数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的

image.png

2.3单链表与顺序表的对比

• 存储方式：顺序表用一组连续的存储单元依次存储线性表的数据元素；而单链表用一组任意的存储单元存放线性表的数据元素。

• 时间性能：采用循序存储结构时查找的时间复杂度为O(1)，插入和删除需要移动平均一半的数据元素，时间复杂度为O(n)。采用单链表存储结构的查找时间复杂度为O(n)，插入和删除不需要移动元素，时间复杂度仅为O(1）。

• 空间性能：采用顺序存储结构时需要预先分配存储空间，分配空间过大会造成浪费，过小会造成问题。采用单链表存储结构时，可根据需要进行临时分配，不需要估计问题的规模大小，只要内存够就可以分配，还可以用于一些特殊情况，如一元多项的表示。