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

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

分数 8

作者 陈越

单位 浙江大学

请编写程序，将 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;

// 定义顺序表结构
typedef struct {
    int *data;
    int length;
} sqList;

// 初始化顺序表
void initList(sqList &L, int n) {
    L.data = new int[n+1];
    L.length = 0;
}

// 在第i个位置上插入x，并返回是否插入成功
bool insertELem(sqList &L, int i, int x){
    if (i < 1 || i > L.length+1 || L.length >= 10000) {
        return false;
    }
    // 先将下标为i以后的往后挪
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j-1];
    }
    // 再将x插入到第i个位置
    L.data[i-1] = x;
    L.length++;
    return true;
}

int main() {
    int n, x, i;
    cin >> n;

    sqList L;
    initList(L, n);
    // 将数据读取到顺序表
    for (int j = 0; j < n; j++) {
        cin >> L.data[j];
        L.length++;
    }
    //插入元素
    cin >> i >> x;
    bool isInsert = insertELem(L, i, x);
    if (!isInsert) {
        if (L.length >= 10000) {
            cout << "错误：表满不能插入。" << endl;
        } else if (i < 1 || i > L.length+1) {
            cout << "错误：插入位置不合法。" << endl;
        }
    }
    // 无论是否插入成功，都在一行中顺序输出表中的元素
    for (int j = 0; j < L.length; ++j) {
        cout << L.data[j] << " ";
    }
}