数据结构与算法--顺序表(Java)

数据结构与算法—顺序表（Java）

顺序表（也称为动态数组）是一种基础的线性数据结构，其元素在内存中是连续存储的，支持随机访问，因此在查找与访问特定元素时具有较高的效率。顺序表适合存储数量较为固定且需要频繁访问的数据，例如学生成绩、图书信息等。

顺序表的基本实现

在 Java 中，我们可以用一个数组来实现顺序表。为了方便动态扩展，我们还需要维护一个当前元素数量的变量以及处理数组扩容的逻辑。以下是使用 Java 实现的一个简单的顺序表示例：

import java.util.Arrays;

public class MyArrayList {
    private Object[] data; // 存储数据的数组
    private int size;      // 当前元素个数
    private static final int DEFAULT_CAPACITY = 10; // 默认容量

    // 构造函数
    public MyArrayList() {
        data = new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    // 添加元素
    public void add(Object element) {
        if (size == data.length) {
            resize();
        }
        data[size++] = element; // 将新元素添加到数组末尾，并更新 size
    }

    // 扩容方法
    private void resize() {
        int newCapacity = data.length * 2; // 新容量是原来的两倍
        data = Arrays.copyOf(data, newCapacity); // 扩容
    }

    // 根据索引获取元素
    public Object get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        return data[index];
    }

    // 根据索引设置元素
    public void set(int index, Object element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        data[index] = element;
    }

    // 返回元素个数
    public int size() {
        return size;
    }

    // 打印顺序表内容
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i < size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) {
        MyArrayList list = new MyArrayList();
        list.add("Java");
        list.add("Python");
        list.add("C++");

        System.out.println("顺序表内容：" + list.toString()); // 输出顺序表内容
        System.out.println("第一个元素：" + list.get(0)); // 获取第一个元素

        list.set(1, "JavaScript"); // 修改元素
        System.out.println("修改后的顺序表内容：" + list.toString());
        System.out.println("元素个数：" + list.size()); // 输出元素个数
    }
}

解释代码

1. 数据存储：data 数组用于存储元素，size 表示当前有效元素的数量。
2. 添加元素：add 方法用于添加元素，如果当前数组已满，则调用 resize 方法进行扩容。
3. 扩容机制：resize 方法将数组的容量翻倍，使用 Arrays.copyOf 方法复制原数组中的元素。
4. 获取与设置：get 方法用于获取指定索引的元素，set 方法用于更新指定索引的元素。
5. 其他方法：size 方法返回当前数组中存储的有效元素数量，toString 方法用于输出数组内容的字符串。

总结

顺序表是一种简单且高效的线性数据结构，适合在需要频繁访问、添加元素的场景中使用。尽管Java已经提供了 ArrayList 类来实现动态数组，但理解顺序表的基本实现对于学习更复杂的数据结构与算法是非常重要的。通过上述示例，读者可以掌握顺序表的基本操作，并能在此基础上进行扩展和优化。