题目来源: 我头发还多还能学

顺序表默认结构体

const int MaxSize = 100;
typedef struct{
    int data[MaxSize];
    int length;
}Sqlist;

1、顺序表递增有序，插入元素 $x$ ，仍递增有序

int find(Sqlist L, int x){ // 按元素值查找位置
    int i = 0;
    for (i = 0; i < L.length; i ++ ) {
        if (x < L.data[i])
            break;
    }
    return i;
}

void insert(Sqlist &L, int x) { // 元素后移
    int p = find(L, x);
    for (int i = L.length - 1; i >= p; i -- ) {
        L.data[i + 1] = L.data[i];
    }
    L.data[p] = x;
    L.length ++ ; // 顺序表长度+1
}

2、用顺序表最后一个元素覆盖整个顺序表中最小元素，并返回该最小元素

int Del_Min(Sqlist &L) {
    int pos = 0;
    int min_val = L.data[0];
    for (int i = 0; i < L.length; i ++ ) {
        if (L.data[i] < min_val) {
            min_val = L.data[i];
            pos = i;
        }
    }
    L.data[pos] = L.data[L.length - 1];
    L.length -- ; //注：题目的意思是删除最小元素
    return min_val;
}

3、将顺序表中元素逆置

void Reverse(Sqlist &L) {
    for (int i = 0, j = L.length - 1; i < j; i ++ , j -- ) {
        int temp = L.data[i];
        L.data[i] = L.data[j];
        L.data[j] = temp; 
    }
}

4 将($a_{1},a_{2},a_{3} \cdots a_{m},b_{1},b_{2},b_{3} \cdots b_{n}$)转换成($b_{1},b_{2},b_{3} \cdots b_{n},a_{1},a_{2},a_{3}\cdots a_{m}$)

5、删除顺序表中所有值为 $x$ 的元素（两种方法）

// 法1
void Del(Sqlist &L, int x) {
    int cnt = 0;
    for (int i = 0; i < L.length; i ++ ) {
        if (L.data[i] != x) {
            L.data[cnt ++ ] =  L.data[i];
        }
    }
    L.length = cnt;
}

6、从顺序表中删除给定值在 $s$ 到 $t$ 之间（包含 $s$ 和 $t$）的所有元素

7、从有序表中删除所有值重复的元素

8、两个递增有序表合并成一个递增有序表

9、求两个递增序列合并后的中位数（两种方法）

10、设计一个时间上尽可能高效的算法，找出数组中未出现的最小正整数

11、若一个整数序列中有过半相同元素，则称其为主元素，设计一个算分1

函数自测模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MaxSize = 100;

// 顺序表默认结构体
typedef struct {
    int data[MaxSize];
    int length;
}Sqlist;


// 顺序表的初始化
void InitList(Sqlist &L) {
    L.length = 0;
}

// 1、顺序表递增有序，插入元素x， 仍递增有序
int find(Sqlist L, int x){ // 按元素值查找位置
    int i = 0;
    for (i = 0; i < L.length; i ++ ) {
        if (x < L.data[i])
            break;
    }
    return i;
}

void insert(Sqlist &L, int x) { // 元素后移
    int p = find(L, x);
    for (int i = L.length - 1; i >= p; i -- ) {
        L.data[i + 1] = L.data[i];
    }
    L.data[p] = x;
    L.length ++ ; // 顺序表长度+1
}

// 2、用顺序表最后一个元素覆盖整个顺序表中最小元素，并返回该最小元素
int Del_Min(Sqlist &L) {
    int pos = 0;
    int min_val = L.data[0];
    for (int i = 0; i < L.length; i ++ ) {
        if (L.data[i] < min_val) {
            min_val = L.data[i];
            pos = i;
        }
    }
    L.data[pos] = L.data[L.length - 1];
    L.length -- ;
    return min_val;
}

// 3、将顺序表中的元素逆置
void Reverse(Sqlist &L) {
    for (int i = 0, j = L.length - 1; i < j; i ++ , j -- ) {
        int temp = L.data[i];
        L.data[i] = L.data[j];
        L.data[j] = temp; 
    }
}

// 5、删除顺序表中所有值为x的元素
void Del(Sqlist &L, int x) {
    int cnt = 0;
    for (int i = 0; i < L.length; i ++ ) {
        if (L.data[i] != x) {
            L.data[cnt ++ ] =  L.data[i];
        }
    }
    L.length = cnt;
}


// 输出顺序表中元素和表长
void PrintList(Sqlist L) {
    for (int i = 0; i < L.length; i ++ ) {
        printf("L.data[%d] = %d\n", i, L.data[i]);
    }

    cout << "L的表长为" << L.length << endl;
}

// 主函数中分别对各个函数进行测试
int main()
{
    Sqlist L;

    InitList(L);

    for (int i = 0; i < 10; i ++ ) {
        L.data[i] = i;
        L.length ++ ;
    }

    PrintList(L);

    cout << "------------------------------" << endl;

    // insert(L, 5);
    // PrintList(L);

    //Del_Min(L);
    //PrintList(L);

    //Reverse(L);
    //PrintList(L);

    //Del(L, 5);
    //PrintList(L);


    return 0;
}