数据结构常考基础代码题-顺序表有序插入

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

第一步：定义顺序表结构体

根据题目中的“顺序表递增有序”，我们需要定义一个顺序表结构体，用于存储元素和顺序表的相关信息。

typedef struct {
    int *data; // 动态数组存储元素
    int length; // 顺序表当前长度
    int size; // 顺序表的最大容量
} Sqlist;

第二步：实现查找插入位置的函数

根据题目中的“插入元素 x”，我们需要实现一个函数 find，用于在列表里一直往前找到第一个不小于 x 的数的索引。

int find(Sqlist L, int x) {
    int i = 0;
    for (; i < L.length; i++) {
        if (x <= L.data[i]) {
            break;
        }
    }
    return i; // 返回找到的位置
}

第三步：实现插入元素的函数

根据题目中的“插入元素 x，仍递增有序”，我们需要实现一个函数 insert，用于将元素 x 插入到顺序表中，并保持顺序表的递增有序性。

void insert(Sqlist *L, int x) {
    int p = find(*L, x); // 找到插入位置
    // 如果顺序表已满，需要扩容
    if (L->length == L->size) {
        L->size = L->size * 2 + 1; // 扩容策略
        int *newData = (int *)realloc(L->data, L->size * sizeof(int));
        if (!newData) {
            exit(-1); // 内存分配失败，退出程序
        }
        L->data = newData;
    }
    // 将p位置及之后的元素向后移动
    for (int j = L->length; j > p; j--) {
        L->data[j] = L->data[j - 1];
    }
    // 插入元素x
    L->data[p] = x;
    L->length++; // 更新顺序表长度
}

第四步：在 main 函数中测试插入操作

最后，我们需要在 main 函数中创建顺序表并测试插入操作，以确保代码的正确性。

int main() {
    Sqlist L;
    L.size = 10; // 初始化最大容量
    L.length = 0;
    L.data = (int *)malloc(L.size * sizeof(int));
    if (!L.data) {
        exit(-1); // 内存分配失败，退出程序
    }

    // 插入元素
    insert(&L, 5);
    insert(&L, 3);
    insert(&L, 8);

    // 打印顺序表
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");

    // 释放内存
    free(L.data);
    return 0;
}