PTA 算法2-3 从顺序表 list 中删除第 i 个元素

算法2-3 从顺序表 list 中删除第 i 个元素

分数 15

作者 陈越

单位 浙江大学

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

输入格式：

输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔；最后一行给出删除位序 i，为 int 范围内的整数。

输出格式：

如果删除的位置不合法，则不能删除，在一行中输出句子 错误：不存在这个元素。。无论是否删除成功，都在一行中顺序输出表中的元素，每个元素后面跟一个空格。

输入样例 1：

5
1 2 3 4 5
3

输出样例 1：

1 2 4 5 

输入样例 2：

5
4 3 6 8 0
0

输出样例 2：

错误：不存在这个元素。
4 3 6 8 0 

答案

#include <iostream>
using namespace std;

// 顺序表结构：存储元素的数组和当前长度
typedef struct {
    int *elem;
    int length;
} SqList;

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

// 删除元素
bool DeleteElem(SqList &L, int i) {
    if (i < 1 || i > L.length) {
        return false;
    }
    for (int j = i; j < L.length; j++) {
        L.elem[j - 1] = L.elem[j];
    }
    L.length--;
    return true;
}

// 顺序表的销毁
void DestroyList(SqList &L) {
    delete[] L.elem;
    L.elem = nullptr;
    L.length = 0;
}

int main() {
    int n, i;
    // 读取存入顺序表元素的个数
    cin >> n;
    // 初始化顺序表
    SqList L;
    InitList(L,n);
    // 将输入的n个元素存入顺序表
    for(int j = 0; j < n; j++) {
        cin >> L.elem[j];
        L.length++;
    }
    // 读取删除元素的位序
    cin >> i;
    // 删除第i个元素
    bool isDelete = DeleteElem(L,i);
    if (!isDelete) {
        cout << "错误：不存在这个元素。" << endl;
    }
    // 顺序输出表中的元素，每个元素后面跟一个空格
    for (int j = 0; j < L.length; ++j) {
        cout << L.elem[j] << " ";
    }
    DestroyList(L);
}

注意下标：

• 删除第i个元素，就是把下标为i的依次往前挪

• 所以是：

  for (int j = i; j < L.length; j++) {
          L.elem[j - 1] = L.elem[j];
      }
      L.length--;