2.2 线性表的顺序表示

[!info] 基础概念相关提炼内容见 array-list。

顺序表的定义 Sequence List

线性表的顺序存储 -> 顺序表
顺序表的特点是表中元素的逻辑顺序与其物理顺序相同
顺序表的结构类型定义
- 静态分配
- 动态分配
- C 的动态分配语句
- L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize;
- C++的动态分配语句
- L.data = new ElemType[InitSize];

顺序表上基本操作的实现

插入操作
- 最好情况：表尾插入，时间复杂度为 $O(1)$
- 最坏情况：表头插入，时间复杂度为 $O(n)$

// 插入操作代码
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1 )          // i值不合法
        return false;
    else if (L.length >= MAXSIZE)            // 当前存储空间已满
        return false;
    for (int j = L.length ; j >= i ; j--)
        L.elem[j] = L.elem[j - 1];           // 插入位置及之后位置后移
    L.elem[i - 1] = e;                       // 将新元素放入第i个位置
    L.length++;                              //表长增加1
    return true;
}

删除操作
- 最好情况：删除表尾元素，时间复杂度为 $O(1)$
- 最坏情况：删除表头元素，时间复杂度为 $O(n)$
- 平均情况： $E_{del} = \frac 1n \sum^n_{i=1}(n-i)=\frac 1n \frac {(n-1)n}2 = \frac{n-1}2$ ，时间复杂度为 $O(n)$

// 删除操作代码
bool ListDelete(SqList& L, int i, ElemType e) {
    if (i < 1 || i > L.length)             // 判断i值是否合理
        return false;
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++)
        L.elem[j - 1] = L.elem[j];
    L.length--;
    return true;
}

按值查找（顺序查找）
- 最好情况：查找的元素就在表头，时间复杂度为 $O(1)$
- 最坏情况：查找的元素在表尾（或不存在），时间复杂度为 $O(n)$
- 平均情况： $E_{find} = \frac 1n \sum^n_{i=1}i= \frac{n+1}2$ ，时间复杂度为 $O(n)$

// 按值查找（顺序查找）代码
int LocateElem(SqList &L, ElemType e){
    int i;
    for(i = 0; i < L.length; i++){
        // TODO
    }
}

顺序表的定义 Sequence List​

顺序表上基本操作的实现​

习题​

顺序表的定义 Sequence List

顺序表上基本操作的实现

习题