线性表--顺序存储结构

发布于:2021-10-16 13:17:04

一、线性表的顺序存储结构

线性表有两种物理存储结构:顺序存储结构和链式存储结构。


顺序存储结构

①定义:
用一段地址连续的存储单元依次存储线性表的数据元素。


②线性表(a1,a2,…,an)的顺序存储如下:




物理上的存储方式事实上就是在内存中找个初始地址,然后通过占位的形式,把一定的内存空间给占了,然后把相同数据类型的数据元素依次放在这块空地中。



③线性表顺序存储结构的结构代码:


#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length; // 线性表当前长度
} SqList;

④顺序存储结构封装需要三个属性:


存储空间的起始位置,数组data,它的存储位置就是线性表存储空间的存储位置。线性表的最大存储容量:数组的长度MaxSize。线性表的当前长度:length。

注意:数组的长度与线性表的当前长度需要区分一下:数组的长度是存放线性表的存储空间的总长度,一般初始化后不变。而线性表的当前长度是线性表中元素的个数,是会变化的。



二、地址计算方法

假设ElemType占用的是c个存储单元(字节),那么线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是(LOC表示获得存储位置的函数):LOC(ai+1) = LOC(ai) + c


所以对于第i个数据元素ai的存储位置可以由a1推算得出:LOC(ai) = LOC(a1) + (i-1)*c



通过这个公式,我们可以随时计算出线性表中任意位置的地址,不管它是第一个还是最后一个,都是相同的时间。那么它的存储时间性能就为O(1),我们通常称为随机存储结构。



注意:线性表是从1开始计算的



三、线性表的操作
1.获得元素

实现GetElem的具体操作,即将线性表L中的第i个位置元素值返回。就程序而言非常简单了,我们只需要把数组第i-1下标的值返回即可。


#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

// Status 是函数的类型,其值是函数结果状态代码,如OK等。
// 初始条件:顺序线性表L已存在,1 <= i <= ListLength(L)
// 操作结果:用e返回L中第i个数据元素的值。

Status GetElem(SqList L, int i, ElemType *e)
{
if( L.length==0 || i<1 || i>L.length )
{
return ERROR;
}
*e = L.data[i-1];

return OK;
}


注:这里返回值类型Status是一个整型,约定返回1代表OK,返回0代表ERROR。



2.插入操作

线性表的顺序存储结构具有随机存储结构的特点,时间复杂度为O(1)。


实现ListInsert(*L, i, e),即在线性表L中的第i个位置插入新元素e。


插入算法的思路:


如果插入位置不合理,抛出异常;如果线性表长度大于等于数组长度,则抛出异常或动态增加数组容量;从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;将要插入元素填入位置i处;线性表长+1。

代码:


/* 初始条件:顺序线性表L已存在,1<=i<=ListLength(L)。 */
/* 操作结果:在L中第i个位置之前插入新的数据元素e,L长度+1。*/

Status ListInsert(SqList *L, int i, ElemType e)
{
int k;

if( L->length == MAXSIZE ) // 顺序线性表已经满了
{
return ERROR;
}
if( i<1 || i>L->length+1) // 当i不在范围内时
{
return ERROR;
}
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 OK;
}

3.删除操作

算法的思路:


    如果删除位置不合理,抛出异常;取出删除元素;从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;表长-1。

实现代码:


/* 初始条件:顺序线性表L已存在,1<=i<=ListLength(L) */
/* 操作结果:删除L的第i个数据元素,并用e返*渲担琇的长度-1 */
Status ListDelete(SqList *L, int i, ElemType *e)
{
int k;

if( L->length == 0 )
{
return ERROR;
}
if( i<1 || i>L->length )
{
return ERROR;
}

*e = L->data[i-1];

if( i < L->length )
{
for( k=i; k < L->length; k++ )
{
L->data[k-1] = L->data[k];
}
}

L->length--;

return OK;
}

插入和删除的时间复杂度:


最好的情况:插入和删除操作刚好要求在最后一个位置操作,因为不需要移动任何元素,所以此时的时间复杂度为O(1)。最坏的情况:如果要插入和删除的位置是第一个元素,那就意味着要移动所有的元素向后或者向前,所以这个时间复杂度为O(n)。*均情况,取中间值O((n-1)/2)。*均情况复杂度简化后还是O(n)。
五、线性表顺序存储结构的优缺点

线性表的顺序存储结构,在存、读数据时,不管是哪个位置,时间复杂度都是O(1)。而在插入或删除时,时间复杂度都是O(n)。
这就说明,它比较适合元素个数比较稳定,不经常插入和删除元素,而更多的操作是存取数据的应用。


优点:


无须为表示表中元素之间的逻辑关系而增加额外的存储空间。可以快速地存取表中任意位置的元素。

缺点:


插入和删除操作需要移动大量元素。当线性表长度变化较大时,难以确定存储空间的容量。容易造成存储空间的“碎片”

相关推荐

最新更新

猜你喜欢