顺序表（SqList）笔记

1. 顺序表的基本概念

顺序表是用一段地址连续的存储单元依次存储数据元素的线性结构，通常借助数组实现。其特点是：

• 元素在内存中连续存放
• 可以通过下标随机访问元素（时间复杂度 O (1)）
• 插入和删除操作可能需要移动大量元素（时间复杂度 O (n)）

2. 顺序表的定义与初始化

2.1 数据结构定义

#define MaxSize 10  // 定义顺序表的最大容量
typedef struct {
    int data[MaxSize];  // 用静态数组存储数据元素
    int length;         // 记录当前顺序表的长度
} SqList;

2.2 初始化函数

void InitList(SqList& L) {
    L.length = 0;  // 初始长度为0（空表）
    // 可选：初始化数组元素为0
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;
    }
}

• 初始化的核心是将 length 设为 0
• C++ 中使用引用（&）传参，相当于直接操作原变量
• 在 C 语言中需用指针（*）替代引用

3. 基本操作实现

3.1 插入操作

在第 i 个位置（位序从 1 开始）插入元素 e

void ListInsert(SqList& L, int i, int e) {
    // 合法性检查
    if (i < 1 || i > L.length + 1) {
        cout << "插入位置不合法！" << endl;
        return;
    }
    if (L.length >= MaxSize) {
        cout << "顺序表已满，无法插入！" << endl;
        return;
    }

    // 元素后移（从最后一个元素开始）
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;  // 插入新元素（位序转下标）
    L.length++;         // 长度加1
}

• 插入位置范围：[1, L.length + 1]
• 当插入位置等于 L.length + 1 时，为表尾插入，无需移动元素
• 时间复杂度：O (n)，取决于需要移动的元素个数

3.2 删除操作

删除第 i 个位置的元素，并返回删除的值

bool ListDelete(SqList& L, int i, int& e) {
    // 合法性检查
    if (i < 1 || i > L.length) {
        cout << "删除位置不合法！" << endl;
        return false;  // 删除失败
    }

    e = L.data[i - 1];  // 保存被删除的元素

    // 元素前移（从删除位置的下一个元素开始）
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;  // 长度减1
    return true;  // 删除成功
}

• 删除位置范围：[1, L.length]
• 当删除最后一个元素时，无需移动其他元素
• 时间复杂度：O (n)，取决于需要移动的元素个数

3.3 打印操作

输出顺序表中的所有元素

void PrintList(SqList& L) {
    cout << "顺序表元素（共" << L.length << "个）：";
    for (int i = 0; i < L.length; i++) {
        cout << L.data[i] << " ";
    }
    cout << endl;
}

4. 完整示例代码

#include <iostream>
using namespace std;

#define MaxSize 10  // 顺序表最大容量

// 顺序表类型定义
typedef struct {
    int data[MaxSize];  // 存储数据的静态数组
    int length;         // 当前元素个数
} SqList;

// 初始化顺序表
void InitList(SqList& L) {
    L.length = 0;  // 初始长度为0（空表）
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;  // 数组元素初始化为0
    }
}

// 插入操作：在第i个位置插入元素e（位序从1开始）
void ListInsert(SqList& L, int i, int e) {
    // 合法性检查
    if (i < 1 || i > L.length + 1) {
        cout << "插入位置不合法！" << endl;
        return;
    }
    if (L.length >= MaxSize) {
        cout << "顺序表已满，无法插入！" << endl;
        return;
    }

    // 元素后移（从最后一个元素开始）
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;  // 插入新元素（注意位序与下标转换）
    L.length++;         // 长度+1
}

// 删除操作：删除第i个位置的元素，并用e返回删除的值
bool ListDelete(SqList& L, int i, int& e) {
    // 合法性检查
    if (i < 1 || i > L.length) {  // 注意：删除时i不能超过当前长度
        cout << "删除位置不合法！" << endl;
        return false;  // 删除失败
    }

    e = L.data[i - 1];  // 保存要删除的元素

    // 元素前移（从删除位置的下一个元素开始）
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];  // 覆盖前一个位置
    }
    L.length--;  // 长度-1
    return true;  // 删除成功
}

// 打印顺序表元素
void PrintList(SqList& L) {
    cout << "顺序表元素（共" << L.length << "个）：";
    for (int i = 0; i < L.length; i++) {
        cout << L.data[i] << " ";
    }
    cout << endl;
}

int main() {
    SqList L;
    InitList(L);

    // 演示插入操作
    ListInsert(L, 1, 10);
    ListInsert(L, 2, 20);
    ListInsert(L, 3, 30);
    ListInsert(L, 4, 40);
    PrintList(L);  // 输出：10 20 30 40

    // 演示删除操作
    int delVal;
    bool isDeleted = ListDelete(L, 2, delVal);  // 删除第2个元素（20）
    if (isDeleted) {
        cout << "删除成功，删除的元素是：" << delVal << endl;
    }
    PrintList(L);  // 输出：10 30 40

    // 测试边界情况
    ListDelete(L, 5, delVal);  // 位置5超出当前长度（3），删除失败

    return 0;
}

5. 关键知识点总结

5.1 位序与下标的关系

• 位序：顺序表中元素的位置编号，从 1 开始
• 下标：数组的索引，从 0 开始
• 转换关系：位序 i 对应下标 i-1

5.2 插入与删除的对比

操作	位置范围	元素移动方向	循环范围
插入	[1, L.length + 1]	向后移动	j 从 L.length 到 i
删除	[1, L.length]	向前移动	j 从 i 到 L.length-1

5.3 顺序表的优缺点

• 优点：
  • 可以随机访问，查询效率高（O (1)）
  • 存储密度高，无需额外存储指针信息
• 缺点：
  • 插入删除操作效率低（O (n)）
  • 大小固定，不利于动态扩展
  • 连续存储要求有大片连续的内存空间

6. 适用场景

顺序表适合用于：

• 频繁查询数据，较少进行插入删除操作的场景
• 已知数据量大小，不需要频繁扩容的场景
• 需要快速随机访问元素的场景