数据结构的基本概念

1.逻辑结构

逻辑结构分为四种类型：集合结构，线性结构，树形结构，图形结构。

集合结构

数据元素同属一个集合，单个数据元素之间没有任何关系。

线性结构

数据元素间是线性排列关系。一对一。

树形结构

树形结构中的数据元素所组成图形类似于树状图。一对多。

图形结构

数据元素之间是多对多的关系。

2.物理结构（存储结构）

物理结构又叫存储结构，分为四种种，顺序存储结构、链式存储结构、索引结构、散列结构。

顺序存储结构

一段连续的内存空间。

优点：随机访问

缺点：插入删除效率低，大小固定

链式存储结构

不连续的内存空间

优点：大小动态扩展，插入删除效率高

缺点：不能随机访问

索引存储结构

为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表。

优点：对顺序查找的一种改进，查找效率高

缺点：需额外空间存储索引

散列存储结构

选取某个函数，数据元素根据函数计算存储位置可能存在多个数据元素存储在同一位置，引起地址冲突

优点：查找基于数据本身即可找到，查找效率高，存取效率高。

缺点：存取随机，不便于顺序查找。