静态数组
| 静态数组 | |
|---|---|
| 术语名称 | 静态数组 |
| 英语名称 | static array |
静态数组(static array)指逻辑结构为线性表、存储结构为数组，且数组长度不可变的数据结构。或者形容为长度不可变的顺序表。
在编程语言中，静态数组通常表现为一种在声明时就已经确定大小的数组类型，长度在运行时不可变。
语言实例
| 静态数组 | |||
|---|---|---|---|
| 语言 | 版本/库 | 对应内容 | 说明 |
| C | C89 | 数组类型，如类型int [100]
|
内置类型 |
| C++ | C++11 | std::array
|
STL |
| C++ | Boost | boost::array
|
- |
实现实例
libcxx: libc/src/__support/CPP/array.h
libstdc++: libstdc++-v3/include/std/array
GSSDS 定义
GSSDS: array/include/sds/array/array.h
时间复杂度估计与优化
本节讨论静态数组对其逻辑结构线性表的操作实现。 由于静态数组长度不可变，其创建、清空、插入、删除均与普通线性表的创建为空表、插入删除元素变化长度有区别，不参与相关问题的讨论。
记数组长度为 [math]\displaystyle{ n }[/math] 。
| 操作 | 最好 | 最坏 | 平均 | |
|---|---|---|---|---|
| 基本操作 | 长度 Length/Size
|
[math]\displaystyle{ O(1) }[/math] ，返回值固定，可常量折叠不消耗运行时间 | ||
| 元素获取 | 指定索引、指定位置 Get
|
[math]\displaystyle{ O(1) }[/math] ，只需要计算地址偏移 | ||
头部 Head
| ||||
尾部 Rear
| ||||
| 元素顺序 | 指定位置前趋后继 Pred/Succ
|
[math]\displaystyle{ \Theta(1) }[/math] ，只需要计算地址偏移 | ||