数据结构每日一题day3（顺序表）★★★★★
题目描述：顺序表L的元素递增有序排列，设计一个算法在插入元素x后保持该顺序表仍然递增有序排列,插入成功后返回插入元素所在位置,不成功返回-1
算法思想：在递增有序的顺序表中插入元素 x 并保持有序性，步骤如下：
合法性检查：若顺序表已满（length == MAXSIZE）或指针为空，插入失败，返回 -1。
查找插入位置：遍历顺序表，找到第一个大于等于 x 的元素的位置 i；若所有元素均小于 x，则插入到表尾（i = length）。
元素后移：从表尾开始，将位置 i 及之后的元素全部后移一位，腾出插入位置。
插入元素：将 x 存入位置 i，表长加 1，返回插入位置 i。
复杂度分析：时间复杂度O(n)空间复杂度O(1)
代码实现：
#include <stdbool.h>
#define MAXSIZE 100 // 假设顺序表最大容量
typedef struct {
int data[MAXSIZE];
int length;
} SeqList;
int InsertOrder(SeqList *L, int x) {
// 检查表是否已满或指针为空
if (L == NULL || L->length >= MAXSIZE) {
return -1;
}
int i;
// 找到第一个大于等于x的元素的位置
for (i = 0; i < L->length; i++) {
if (L->data[i] >= x) {
break;
}
}
// 若所有元素均小于x，i此时等于length
// 从后向前移动元素，腾出插入位置
for (int j = L->length; j > i; j--) {
L->data[j] = L->data[j - 1];
}
L->data[i] = x; // 插入x
L->length++; // 表长增加
return i; // 返回插入位置
}