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

[[分类:线性表]]
[[分类:顺序存储结构]]
{{InfoBox
|name=静态数组
|eng_name=static array
}}
{{#seo:
|keywords=静态数组
|description=介绍了静态数组，即逻辑结构为线性表、存储结构为数组、长度不可变（不允许动态内存分配）的数据结构，即长度不可变的顺序表。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2024-7-27
}}
'''静态数组'''('''static array''')指逻辑结构为[[线性表]]、存储结构为[[数组]]，且数组长度不可变的数据结构。或者形容为长度不可变的顺序表。

在[[编程语言]]中，静态数组通常表现为一种在声明时就已经确定大小的[[数组（数据类型）|数组]]类型，长度在运行时不可变。

== 语言实例 ==

{{数据结构实例
|c=数组类型，如类型<syntaxhighlight inline lang="c">int [100]</syntaxhighlight>
|c_ex=内置类型
|cpp=[https://en.cppreference.com/w/cpp/container/array <syntaxhighlight inline lang="cpp">std::array</syntaxhighlight>]
|cpp_ver=C++11
|cpp_ex=STL
|boost=[https://www.boost.org/doc/libs/1_85_0/doc/html/array.html <syntaxhighlight inline lang="cpp">boost::array</syntaxhighlight>]
}}

== 实现实例 ==

{{Libcxx|libc/src/__support/CPP/array.h|https://github.com/llvm/llvm-project/blob/215eee60497489ae0cc7cc78c0d8b8270e057a70/libc/src/__support/CPP/array.h#L19}}

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

== GSSDS 定义 ==

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

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

本节讨论静态数组对其逻辑结构线性表的操作实现。
由于静态数组长度不可变，其创建、清空、插入、删除均与普通线性表的创建为空表、插入删除元素变化长度有区别，不参与相关问题的讨论。

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

{| class='wikitable' style='width:100%'
! colspan=2 | 操作
! 最好
! 最坏
! 平均
|-
! 基本操作
! 长度 <code>Length/Size</code>
| colspan=3 | <math>O(1)</math> ，返回值固定，可[[常量折叠]]不消耗运行时间
|-
! rowspan=3 | 元素获取
! 指定索引、指定位置 <code>Get</code>
| rowspan=3 colspan=3 | <math>O(1)</math> ，只需要计算地址偏移
|-
! 头部 <code>Head</code>
|-
! 尾部 <code>Rear</code>
|-
! 元素顺序
! 指定位置前趋后继 <code>Pred/Succ</code>
| rowspan=3 colspan=3 | <math>\Theta(1)</math> ，只需要计算地址偏移
|}


{{数据结构}}