实现一个动态调整大小的数组_阅文集团笔试题

我们知道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()函数的返回值，即：该下标对应的整数

#include <bits/stdc++.h> using namespace std; #define INIT_SIZE 10 #define RESIZE 10 struct Array { int capacity; int used; int* arr; }; void init_Array(Array* array) { array->capacity = INIT_SIZE; array->used = 0; array->arr = (int*) malloc(sizeof(int) * INIT_SIZE); memset(array->arr, 0, INIT_SIZE * sizeof(int)); } //扩容 void resize(Array* array, int size) { if(!array) return; array->arr = (int*) realloc(array->arr, sizeof(int) * size); array->capacity = size; } void push(Array* array, int num) { if(array->capacity < array->used + 1) { resize(array, array->capacity + RESIZE); } array->arr[array->used++] = num; } int pop(Array* arr) { if(!arr) return -1; if(arr->used+1 > arr->capacity || arr->used < 0) return -1; int num = arr->arr[--arr->used]; if(arr->capacity - RESIZE > arr->used + 1) { resize(arr, arr->capacity - RESIZE); } return num; } int get(Array* arr, int idx) { if(idx >= arr->used || idx < 0) return -1; return arr->arr[idx]; } int main() { string op; int num; Array* arr = new Array; init_Array(arr); while(cin >> op) { if(op == "push") { cin >> num; push(arr, num); cout << arr->used << endl; }else if(op == "pop") { cout << pop(arr) << endl; }else if(op == "get") { cin >> num; cout << get(arr, num) << endl; } } return 0; }

#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; }

实现一个动态调整大小的数组

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题