引入

我们知道，数据结构分为逻辑结构和物理结构，线性表就是一种逻辑结构，那么线性表对应的物理存储结构是什么呢？如何操作这些存储结构呢？

线性表的物理存储结构

线性表有两种物理存储结构

顺序存储结构：顺序存储结构指的是一段地址连续的存储单元一次存储线性表中的数据元素。我们很容易想到的就是数组，数组就是地址相连的一段元素，是顺序存储结构。
链式存储结构： 稍后详细介绍。

线性表的顺序存储结构

这节我们主要讲线性表的顺序存储结构，其实顺序存储结构在物理上的存储方式就是：

在内存中找到一个初始地址
通过占位的形式，把一定的内存空间给占了
最后，把相同数据类型的数据元素依次放在这块空间里

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

#define MAXSIZE 20  //定义常量 MAXSIZE 为 20
typedef int ElemType;  //将 int 类型 别名位 ElemType
typedef struct {
//定义一个结构体变量包含两个元素
Elemtype data[MAXSIZE];
// 一个整型 data 数组，元素有20个
int length;
// 一个整型的长度
} SqList；
//将结构体类型名设置为 SqList

上面的 ElemType 可以是任何类型，例子中我们把它当做整型。

顺序存储结构封装的三要素

根据上面的例子，我们总结了封装一个顺序存储结构的三要素：

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

最大存储容量和当前长度的区别
最大存储容量：表示的是存放线性表空间的总长度，一般不变
当前长度：表示的是线性表当前存放的元素个数，随着插入/删除而改变。

顺序存储结构地址计算方法

对于顺序存储结构的第 i 个数据元素 ai 的存储位置可以由 a1推出

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

其中

LOC(a1)是 a1 的位置
c 表示的是 ElemType 的字节长度（int 4字节）
第 i 个元素跟 a1 插 (i-1) 个 c ，所以 c*(i-1)
这样我们就可以推算出任何元素的位置了

时间复杂度：因为不管是第一个还是最后一个，我们只计算一次，所以时间复杂度为 O(1) 。
我们通常也称为随机存储结构。

顺序存储结构中获取元素

我们知道了如何在众多元素中找到某一个元素的位置，那么我们就可以利用这一点，来获取第 i 个元素的值了。

#define MAXSIZE 20  //定义常量 MAXSIZE 为 20
typedef int ElemType;  //将 int 类型 别名位 ElemType
typedef struct {
//定义一个结构体变量包含两个元素
Elemtype data[MAXSIZE];
// 一个整型 data 数组，元素有20个
int length;
// 一个整型的长度
} SqList；
//将结构体类型名设置为 SqList

Status GetElem ( SqList *L , int i ,ElemType *e){
// 字定义变量，输入顺序存储结构体、要输出的位置和返回到哪个指针
if(L.length==0 || i<1 || i>L.lenght){
// 结构体的长度不能为空，结构体的位置不能小于1，位置当然也不能大于结构体的元素长度
return ERROR;
// 否则返回REEOR，这个上面用 define 定义过
}
*e = L.data[i-1];
// 把输入的要存储的 i 个元素值的地址赋值
return OK;
}

主要就是一下几个思路：

输入：输入的是线性表、索引地址、存储地址
判断条件：线性表不为空、索引不为0或者负数、索引在线性表的长度范围内，也就是索引值合法。
输出：知道了索引位置，也知道了数据存储是从0开始的，所以索引位置的值应该是 i-1 ，也就是找到这个索引所对应的数组下标。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。