数据结构概念小结

0x00 存储结构

数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

1. 顺序存储：在计算机从用一组地址连续的存储单元依次存储线性表的各个数据元素称为顺序存储。
   • 可随机存取表中元素。
   • 除末尾外，在其余位置插入和删除操作需要移动数据。
   • 存储密度大。
2. **链接存储：**用一组离散的可以位于任意位置的存储单元来存储线性表的数据元素称为链接存储，比如单链表。
   • 存储密度小，在填充相同大小内存空间的情况下，使用顺序表存储的元素要比使用链表存储的元素多，因为链式存储每一个结点都需要附加一个占用空间指针域。
   • 逻辑上的相邻结点，物理上不必相邻。
   • 插入和删除操作灵活，无需移动其中元素。
   • 获取某个结点数据时比顺序存储慢。
3. 索引存储：除存储结点信息之外，还建立附加的索引表来标识结点的地址，索引表往往由若干索引项组成。
   • 使用索引来确定结点的存储位置，检索速度快，但需要占用多余的空间来存储索引表。
4. **散列存储：**即为hash存储，力图将数据元素的存储位置与关键码之间建立确定的对应关系，以用来加速查找过程的存储结构。
   • 可以进行快速的查找，可以依据存储数据的部分内容来找到数据在数组中的存储位置，进而实现数据的快速访问，在查找某一个数据时，使用这个数据或者这个数据的部分作为映射函数的输入，映射函数的输出即为数据存储的位置，这样进行随机查找时就省去了遍历数组的时间，将$O(N)$的复杂度缩小到常数级$O(1)$。