数据结构与算法（五）线性表的顺序存储结构

举个现实中的例子：一群人排队去看电影（就和前几篇我们一直提到的关于排队的情景那样）当第一个同学进入到电影院，找到了自己的位置，接着后面的同学们果断地依次坐下，这样子就建立起了一个线性表。本算法的时间复杂度为O(1)刚才我们提到过排队的问题，如果这时候有一个人要回到队列当中，我们应该怎么做，我们会找到他要插入位置的那个同学，让他以及它后面的同学全部往后移动一个位置，再将新同学安排在这个位置里面。注意

Felix Du

2236人浏览 · 2024-09-19 10:30:00

Felix Du · 2024-09-19 10:30:00 发布

2、初始化线性表：InitList(&L)

3、销毁线性表（DestroyList(&L))

4、判断线性表是否为空间（ListEmpty(L))

5、求线性表的长度（ListLength（L))

6、输出线性表（DispList(L))

7、查找元素的操作（GetElem与LocateElem）

（1）按序号求线性表中的元素：GetElem(L,i,&e)

（2）按元素查找：LocateElem（L，e）

8、插入数据元素：ListInsert(&L,i,e)

9、删除数据元素：ListDelet:(&L,i,&e)

六、线性表的顺序存储结构的优缺点分析

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

我们可以想象，线性表有两种物理存储结构：顺序存储结构和链式存储结构。对于线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表 $(a_1,a_2,...,a_n)$ 的顺序存储如下图：

如图可见，线性表的顺序存储和数组长得一样。物理上的存储方式事实上就是在内存中找个初始地址，然后通过占位的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中。举个现实中的例子：一群人排队去看电影（就和前几篇我们一直提到的关于排队的情景那样）当第一个同学进入到电影院，找到了自己的位置，接着后面的同学们果断地依次坐下，这样子就建立起了一个线性表。可是现实中总会有些突发情况，其中一个同学临时有事，看不了电影，因为他买了电影票了，所以就算他的位置空着，也没有人会坐上去。这就是顺序存储结构的特性之一。

接下来让我们来看线性表顺序存储的结构代码：

#define MAXSIZE 20//线性表不会超过20个元素
typetdef struct
{
    ElemType data[MAXSIZE];//存放线性表中的元素
    int length;//存放线性表的长度
}Sqlist//顺序表类型

从上面代码我们可以看到，这里我们封装了一个结构，事实上就是对数组进行封装，增加了个当前长度的变量罢了。（通过sqlist这个结构对数组进行封装，多了一个length的变量）

总结一下：顺序存储结构封装需要三个属性。

1、存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置。（类似队伍的第一个同学找到自己的位置）

2、线性表的最大存储容量，数组长度maxsize（也就是我们总共买了多少张票）

3、线性表的当前长度：length（也就是总共来了多少人）

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

二、地址计算方法

我们或许习惯了数组从0开始的计算方法，但我们提到过，线性表与数组的计算方法有所不同，线性表与我们现实生活一样，都是从1开始回归正常思维。假设ElemType占用的是c个存储单元（字节），那么线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是（LOC即为location，表示获得存储位置的函数）： $LOC(a_i+1)=LOC(a_i)+c$ 。所以对于第i个数据元素 $a_i$ 的存储位置可以由 $a_1$ 推断得出： $LOC(a_i)=LOC(a_1)+(i-1)*c$

结合下图来理解：

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

三、顺序表的基本运算

1、建立顺序表

这里介绍整体创建顺序表，即由数组元素a[0...n-1]创建顺序表L。其方法是将数组a中的每个元素依次放入顺序表中，并将n赋给顺序表的长度域。算法如下：

void CreatList(SqList * &L,ElemType a[],int n)//由a中的n个元素建立顺序表
{
    int i=0,k=0;//k表示L中元素的个数，初始值为0
    L=(SqList *)malloc(sizeof(SqList));//分配存放线性表的空间
    while(i<n)//i扫描数组a的元素
    {
        L->data[k]=a[i];//将元素a[i]存放到L中
        k++;i++;
    }
    L->length=k;//设置L的长度k
}

