查看“︁动态数组”︁的源代码

[[分类:线性表]]
[[分类:顺序存储结构]]
{{InfoBox
|name=动态数组
|eng_name=dynamic array
|aliases=变长数组,resizable array,growable array,array list
}}
{{#seo:
|keywords=动态数组,变长数组
|description=介绍了动态数组，即逻辑结构为线性表、存储结构为数组、长度可变（允许动态内存分配）的数据结构，即长度可变的顺序表。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2024-10-19
}}
'''动态数组'''('''dynamic array''')或'''变长数组'''('''resizable array''')指逻辑结构为[[线性表]]、存储结构为[[数组]]，且数组长度可变的数据结构。也就是长度可变的顺序表。

在有些[[编程语言]]中，动态数组可能被实现为基本的[[数组（数据类型）|数组]]类型。

动态数组通常涉及内存的动态分配、移动和动态释放，因此被称为动态数组。
本质上，动态数组和[[静态数组]]的区分是其是否涉及运行期的（即'''动态'''）内存分配释放操作。
即使长度不进行变更，如果语言允许数组长度编译时未知，在运行期重新分配，这一数组也视为不太典型的动态数组；
相反，如果编译时预设了最大长度，运行期修改其可使用范围，则应当视为不太典型的静态数组，只是这种“静态分配动态长度”的数组使用上和动态数组更加类似，有时会被误分类为动态数组。

== 语言实例 ==

{{数据结构实例
|c=包括三种：
# 通过动态分配和指针转换实现，如<syntaxhighlight inline lang="c">malloc,calloc,realloc</syntaxhighlight>系列函数
# 变长数组(variable-length array, VLA)语法（GCC 扩展，C99 采纳），不要求编译期确定长度的数组，长度可以接受整形表达式，运行时动态分配
# 柔性数组（GCC 扩展，C99 采纳），结构体最后一个成员是长度为 0 的数组，运行时加上数组一起分配内存，并通过这个指向成员后的数组基址索引元素
|c_ex=标准库及语法规则
|cpp=[https://en.cppreference.com/w/cpp/container/vector <syntaxhighlight inline lang="cpp">std::vector</syntaxhighlight>]
|cpp_ex=STL
}}

== 实现实例 ==

{{Libcxx|libc/src/__support/CPP/array.h|https://github.com/llvm/llvm-project/blob/9a3e66e314e698ffb08dba151bc098b6b8867c61/libcxx/include/vector#L388}}

{{Libstdc++|libstdc++-v3/include/std/array|https://github.com/gcc-mirror/gcc/blob/7eecc08ccf75679e6ae688d92e50afae935547ab/libstdc%2B%2B-v3/include/bits/stl_vector.h#L428}}

== GSSDS 定义 ==

{{Gitea|array/include/sds/dynamic_array/dynamic_array.h}}

== 时间复杂度估计与优化 ==

本节讨论动态数组对其逻辑结构线性表的操作实现。

=== 插入删除操作 ===

由于需要保持索引与地址的公式关系，元素的插入和删除需要较复杂的操作，见[[数组的插入、删除]]。

=== 重新分配操作 ===

动态数组的一个常见使用方式是逐渐加入新元素，如果每次扩展 <math>\Delta s</math> 的大小，此时添加 <math>n</math> 次需要添加 <math>\tfrac{n}{\Delta s}</math> 次重新的内存分配。如果每次以不大于 2 的比例增加，则这个复杂度可以被平摊到线性。这一比例称为'''增长因子'''('''growth factor''')。在不同的实现中，增长因子可能为 1.5 （如 MSVC ， Java ），也可能为 2 （如 gcc libcxx ，  clang stdlibc++）<ref>https://www.zhihu.com/question/36538542 C++ STL 中 vector 内存用尽后，为啥每次是两倍的增长，而不是3倍或其他数值？ - 知乎]</ref><ref>https://en.wikipedia.org/wiki/Dynamic_array#Growth_factor</ref> 。

=== 时间复杂度 ===

记数组长度为 <math>n</math> 。

{| class='wikitable' style='width:100%'
! colspan=2 | 操作
! 最好
! 最坏
! 平均
|-
! rowspan=3 | 基本操作
! 初始化 <code>Create</code>
| colspan=3 | 一次分配，可能和是否指定预计长度相关
|-
! 长度 <code>Length/Size</code>
| colspan=3 | <math>O(1)</math> ，用保存的长度或指针差
|-
! 清空
| colspan=3 | 一次释放，可能和长度有关
|-
! rowspan=3 | 元素获取
! 指定索引、指定位置 <code>Get</code>
| rowspan=3 colspan=3 | <math>O(1)</math> ，只需要计算地址偏移
|-
! 头部 <code>Head</code>
|-
! 尾部 <code>Rear</code>
|-
! rowspan=4 | 插入删除
! 动态内存分配附加
| colspan=3 | 平摊 <math>O(n)</math> ，每次使用增长因子扩展
|-
! 指定索引、指定位置（无重新分配） <code>Insert/Remove</code>
| <math>\Theta(1)</math> ，尾部
| <math>\Theta(n)</math> ，头部
| <math>\sim\tfrac{n}{2}=\Theta(n)</math> ，平均后续长度
|-
! 头部（无重新分配）
| colspan=3 | <math>\Theta(n)</math>
|-
! 尾部（无重新分配）
| colspan=3 | <math>\Theta(1)</math>
|-
! 元素顺序
! 指定位置前趋后继 <code>Pred/Succ</code>
| rowspan=3 colspan=3 | <math>\Theta(1)</math> ，只需要计算地址偏移
|}


{{数据结构}}