数据结构

一、顺序表定义

1、 顺序表的插入

数据结构的插入代码

bool ListInsert(SqList &L,int i,ElemType e){
    // 1. 判断插入位序i是否合法：逻辑位序范围是1≤i≤L.length+1
    if(i<1||i>L.length+1) 
        return false;
    // 2. 判断顺序表存储空间是否已满
    if(L.length>=MaxSize)
        return false;
    // 3. 从后往前移动元素：把第i个及之后元素向后挪一位，避免覆盖
    for(int j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    // 4. 在腾出的空位放入新元素e（逻辑第i位对应数组下标i-1）
    L.data[i-1]=e;
    // 5. 顺序表有效长度+1
    L.length++;
    return true;
}

1. 位序与数组下标区分

• 代码里的位序 i 从 1 开始计数（面向用户的逻辑位置），而数组data下标从 0 开始，所以第i个逻辑元素存在data[i-1]处。
• 判断合法时用L.length+1：最多可以在表尾最后一个元素的下一位（L.length+1位）插入；
• 移动元素循环只用L.length：已有元素最大逻辑位序是L.length，从最后一个已有元素开始后移。

2. 元素移动方向必须从后往前

   如果从前往后移，会把后面还没移动的元素提前覆盖，导致数据丢失，这是选择题高频易错点。

3. 失败的两种情况

• i<1或i>L.length+1：插入位置不在合法区间；
• L.length>=MaxSize：数组已经存满，没有多余空间插入新元素。

1.1、举实例演示

设MaxSize=5，初始L.length=3，data=[10,20,30]，在i=2插入e=15：

1. 校验：1≤2≤3+1、3<5，合法；

2. 循环

   j=3,2

   ：

   • j=3：data[3]=data[2]=30
   • j=2：data[2]=data[1]=20

3. data[1]=15，数组变为[10,15,20,30]；

4. L.length=4，插入成功返回true。

1.2、时间复杂度分析

• 最好情况：在表尾（i=L.length+1）插入，循环不执行，(O(1))；
• 最坏情况：在表头（i=1）插入，要移动全部n个元素，(O(n))；
• 平均情况：平均移动n/2个元素，时间复杂度(O(n))

2.1、 顺序表的删除

bool ListDelete(SqList &L,int i,ElemType &e){
    //1.判断删除位序合法性：1≤i≤L.length
    if(i<1 || i>L.length)
        return false;
    //2.取出被删元素
    e = L.data[i-1];
    //3.元素前移：从i+1位开始往前覆盖
    for(int j=i;j<L.length;j++)
        L.data[j-1] = L.data[j];
    //4.长度减1
    L.length--;
    return true;
}

1. 位置合法判断差异

• 插入：1≤i≤L.length+1（可插在末尾元素之后）
• 删除：1≤i≤L.length（只能删已有元素，不能删末尾空位）

2. 元素移动方向相反

• 插入：

  从后往前移

  （防止后方数据被覆盖）

j = L.length; j >= i; j--

• 删除：

  从前往前移

  （用后面元素覆盖前面被删位置）

j = i; j < L.length; j++

3. 参数区别

删除多了引用参数&e，用来把被删掉的元素值返回出去，考研伪代码固定写法。

4. 时间复杂度

• 最好：删除最后一个元素，循环不执行，(O(1))
• 最坏：删除第一个元素，移动全部(n-1)个元素，(O(n))
• 平均：移动约n-1/2)次，整体(O(n))

5、边界易错点

1. 不能删除i=L.length+1，这个位置本来就没有元素；
2. 循环终止条件j<L.length：最后一个元素下标是L.length-1，j 最大取到L.length-1；
3. 数组下标统一做i-1换算：逻辑位序转数组下标。

2.2、 顺序表的查询

一、两种查询：按位查找（GetElem）、按值查找（LocateElem）

1. 按位查找（给定逻辑位置 i，取元素）

考研伪代码

按照位置查找

bool GetElem(SqList L,int i,ElemType &e){
    // 合法位序：1≤i≤L.length
    if(i<1 || i>L.length)
        return false;
    e = L.data[i-1]; //逻辑位序转数组下标
    return true;
}

最好：第一个元素就匹配，(O(1))

最坏：遍历完所有元素都不匹配，(O(n))

平均时间复杂度：(O(n))

2、按照值查找

int LocateElem(SqList L,ElemType e){
    for(int i=0;i<L.length;i++){
        if(L.data[i]==e)
            return i+1; //下标转逻辑位序
    }
    return 0; //查找失败返回0
}