顺序存储的原理
上一章简单讲解了线性表的顺序存储结构,读者应对线性表的顺序存储结构原理已有所了解。所谓顺序存储,就是在存储器中分配一段连续的存储空间,逻辑上相邻的数据元素其物理存储地址也是相邻的。假如要用顺序表来存储四个字母,则需要在内存中分配四个连续的存储单元,如图1所示。
图1 顺序存储结构
在图1中,要存储的四个字母被存储在一段连续的存储空间中。由存储空间的地址可以看出,这四个存储单元是连续的,第一个存储单元由序号0来标记,接下来的存储单元依次递增标记序号,这样在查找元素时,只要找到相应的索引就能找到元素,非常方便。线性表的这种存储方式称为顺序存储或顺序映射,又由于逻辑上相邻的两个元素在对应的顺序表中的存储位置也相邻,因此这种映射也称为直接映射。
在图1中,我们分配了四个存储单元来存储这四个字符,表的长度为4,容量也为4。但要注意的是,表的长度未必与容量相同。表的长度要小于等于表的容量,因为可能申请了四个存储单元,但只存入3个元素。
在顺序存储中,只要确定了线性表在存储空间里的起始位置,线性表中任意元素就都可随机存取,所以线性表的顺序存储结构是一种随机存取的结构。在高级语言中,顺序存储是用数组来实现的。
在顺序存储中,系统不需要为表元素之间的逻辑关系增加额外的存储空间,而且在存取元素时,它可以根据给出的下标快速计算出元素的存储地址,从而达到随机读取的目的。例如在图2-1中,如果要读取第3个元素,因它的下标为2(与第1个元素之间有两个间隔),由内存段的起始地址和元素相差个数可以快速计算出第3个元素的存储地址(0x001 + 1*2 = 0x003),计算出地址后,就可以方便地对数据进行操作。
但是,如果在顺序表中插入或删除元素,效率会特别低。对插入来说,只限于在表的长度小于表的容量的顺序表中,如果插入大量数据,很难保证空间是否充足。而且一旦分配了存储空间,如果想要扩充容量,需要重新分配空间,然后将原来的数据复制到新的空间中,非常麻烦。另一方面,即使空间充足,那么在插入位置之后的元素必须都要向后移动,这个效率非常低。同理,如果要删除大量元素,那么势必会造成空间的浪费,而且删除元素后,后面的元素都要向前移动,效率也会非常低。