004.线性表3-8

@author: 小甲鱼

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

1.顺序存储结构的介绍

顺序存储的概念

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

没错，就是跟数组一样。。
物理上存储方式本质是：在内存中找到一个初始化的地址，通过占位的形式。把一定的内存空间给占了，然后把相同数据类型的数据元素一次放在这个空地中。


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

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

注意， 数组长度与线性表的当前长度的区别？

• 1.数组的长度就是存放线性表的存储空间的总长度，一般初始化后不变。
• 2.线性表中的当前长度 是 线性表中元素个数，是会变化的。 就像突然 鱼油看见妹子，一个人跑出去搭讪去咯。

地址计算方法

我们计算任意一个元素的位置地址，时间复杂度都为 O(1)，我们通常称为： 随机存储结构。



2.get获取元素操作

GetElem的具体操作
传入数组，元素下标，返回指针地址.
时间复杂度为： O(1)

3.insert插入／delete删除 元素操作

ListInsert／ListDelete 的具体操作
传入数组，插入元素(找到元素位置，后面的元素都后移一位, 然后插入元素), 返回数组就行。
传入数组，删除元素(找到元素位置，先删除，后面的元素都向前移动一位), 返回数组就行。
时间复杂度为： O(n)

4.优缺点的分析