1、顺序存储结构

1.1、顺序存储的定义

说这么多的线性表，我们来看看线性表的两种物理结构的第一种——顺序存储结构。

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表（a1,a2,......,an）的顺序存储示意图如下：

image-20200405195000254

1.2、顺序存储方式

线性表的顺序存储结构，说白了，和刚才的例子一样，就是在内存中找了块地儿，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用C语言（其他语言也相同）的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

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

// 存储空间初始分配量
#define MAXSIZE 20
// ElemtType类型根据实际情况而定，这里假设为int
typedef int ElemtType;

typedef struct {
    // 数组存储数据的元素，最多为MAXSIZE个
    ElemtType data[MAXSIZE];
    // 线性表当前的长度
    int length;
} Sqlit;

这里，我们就发现描述顺序存储结构需要三个属性：

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

1.3、数组长度与线性表长度区别

注意哦，这里有两个概念“数组的长度”和“线性表的长度”需要区分一下。

数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。

数组的大小一定不可以变吗？我怎么看到有书中谈到可以动态分配的一维数组。是的，一般高级语言，比如C、VB、C++都可以用编程手段实现动态分配数组，不过这会带来性能上的损耗。

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。在任意时刻，线性表的长度应该小于等于数组的长度。

1.4、地址计算方法

由于我们数数都是从1开始数的，线性表的定义也不能免俗，起始也是1，可C语言中的数组却是从0开始第一个下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数据元素的序号和存放它的数组下标之间存在对应关系（如图3-4-3所示）。

image-20200405200611248

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。

由于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。

LOC(ai+1)=LOC(ai)+c

所以对于第i个数据元素ai的存储位置可以由a1推算得出：

LOC(ai)=LOC(a1)+(i-1)*c

从下图来理解

image-20200405201227287

通过这个公式，你可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用我们算法中学到的时间复杂度的概念来说，它的存取时间性能为。我们通常把具有这一特点的存储结构称为随机存取结构。

2、顺序存储结构的插入与删除

2.1、获得元素

对于线性表的顺序存储结构来说，如果我们要实现GetElem操作，即将线性表L中的第i个位置元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。来看代码：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
// Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int Status;

// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)操作结果：用e返回L中第i个数据元素的值
Status GetElem(SqList L, int i, ElemtType *e) {
    if (L.length == 0 || i < 1 || i > L.length) {
        return ERROR;
    }
    *e = L.data[i - 1];
    return OK;
}

2.2、插入操作

刚才我们也谈到，这里的时间复杂度为O(1)。我们现在来考虑，如果我们要实现ListIn-sert（*L,i,e），即在线性表L中的第i个位置插入新元素e，应该如何操作？

举个例子，本来我们在春运时去买火车票，大家都排队排的好好的。这时来了一个美女，对着队伍中排在第三位的你说，“大哥，求求你帮帮忙，我家母亲有病，我得急着回去看她，这队伍这么长，你可否让我排在你的前面？”你心一软，就同意了。这时，你必须得退后一步，否则她是没法进到队伍来的。这可不得了，后面的人像蠕虫一样，全部都得退一步。骂声四起。但后面的人也不清楚这加塞是怎么回事，没什么办法。

这个例子其实已经说明了线性表的顺序存储结构，在插入数据时的实现过程（如图3-5-1所示）。

image-20200405202449263

插入算法的思路：

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

实现代码如下：

// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)，
// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
Status ListInsert(SqList *L, int i, ElemtType e) {
    // 顺序表是否已满
    if (L->length == MAXSIZE) {
        return OK;
    }
    // 判断i值是否在合理的范围内
    if (i < 1 || i > L->length + 1) {
        return ERROR;
    }
    // 如果插入的数据不在表尾部
    if (i <= L->length) {
        //将要插入位置后数据元素向后移动一位
        for (int j = L->length - 1; j >= i - 1; j--) {
            L->data[j + 1] = L->data[j];
        }
    }
    // 将新元素e 放入第i个位置上
    L->data[i - 1] = e;
    // 更新顺序表的长度
    L->length++;
    return OK;
}

2.3、删除操作

接着刚才的例子。此时后面排队的人群意见都很大，都说怎么可以这样，不管什么原因，插队就是不行，有本事，找火车站开后门去。就在这时，远处跑来一胖子，对着这美女喊，可找到你了，你这骗子，还我钱。只见这女子二话不说，突然就冲出了队伍，胖子追在其后，消失在人群中。哦，原来她是倒卖火车票的黄牛，刚才还装可怜。于是排队的人群，又像蠕虫一样，均向前移动了一步，骂声渐息，队伍又恢复了平静。

这就是线性表的顺序存储结构删除元素的过程（如图所示）。

image-20200405204126327

删除算法的思路：

• 如果删除位置不合理，抛出异常；
• 取出删除元素；
• 从删除元素的位置，直到最后一个元素的位置，分别将它们向前移动一个位置；
• 表长度减1；

实现代码如下：

// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1

Status ListDelete(SqList *L, int i, ElemtType *e) {
    // 线性表为空
    if (L->length == 0) {
        return ERROR;
    }
    // 位置不正确
    if (i < 1 || i > L->length) {
        return ERROR;
    }
    if (e != NULL) {
        *e = L->data[i - 1];
    }
    // 如果删除不是最后位置
    if (i < L->length) {
        // 将每个元素前移一个位置
        for (int j = i; j < L->length; j++) {
            L->data[j - 1] = L->data[j];
        }

    }
    L->length--;
    return OK;
}

2.4、输出所有元素

算法思路：

• 判断线性表是否为空；
• 从第一个位置开始表里到最后一个位置，依次输出所有的元素；

代码实现：

// 初始条件：顺序线性表L已存在
Status ListPrint(SqList L) {
    if (L.length == 0) {
        return ERROR;
    }
    for (int i = 1; i <= L.length; i++) {
        ElemtType elem;
        // 调用获取元素的函数，在2.1中定义的函数
        GetElem(L, i, &elem);
        printf("%d  ", elem);
    }
    printf("\n");
    return OK;
}

2.5、清空线性表

算法思路：

• 我们只需要把表的长度置为0即可。

// 初始条件：顺序线性表L已存在
Status ListClear(SqList *L) {
    L->length = 0;
    return OK;
}

2.6、时间复杂度分析

现在我们来分析一下，插入和删除的时间复杂度。

2.6.1、最好情况

如果元素要插入到最后一个位置，或者删除最后一个元素，此时时间复杂度为，因为不需要移动元素的，就如同来了一个新人要正常排队，当然是排在最后，如果此时他又不想排了，那么他一个人离开就好了，不影响任何人。

2.6.2、最坏情况

如果元素要插入到第一个位置或者删除第一个元素，此时时间复杂度是多少呢？那就意味着要移动所有的元素向后或者向前，所以这个时间复杂度为。

2.6.3、平均情况

至于平均的情况，由于元素插入到第i个位置，或删除第i个元素，需要移动个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，也就说位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等，为。

3、总结

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是；而插入或删除时，时间复杂度都是。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。当然，它的优缺点还不只这些……

线性表顺序存储结构的优缺点

image-20200405213036323