PTA 算法2-2 在顺序表 list 的第 i 个位置上插入元素 x

算法2-2 在顺序表 list 的第 i 个位置上插入元素 x

分数 15

作者 陈越

单位 浙江大学

请编写程序，将 n 个整数存入顺序表，对任一给定整数 x，将其插入顺序表中指定的第 i 个位置。注意：i 代表位序，从 1 开始，不是数组下标。

输入格式：

输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔；最后一行给出插入位置 i 和待插入的元素 x，均为 int 范围内的整数。

输出格式：

分以下几种情况输出：

• 如果顺序表中已经有 104 个元素了，则不能插入，在一行中输出句子 错误：表满不能插入。。
• 如果插入的位置不合法，则不能插入，在一行中输出句子 错误：插入位置不合法。。
• 无论是否插入成功，都在一行中顺序输出表中的元素，每个元素后面跟一个空格。

输入样例 1：

5
1 2 3 4 5
3 8

输出样例 1：

1 2 8 3 4 5 

输入样例 2：

5
4 3 6 8 0
0 1

输出样例 2：

错误：插入位置不合法。
4 3 6 8 0 

答案

#include<iostream>
using namespace std;
#define MaxSize 10000
// 顺序表结构：存储元素的数组和当前长度
typedef struct {
    int *elem;
    int length;
} SqList;

// 初始化顺序表：分配内存
void InitList(SqList &L) {
    L.elem = new int[MaxSize];
    L.length = 0;
}

// 将 x 插入顺序表中的第 i 个位置
bool ListInsert(SqList &L,int i,int x) {
    if (L.length >= MaxSize) {
        return false;
    }
    if (i < 1 || i > L.length + 1) {
        return false;
    }
    // 将第i个元素及以后的元素往后挪
    for (int k = L.length; k >= i; k--) {
        L.elem[k] = L.elem[k - 1];
    }
    // 插入第i个位置
    L.elem[i - 1] = x;
    L.length++;
    return true;
}

// 顺序表的销毁:释放内存
void DestroyList(SqList &L) {
    delete[] L.elem;
    L.elem = nullptr;
    L.length = 0;
}
int main() {
    int x,i,n;
    //输入存入到顺序表中的元素的个数
    cin >> n;

    SqList L;
    InitList(L); // 初始化

    // 读取 n 个元素，存入顺序表
    for (int j = 0; j < n; j++) {
        cin >> L.elem[j];
        L.length++;
    }

    // 读取插入位置和待插元素
    cin >> i;
    cin >> x;

    // 在 i 处插入元素 x
    bool isInsert = ListInsert(L,i,x);
    if (!isInsert) {
        if (L.length >= MaxSize) {
            cout << "错误：表满不能插入。";
            cout << endl;
        }
        if (i < 1 || i > L.length + 1) {
            cout << "错误：插入位置不合法。";
            cout << endl;
        }
    }

    // 打印顺序表
    for (int j = 0; j < L.length; j++) {
        cout << L.elem[j] << " ";
    }
    cout << endl;
    DestroyList(L);
}

注意插入逻辑

• 元素后移：在插入元素时，要从最后一个元素（下标为 L.length - 1）开始，到第 i 个元素的位置（下标为 i - 1），依次向后移动一位，为新元素腾出位置。这里要注意循环的范围和结束条件，确保所有需要后移的元素都正确移动。
• 长度更新：插入成功后，要将顺序表的长度 L.length 加 1，保证长度与实际元素个数一致。

因为下标是从0开始数的，所以插入到第i个位置，是从下标为i-1的位置开始挪到第i个位置