数据结构与算法 / 系统课时

静态数组

静态数组

静态数组用一段固定长度的连续空间保存同类型元素。本课将从内存布局出发,解释下标为何能实现常数时间访问,并通过一个固定容量数组类演示插入、删除、容量限制和下标边界。

学习目标

  • 能够区分数组的容量 capacity 与有效元素数量 size。
  • 能够解释索引访问、插入和删除的时间复杂度来源。
  • 能够正确处理越界、满容量和元素搬移问题。

内存布局与索引访问

静态数组在创建时就确定容量,元素按固定宽度连续排列。若首元素地址为 base,每个元素占用 w 个字节,则下标 i 的地址可直接计算为:

address(i)=base+i×waddress(i)=base+i\times w

在固定宽度、可随机访问的数组模型中,读取或写入合法下标是 Θ(1)\Theta(1)。Java 规范保证数组长度固定与下标检查,程序不直接计算对象地址。引用数组的槽位保存引用,所指对象不要求彼此相邻。连续遍历通常有利于局部性,实际布局和缓存由实现决定。

静态数组的连续内存布局与元素搬移

数组对象通常同时维护两个量:

名称 含义 合法范围
capacity 底层数组可容纳的最大元素数 创建后固定
size 当前有效元素数量 0..capacity
访问下标 已存在元素的位置 0..size - 1
插入下标 新元素可插入的位置 0..size

直接访问任意有效元素为 Θ(1)\Theta(1)。在中间插入时,需要把插入点及其后的元素向右搬移;删除时,需要把删除点之后的元素向左搬移。因此头部或中间插入、删除的最坏时间复杂度为 Θ(n)\Theta(n),尾部插入和删除在无需扩容时可达到 Θ(1)\Theta(1)。

插入、删除与边界规则

本例先检查插入下标,再检查容量。有效长度为 n 时,在 i 处插入需要向右搬 n−i 个槽位,删除 i 则向左搬 n−i−1 个槽位。成功后才更新 size。必须从后向前搬移,否则较早写入的新位置会覆盖尚未复制的旧元素。

删除操作应先保存待删除值,再从前向后搬移后续元素,最后清理原末尾位置并减少 size。对于基本类型数组,清理尾部主要用于保持状态易于观察;对于对象数组,清空引用还能避免无意延长对象生命周期。

边界判断需要区分访问与插入。访问下标等于 size 时越界,但插入下标等于 size 表示在尾部追加,是合法操作。数组已满时继续插入必须明确失败,不能静默覆盖已有元素。

完整实现与验证

下面的 Java 17 示例实现一个固定容量的整数数组。它不自动扩容,便于观察静态数组的核心行为。

java
import java.util.Arrays;

public class StaticArrayDemo {

    private static final class FixedIntArray {
        private final int[] elements;
        private int size;

        private FixedIntArray(int capacity) {
            if (capacity <= 0) {
                throw new IllegalArgumentException("容量必须大于 0");
            }
            this.elements = new int[capacity];
        }

        private int size() {
            return size;
        }

        private int capacity() {
            return elements.length;
        }

        private int get(int index) {
            checkElementIndex(index);
            return elements[index];
        }

        private void insert(int index, int value) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("非法插入下标: " + index);
            }
            if (size == elements.length) {
                throw new IllegalStateException("数组已满");
            }

            // 从后向前搬移,避免覆盖仍需复制的元素。
            for (int i = size; i > index; i--) {
                elements[i] = elements[i - 1];
            }

            elements[index] = value;
            size++;
        }

        private int delete(int index) {
            checkElementIndex(index);
            int removed = elements[index];

            // 删除点之后的元素依次左移。
            for (int i = index; i < size - 1; i++) {
                elements[i] = elements[i + 1];
            }

            elements[size - 1] = 0;
            size--;
            return removed;
        }

        private int[] toArray() {
            return Arrays.copyOf(elements, size);
        }

        private void checkElementIndex(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("非法访问下标: " + index);
            }
        }
    }

    public static void main(String[] args) {
        FixedIntArray array = new FixedIntArray(6);

        array.insert(0, 10);
        array.insert(1, 20);
        array.insert(2, 30);

        System.out.println("初始: " + Arrays.toString(array.toArray()));
        System.out.println("下标 1 的元素: " + array.get(1));

        array.insert(1, 15);
        System.out.println("在下标 1 插入 15: " + Arrays.toString(array.toArray()));

        int removed = array.delete(2);
        System.out.println("删除下标 2 的元素: " + removed);
        System.out.println("删除后: " + Arrays.toString(array.toArray()));
        System.out.println(
            "size = " + array.size() + ", capacity = " + array.capacity()
        );
    }
}

运行命令:

bash
javac -encoding UTF-8 StaticArrayDemo.java
java StaticArrayDemo

预期输出

text
初始: [10, 20, 30]
下标 1 的元素: 20
在下标 1 插入 15: [10, 15, 20, 30]
删除下标 2 的元素: 20
删除后: [10, 15, 30]
size = 3, capacity = 6

常见错误包括把 capacity 当成有效元素数量、在插入时从前向后搬移、允许 get(size)、数组满后继续写入,以及删除后忘记更新 size。验证时覆盖空状态、单元素、头尾搬移、非法下标和满容量。检查失败前后 size 与已有元素一致。这个包装类要求容量为正,但 Java 本身允许零长度数组。toArray 创建有效区间的副本,时间与额外数组空间都随 size 增长。

本课总结

  • 静态数组依靠连续内存和地址计算实现 Θ(1)\Theta(1) 索引访问。
  • capacity 表示固定容量,size 表示当前有效元素数量,两者不能混用。
  • 中间插入和删除需要搬移元素,最坏时间复杂度为 Θ(n)\Theta(n)。

下一课预告

后续将继续学习动态数组如何通过扩容突破固定容量限制,并分析偶发复制成本为何能够被多次低成本追加操作摊平。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

静态数组

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通