顺序表

删除特定元素x

对一个长度为n的顺序表，删除所有值为x的元素

法一：从头到位扫描顺序表，用变量k记录当前位置i前面的所有值为x的元素个数，如果当前元素不为x，就前移k个位置

void delete_x_1(SqList &L, ElemType x){
    int k=0, i=0;
    while(i<L.length){
       if(L.data[i]==x)
           k+=1;
       else
           L.data[i-k]=L.data[i];
       i++;
    }
    L.length=L.length-k;
}

法二：使用头尾指针（head=1，tail=n），从两端向中间移动，在遇到最左端的值为x的元素后，将最右端值非x的元素移过去，同时两指针向中间移动，直至相遇，但这种方法会改变元素原来的相对位置。

#include <stdio.h>

// 函数声明
int delete_x(int SqList[], int n, int x);

int main() {
    int arr[] = {1, 2, 3, 2, 4, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 2;
    
    // 调用函数并获取删除x后有效元素的个数
    int new_n = delete_x(arr, n, x);
    
    printf("After deleting %d, the sequence list is: ", x);
    for(int i = 0; i < new_n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

// 删除顺序表中所有值为x的元素的函数
int delete_x(int SqList[], int n, int x) {
    int i = 0; // 头指针
    int j = n - 1; // 尾指针
    
    while (i <= j) {
        // 找到最左端值为x的元素
        while (i <= j && SqList[i] != x) {
            i++;
        }
        // 找到最右端值不为x的元素
        while (i <= j && SqList[j] == x) {
            j--;
        }
        
        // 如果i<=j，交换这两个元素，然后移动指针
        if (i <= j) {
            int temp = SqList[i];
            SqList[i] = SqList[j];
            SqList[j] = temp;
            i++;
            j--;
        }
    }
    
    // i的位置是第一个可能为x的位置，因此有效元素数量为i
    return i;
}

删除重复元素

删除有序顺序表中的重复元素，使剩余元素都各不相同，如[1，2，2，2，2，3，3，3，4，4，5]——>[1，2，3，4，5]

bool delete_same(SqList &L){
    if(L.length<=1) {
        return true;
    }
    int i,j;
    for(i=0,j=1;j<L.length;j++){
        if(L.data[i]!=L.data[j]){
            L.data[++i]=L.data[j];
        }
    }
    L.length=i+1;
    return true;
}

合并有序顺序表

循环右移

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

189. 轮转数组 - 力扣（LeetCode）

交换位置

一个数组a[m+n]存放了两个线性表（a1 ~ an）和（b1 ~ bn），编写函数交换他们的位置

思路：先将整个数组逆转为[bn ~ b1 ，an ~ a1]，然后分别对两个线性表再进行逆转—→[b1 ~ bn，a1 ~ an]，即为所求

void reverse(DataType a[], )

查找公共部分

给出三个序列A，B，C，长度均为n，且无重复的递增序列。请输出三个序列共有的所有元素。

查找中位数

一个长度为L的升序序列S，位于

查找主元素

查找未出现的最小整数

计算最小距离