数据结构：线性表走起！（顺序存储结构）

小Bob 小Bob Bob来啦

2020年09月23日 23:38 __ _ _ _ _

文章配图

点击上方「蓝字」关注”程序员Bob”

每天与你不见不散！

文章配图

每日一句，送给最珍贵的你：

愿你慢慢长大，愿你有好运，如果没有，希望你在不幸中学会慈悲；愿你被很多人爱，如果没有，希望你在寂寞中学会宽容。——刘瑜《愿你慢慢长大》

上次我们学到了线性表的定义以及相关抽象数据类型。

在最开始我们说数据结构时，聊到了关于物理结构，也提到了物理结构包括顺序存储结构和链式存储结构，这里就先介绍关于线性表的顺序结构啦。

关于顺序结构：数据结构笔记：第一章（数据结构绪论）

文章配图

每日推荐：

文章配图

顺序结构定义

文章配图

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

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

文章配图

顺序存储结构方式

线性表的顺序存储就如我们在教师上课占座位一样，用身上能拿出来的物品为室友占个好位置，然后等室友来后按占好的位置坐下。

那么顺序存储结构也就类似于占座位，只是在计算机中是把内存空间给占了，然后把相同数据类型给放进去的操作，到这里不知大家有没有发现和以前学过的 一维数组 很像，即我们也可以通过数组来实现顺序存储结构。 只需把第一个数据元素存到数组下标为0的地方，接着把线性表相邻的数据元素存储在数组中相邻的地方。

当然线性表也和数组也是有限制的，比如线性表的当前的长度不能超过存储容量，即数组的长度。

如下面线性表的 顺序存储结构代码 ：

#define Maxsize 20typedef int ElemType;typedef struct{  ElemType data[Maxsize];    //数组存储数据元素，最大值为Maxsize  int length;                //线性表当前长度  }SqList;

如上代码所示，我们即可发现在 顺序存储结构会有三个属性：

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

既然有数组长度，那么为什么还会有线性表的长度呢？？？

数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。有点小伙伴可能会说用动态数组，但实际上这会带来性能上的损耗。

而线性表的长度是线性表中数据元素的个数，随着线性表在插入和删除操作的进行，这个量是可以变化的。

且线性表的长度是要小于等于数组的最长长度的。

文章配图

地址计算 ** 在线性表中我们也看见它的起始为1，而数组的起始下标为0，这是我们需要注意的地方。 **
所以当我们用数组存储顺序时就意味着要分配固定长度的数组空间，由于在线性表中我们要进行插入及其其它操作，所以分配的数组空间要大于等于当前线性表的长度。

存储器中的每个单元都有自己的编号，这个编号叫 地址。

文章配图

假设每个数据元素占用的是c个内存单元，那么第i+1个数据元素的存储单元和第i个数据元素的存储单元的位置满足如下关系： LOC(Ai+1)=LOC(Ai)+c ,因此可以推出第i个数据元素的存储单元和第一个元素存储单元的位置关系： **
LOC(Ai)=LOC(A1)+(i-1)*c。 ** ** 存取的时间复杂度分析由上面这个公式可以轻易地推算出每个数据元素的位置地址，那么我们对于线性表中每个位置的数据元素的进行读入和取出操作的时间对于计算机而言来说都是相同的，是一个常数，用算法的时间复杂度概念来说，它的存取时间性能为O(1)，通常把具有这种特点的存储结构称为随机存取结构。 ** **
**
文章配图

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

文章配图

插入操作之前我们首先要获得元素，代码如下：

typedef int status;  //status是函数的类型(整型)status GetElem (SqList L,int i,ElemType *e){//初始条件：顺序线性表L已存在，1<=i<=ListLength（L)//结果：用e返回L中第i个数据元素的值。  if(L.length==0 || i<1 || i>L.length)    return 0;  *e=L.data[i-1];  return 1;}

插入操作思路：

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

实现代码如下：

//初始条件：顺序线性表L已存在，1<=i<=ListLength（L)//结果：在L中第i个位置之前插入新的数据元素e,然后表长加1，status ListInsert (SqList *L,int i,ElemType e){int k;if(L->length==Maxsize)    //线性表已满  return 0;if(i<1 || i>L->length+1)    //当i不在范围时  return 0;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 1;}

删除操作思路：

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

实现代码实例如下：

//初始条件：顺序线性表L已存在，1<=i<=ListLength（L)//结果：删除L中的第i个数据元素，并用e返回其值，L的长度减1.Status ListDelete (SqList *L,int i,ElemType *e){int k;if(L->length==0)    //线性表为0  return 0;if(i<1 || i>L->length)  return 0;*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 1;}

插入和删除的时间复杂度分析

最好的情况就是在表尾插入或删除一个数据元素，这时不需要移动其他数据元素，时间复杂度为O(n)。最坏的情况是在第一个位置插入或删除一个数据元素，时间复杂度为O(n)。

从所有的元素来看，位置越靠前，移动次数越多，位置越靠后，移动次数越少，平均移动次数和中间的数据元素移动的次数是相同的，为(n-1)/2。 所以插入和删除的平均时间复杂度为O(n)。

文章配图