调用上述算法创建好L所指的顺序表后，需要回传给对应的实参，也就是说L是输出型参数，所以在形参L的前面需要加上引用符“&”。

2、初始化线性表：InitList(&L)

该运算功能是构造一个空的线性表L，实际上只需分配线性表的存储空间并将length域设置为0即可。算法如下：

void InitList(SqList *&L)
{
    L=(SqList * )malloc(sizeof(SqList));//分配存放线性表的空间
    L->length=0;//置空线性表的长度为0
}

本算法的时间复杂度为O(1)。

3、销毁线性表（DestroyList(&L))

该运算功能是释放线性表L占用的内存空间。算法如下：

void DestroyList（SqList *&L）
{
    free(L);//释放L所指的顺序表空间
}

本节的顺序表是通过malloc函数分配存储空间的，当不再需要顺序表时务必调用DestroyList基本运算释放其存储空间；否则，尽管系统会自动释放顺序表的指针变量L，但不会自动释放L指向的存储空间，如此可能会造成内存泄漏。本算法的时间复杂度为O(1)

4、判断线性表是否为空间（ListEmpty(L))

该运算返回一个布尔值表示L是否为空表。若L为空表，返回true，否则返回false。算法如下：

bool ListEmpty（SqList *L）   
{
    return(L->length==0);
}

5、求线性表的长度（ListLength（L))

该运算返回顺序表L的长度，实际上只需返回length域的值即可。算法如下：

int ListLength(SqList *L)
{
    return(L->length);
}

6、输出线性表（DispList(L))

该运算依次输入L中各元素的值。算法如下：

void DispList(SqList *L)
{
    for(int i=0;i<L->length;i++)
        printf("%d",L->data[i]);
    printf("\n");
}

本算法中的基本操作为for循环中的printf语句，故时间复杂度为O(n)

7、查找元素的操作（GetElem与LocateElem）

（1）按序号求线性表中的元素：GetElem(L,i,&e)

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

bool GetElem(SqList *L,ElemType e)
{
    int i=0;
    while(i<1||i>L->length)
        return false;//参数i错误时返回false
    e=L->data[i-1];//取元素的值
    return true;//成功找到元素时返回true
}

本算法的时间复杂度为O(1)

（2）按元素查找：LocateElem（L，e）

按运算顺序查找第一个值为e的元素的逻辑符号，若这样的元素不存在，则返回值为0。算法如下：

int LocateElem(SqList *L,ElemType e)
{
    int i=0;
    while(i<L->length && L->data[i]!=e)
        i++;//查找元素e
    if(i>=L->length)
        return 0;//未找到时返回0
    else
        return i+1;//找到后返回其逻辑符号
}

该算法的时间复杂度为O(n)

8、插入数据元素：ListInsert(&L,i,e)

刚才我们提到过排队的问题，如果这时候有一个人要回到队列当中，我们应该怎么做，我们会找到他要插入位置的那个同学，让他以及它后面的同学全部往后移动一个位置，再将新同学安排在这个位置里面。所以我们插入算法的思路如下：

-如果插入位置不合理，抛出异常；

-如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量；

-从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置；

-将要插入元素填入位置i处；

-线性表长度+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 true;
}

时间复杂度为O(n)

9、删除数据元素：ListDelet:(&L,i,&e)

我们完全可以借鉴前面插入数据元素的算法，得到删除数据算法的思路：

-如果删除位置不合理，抛出异常；

-取出删除元素

-从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；

-表长-1

算法如下：

Status ListDelet(SqList *L,int i,ElemType *e)
{
    int k;
    if(L->length == 0)
    {
        return ERROR;
    }
    if(i<q||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 true;
}