【线性表】

好久没更新啦，来喽来喽~~~

喏，看这个图，什么意思呢？先容大家思考思考......

1.线性表的定义

2.线性表的抽象数据类型

3.线性表的顺序存储结构

（1）顺序存储定义

（2）顺序存储方式

(3)数组长度与线性表长度区别

（4）地址计算方法

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

（1）获得元素操作

（2）插入操作

（3）删除操作

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

1.线性表的定义

线性表，从名字来听，是不是觉得是具有像线一样性质的表呢？接下来进入正题：

线性表：是零个或者多个具有相同特性的数据元素的有限序列。

说明：首先，其是一个序列，换言之，元素之间是有顺序的，如果说元素存在多个，那第一个元素它是没有前驱，最后一个元素是没有后继的，而其他中间部分的元素有且仅有一个前驱和后继了。

其次，线性表它是有限的！

线性表在逻辑上是线性结构，也就是说是连续的一条直线，但在物理结构上并非是这个样子的，一般来说，线性表在物理上存储时，通常是以数组和链式结构的形式存储的。（后面我们都会介绍到的哦，不用着急哦~）

2.线性表的抽象数据类型

对于一个线性表来说，插入数据和删除数据都是必须的操作，所以就会出现线性表的抽象数据类型，如下：

说明：这些操作是线性表中最基本的一些操作，对于不同场景不同应用，线性表的基本操作是不相同的，如果遇到更复杂的操作，还可以用这些基本操作的组合来实现。

线性表的数据对象集合为{a1,a2,......，an},每个元素的类型均为DataType。数据元素之间的关系是一对一的关系。

3.线性表的顺序存储结构

（1）顺序存储定义

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

（2）顺序存储方式

线性表的顺序存储结构，简单来讲，就是在内存中找了块空地，通过占位置的方式，把一定的内存空间给占有了，接着把相同数据类型的数据元素依次存放在这块空地中。（由于线性表的每个数据元素它的类型都是一样的，所有我们可以通过用某种程序语言的一维数组进而来实现顺序存储结构。）总结一下就是，把第一个数据元素存到数组下标为0的位置中，然后把线性表相邻的元素存储在数组中相邻的元素即可。

描述顺序存储结构需要的属性：

a:存储空间的起始位置：数组data,它的存储位置就是存储空间的存储位置。

b:线性表的最大存储容量：数组的长度

c:线性表的当前长度length

(3)数组长度与线性表长度区别

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

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

不过，在任意时刻，线性表的长度应该小于等于数组的长度。

（4）地址计算方法

因为在C语言中，数组是从0开始第一个下标的，所以线性表的第i个元素也是要存储在数组下标为 i-1的位置（也就是数据元素的序号和存放它的数组下标之间存在着对应关系）

前面刚提到，数组存储分配后这个量一般是不变化的，也就是要分配固定长度的数组空间，而又因为线性表可以进行修改操作，所以，这里分配的数组空间要大于等于当前线性表的长度！

由于每个数据元素，无论是什么类型的，其都需要占有一定的存储单元空间。这里假设一下，帮助大家理解，假设每个数据元素它占用了c个存储单元（存储单元：指存储器中可存放一个字或若干个字节的基本单位），那么，线性表中第 i+1 个数据元素与第 i 个数据元素的存储位置满足关系：

看图可以更快理解哦：

那么，通过这个公式的话，无论遇到什么样的，你都是可以算出线性表中任意位置的地址，这里可就不管它是第一个或者最后一个啦，都是相同的时间。

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

（1）获得元素操作

对线性表得顺序存储结构而言，如果将线性表L中的第 i 个位置元素返回，其实蛮简单的，对我们来说，也就是当 i 的数值在数组下标范围内，就是把数组第 i - 1 个下标的值返回就好啦~

上代码，哈哈哈哈

typedef int Status;
//操作结果：用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是一个整型。

这里是把指针*e的值修改成L.data[i-1],这才是真正要返回的数据。

（2）插入操作

如果说在线性表L中的第 i 个位置插入新元素e -----ListInsert(*L,i,e) ,又该如何操作呢？

讲思路之前给大家举个例子吧，可能会帮助大家理解哦~

假如某天早上大家去上课，排队在买早餐，两眼朦胧的排着队，排的好好的，突然来了一位很漂亮的小姐姐，轻声细语的跟你说同学，不好意思，我可以插个队吗，我昨晚到现在没吃饭，饿的胃都疼，欸，你一瞧，心软了，说好吧，那既然点头答应了，不得自己往后退啊，要不然这位小姐姐进不来，可后面排了好多人嘞，可这是，后面好多人都在骂骂咧咧，也许你前后的人知道因果，可后边的人不知道哇，哗哗一大片吵闹声......那如果说让这个小姐姐插队，是不是只能这样啊，哈哈哈

思路：

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

b:如果线性表长度大于等于数组长度，那么就应该抛出异常或者动态增容；

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

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

e:最后表长加 1；

如果我们把这个思路转换成代码的形式呢？

//插入操作Status ListInsert(SqList* L, int i, ElemType e)
{int m;if (L->length == MAXSIZE)return ERROR;if (i < 1 || i > L->length + 1)return ERROR;if (i <= L->length){for (m = L->length - 1; m >= i - 1; m--){L->data[m + 1] = L->data[m];}}L->data[i - 1] = e;L->length++;return OK;
}

（3）删除操作

如果说，这位小姐姐在后面同学的吵闹中，插队没成功，那大家都往前移动一步，整个队伍是不是恢复原状了~ 那么，这个过程就很类似线性表的顺序存储结构删除元素的过程。

思路：

a:如果删除位置不合理的话，抛出异常；

b:取出删除的元素；

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

d：最后表长减1；

同理，如果将整个思路转换成代码，又是怎样的呢？

//删除操作
Status ListDelete(SqList* L, int i, ElemType* e)
{int m;if (L->length == 0)return ERROR;if (i<1 || i>L->length)return ERROR;*e = L->data[i - 1];if (i < L->length){for (m = i; m < L->length;m++){L->data[m - 1] = L->data[m];}}L->length--;return OK;
}

通过上面的插入删除，就能够总结出，线性表的顺序存储结构，在读数据的时候，无论处于哪个位置，时间复杂度都是O（1），在插入或者删除数据的时候，时间复杂度都是O（n）