线性表的操作

插入

插入操作是指向线性表中添加新元素的操作，可以在表的任意位置进行插入。插入操作的关键在于确定要插入的位置，以及将新元素正确地插入到指定位置之后，可能需要调整表中其他元素的位置。

顺序表

插入(元素, 位置):
    如果 位置 < 0 或 位置 > 表的长度 + 1:
        返回 "无效位置"
    
    如果 表已满:
        返回 "表已满，无法插入"
    
    如果 位置 == 0:  // 插入到表头
        将所有元素右移一位
        表[位置] = 元素
    否则 如果 位置 == 表的长度:  // 插入到表尾
        表[位置] = 元素
    否则:  // 插入到中间某个位置
        将所有位置大于插入位置的元素右移一位
        表[位置] = 元素
    
    表长度增加1

链表

链表插入(元素, 位置):
    如果 位置 < 0 或 位置 > 链表长度:
        返回 "无效位置"
    
    创建一个新节点，并将新元素存储在节点中
    
    如果 位置 == 0:  // 插入到链表头部
        将新节点的下一个节点指向链表的头节点
        将链表的头节点指向新节点
    否则:
        获取链表中第 (位置 - 1) 个节点
        将新节点的下一个节点指向第 (位置 - 1) 个节点的下一个节点
        将第 (位置 - 1) 个节点的下一个节点指向新节点
        
    链表长度增加1

删除

删除操作的实现涉及将被删除元素从表中移除，并可能需要调整其他元素的位置以保持表的结构正确性。

顺序表

删除(位置):
    如果 位置 < 0 或 位置 >= 表的长度:
        返回 "无效位置"
    
    被删除元素 = 表[位置]
    
    如果 位置 == 0:  // 删除表头元素
        将所有元素左移一位
    否则 如果 位置 == 表的长度 - 1:  // 删除表尾元素
        将表的长度减1
    否则:  // 删除中间某个位置的元素
        将位置后面的所有元素左移一位
    
    返回被删除元素

链表

链表删除(位置):
    如果 位置 < 0 或 位置 >= 链表长度:
        返回 "无效位置"
    
    如果 位置 == 0:  // 删除表头元素
        被删除节点 = 链表头节点
        链表头节点 = 链表头节点的下一个节点
    否则:
        获取链表中第 (位置 - 1) 个节点
        被删除节点 = 第 (位置 - 1) 个节点的下一个节点
        将第 (位置 - 1) 个节点的下一个节点指向被删除节点的下一个节点
    
    链表长度减少1
    返回被删除节点的值

查找

折半查找

也称为二分查找，通常用于在有序数组或列表中查找特定元素的位置。
时间复杂度为O(log n)，其中n是元素数量

伪代码

函数 binary_search(数组 arr, 目标值 target) -> 整数
    左边界 left 设为 0
    右边界 right 设为 数组长度 - 1
    
    当 左边界 <= 右边界 时执行：
        中间位置 mid 设为 (左边界 + 右边界) / 2
        
        如果 数组[mid] == target，则返回 mid
        否则如果 数组[mid] < target，则 左边界 设为 mid + 1
        否则 右边界 设为 mid - 1
    
    返回 -1  // 没有找到目标值

C++

int binary_search(vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)  return mid; // 找到目标值，返回索引
        else if (arr[mid] < target)  left = mid + 1; // 目标值在右半部分，更新左边界
        else right = mid - 1; // 目标值在左半部分，更新右边界
    }

    return -1; // 没有找到目标值
}

修改

线性表的修改操作通常指的是更新或替换表中某个位置的元素。这可以包括更新元素的值或者完全替换掉原来的元素。

顺序表

修改(位置, 新元素):
    如果 位置 < 0 或 位置 >= 表的长度:
        返回 "无效位置"
    
    表[位置] = 新元素

链表

链表修改(位置, 新元素):
    如果 位置 < 0 或 位置 >= 链表长度:
        返回 "无效位置"
    
    找到链表中第 (位置) 个节点
    将该节点的值更新为 新元素

遍历

链表的遍历操作是指依次访问链表中的每个节点，并对每个节点执行某种操作或者获取节点的值。遍历操作可以用来查找特定值、打印链表的所有元素、计算链表的长度等

顺序表

顺序表遍历(顺序表):
    对于 每个元素 在 顺序表 中:
        执行某种操作（如打印元素的值）

链表

链表遍历(链表头):
    当前节点 = 链表头
    当 当前节点 不为空时:
        对当前节点执行某种操作（如打印节点的值）
        当前节点 = 当前节点的下一个节点

获取长度

线性表一般包含表示长度的属性（如 length），可以直接读取该属性来获取链表的长度，而不需要额外编写方法来获取长度

顺序表

获取长度(顺序表):
    返回 顺序表中元素的个数

链表

获取链表长度(链表头):
    计数 = 0
    当前节点 = 链表头
    当 当前节点 不为空时:
        计数增加1
        当前节点 = 当前节点的下一个节点
    
    返回 计数

清空

判空

反转

排序