线性表的顺序表示

顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第 个元素的存储位置后面紧接着存储的是第 个元素，称 为元素 在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

假设线性表 L 储存的起始位置为 LOC(A)，sizeof(ElemType) 是每个数据元素所占用储存空间的大小，则表 L 所对应的顺序存储如下图所示。

注意：线性表中元素的位序是从 1 开始的，而数组中元素的下标是从 0 开始的。

顺序表的实现方式

静态分配

假定线性表的元素类型为 ElemType（以下具体操作使用int类型），则线性表的顺序存储类型描述为：

#define MaxSize 10             // 定义线性表的最大长度
typedef struct{
    ElemType data[MaxSize];    // 顺序表的元素
    int length;                // 顺序表的当前长度
} StaticSqList;                // 顺序表的类型定义 Sq:sequence

一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序崩溃。

// 初始化一个顺序表
void InitList(StaticSqList &L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;  // 将所有数据元素设置默认值(可省略)
    }
    L.length = 0;       // 顺序表初始长度为0
}
int main(){
    StaticSqList L;     // 声明一个顺序表
    InitList(L);        // 初始化顺序表
    // ...  相关操作
    return 0;
}

动态分配

而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。

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

• C 的初始动态分配语句为：L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
• C++ 的初始动态分配语句为：L.data = new ElemType[InitSize];

  注意：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。

#include <cstdlib>
// 初始化
void InitList(DynamicSqList &L) {
    // 使用malloc函数申请一片连续的储存空间
    L.data = (int *) malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}
/**
 * 动态增加数组的长度
 * @param L 顺序表
 * @param len 在原基础上扩展的大小
 */
void IncreaseSize(DynamicSqList &L, int len) {
    int *p = L.data;
    L.data = (int *) malloc((L.MaxSize + len) * sizeof(int));
    for (int i = 0; i < L.length; i++) {     // 将数据复制到新区域
        L.data[i] = p[i];
    }
    L.MaxSize += len;    // 增加顺序表的最大长度
    free(p);             // 释放原来的内存空间
}
int main(){
    DynamicSqList L;     // 声明一个顺序表
    InitList(L);         // 初始化顺序表
    // ... 插入操作
    IncreaseSize(L,5);
    return 0;
}

顺序表的特点

• 随机访问，即通过首地址和元素序号可在时间 #card=math&code=O%281%29&id=oCVXA) 内找到指定的元素。
• 存储密度高，每个结点只存储数据元素。
• 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
• 插入、删除操作不方便，逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

顺序表上基本操作的实现

插入操作

在顺序表 L 的第 i（1≤i≤L.length+1）个位置插入新元素 e。

• 若 i 的输入不合法，则返回 false，表示插入失败；
• 否则，将顺序表的第 i 个元素及其后的所有元素右移一个位置，腾出一个空位置插入新元素 element，顺序表长度增加 1，插入成功，返回 true。

  /**
  * 插入操作
  * @param L 顺序表
  * @param i 位置
  * @param element 要插入的元素
  * @return 插入成功true,失败false
  */
  bool ListInsert(StaticSqList &L, int i, int element) {
    // 判断i的范围是否有效
    if (i < 1 || i > L.length + 1) {
        return false;
    }
    // 储存已满不能插入
    if (L.length >= MaxSize) {
        return false;
    }
    // 将第i个元素及之后的元素后移
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    // 在位置 i 处放入e
    L.data[i - 1] = element;
    // 线性表长度加1
    L.length++;
    return true;
  }
  

  最好情况：在表尾插入（即 ）,元素后移语句不执行，时间复杂度为 #card=math&code=O%281%29&id=Ex5mR)。
  最坏情况：在表头插入（即 ）,元素后移语句将执行 次，时间复杂度为 #card=math&code=O%28n%29&id=u7Gea)。
  平均情况：假设 #card=math&code=p_i%20%5C%20%28p_i%3D%5Cfrac%7B1%7D%7Bn%2B1%7D%20%29&id=DQnSn) 是在第 个位置上插入一个结点的概率，则在长度为 的线性表中插入一个结点时，所需移动结点的平均次数为：

因此，线性表插入算法的平均时间复杂度为 。

删除操作

删除顺序表 L 中第 i（1≤i≤L.length+1）个位置的元素，若成功则返回 true，并将被删除的元素用引用变量 element 返回，否则返回 false。

/**
 * 删除操作
 * @param L
 * @param i
 * @param element
 * @return
 */
bool ListDelete(StaticSqList &L, int i, int &element) {
    // 判断i的范围是否有效
    if (i < 1 || i > L.length + 1) {
        return false;
    }
    // 将被删除的元素赋值给element
    element = L.data[i - 1];
    // 将第i个位置后的元素前移
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

最好情况：删除表尾元素（即 ），无须移动元素，时间复杂度为 #card=math&code=O%281%29&id=ELf7i)。
最坏情况：删除表头元素（即 ），需移动除第一个元素外的所有元素，时间复杂度为 #card=math&code=O%28n%29&id=h35pb)。
平均情况：假设 #card=math&code=p_i%20%5C%20%28p_i%3D%5Cfrac%20%7B1%7D%7Bn%7D%20%29&id=d8dlj) 是删除第 个位置上结点的概率，则在长度为 的线性表中删除一个结点时，所需移动结点的平均次数为：

因此，线性表删除算法的平均时间复杂度为 。

按位查找

在顺序表 L 中，获取第 i 个位置的元素的值。

/**
 * 按位查找
 * @param L
 * @param i
 * @return 第i个位置的元素的值
 */
int GetElem(StaticSqList L, int i) {
    return L.data[i - 1];
}

时间复杂度：#card=math&code=O%281%29&id=UFw15)

按值查找

在顺序表 L 中查找第一个元素值等于 element 的元素，并返回其位序。

/**
 * 按值查找
 * @param L
 * @param element 需要查找的元素值
 * @return 查找到则返回位序(索引+1)，否则返回0
 */
int LocateElem(StaticSqList L, int element) {
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] == element) {
            return i + 1; // 下标为 i 的元素值等于 element,返回其位序 i+1
        }
    }
    return 0;
}

• 最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为 #card=math&code=O%281%29&id=n2DAW)。
• 最坏情况：查找的元素在表尾（或不存在）时，需要比较 次，时间复杂度为 #card=math&code=O%28n%29&id=Dr33k)。
• 平均情况：假设 #card=math&code=p_i%20%5C%20%28p_i%3D%5Cfrac%20%7B1%7D%7Bn%7D%29&id=yO5az) 是查找的元素在第 i （1≤i≤L. length）个位置上的概率，则在长度为 的线性表中查找值为 e 的元素所需比较的平均次数为：

因此，线性表按值查找算法的平均时间复杂度为 。