【PTA刷题】 顺序表（删除）(代码+详解)

题目

已知一组数据，采用顺序存储结构存储，其中所有的元素为整数。设计一个算法，删除元素值在[x,y]之间的所有元素

输入格式:

输入包含三行数据，第一行是表中元素个数，第二行是顺序表的各个元素，第三行是区间x和y。

输出格式:

删除元素值在[x,y]之间的所有元素后，输出新的顺序表。(最后无空格)

输入样例:

在这里给出一组输入。例如：

10
55 11 9 15 67 12 18 33 6 22
10 20

输出样例:

在这里给出相应的输出。例如：

55 9 67 33 6 22

C代码

#include<stdio.h>

int main(){
    int n; // 定义一个整数 n，用于存储数组中元素的数量
    scanf("%d",&n); // 读取用户输入的元素数量

    int arr[1000]; // 定义一个整数数组，最大长度为1000
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]); // 循环读取用户输入的数组元素
    }

    int x, y; // 定义两个整数 x 和 y，表示要删除的元素值的区间
    scanf("%d %d", &x, &y); // 读取区间 x 和 y 的值

    int newSize = 0; // 定义一个新的变量用于存储删除元素后的数组长度
    for(int i = 0; i < n; i++){
        if(arr[i] < x || arr[i] > y){ // 检查当前元素是否不在 x 和 y 的区间内
            arr[newSize] = arr[i]; // 将不在区间内的元素移到数组前端
            newSize++; // 更新新数组的长度
        }
    }

    for(int i = 0; i < newSize; i++){ // 遍历新数组
        printf("%d", arr[i]); // 打印每个元素
        if(i < newSize - 1){ 
            printf(" "); // 如果不是最后一个元素，则打印一个空格
        }
    }

    return 0; // 程序结束
}

详解

上面的代码给出了详细的注释,目的是为了帮助你更好的理解,你平时写代码的时候可以不用添加这麽多注释.

这个题目的目的是从一个顺序存储的整数数组中删除所有在区间 [x, y] 内的元素。现在，我将详细解释这个算法的运作原理和代码的各个部分。

变量初始化和输入读取:

• int n; 用于存储数组中元素的数量。
• scanf("%d",&n); 读取元素数量。
• int arr[1000]; 定义一个大小为 1000 的整数数组，假设数组的最大长度不会超过 1000。
• 接下来的循环用于读取数组中的元素。
• int x, y; 用于存储区间的边界值 x 和 y。
• scanf("%d %d",&x,&y); 读取 x 和 y 的值。

删除操作:

• 定义一个新的变量 int newSize = 0; 用于记录删除元素后数组的新长度。
• 接下来的循环遍历数组 arr。
• 对于每个元素 arr[i]，检查其是否不在区间 [x, y] 内（即 arr[i]<x||arr[i]>y）。
• 如果元素不在区间内，它将被“保留”，即 arr[newSize] = arr[i]; newSize++;。这里我们实际上是在原数组上进行覆盖操作，将不需要删除的元素向数组的前端移动。

输出结果:

• 最后一个循环用于输出新数组。
• 循环遍历新数组的每个元素，并打印它们。
• 如果当前元素不是最后一个元素，那么在它后面打印一个空格，以满足输出格式要求。

这个算法的关键点在于它原地（in-place）修改了数组，而没有使用额外的空间来存储结果。这样做既节省了空间，又保持了算法的效率。