动态数组：
- 内存区域连续，即每个元素的内存地址连续。
- 可用索引查看元素，数组[索引号]。
- 指定位置删除元素，该位置之后的元素全部往前移动一位。
- 指定位置添加元素，从最后到该位置的元素全部往后移动一位。
- 物理大小：创建数组时，指定的容量大小。逻辑大小：实际已使用的容量大小。
- 扩容：数组满时，扩大数组的内存空间。（方法：开辟新的内存空间，将原数组内容复制到新的内存区域。）
- 缩容：数组使用容量远小于数组物理大小时，缩小数组的内存空间。（方法：开辟新的内存空间，将原数组内容复制到新的内存区域。）
C语言实现：
创建结构体数据类型：
typedef struct Array
{int *p; // 数组地址，即连续内存地址的首地址int length; // 数组物理大小，即最大容纳多少元素int n; // 数组逻辑大小，即实际存储多少元素
}Array; // 别名创建数组变量：
Array array;初始化数组：
void init(Array *arr, int len)
{arr->p = (int *)malloc(len * sizeof(int)); // 分配数组内存空间if(arr->p == NULL){perror("Memory allocation failed");exit(-1);}arr->length = len; // 指定数组物理大小arr->n = 0; // 逻辑大小初始化为0
}扩容、缩容：
使用realloc动态分配内存空间，若分配新内存，会将内容复制到新地址。
void resize(Array *arr, int len)
{int *t = (int *)realloc(arr->p, len * sizeof(int));// for(int k = 0; k < arr->n; k++)// {// t[k] = arr->p[k];// }arr->p = t;arr->length = len;
}添加元素：
若数组满，扩容（本文为内存空间扩大一倍）。
// 在数组尾部添加
void append(Array *arr, int data)
{if(arr->length == arr->n) // 若数组满，扩容一倍{int newlength = arr->length * 2; resize(arr, newlength);}arr->p[arr->n] = data;arr->n++; // 每添加一个元素，逻辑大小+1
}// 在数组指定位置添加元素
void insert(Array *arr, int i, int data)
{if(arr->length == arr->n) // 数组满，扩容一倍{int newlength = arr->length * 2;resize(arr, newlength);}if(i < 0 || i > arr->n) // 检查索引号是否越界{perror("index out of bounds");return ;}// 从最后一个元素到指定位置元素都要往后移动一位，空出位置给新元素int k;for(k = arr->n - 1; k >= i; k--){arr->p[k+1] = arr->p[k];}arr->p[k + 1] = data;arr->n++;
}删除元素：
若数组实际存储数据小于物理大小的一半，缩容（本文将内存空间缩小一半但不小于4）。
// 从数组尾部删除元素
int pop(Array *arr)
{if(arr->n == 0) return -1;int value = arr->p[arr->n - 1];arr->n--; // 每删除一个元素，逻辑大小-1// 若实际数据<物理大小一半，缩容，但物理大小不小于4 if(arr->n < ceil(arr->length / 2) && arr->length > 4){int newlength = ceil(arr->length / 2);resize(arr, newlength);}return value;
}// 在数组指定位置删除元素
int del(Array *arr, int i)
{if(i < 0 || i > arr->n || arr->n == 0) // 检查索引号是否越界{perror("index out of bounds");exit(-1);}int value = arr->p[i]; // 从指定位置到最后的元素都要往前移动一位for(int k = i; k < arr->n; k++){arr->p[i] = arr->p[i+1];}arr->n--;if(arr->n < ceil(arr->length / 2) && arr->length > 4) // 达到条件，缩容{int newlength = ceil(arr->length / 2);resize(arr, newlength);}return value;
}遍历数组元素，获取指定位置元素：
// 遍历数组元素
void travel(Array *arr)
{if(arr->n == 0) return ;printf("elements: ");for(int k = 0; k < arr->n; k++){printf("%d ", arr->p[k]);}printf("\n");
}// 获取指定位置元素
int get(Array *arr, int i)
{if(i < 0 || i > arr->n || arr->n == 0) // 检查索引号是否越界{perror("index out of bounds");exit(-1);}return arr->p[i];
}排序（从小到大），倒置（从最后到开头）：
// 排序（从小到大,冒泡排序,还有其他排序方法此处省略）
void sort(Array *arr)
{int x = 0;for(int k = arr->n-1; k > 0; k--){for(int i = 0; i < k; i++){if(arr->p[i] > arr->p[i+1]){int tmp = arr->p[i];arr->p[i] = arr->p[i+1];arr->p[i+1] = tmp;x = 1;}}if(x == 0) break;}
}// 倒置（从最后到开头）
void inverse(Array *arr)
{if(arr->n == 0) return;for(int i = 0, k = arr->n-1; i < k; i++, k--){int tmp = arr->p[i];arr->p[i] = arr->p[k];arr->p[k] = tmp;}
}完整代码：（array.c）
#include <stdio.h>
#include <stdlib.h>
#include <math.h>/* structure */
typedef struct Array // array structure
{int *p; // array memory addressint length; // maximum number of arrayint n; // actual number of array
}Array;/* function prototype */
void init(Array *, int); // array initialization
void resize(Array *, int); // increase or reduce the size of the array
void append(Array *, int); // add element to the end of the array
void insert(Array *, int, int); // add element to the specify location(start with 0)
void travel(Array *); // show element one by one
int pop(Array *); // delete element from the end of the array
int del(Array *, int); // delete element from the specify location of the array
int get(Array *, int); // show element at the specify location(start with 0)
void sort(Array *); // sort array from small to large
void inverse(Array *); // sort array form end to start/* main function */
int main(void)
{Array array;init(&array, 4);printf("lenght is %d, actual is %d\n", array.length, array.n);append(&array, 2);append(&array, 9);printf("lenght is %d, actual is %d\n", array.length, array.n);travel(&array);insert(&array, 1, 12);insert(&array, 0, 25);printf("lenght is %d, actual is %d\n", array.length, array.n);travel(&array);get(&array, 2); // get element that index=2(start with 0)sort(&array); // sort from small to largetravel(&array);inverse(&array); // sort from end to starttravel(&array);append(&array, 66); // actual length > length,need increase the size of the arrayprintf("lenght is %d, actual is %d\n", array.length, array.n);travel(&array);del(&array, 3);printf("lenght is %d, actual is %d\n", array.length, array.n);travel(&array);pop(&array); // actual length < length/2,need reduce the size of the arrayprintf("lenght is %d, actual is %d\n", array.length, array.n);travel(&array);pop(&array);pop(&array);pop(&array);printf("lenght is %d, actual is %d\n", array.length, array.n);travel(&array);return 0;
}/* subfunction */
void init(Array *arr, int len) // array initialization
{arr->p = (int *)malloc(len * sizeof(int));if(arr->p == NULL){perror("Memory allocation failed");exit(-1);}arr->length = len;arr->n = 0;
}void resize(Array *arr, int len) // increase or reduce the size of the array
{int *t = (int *)realloc(arr->p, len * sizeof(int));//for(int k = 0; k < arr->n; k++)//{// t[k]= arr->p[k];//}arr->p = t;arr->length = len;
}void append(Array *arr, int data) // add element to the end of the array
{if(arr->length == arr->n) // if array is full, expand the array to double size{int newlength = arr->length * 2; resize(arr, newlength);}arr->p[arr->n] = data;arr->n++;
}void insert(Array *arr, int i, int data) // add element to the specify location(start with 0)
{if(arr->length == arr->n) // if array is full, expand the array to double size{int newlength = arr->length * 2;resize(arr, newlength);}if(i < 0 || i > arr->n){perror("index out of bounds");return ;}int k;for(k = arr->n - 1; k >= i; k--) // from end to i,each element move back a place{arr->p[k+1] = arr->p[k];}arr->p[k + 1] = data; // leave an empty slot for the new elementarr->n++;
}void travel(Array *arr) // show element one by one
{if(arr->n == 0) return ;printf("elements: ");for(int k = 0; k < arr->n; k++){printf("%d ", arr->p[k]);}printf("\n");
}int pop(Array *arr) // delete element from the end of the array
{if(arr->n == 0) return -1;int value = arr->p[arr->n - 1];arr->n--;if(arr->n < ceil(arr->length / 2) && arr->length > 4) // reduce the size of array{int newlength = ceil(arr->length / 2);resize(arr, newlength);}return value;
}int del(Array *arr, int i) // delete element from the specify location of the array
{if(i < 0 || i > arr->n || arr->n == 0){perror("index out of bounds");exit(-1);}int value = arr->p[i]; // from i to end,each element move forward one placefor(int k = i; k < arr->n; k++){arr->p[i] = arr->p[i+1];}arr->n--;if(arr->n < ceil(arr->length / 2) && arr->length > 4) // reduce the size of array{int newlength = ceil(arr->length / 2);resize(arr, newlength);}return value;
}int get(Array *arr, int i) // show element at the specify location(start with 0)
{if(i < 0 || i > arr->n || arr->n == 0){perror("index out of bounds");exit(-1);}return arr->p[i];
}void sort(Array *arr) // sort array from small to large
{int x = 0;for(int k = arr->n-1; k > 0; k--){for(int i = 0; i < k; i++){if(arr->p[i] > arr->p[i+1]){int tmp = arr->p[i];arr->p[i] = arr->p[i+1];arr->p[i+1] = tmp;x = 1;}}if(x == 0) break;}
}void inverse(Array *arr) // sort array form end to start
{if(arr->n == 0) return;for(int i = 0, k = arr->n-1; i < k; i++, k--){int tmp = arr->p[i];arr->p[i] = arr->p[k];arr->p[k] = tmp;}
}编译链接： gcc -o array array.c
执行可执行文件： ./array
