动态数组基本概念
最简单的数据结构-动态数组
一、静态数组的诸多问题
静态数组在编译时需要确定它的大小，且一旦确定好了数组大小，在程序运行中就无法改变其大小，主要会导致以下问题：
内存浪费由于一开始并不知道应该分配的内存空间的大小，因此当数据量很小而分配的数组空间很大时，会导致内存资源的浪费。不灵活当需要存储的数据大小超过了数组的大小时，需要程序员手动修改数组的大小，而程序运行过程中是无法做这些申请的。- 此外，数组一般存放在内存
栈区，由编译器自行管理和分配，对程序员是不可见的。一般来说，内存栈区的大小很小，因此使用过多的数组很容易导致栈溢出错误。
二、动态数组需要解决的问题
对于静态数组会导致的内存浪费，扩展不灵活，以及栈溢出风险等问题，必须设计一种新的数据结构来解决这些程序设计过程中的问题。
静态数组的初始化、增删改查以及销毁的设计原则主要有以下几点：
1. 安全性
用指针代替数组
静态数组存储在栈中，因此无法存储过大的数据量，因此在定义动态数组的数据结构时，不宜使用数组，应该用指针代替。否则会使用到大量的栈内存空间，导致栈溢出错误。
2. 实现简单
在设计动态数组的数据结构和函数时，需要注意：
- 数据结构的实现应该尽量简单。
- 函数中不宜存在大量的递归和嵌套。
- 在保证代码可读性的基础上尽可能提升代码的执行效率。
3. O(1)查找
动态数组需要保留数组的特性，即O(1)查找，在申请内存空间时需要申请一段连续的内存空间。
4. 节约内存与灵活分配存储空间
静态数组的大小应该与当前实时的动态数组中有效的数据量大小相差不多，即需要根据数据量所占内存空间的大小建立相应的动态数组。在数组初始化、删除、修改和查找动态数组数据时会改变动态数组的大小，需要设计相应的数据算法。
初始化：
在初始化动态数组时，传入与数据量大小相关的一个变量：
算法思想：
- 直接根据数据量大小新建一个同样大小的动态数组。
- 根据传入的数据个数，建立一个有一定空内存空间的动态数组，空内存空间与有数据的内存空间的比例应该适当，例如
2:8。 - 在传入的数据个数的基础上加上一个固定的数字留作特殊情况的使用，例如
10。
删除修改：
当动态数组删除或修改数据时，会改变动态数组中有效数据的个数。因此，需要根据当前空内存空间的大小对动态数组的空间进行调整。
算法思想：
何时进行扩容、收缩：
- 当空数据数量达到一定
个数时就重新对动态数组进行扩展或收缩。 - 当空数据所占
比例达到一定值时，对动态数组进行扩展或收缩。
扩容、收缩方法：
- 每次
扩容、收缩一定倍数。 - 每次
扩容、收缩固定比例。 - 自定义
扩容、收缩比例或个数。
查找：
既然动态数组是一种数据类型，因此在实际使用过程中会设计到查找特定数据，例如：在一个学校的教务系统中查找某一个班的学生并返回查找结果。
算法思想：
只需要根据需要传出的数据大小按照初始化的设计思想返回一个数组即可。
三、动态数组区别于数组的特性
1. 添加元素
只支持两种添加元素的方法：
- 在第一个空元素位置处插入。
- 在非空位置插入：将当前位置以及后续位置的非空数据依次往后顺移一个位置后插入。
2. 数组扩容
当向动态数组中添加数据时，会发生扩容：扩容操作会分配一个新的内存空间，将原有的元素全部拷贝到新的内存空间中，并释放原有的内存空间。
3. 数组缩容
当删除数组中的数据时，或发送缩容：也是会申请一个新的内存空间，将原有的元素全部拷贝到新的内存空间中，并释放原有的内存空间。
4. 删除元素
当进行删除操作时，需要将当前删除的位置处所有的数据往前移动一个位置。