顺序表课后题

// 1.遍历整个表，找到最小值并用指针min用来保存最小值，j用来保存最小值所在的位置 
// 遍历结束后将最后一个元素覆盖最小元素

bool del(SqlList &L,int &min) {
    int i = 0;
    int j;
    min = L.data[0];
    if (L.length == 0) {
        return false;
    }
    while (i < L.length-1) {
        if (min > L.data[++i]) {
            min = L.data[i];
            j = i;
        }
    }
    L.data[j] = L.data[L.length-1];
    L.length = L.length - 1;
    return true;
        
}

//2.逆置顺序表

bool exchange(SqlList& L) {
    int x;
    if (L.length == 0) {
        return false;
    }
    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;
    }
    return true;
}

//3.删除所有值为x的数据元素
//开始时i，j都为0，若L.data[j]!=x时，L.data[i]=L.data[j],i+1;
bool del(SqlList& L, int x) {
    int i = 0;
    if (L.length == 0) {
        return false;
    }
    for (int j = 0; j < L.length; j++) {
        
        if (L.data[j] != x) {
            L.data[i] = L.data[j];
            i = i + 1;
        }
    }
    L.length = i;
    return true;
}

//4.删除值有序顺序表中值为s与t之间的所有元素
bool del(SqlList& L,int s,int t) {
    int i=0;
    if (s >= t && L.length == 0) {
        return false;
    }
    for (int j = 0; j < L.length; j++) {
        if (L.data[j] < s || L.data[j] > t) {
            L.data[i] = L.data[j];
            i = i + 1;
        }
    }
    L.length = i;
    return true; 
}

//5.删除顺序表中值为s与t之间的所有元素
bool del(SqlList& L, int s, int t) {
    int i = 0;
    if (s >= t && L.length == 0) {
        return false;
    }
    for (int j = 0; j < L.length; j++) {
        if (L.data[j] < s || L.data[j] > t) {
            L.data[i] = L.data[j];
            i = i + 1;
        }
    }
    L.length = i;
    return true;
}

//6.删除有序顺序表中所有重复元素
bool del(SqlList& L) {
    int i = 0;
    if (L.length == 0) {
        return false;
    }

    for (int j = 1; j < L.length; j++) {
        if (L.data[i] != L.data[j]) {
            L.data[i + 1] = L.data[j];
            i = i + 1;
        }
    }
    L.length = i+1;
    return true;
}

//7.两个有序表合并成一个新的有序表
bool Merge(SqList A, SqList B, SqList& L) {
    int a = 0, b = 0, i = 0;
    while (A.length + B.length > MaxSize) {
        return false;
    }
    while (a < A.length && b < B.length) {    //在A和B表都有值的时候开始遍历比较，将小的数放到L表
        if (A.data[a] < B.data[b]) {
            L.data[i] = A.data[a];
            a = a++;
            i = i++;
        }
        else {
            L.data[i] = B.data[b];
            i = i + 1;
            b = b + 1;
        }
    }
        if (a < A.length) {       //将A剩下没比较完的表的值放进L表里
            L.data[i] = A.data[a];
            i = i + 1;
            a = a + 1;
        }
        if (b < B.length) {      //将B剩下没比较完的表的值放进L表里
            L.data[i] = B.data[b];
            i = i + 1;
            b = b + 1;
        }
        L.length = i;
        return true;
    
}

//8
void Reverse(SqlList& R, int left, int right) {
    int temp;
    if (left >= right || right > R.length) {
        return;
    }
    while (left < right && left != right) {
        temp = R.data[left];
        R.data[left] = R.data[right];
        R.data[right] = temp;
        right--;
        left++;
    }
}
void Exchange(SqlList& R, int m,int n) {
    Reverse(R, 0, m-1);
    Reverse(R, m, m+n-1);
    Reverse(R, 0, m+n - 1);
}

//9.在增序的顺序表中查找值为x的元素并与其后继元素位置交换（折半查找）
bool search(SqlList& L, int x) {
    int low = 0, high = L.length, mid = L.length / 2,t;
    if (L.length == 0) {
        return false;
    } 

    while (true) {
        if (x > L.data[mid]) {
            low = mid + 1;
            mid = (low + high) / 2;
        }
        if (x < L.data[mid]) {
            high = mid - 1;
            mid = (low + high) / 2;
        }
        if (x == L.data[mid]) {
            t = L.data[mid + 1];
            L.data[mid + 1] = L.data[mid];
            L.data[mid] = t;
            return true;
        }
        if (low > high) {
            for (int i = L.length; i >= low; i--) {
                L.data[i + 1] = L.data[i];
            }
            L.data[low] = x;
            L.length = L.length + 1;
            return true;
        }
    }
}

