顺序表
顺序表用数组实现,是最简单也最常用的存储方式。核心操作包括插入、删除、查找。
在第 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 个元素;平均移动 个元素。因此:
删除操作:同理,平均移动 个元素,。
按位查找:通过下标直接访问,。
顺序表插入/删除时,需整体移动元素,时间复杂度为 ;而链表只需修改指针,插入/删除为 。二者截然不同,易混淆!
习题 1
在长度为 n 的顺序表中,在第 i(1≤i≤n+1)个位置插入一个元素,需要移动的元素个数为( )
A. n-i+1 B. n-i C. i D. i-1
解题思路:
本题考查顺序表按位置插入时的元素移动个数。顺序表靠连续存储保证逻辑相邻,插入会让插入点之后的元素整体后移,因此移动个数就是从插入位置到表尾的元素个数。
详细步骤:
- 在第 个位置插入元素时,为保持原有元素的相对次序,第 个及其之后的元素都必须向后移动一格。
- 需要移动的元素是从第 个到第 个,共 个。
- 当 (在表尾插入)时,移动个数为 0,与公式一致。
最终答案:
A。
习题 2
如何实现线性表的遍历?
解题思路:
本题考查顺序表与链表的遍历方式。两者都要按逻辑次序访问每个元素,区别在于“如何定位下一个元素”:顺序表靠下标自增,链表靠指针后移。
详细步骤:
- 顺序表:元素存放在连续空间中,利用下标循环 for (i = 0; i < L.length; i++) 依次访问 L.data[i]。
- 链表:从首元结点开始,令指针 p 指向当前结点,访问后执行 p = p->next,直到 p 为空。
- 两者访问的元素逻辑次序相同,差别只是寻址方式,因此复杂度都是 。
最终答案:
顺序表:利用下标循环,for (i = 0; i < L.length; i++) 依次访问 L.data[i]。链表:从首元结点开始,利用指针 p 逐结点访问,p = p->next 直到 p 为空。
