1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删运算的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

输入样例：
5
3 4 1 6 7
6
5 2 7 9 3 6
0

输出样例：
1
3 4 6 7
2
5 6 7 9 3
error

#include <stdio.h>

#define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

int ListDelete(SqList *L);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        printf("%d\n", ListDelete(&L));
        ListPrint(L);
    }
    printf("error");
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

int ListDelete(SqList *L) {
    int min_pos = 0, min_val = 0;

    for (int i = 0; i < L->length; i++) {
        if (L->data[i] < L->data[min_pos]) min_pos = i;
    }
    min_val = L->data[min_pos];
    L->data[min_pos] = L->data[L->length - 1];
    L->length--;
    return min_val;
}

2.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为 $O (1)$ 。

输入样例：
5
3 4 1 6 7
6
5 2 7 9 3 6
0

输出样例：
7 6 1 4 3
6 3 9 7 2 5

#include <stdio.h>

#define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

void ListInvert(SqList *L);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        ListInvert(&L);
        ListPrint(L);
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListInvert(SqList *L) {
    for (int i = 0; i < L->length / 2; i++) {
        L->data[i] = L->data[i] + L->data[L->length - i - 1];
        L->data[L->length - i - 1] = L->data[i] - L->data[L->length - i - 1];
        L->data[i] = L->data[i] - L->data[L->length - i - 1];
    }
}

3.对长度为n的顺序表L，编写一个时间复杂度为 $O (n)$ 、空间复杂度为 $O (1)$ 的算法，该算法删除线性表中所有值为x的数据元素。

#include <stdio.h>

#define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

void ListDelete(SqList *L, int x);

void ListDelete_(SqList *L, int x);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        int x;

        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        scanf("%d", &x);
        ListDelete(&L, x);
        /*ListDelete_(&L, x);*/
        ListPrint(L);
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListDelete(SqList *L, int x) {
    int cursor = 0, offset = 0;//offset记录等于x的元素的个数

    while (cursor + offset < L->length) {
        if (L->data[cursor + offset] == x) {
            offset++;
        } else {
            L->data[cursor] = L->data[cursor + offset];//将当前不等于x的元素向前偏移offset
            cursor++;
        };
    }
    L->length -= offset;//更新顺序表长度
}

void ListDelete_(SqList *L, int x) {
    int slow = 0;

    for (int fast = 0; fast < L->length; fast++) {
        if (L->data[fast] != x) {
            L->data[slow] = L->data[fast];
            slow++;
        }
    }
    L->length = slow;//更新顺序表长度
}

4.从有序顺序表中删除其值在给定值s与t之间（s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

输入样例：
5
1 2 3 4 5
2 4
6
5 6 7 8 9 10
8 10
0

输出样例：
1 5
5 6 7
error

#include <stdio.h>

#define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

void ListDelete(SqList *L, int s, int t);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        int s, t;

        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        scanf("%d %d", &s, &t);
        if (s >= t) break;
        ListDelete(&L, s, t);
        ListPrint(L);
    }
    printf("error");
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListDelete(SqList *L, int s, int t) {
    int slow = 0;

    for (int fast = 0; fast < L->length; fast++) {
        if (L->data[fast] < s || L->data[fast] > t) {
            L->data[slow] = L->data[fast];
            slow++;
        }
    }
    L->length = slow;
}

5.从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

输入样例：
5
3 4 1 6 7
4 6
6
5 2 7 9 3 6
7 9
0

输出样例：
3 1 7
5 2 3 6

#include <stdio.h>

#define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

void ListDelete(SqList *L, int s, int t);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        int s, t;

        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        scanf("%d %d", &s, &t);
        if (s >= t) break;
        ListDelete(&L, s, t);
        ListPrint(L);
    }
    printf("error");
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListDelete(SqList *L, int s, int t) {
    int slow = 0;

    for (int fast = 0; fast < L->length; fast++) {
        if (L->data[fast] < s || L->data[fast] > t) {
            L->data[slow] = L->data[fast];
            slow++;
        }
    }
    L->length = slow;
}

6.从有序表中删除所有其值重复的元素，使表中所有元素的值均不同。

