线性表

线性表的逻辑结构

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n= 0时线性表是一个空表。若用L命名线性表，则其一般表示为L= (a1,a2, …,ai,ai+1,… ,an）

特点：线性表中第一个元素称为表头元素；最后一个元素称为表尾元素。
除第一个元素外，每个元素有且仅有一个直接前驱。
除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的顺序存储

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

静态分配

建立顺序表的三个属性:

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

定义

#define MaxSize 10
//定义最大长度
typedef struct{
    ElemType data[MaxSize];    //用静态的“数组”存放数据元素
    int length;    //顺序表的当前长度
}SqList;    //顺序表的类型定义（静态分配方式）

初始化

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;//将所有元素的初始值默认设置为0
        //这一步其实可以省略，但是省略之后，有可能受到内存中"脏数据"的影响
    }
    L.length = 0;
}

动态分配