数据结构基础

1、数据结构三要素：

逻辑结构、物理结构、数据运算

2、逻辑结构

逻辑结构是数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构。

线性结构包括：线性表、栈、队列、串、数组
非线性结构包括：树、图、集合

3、物理结构
又称为存储结构，指数据结构在计算机中的表示。数据的存储结构主要有：顺序存储,链式存储,索引存储,散列存储
1）顺序存储：数据存储在物理位置上相邻的存储单元里，元素之间的关系由存储单元的临接关系来体现。优点是便于存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元。因此可能产生较多的外部碎片。

2）链式存储：不要求存储数据之间关系相邻，元素之间使用额外的数据记录相邻的元素地址。优点是不会出现碎片现象，充分利用存储单元。缺点是占用了额外的存储空间，且指定顺序变量。

3）索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式为（关键字：地址），其优点是索引速度快，缺点是增加了附加的索引表，会占用较多的存储空间。

4）散列存储：根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。