输入样例：
5
1 2 2 2 3
10
1 2 2 2 3 4 4 4 5 5 

输出样例：
1 2 3
1 2 3 4 5

#include <stdio.h>

#define MAX_SIZE 10

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

void ListDelete(SqList *L);

void ListDelete_(SqList *L);

int main() {
    SqList L;

    while (scanf("%d", &L.length) && L.length!= 0) {
        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        /*ListDelete(&L);*/
        ListDelete_(&L);
        ListPrint(L);
    }
    printf("error");
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}
/*对有序表和无序表都适用*/
void ListDelete(SqList *L) {
    for (int i = 0; i < L->length; i++) {
        int same = 0;//重复元素的个数
        /*将当前元素与后面的所有元素进行比较*/
        for (int j = i + 1; j < L->length; j++) {
            if (L->data[i] == L->data[j]) {
                same++;
            } else {
                L->data[j - same] = L->data[j];
            }
        }
        L->length -= same;
    }
}
/*只能处理有序表*/
void ListDelete_(SqList *L) {
    int slow = 0, fast = 1;

    while (fast < L->length) {
        if (L->data[slow] != L->data[fast]) {
            L->data[++slow] = L->data[fast];
        }
        fast++;
    }
    L->length = slow + 1;
}

7.将两个有序顺序表合并为一个新的有序顺序表。

输入样例：
3 4
1 3 5
2 4 6 8
0 0

输出样例：
1 2 3 4 5 6 8

#include <stdio.h>

#define MAX_SIZE 10

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

void ListMerge(SqList A, SqList B, SqList *L);

