顺序表练习：设顺序表L是一个递增有序表，试写一算法，将x插入其后仍保持L的有序性，用C++

在C++中，如果你想在递增有序的顺序表（List）中插入一个新元素`x`并保持有序性，可以采用二分查找法找到合适的位置，然后插入。以下是简单的步骤：

#include <iostream>

// 定义一个结构体或类表示顺序表的节点
struct Node {
    int data;
    Node* next;
};

// 插入函数
void insertInOrder(Node** head, int x) {
    // 如果列表为空，直接创建一个新的节点作为头结点
    if (*head == nullptr) {
        *head = new Node();
        (*head)->data = x;
        (*head)->next = nullptr;
    } else {
        // 找到插入位置
        Node* current = *head;
        Node* prev = nullptr;

        while (current != nullptr && current->data < x) {
            prev = current;
            current = current->next;
        }

        // 插入新节点
        if (prev != nullptr) {
            prev->next = new Node();
            prev->next->data = x;
            prev->next->next = current;
        } else {
            // 如果x大于所有现有节点，则将其放在最后
            current->next = new Node();
            current->next->data = x;
            current->next->next = nullptr;
        }
    }
}

int main() {
    // 示例用法
    Node* listHead = nullptr;  // 初始化空列表

    // 添加一些已排序的元素
    insertInOrder(&listHead, 5);
    insertInOrder(&listHead, 2);
    insertInOrder(&listHead, 8);

    // 插入新元素x
    int x = 4;
    insertInOrder(&listHead, x);

    // 打印结果以验证顺序表是否保持有序
    Node* temp = listHead;
    while (temp != nullptr) {
        std::cout << temp->data << " ";
        temp = temp->next;
    }

    return 0;
}