二、数据的存储结构

数据的存储结构是建立一种由逻辑结构到存储空间的映射：对于逻辑结构（K，r）, 其中r Î R，对它的结点集合K建立一个从K 到存储器M 的单元的映射：K->M，其中每个结点j ÎK都对应一个惟一的连续存储区域c Î M。
    常用的基本存储映射方法有顺序方法、链接方法、索引方法和散列方法。
    顺序存储把一组结点存放在按地址相邻的存储单元里，结点间的逻辑关系用存储单元的自然顺序关系来表达的，即，用一块存储区域存储线性数据结构。顺序存储法为使用整数编码访问数据结点提供了便利。因为，顺序存储方法的存储空间除了存储有用数据外，没有用于存储其他附加的信息，所以顺序存储结构一般也被称为紧凑存储结构。
    链接法是在结点的存储结构中附加指针字段来存储结点间的逻辑关系。链接法中数据结点包括两部分：数据字段存放结点本身的数据，指针字段存放指向其后继结点的指针。链接方法适用于那些需要经常进行增删结点的复杂数据结构。
    索引法是顺序存储的一种推广，用于大小不等的数据结点的顺序存储。通过建造一个由整数域Z映射到存储地址域的函数，把整数索引值映射到结点的存储地址，从而形成一个存储一串指针的索引表，每个指针指向存储区域的一个数据结点。
    作为索引法的一种延伸和扩展，散列法利用散列函数进行索引值的计算，然后通过索引表求出结点的指针地址。