Skip to content

Latest commit

 

History

History
125 lines (88 loc) · 3.43 KB

2.2.2 顺序表上基本操作的实现.md

File metadata and controls

125 lines (88 loc) · 3.43 KB
Raw

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


  • 插入操作

    bool ListInsert(SqList &L, int i, ElemType e) {
    if(i<1 || i>L.length+1)
        return false;
    if(L.length >= MaxSize)
        return false;
    for(int j=L.length; j>=i; j--)
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;
    L.length++;

    return true;
}

    • eg：ListInsert(L, 3, 'e')

      • 执行前：L.data：['a', 'c', 'g', 'w', 'f', '', '']

      • 执行后：L.data：['a', 'c', 'e', 'g', 'w', 'f', '']

    • 时间复杂度：

      • 最好时间复杂度：在尾部进行插入，不用进行数组元素的“向后移动”，故此时的时间复杂度为 O(1)

      • 最坏时间复杂度：在头部进行插入每个数组元素均向后进行移动，时间复杂度为 O(n)

      • 平均时间复杂度：（不可插入情况不做讨论）可以插入的位置有 n+1 个，所以每个位置插入的概率是 1/(n+1)，每种概率下数组元素移动的距离为 n-i+1，根据等差数列求和公式，T(n) = O(n)

  • 删除操作

    bool ListDelete(SqList &L, int i, ElemType &e) {
    if(i<1 || i>L.length)
        return false;
    e = L.data[i-1];
    for(int j=i; j<L.length; j++)
        L.data[j-1] = L.data[j];
    L.length--;

    return true;
}

    • eg：ListDelete(L, 3, e)

      • 执行前：L.data：['a', 's', 'd', 'f', 'g', 'h', '']

      • 执行后：L.data：['a', 's', 'f', 'g', 'h', '', '']

    • 时间复杂度：

      • 最好时间复杂度：删除最后一个数据元素，不用进行数组元素的“向前移动”，故此时的时间复杂度为 O(1)

      • 最坏时间复杂度：删除头部数据元素，第二个开始每个数组元素均向前进行移动，时间复杂度为 O(n)

      • 平均时间复杂度：（不可删除情况不做讨论）可以删除的位置有 n 个，所以每个位置被删除的概率是 1/n，每种概率下数组元素移动的距离为 n-i，根据等差数列求和公式，T(n) = O(n)

  • 按值查找

    int LocateElem(SqList L, ElemType e) {
    int i;
    for(i=0; i<L.length; i++)
        if(L.data[i] == e)
            return i+1;
    return 0;
}

    • 时间复杂度：

      • 最好时间复杂度：查找第一个数据元素，此时的时间复杂度为 O(1)

      • 最坏时间复杂度：查找最后一个数据元素，此时的时间复杂度为 O(n)

      • 平均时间复杂度：（不可查找情况不做讨论）可以查找的位置有 n 个，所以每个位置被查找的概率是 1/n，每种概率下查找需要遍历到的数组元素为 i，根据等差数列求和公式，T(n) = O(n)


💡 题型

  xxx

单项选择题

  1. xxxx（ ）

    A. xxx
    B. XX
    C. Xx
    D. xX

    查看解析

    答案：x

-- 完 --