顺序表

顺序表用数组实现,是最简单也最常用的存储方式。核心操作包括插入、删除、查找。

顺序表的插入

在第 i 个位置插入元素 x,需要将第 i 个到最后一个元素依次后移一位。

#define MaxSize 100
typedef struct {
    int data[MaxSize];
    int length;  // 当前长度
} SqList;

// 在第 i 个位置插入元素 x(i 从 1 开始)
bool ListInsert(SqList &L, int i, int x) {
    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] = x;
    L.length++;
    return true;
}

顺序表的删除

删除第 i 个位置的元素,需要将第 i+1 个到最后一个元素依次前移一位。

// 删除第 i 个位置元素,用 e 返回
bool ListDelete(SqList &L, int i, int &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;
}

复杂度推导

插入操作:最好情况(插在表尾)移动 0 个元素;最坏情况(插在表头)移动 n 个元素;平均移动 n2\frac{n}{2} 个元素。因此:

Tinsert(n)=O(n)T_{insert}(n) = O(n)

删除操作:同理,平均移动 n−12\frac{n-1}{2} 个元素,Tdelete(n)=O(n)T_{delete}(n) = O(n)。

按位查找:通过下标直接访问,Tget(n)=O(1)T_{get}(n) = O(1)。

习题

习题 1

在长度为 n 的顺序表中,在第 i(1≤i≤n+1)个位置插入一个元素,需要移动的元素个数为( )

A. n-i+1 B. n-i C. i D. i-1

顺序表插入操作元素移动时间复杂度

解题思路:

本题考查顺序表按位置插入时的元素移动个数。顺序表靠连续存储保证逻辑相邻,插入会让插入点之后的元素整体后移,因此移动个数就是从插入位置到表尾的元素个数。

详细步骤:

  1. 在第 ii 个位置插入元素时,为保持原有元素的相对次序,第 ii 个及其之后的元素都必须向后移动一格。
  2. 需要移动的元素是从第 ii 个到第 nn 个,共 n−i+1n - i + 1 个。
  3. 当 i=n+1i = n + 1(在表尾插入)时,移动个数为 0,与公式一致。

最终答案:

A。

习题 2

如何实现线性表的遍历?

顺序表链表遍历操作指针操作

解题思路:

本题考查顺序表与链表的遍历方式。两者都要按逻辑次序访问每个元素,区别在于“如何定位下一个元素”:顺序表靠下标自增,链表靠指针后移。

详细步骤:

  1. 顺序表:元素存放在连续空间中,利用下标循环 for (i = 0; i < L.length; i++) 依次访问 L.data[i]。
  2. 链表:从首元结点开始,令指针 p 指向当前结点,访问后执行 p = p->next,直到 p 为空。
  3. 两者访问的元素逻辑次序相同,差别只是寻址方式,因此复杂度都是 O(n)O(n)。

最终答案:

顺序表:利用下标循环,for (i = 0; i < L.length; i++) 依次访问 L.data[i]。链表:从首元结点开始,利用指针 p 逐结点访问,p = p->next 直到 p 为空。

发现内容有问题?

告诉我们哪里需要改进。