3.顺序表

#include<iostream>
#include<cstdio>
#include<cmath>

#define MaxSize 50
using namespace std;
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L) {
    L.length = 0;
}

int GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length)
        return 0;
    e = L.data[i - 1];
    return i;
}

int LocateElem(SqList L, ElemType e) {
    int i = 0;
    while (i < L.length && L.data[i] != e) i++;
    if (i >= L.length)
        return 0;
    else
        return i + 1;
}

int ListInsert(SqList &L, ElemType e, int i) {
    int j;
    if (i < 1 || i > L.length + 1)
        return 0;
    i--;
    for (j = L.length; j > i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i] = e;
    L.length++;
    return 1;
}

int ListDelete(SqList &L, int i, ElemType &e) {
    int j;
    if (i < 1 || i > L.length)
        return 0;
    i--;
    e = L.data[i];
    for (j = i; j < L.length - 1; j++)
        L.data[j] = L.data[j + 1];
    L.length--;
    return 1;
}

void Merge(SqList L1, SqList L2, SqList &L3) {
    int i = 0, j = 0, k = 0;
    while (i < L1.length && j < L2.length) {
        if (L1.data[i] < L2.data[j]) {
            L3.data[k] = L1.data[i];
            i++;
            k++;
        } else {
            L3.data[k] = L2.data[j];
            j++;
            k++;
        }

    }
    while (i < L1.length) {
        L3.data[k] = L1.data[i];
        i++;
        k++;
    }
    while (j < L2.length) {
        L3.data[k] = L2.data[i];
        j++;
        k++;
    }
    L3.length = k;
}

void reverse(SqList &L) {//所有元素逆置，复杂度为O(n)
    ElemType x;
    for (int i = 0; i < L.length / 2; i++) {
        x = L.data[i];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = x;
    }
}

//--------------------start----------------
//循环左移，时间复杂度O(n)，空间复杂度O(1)
void reverse(int R[], int left, int right) {
    int k = left, j = right, tmp;
    while (k < j) {
        tmp = R[k];
        R[k] = R[j];
        R[j] = tmp;
        k++;
        j--;
    }
}

void leftShift(int R[], int n, int p) {//循环左移
    if (p > 0 && p < n) {
        reverse(R, 0, n - 1);//全部逆置
        reverse(R, 0, n - p - 1);//逆置前n-p个
        reverse(R, n - p, n - 1);//逆置后p个
    }
}

//---------------------end-------------------
//---------------------start-----------------
//删除所有元素值为x的元素，空间复杂度为O(1)：法一
void delall1(SqList &L, ElemType x) {
    int i, k = 0;//k记录L中不为x的元素个数，初值为0
    for (i = 0; i < L.length; i++) {
        if (L.data[i] != x) {
            L.data[k] = L.data[i];
            k++;
        }
    }
}

//---------------------end-------------------
//---------------------start-----------------
//删除所有元素值为x的元素，空间复杂度为O(1)：法二
void delall2(SqList &L, ElemType x) {
    int i, k = 0;
    while (i < L.length) {
        if (L.data[i] == x)
            k++;
        else
            L.data[i - k] = L.data[i];//将不为x的元素前移k个位置
        i++;
    }
    L.length -= k;
}

