数据结构基本概念

什么是数据结构

巧妇难为无米之炊（巧:妇比喻算法，米:比喻数据结构）

数据结构

数据之间相互存在的一种或多种特定的关系的元素的集合（如隔壁老王和隔壁老宋）

逻辑结构

Paste_Image.png

物理结构（存储结构）

Paste_Image.png

抽象数据类型

数据类型：一组性质相同的值的集合及定义在此集合上的一些操作的总称
抽象数据类型：一个数字模型及定义在该模型上的一组操作

线性表（List）

Paste_Image.png

a1是a2的前驱，ai+1 是ai的后继，a1没有前驱，an没有后继。n为线性表的长度，若n==0时，线性表为空表

顺序存储方式线性表

Paste_Image.png

存储位置连续，可以很方便计算各个元素的地址如每个元素占C个存储单元，那么有：
Loc(An) = Loc(An-1) + C,于是有：Loc(An) = Loc(A1）+（i-1）*C;
优点：查询很快
缺点：插入和删除效率慢

Paste_Image.png

链式存储方式线性表

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的
为了表示每个数据元素Ai与其直接后继数据元素Ai+1之间的逻辑关系，对数据元素Ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息
优点：删除还插入效率高
缺点：查询效率低