线性表的顺序存储结构总结

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元（比如C语言里面的数组），依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

顺序表任意元素可以在单位时间内找到存储位置。

注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的 在具体的题目中需要分辨清楚。

一、如何建立顺序表的结构

首先我们要在内存中“找块地”，而且是连续的，那么我们可以先确定存储空间的起始位置；然后还要知道这块地有多大，那么这块地的大小我们也要确定；最后我们要将表中各个元素对号入座，那就要知道有多少元素，也就是表的长度。

二、建立顺序表的三个属性

1. 存储空间的起始位置（数组名data）
2. 顺序表最大存储容量（MaxSize）
3. 顺序表当前的长度（length）

#define MaxSize 50 //定义线性表的最大长度

typedef int Elemtype //假定表中元素类型是int

typedef struct{

ElemType data [MaxSize]; //顺序表的元素(数组)

int length; //顺序表的当前长度

}SqList; //顺序表的类型定义

这里线性表的数组data是静态分配（开数组)的，大小固定,一旦满了就溢出。

其实数组还可以动态分配空间，存储数组的空间是在程序执行过程中通过动态存储分配语句分配。

typedef int Elemtype;

typedef struct{

ElemType *data; //指示动态分配数组的指针

int MaxSize,length; //数组的最大容量和当前个数

} SeqList;

C语言的动态分配语句

#define InitSize 100

SeqList L;

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

注意：动态分配并不是链式存储，同样还是属于顺序存储结构，只是分配的空间大小可以在运。

三、总结

1. 顺序表最主要的特点是随机访问（C语言中基于数组），即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。
2. 顺序表的存储密度高，每个结点只存储数据元素。无需给表中元素花费空间建立它们之间的逻辑关系（因为物理位置相邻特性决定）
3. 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。