引入
我们知道，数据结构分为逻辑结构和物理结构，线性表就是一种逻辑结构，那么线性表对应的物理存储结构是什么呢？如何操作这些存储结构呢？
线性表的物理存储结构
线性表有两种物理存储结构
- **顺序存储结构：**顺序存储结构指的是一段地址
连续的存储单元一次存储线性表中的数据元素。我们很容易想到的就是数组，数组就是地址相连的一段元素，是顺序存储结构。 - 链式存储结构： 稍后详细介绍。
线性表的顺序存储结构
这节我们主要讲线性表的顺序存储结构，其实顺序存储结构在物理上的存储方式就是：
- 在内存中找到一个初始地址
- 通过占位的形式，把一定的内存空间给占了
- 最后，把相同数据类型的数据元素依次放在这块空间里
线性表顺序存储的结构代码
#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 ，也就是找到这个索引所对应的数组下标。
尾巴
这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。
评论