笔记：计算机公共基础知识学习内容——单链表、链性存储结构 \ 索引存储结构 \ 散列存储结构

- 单链表 / 链式存储结构

1. 链表不限制数据的物理存储状态，物理位置是随机的。

2. 链表的构成：

   • 头指针：永远指向链表第一个结点的位置，用于指出链表的位置，便于找到链表。
   • 存储结点
     
     - 头结点：链表的第一个结点。不 存任何数据的空结点，为了方便解决某些实际问题。
     - 首元结点：链表中第一个存有数据的结点。
     - 其他结点：链表中其他的结点。
     
   • 指针域：指出后件的结点（常见）。
     双向链表：每个结点设有两个指针域，一个指向前件，一个指向后件。

- 索引存储方式

1. 采用附加索引表的方式来存储节点信息。

2. 索引表由若干索引项(关键字、地址)组成。

   • 关键字能唯一标识一个节点的数据项。

3. 索引存储方式分为：
   1. 稠密索引：
   每个节点在索引表中都有一个索引项。其中，索引项的地址指示出节点所在的存储位置。
   3. 稀疏索引：
   一组节点在索引表中只对应一个索引项。其中，索引项的地址指示出一组节点的起始存储位置。

- 散列存储方式 / Hash存储方式

根据节点的关键字直接计算出该节点的存储地址。