2021届阅文C 方向笔试卷 5/13 实现一个动态调整大小的数组

2021届阅文C 方向笔试卷 企业提供原题01:56:12
5/13
[编程题]实现一个动态调整大小的数组
时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

我们知道C++的数组需要在编译时决定大小，但很多时候，我们往往不能提前预估数组的大小，为此我们设计一个动态数组，即：当向数组中添加新元素时，如果数组空间不够，那么自动对数组进行扩容；如果从数组中删除了较多元素，那么也可以自动对数组进行缩容。

请实现一个简化的动态数组，该数组存储整数（int），只提供三个操作：
1. 向数组尾部追加一个新元素，如果空间不够，那么自动扩容，同时要求该追加操作的均摊时间复杂度为O(1)：void push(int num);
2. 从数组尾部删除一个元素，如果数组不为空，返回被删除的元素，如果数组为空，返回-1，不执行删除操作。当删除较多元素后，可以对数组进行缩容，但要求从尾部删除元素的操作，均摊时间复杂度为O(1): int pop();
3. 根据数组下标获取对应的整数，如果下标越界，返回-1，时间复杂度O(1)：int get(int idx);


输入描述:
输入为一系列的操作，一行一个操作，操作分为三类：
1. 从尾部追加新元素，格式为：push + 空格 + 整数
2. 删除尾部元素，格式为：pop
3. 根据下标获取元素，格式为：get + 空格 + 下标索引

输出描述:
每个操作对应一行输出：
1. 对于push操作，输出push之后数组的大小
2. 对于pop操作，输出pop()函数的返回值，即：删除的整数
3. 对于get操作，输出get()函数的返回值，即：该下标对应的整数

输入例子1:
push 1
push 3
pop
push 4
get 0
get 4

输出例子1:
1
2
3
2
1
-1

C语言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
  
#define CMD_PUSH "push"
#define CMD_POP "pop"
#define CMD_GET "get"
typedef struct array_type{
    int *array_base;
    int size;
}array_t, *parray_t;
  
int *auto_array_creat(){
    parray_t pARRAY = NULL;
    pARRAY = (parray_t)malloc(sizeof(array_t));
    memset(pARRAY, 0, sizeof(array_t));
    return pARRAY;
}
  
void destory(parray_t pARRAY){
    free(pARRAY->array_base);
    free(pARRAY);
}
  
int push(int data, parray_t pARRAY){
    pARRAY->array_base = (int *)realloc(pARRAY->array_base, (pARRAY->size + 1)*sizeof(int));
    pARRAY->array_base[pARRAY->size] = data;
    pARRAY->size = pARRAY->size + 1;
    return pARRAY->size;
}
  
int pop(parray_t pARRAY){
    if(pARRAY->size <= 0) return -1;
    int ret = pARRAY->array_base[pARRAY->size - 1];
    pARRAY->array_base = (int *)realloc(pARRAY->array_base, (pARRAY->size - 1)*sizeof(int));
    pARRAY->size = pARRAY->size - 1;
    return ret;
}
  
int get(int index, parray_t pARRAY){
    return (index < 0 || index >= pARRAY->size)? -1:pARRAY->array_base[index];
}
  
int main(){
    parray_t pARRAY = NULL, pARRAY_TMP = NULL;
    char cmd[10];
    int data;
    if(NULL == (pARRAY = auto_array_creat())){
        printf("create auto_array failed.\n");
        return -1;
    }
    pARRAY_TMP = pARRAY;
      
    while(EOF != scanf("%s", cmd)){
        if(strcmp(cmd, CMD_PUSH) >= 0){
            scanf("%d", &data);
            printf("%d\n", push(data, pARRAY));
        }
        else if(strcmp(cmd, CMD_POP) >= 0){
            printf("%d\n", pop(pARRAY));
        }
        else if(strcmp(cmd, CMD_GET) >= 0){
            scanf("%d", &data);
            printf("%d\n", get(data, pARRAY));
        }
    }
  
    destory(pARRAY);
    pARRAY = NULL;
    pARRAY_TMP = NULL;
 
    return 0;
}