|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用数据结构 > 线性结构 > 线性表 > 线性表的存储结构 >
|
|
相关知识点：2个
|
|
|
|
|
线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，如下图所示。在这种存储方式下，元素间的逻辑关系无需占用额外的空间来存储。
|
|
|
|
|
|
|
|
一般地，以LOC（a1）表示线性表中第一个元素的存储位置，L表示每个元素所占空间的大小，则顺序存储结构中，第i个元素ai的存储位置为：
|
|
|
|
|
|
线性表采用顺序存储结构的优点是可以随机存取表中的元素，按序号查找元素的速度很快。缺点是插入和删除操作需要移动元素，插入元素前要移动元素以挪出空的存储单元，然后再插入元素；删除元素时同样需要移动元素，以填充被删除的元素空出来的存储位置。
|
|
|
|
在表长为n的线性表中插入新元素时，共有n+1个可插入位置，在位置1（元素a1所在位置）插入元素时需要移动n个元素，在位置n+1（元素an所在位置之后）插入元素时不需要移动元素，因此，等概率下插入一个元素时平均的移动元素次数Einsert为：
|
|
|
|
|
|
|
|
在表长为n的线性表中删除元素时，共有n个可删除的元素，删除元素a1时需要移动n-1个元素，删除元素an时不需要移动元素，因此，等概率下删除一个元素时平均的移动元素次数Edelete为：
|
|
|
|
|
|
|