int main() {
    SqList A;
    SqList B;

    while (scanf("%d %d", &A.length, &B.length) && A.length != 0 && B.length != 0) {
        SqList L;

        L.length = 0;
        for (int i = 0; i < A.length; i++) {
            scanf("%d", &(A.data[i]));
        }
        for (int i = 0; i < B.length; i++) {
            scanf("%d", &(B.data[i]));
        }
        ListMerge(A, B, &L);
        ListPrint(L);
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListMerge(SqList A, SqList B, SqList *L) {
    int cur_a = 0, cur_b = 0, cursor = 0;

    while (cur_a < A.length && cur_b < B.length) {
        if (A.data[cur_a] < B.data[cur_b]) {
            L->data[cursor++] = A.data[cur_a++];
            L->length++;
        } else {
            L->data[cursor++] = B.data[cur_b++];
            L->length++;
        }
    }
    while (cur_a < A.length) {
        L->data[cursor++] = A.data[cur_a++];
        L->length++;
    }
    while (cur_b < B.length) {
        L->data[cursor++] = B.data[cur_b++];
        L->length++;
    }
}

8.已知在一维数组A[m+n]中依次存放两个线性表 $(a_1, a_2, a_3, \dots a_m)$ 和 $(b_1, b_2, b_3, \dots b_n)$ 。试编写一个函数，将数组中两个顺序表的位置互换，即将 $(b_1, b_2, b_3, \dots b_n)$ 放在 $(a_1, a_2, a_3, \dots a_m)$ 前面。

输入样例：
2 3
1 2 3 4 5
2 5
1 2 3 4 5 6 7
0 0

输出样例：
3 4 5 1 2
3 4 5 6 7 1 2

#include <stdio.h>

#define MAX_SIZE 10

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

void ListInvert(SqList *L, int start, int end);

void ListSwap(SqList *L, int m, int n);

int main() {
    int m, n;
    SqList L;

    while (scanf("%d %d", &m, &n) && m != 0 && n != 0) {
        L.length = m + n;
        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        ListSwap(&L, m, n);
        ListPrint(L);
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListSwap(SqList *L, int m, int n) {
    ListInvert(L, 0, L->length - 1);
    ListInvert(L, 0, n - 1);
    ListInvert(L, L->length - m, L->length - 1);
}

void ListInvert(SqList *L, int start, int end) {
    for (int i = start; i <= (start + end) / 2; i++) {
        int tmp = L->data[i];
        L->data[i] = L->data[start + end - i];
        L->data[start + end - i] = tmp;
    }
}

9.线性表 $(a_1, a_2, a_3, \dots a_n)$ 中的元素递增有序且按顺序存储于计算机内，要求设计一个算法，完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。

输入样例：
5
1 3 5 7 9
7
5
1 3 5 7 9
6
0

输出样例：
1 3 5 9 7
1 3 5 6 7 9

#include <stdio.h>

#define MAX_SIZE 10

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

void SearchExchangeInsert(SqList *L, int x);

int BinarySearch(SqList L, int key);

int main() {
    SqList L;

    while (scanf("%d", &(L.length)) && L.length != 0) {
        int x;

        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        scanf("%d", &x);
        SearchExchangeInsert(&L, x);
        ListPrint(L);
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void SearchExchangeInsert(SqList *L, int x) {
    int pos = BinarySearch(*L, x);

    if (pos != -1) {
        /*exchange*/
        L->data[pos] = L->data[pos] + L->data[pos + 1];
        L->data[pos + 1] = L->data[pos] - L->data[pos + 1];
        L->data[pos] = L->data[pos] - L->data[pos + 1];
    } else {
        /*insert*/
        int i = L->length - 1;
        while (L->data[i] > x) {
            L->data[i + 1] = L->data[i];
            i--;
        }
        L->data[i + 1] = x;
        L->length++;
    }
}

int BinarySearch(SqList L, int key) {
    int low = 0, high = L.length - 1, mid;

    while (low < high) {
        mid = (low + high) / 2;
        if (L.data[mid] == key) {
            return mid;
        } else if (L.data[mid] > key) {
            high = mid - 1;//继续查找前半部分
        } else {
            low = mid + 1;//继续查找后半部分
        }
    }
    return -1;//查找失败
}

10.设将n（n>1）个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据由 $(X_0, X_1, \dots, X_{n-1})$ 变换为 $(X_p, X_{p+1}, \dots, X_{n-1},X_0, X_1, \dots, X_{p-1})$ 。

输入样例：
5
3 4 1 6 7
3
6
5 2 7 9 3 6
5
0

输出样例：
6 7 3 4 1
6 5 2 7 9 3

#include <stdio.h>

#define MAX_SIZE 10

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

void ListReverse(SqList *L, int low, int high);

void ListMove(SqList *L, int dis);

int main() {
    SqList L;
    int dis;

    while (scanf("%d", &(L.length)) && L.length != 0) {
        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        scanf("%d", &dis);
        ListMove(&L, dis);
        ListPrint(L);
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

void ListMove(SqList *L, int dis) {
    ListReverse(L, 0, L->length - 1);
    ListReverse(L, 0, L->length - dis - 1);
    ListReverse(L, L->length - dis, L->length - 1);
}

void ListReverse(SqList *L, int low, int high) {
    for (int i = low; i <= (high + low) / 2; i++) {
        int tmp = L->data[i];
        L->data[i] = L->data[high + low - i];
        L->data[high + low - i] = tmp;
    }
}

11.两个序列的中位数是含它们所有元素的升序序列的中位数。现在有两个等长升序序列A和B，请设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列的中位数。

#include <stdio.h>

#define MAX_SIZE 10

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

int FindMedian(SqList A, SqList B);

int main() {
    SqList A;
    SqList B;

    while (scanf("%d %d", &(A.length), &(B.length)) && A.length != 0 && B.length != 0) {
        for (int i = 0; i < A.length; i++) {
            scanf("%d", &(A.data[i]));
        }
        for (int i = 0; i < B.length; i++) {
            scanf("%d", &(B.data[i]));
        }
        printf("%d\n", FindMedian(A, B));
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

int FindMedian(SqList A, SqList B) {
    int count = A.length;
    int cur_a = 0, cur_b = 0;
    int median;

    while (count-- > 0) {
        median = (A.data[cur_a] < B.data[cur_b]) ? A.data[cur_a++] : B.data[cur_b++];
    }
    return median;
}

12.对于一个含有n个元素的整数序列，如果元素x重复出现了m次且m>n/2，则称x为该序列的主元素。请设计一个尽可能高效的算法，找出一个序列的主元素，若存在输出该主元素，若不存在输出-1。

输入样例：
8
0 5 5 3 5 7 5 5
8
0 5 5 3 5 1 5 7
0

输出样例：
5
-1

#include <stdio.h>

#define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

int GetMainEle(SqList L);

int main() {
    SqList L;

    while (scanf("%d", &(L.length)) && L.length != 0) {
        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        printf("%d", GetMainEle(L));
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

int GetMainEle(SqList L) {
    int count[MAX_SIZE] = {0};
    for (int i = 0; i < L.length; i++) {
        count[L.data[i]]++;
    }
    for (int i = 0; i < MAX_SIZE; i++) {
        if (count[i] > L.length / 2)
            return i;
    }
    return -1;
}

13.给定一个含n个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。

输入样例：
5
-5 2 9 7 8
5
1 2 3 4 5
0

输出样例：
1
6

#include <stdio.h>

#define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

int QuickSort(SqList *L, int low, int high);

int Partition(SqList *L, int low, int high);

int GetMinVal(SqList L);

int main() {
    SqList L;

    while (scanf("%d", &(L.length)) && L.length != 0) {
        for (int i = 0; i < L.length; i++) {
            scanf("%d", &(L.data[i]));
        }
        printf("%d\n", GetMinVal(L));
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}
/*也可以通过一个标志数组空间换时间*/
int GetMinVal(SqList L) {
    int min = 1;
	/*我这里是通过快排后的遍历得到最小值*/
    QuickSort(&L, 0, L.length - 1);
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == min) {
            min = L.data[i] + 1;
        } else if(L.data[i] > min) {
            break;
        }
    }
    return min;
}

int QuickSort(SqList *L, int low, int high) {
    if (low < high) {
        int pivot_pos = Partition(L, low, high);
        QuickSort(L, low, pivot_pos - 1);
        QuickSort(L, pivot_pos + 1, high);
    }
}

int Partition(SqList *L, int low, int high) {
    int pivot_num = L->data[low];

    while (low < high) {
        while (low < high && L->data[high] >= pivot_num) high--;
        L->data[low] = L->data[high];
        while (low < high && L->data[low] <= pivot_num) low++;
        L->data[high] = L->data[low];
    }
    L->data[low] = pivot_num;
    return low;
}

14.定义三元组(a, b, c)的距离D=|a-b|+|b-c|+|c-a|。给定三个非空整数集合按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有三元组中的最小距离。

输入样例：
3 4 5
-1 0 9
-25 -10 10 11
2 9 17 30 41
0 0 0

输出样例：
2

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

void ListPrint(SqList L);

int GetDis(int x, int y, int z);

bool IsMinVal(int x, int y, int z);

int GetMinDis(SqList A, SqList B, SqList C);

int main() {
    SqList A, B, C;

    while (scanf("%d %d %d", &(A.length), &(B.length), &(C.length))) {
        if (A.length == 0 || B.length == 0 || C.length == 0) break;
        for (int i = 0; i < A.length; i++) {
            scanf("%d", &(A.data[i]));
        }
        for (int i = 0; i < B.length; i++) {
            scanf("%d", &(B.data[i]));
        }
        for (int i = 0; i < C.length; i++) {
            scanf("%d", &(C.data[i]));
        }
        printf("%d%c", GetMinDis(A, B, C), 10);
    }
    return 0;
}

void ListPrint(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32);
    }
}

int GetDis(int x, int y, int z) {
    int dis = 0;

    dis += (x > y) ? x - y : y - x;
    dis += (x > z) ? x - z : z - x;
    dis += (z > y) ? z - y : y - z;
    return dis;
}

bool IsMinVal(int x, int y, int z) {
    return (x < y && x < z) ? true : false;
}

int GetMinDis(SqList A, SqList B, SqList C) {
    int i = 0, j = 0, k = 0;
    int min_dis = INT_MAX, dis;

    while (i < A.length && j < B.length && k < C.length) {
        dis = GetDis(A.data[i], B.data[j], C.data[k]);
        min_dis = (dis < min_dis) ? dis : min_dis;
        if (IsMinVal(A.data[i], B.data[j], C.data[k])) {
            i++;
        } else if (IsMinVal(B.data[j], A.data[i], C.data[k])) {
            j++;
        } else {
            k++;
        };
    }
    return min_dis;
}