|
一、顺序存储定义
线性表的顺序存储结构指的是用一段地址连续的存储单元依次线性表的数据元素。顺序存储的示意图如下：
在这里插入图片描述
二、线性表的地址计算方法
由于c语言的数组的下标是从0开始的，所以线性表第i个元素存储在第i-1的位置。如下图所示：
在这里插入图片描述
由于每个数据元素，不管它是整型还是字符型。都占有一定的存储单元空间。假设占用的是c个单位的存储单元。那么线性表中第i+1个元素的存储位置和第i个元素的存储位置满足以下条件。
LOC(a(i+1)) = LOC(ai) + c
则可以推断出第i个元素ai的位置由a1计算得出：
LOC(ai) = LOC(a1) + (i-1)*c
三、顺序存储结构的插入和删除等操作
1、获取元素（GetElem）:既将线性表的第i个元素的下标返回。
int GetElem (SqList L,int i,ElemType *e)
{
if (L->length==0 || i<l || i>L->length)
return 0;
else
return *e=L->data[i-1];
2、插入操作（ListInsert）：
（1）如果插入位置不合理，返回0;
（2）如果线性表长度大于等于数组长度，返回0；
（3）从最后一个元素开始向前遍 历到第i个位置，分别将它们都向后移动一个位置;
（4）将要插入元素填入位置i处;
（5）表长加1。
代码实现：
bool ListInsert ( SqList *L, int i, ElemType e )
{
int k;
if (L->length==MAXSIZE)/顺序线性表已经满/
return false;
if(i<1 || i>L->length+1) /当i不在范围内时/
return false;
if (i<=L->length) /若插入数据位置不在表尾/
{
for (k=L->length-1;k>=i-1;k–)/将要插入位置后数据元素向后移动一位/
L->data[k+1]-L->data[k];
}
L->data[i-1]=e;/将新元素插入/
L-> length++;
return true;
}
3、删除操作（ListDelete）
(1)如果删除位置不合理，return 0;
(2)取出删除元素;
(3)从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置;
(4)表长减1。
代码实现：
bool ListDelete (SqList *L,int i, ElemType *e)
{
int k;
if (L->length==0 )//线性表为空
return false;
if (i<1 || i>L->length)//删除位置不对
return false;
*e-L->data(i-1];
if ( ilength )//如果删除不是最后位置
{
for (k=i;klength;k++) //将删除位置后继元素后移
L->data[k-1]=L->data [k];
}
L-> length–;
return true;
}
四、顺序存储结构的优缺点
优点：1、不用为表中的元素之间的逻辑关系而增加额外的存储空间。
2、可以快速存取表中任意位置的元素。
缺点：1、删除和插入需要移动大量的元素。
2、当长度变化较大时无法确定存储空间的容量。
|