image.png

顺序存储结构

用一段连续的存储单元依次存储线性表的数据元素
优缺点：
需要预分配存储空间，分大了浪费，小了容易发生上溢

顺序表

使用数组实现，一组地址连续的存储单元，数组大小有两种方式指定，一是静态分配，二是动态扩展。
注：线性表从1开始，而数组从0开始。

image.png

优点：随机访问特性，查找O(1)时间，存储密度高；逻辑上相邻的元素，物理上也相邻；
缺点：插入删除需移动大量元素。

静态分配

静态分配是是数据定义时确定数据空间大小，程序在编译阶段就会变量大小，在程序开始运行前就为它分配好空间。
特点:
在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将产生溢出，就会导致程序崩溃

#define MaxSize 50 // 定义顺序表的最大长度
#typedef int ElemType;
typedef struct _SqList{
    ElemType data [MaxSize] ; // 顺序表的元素
    int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义

动态分配

动态分配是在定义线性表的存储类型时，不是定义好一个数组空间，而是只是定义一个指针，等到程序运行时通过new操作得到一个用于存储线性表的空间，并把这个空间的首地址赋给这个指针。
访问动态存储分配方式的线性表同访问静态存储分配方式的情况完全相同，既可以使用指针又可以使用数组下标的方式。
特点：
而动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，可以另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要一次性地划分所有所需空间给线性表。

#define InitSize 100  // 表长度的初始定义
#typedef int ElemType;
typedef struct _SeqList{
    ElemType *node;  // 指示动态分配数组的指针
    int MaxSize, length;  // 数组的最大容量和当前个数
} SeqList;  // 动态分配数组顺序表的类型定义