//10.将(X0,X1.....X(n-1))变为（Xp,X(p+1).....X(n-1),X0,X1....X(p-1)）
//三次逆置
void Reverse(SqlList &R, int left, int right) {
    int temp;
    if (left >= right || right > R.length) {
        return;
    }
    while (left < right && left != right) {
        temp = R.data[left];
        R.data[left] = R.data[right];
        R.data[right] = temp;
        right--;
        left++;
    }
}
void Exchange(SqlList& R, int p) {
    Reverse(R, 0, R.length - p-1);
    Reverse(R, R.length-p, R.length - 1);
    Reverse(R, 0, R.length - 1);
}

//11.找到两个增序顺序表的中位数
int search(SqlList A, SqlList B) {
    int i = 0, j = 0, k = 0,x;
    while (k < (A.length + B.length) / 2) {
        if (A.data[i] < B.data[j]) {
            x = A.data[i];
            i = i + 1;
        }
        else {
            x = B.data[j];
            j = j + 1;
        }
        k = k + 1;
    }
    return x;
}

//12.寻找主元素
void arr(int* &a, int n) {                       
    a = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        a[i] = 0;
    }
    
}

int search_main(SqliList L) {
    int* P=NULL;
    int max, x = 0;
    arr(P, L.length);
    for (int j = 0; j < L.length; j++) {
        P[L.data[j]]= P[L.data[j]]+1;
    }
    max = 0;
    for (int k = 0; k < L.length; k++) {
        if (max
            max = P[k];
            x = k;
        }
    }
    
    if (max > L.length / 2) {
        return x;
    }
    else {
        return -1;
    }    
}

//13.顺序表中未出现的最小正整数
int search(SqlList L) {
    int max = L.data[0];
    int* P=NULL;
    for (int i = 0; i < L.length; i++) {  //找L表里面的最大值
        if (max < L.data[i]) {
            max = L.data[i];
        }
    }
    max = max + 2;
    P = (int*)malloc(sizeof(int) * max);     //映射
    for (int i = 1; i < max; i++) {
        P[i] = 0;
    }
    P[0] = 1;
    
    for (int j = 0; j < L.length; j++) {     //将出现过的数做标记
        if (L.data[j] > 0) {
            P[L.data[j]] = 1;
        }
    }
    for (int k = 1; k < max; k++) {          //找到最小未出现的正整数
        if (P[k] == 0) {
            return k;
        }
    }

    }

//14.求三元组
int abs(int a) {          //求绝对值
    if (a < 0) {
        return -a;
    }
    else {
        return a;
    }
}
void Min_distance(SqlList& S1, SqlList& S2, SqlList& S3) {
    int min, mi = 0, mj = 0, mk = 0;
    min = abs(S1.data[0] - S2.data[0]) + abs(S2.data[0] - S3.data[0]) + abs(S3.data[0] - S1.data[0]);
    for (int i = 0; i < S1.length ; i++) {
        for (int j = 0; j < S2.length ; j++) {
            for (int k = 0; k < S3.length ; k++) {
                if (abs(S1.data[i] - S2.data[j]) + abs(S2.data[j] - S3.data[k]) + abs(S3.data[k] - S1.data[i]) < min) {
                    min = abs(S1.data[i] - S2.data[j]) + abs(S2.data[j] - S3.data[k]) + abs(S3.data[k] - S1.data[i]);
                    mi = i;
                    mj = j;
                    mk = k;
                }
            }
        }
    }
    printf("%d %d %d", S1.data[mi], S2.data[mj], S3.data[mk]);
}

//不带头结点单链表通过递归删除值为x 的结点

void del(LinkList &L, int x) {
    LNode* p;
    if (L == NULL) {
        return;
    }
    if (L->data == x) {
        p = L;
        L = L->next;
        free(p);
        del(L, x);
    }
    else {
        del(L->next, x);
    }
}