数据结构线性表部分习题

思路：首先应该得找出这个链表里的最小值吧？通过把表里的每个元素与自己设定的最小值进行比较，比较完后更新所设定的最小值为该次比较的较小的值，最后比较完就能获得最小值元素。

bool Del_Min(Sqlist &L, int &value) {
    if (L.length == 0)//判断空表
        return false;
    value = L.data[0];//不妨设第一个元素是最小值
    int pos = 0;//记录元素下标
    for (int i = 0; i < L.length; i++) {//遍历表，寻找最小元素
        if (L.data[i] < value) { //value负责记录此时表的最小值的元素
            value = L.data[i];
            pos = i;
        }
    }
    L.data[pos] = L.data[L.length - 1];
    L.length--;//记得更新L.length!!
    return true;
}

思路：1.若我们不考虑空间复杂度，我们可以开辟一个跟此表一样的连续空间，将表中元素从末往前复制到新表里，再覆盖旧表即可，但此时空间复杂度为O(n)
     2.若在同一表里，我们可以把表平均分为前后两部分，利用对称性，把前后位置对称的元素两两互换位置即可

void Reverse(Sqlist &L) {
    int temp;//定义一个中间变量
    for (int i = 0; i < L.length / 2; i++) {
        temp = L.data[i];
        L.data[i] = L.data[L.length - 1 - i];
        L.data[L.length - 1 - i] = temp;
    }
}

//思路：空间复杂度为O(1)，那只能在原表内进行操作。若通过遍历表找出所有值为x的元素，依次删去并移位，该时间开销极大，不满足O(1)。

void DelElm1(Sqlist &L, int x) {
    int k = 0;//记录不等于x的元素个数
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] != x) {
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}

//
void DelElm2(Sqlist &L, int x) {
    int i = 0;
    int k = 0;//记录等于x的元素个数
    while (i < L.length) {
        if (L.data[i] == x) {
            k++;
        } else {
            L.data[i - k] = L.data[i];
        }//当前元素前移k个位置
        i++;
    }
        L.length = L.length - k;
}