数据结构是计算机存储、组织数据的方式, 它是指相互之间存在一种或多种特定关系的数据元素的集合.
在计算机中, 数据元素并不是孤立的、杂乱无序的, 而是按照一定的内在联系存储起来的, 这种数据之间
的内在联系就是数据结构的组织形式.
分类方式有两种: 按照逻辑结构和按照存储结构
逻辑结构: 描述数据元素之间的逻辑关系
存储结构: 描述数据元素在计算机中的存储结构, 即物理结构
逻辑结构可分为: 集合、线性结构、树形结构、图形结构
在集合中, 数据元素都属于这个集合, 但数据元素之间没有什么关系, 类似于数学中的集合.
线性结构分为 顺序存储 和 链式存储 两种.
顺序存储是由一段连续的空间来存储元素; 链式存储是由分散的单元空间来存储元素, 存储单元由指针连接.
数据元素有自顶向下的层次关系, 一对多
图形结构中的数据元素存在多对多的关系
常见的存储结构有: 顺序存储结构、链式存储结构、索引存储结构、散列表
顺序存储结构把逻辑上相邻的节点存储在地址连续的存储空间里, 数组元素之间的关系由存储单元是否相邻来体现.
顺序存储结构通常用高级语言中的数组来描述.
系统为顺序存储结构分配一段连续的地址空间, 可以提高空间利用率, 对于随机访问元素, 效率非常高,
这是由于相邻的数据元素的存储空间也是相邻的, 所以可以按照元素序号来快速查找到某一个元素.
但也正因为如此, 顺序存储结构在插入和删除元素的时候, 效率则非常低,
这是因为如果插入一个元素, 需要将这个元素之后的元素都向后移动一个位置, 同样, 删除一个元素, 需要将这个元素
后面的元素都向前移动一个位置.
顺序存储结构在使用时有空间的限制, 当需要存取的元素超过预先分配的空间, 会出现溢出问题, 当元素少于分配空间又会造成空间浪费.
链式存储结构在空间上是一些不连续的存储单元, 这些存储单元的逻辑关系通过附加的指针字段来表示.
在链式存储结构中, 可以有指向后继元素的指针字段(如单向链表), 也可以有指向前驱元素的指针字段(如双向链表).
链式存储结构有利于元素的插入和删除, 例如在某个位置插入一个新元素, 只需要让前面的元素指向新元素, 新元素再指向后面的元素,
同理, 当删除一个元素时, 只需要将前后两个元素连接起来即可.
但是, 链式存储结构不适合元素的查找, 而且内存利用率低(分配的存储空间一部分被用来存储节点之间的逻辑关系),
链式存储结构没有空间的限制, 链式存储结构可以在需要的时候方便地分配新空间, 不会造成空间不足或浪费.
索引存储结构主要是为了方便查找数据, 它通常是在存储节点信息的同时, 还建立附加的索引表.
索引表中的每一项称为索引项, 由两个字段组成: 关键字 和 地址.
其中关键字唯一标识一个结点, 地址是指向结点的指针.
索引表可以快速地对数据进行随机访问, 又因为在插入和删除时只需要更改索引表中的地址值, 不必移动结点,
因此在数据更改方面也具有较高的效率, 但是索引存储结构需要额外空间来建立一个索引表, 因此降低了空间利用率.
上图中的索引表一个索引项对应一个结点, 叫做稠密索引, 如果索引表中一个索引项对应一组结点, 叫做稀疏索引, 如下图所示:
散列存储又称为哈希存储, 是一种将数据元素的存储位置与关键字之间建立对应关系的查找技术.
它的基本思想是通过一定的函数关系(散列函数, 又称哈希函数)计算出一个值, 将这个值作为元素的存储地址.
散列存储的访问速度是非常迅速的, 只要给出对应结点的关键字, 它会立即计算出该结点的存储地址.