//---------------------end-------------------
//---------------------start-----------------
//删除所有元素值在x到y之间的所有元素，空间复杂度为O(1)
void delallxy1(SqList &L, ElemType x, ElemType y) {
    int i, k = 0;
    for (i = 0; i < L.length; i++) {
        if (!(L.data[i] >= x && L.data[i] <= y)) {
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}

//---------------------end-------------------
//---------------------start-----------------
//删除所有元素值在x到y之间的元素，空间复杂度为O(1)：法二
void delallxy2(SqList &L, ElemType x, ElemType y) {
    int i, k = 0;
    while (i < L.length) {
        if (L.data[i] >= x && L.data[i] <= y)
            k++;
        else
            L.data[i - k] = L.data[i];
        i++;
    }
    L.length -= k;
}

//---------------------end-------------------
//---------------------start-----------------
//将L中所有小于0的整数放在前面，≥0的放在后半部分，时复O(n)，空复O(1)
void move(SqList &L) {
    ElemType temp;
    int i = 0, j = L.length - 1;
    while (i < j) {
        while (L.data[i] < 0)
            i++;
        while (L.data[i] >= 0)
            j--;
        if (i < j) {
            temp = L.data[i];
            L.data[i] = L.data[j];
            L.data[j] = temp;
        }
    }
}

//---------------------end-------------------
//---------------------start-----------------
//删除顺序表中的重复元素，剩余元素间相对次序保持不变，时复O(n^2)，空复O(1)
void delsame(SqList &L) {
    int i, j = 0, k;
    for (i = 1; i < L.length; i++) {
        k = 0;
        while (k <= j && L.data[k] != L.data[i])
            k++;
        if (k > j) {
            j++;
            L.data[j] = L.data[i];
        }
    }
    L.length = j + 1;
}

//---------------------end-------------------
//---------------------start-----------------
//删除有序顺序表中的重复元素，剩余元素保持相对次序不变
void delsame1(SqList &L) {
    int i, k = 1;//k保存不重复的元素个数
    ElemType e;
    e = L.data[0];
    for (i = 1; i < L.length; i++) {
        if (L.data[i] != e) {//只保存不重复的元素
            L.data[k] = L.data[i];
            k++;
            e = L.data[i];
        }
    }
    L.length = k;//顺序表长度置新值
}

//---------------------end-------------------
//---------------------start-----------------
//顺序表表示集合，求两个集合的交集，时复O(m*n)，空复O(1)
void Intersection(SqList A, SqList B, SqList &C) {
    int i, j, k = 0;//k记录C中元素个数
    for (i = 0; i < A.length; i++) {
        j = 0;
        while (j < B.length && B.data[j] != A.data[i])
            j++;
        if (j < B.length)//表示A.data[i]在B中，将其放C中
            C.data[k++] = A.data[i];
    }
    C.length = k;
}

//---------------------end-------------------
//---------------------start-----------------
//有序表求交集，时复O(m+n)，空复O(1)
void Intersection1(SqList A, SqList B, SqList &C) {
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {
        if (A.data[i] == B.data[j]) {
            C.data[k] = A.data[i];
            i++;
            j++;
            k++;
        } else if (A.data[i] < B.data[i])
            i++;
    }
    C.length = k;
}

//---------------------end-------------------
//---------------------start-----------------
//有序表求并集，时复O(m*n)，空复O(1)
void Union(SqList A, SqList B, SqList &C) {
    int i, j, k;
    for (i = 0; i < A.length; i++) {
        C.data[i] = A.data[i];
    }
    k = A.length;
    for (i = 0; i < B.length; i++) {
        j = 0;
        while (j < A.length && B.data[i] != A.data[j])
            j++;
        if (j == A.length)
            C.data[k++] = B.data[i];
    }
    C.length = k;
}

//---------------------end-------------------
//---------------------start-----------------
//无序表求差集，时复O(m*n)，空复O(1)
void Diffence(SqList A, SqList B, SqList &C) {
    int i, j, k = 0;
    for (i = 0; i < A.length; i++) {
        j = 0;
        while (j < B.length && B.data[j] != A.data[i])
            j++;
        if (j == B.length)
            C.data[k++] = A.data[i];
    }
    C.length = k;
}

//---------------------end-------------------
//---------------------start-----------------
//有序表求差集，时复O(m+n)，空复O(1)
void Diffence1(SqList A, SqList B, SqList &C) {
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {
        if (A.data[i] < B.data[i]) {//只将A中小的元素放入C中
            C.data[k] = A.data[i];
            i++;
            k++;
        } else if (A.data[i] > B.data[i])
            j++;
        else {//公共元素不能放入C中
            i++;
            j++;
        }
    }
    while (i < A.length) {//若A未遍历完，将余下的所有元素放入C中
        C.data[k] = A.data[i];
        i++;
        k++;
    }
    C.length = k;
}
//---------------------end-------------------