顺序表的基本概念及实现
顺序表（Sequential List）是一种线性表的顺序存储实现方式，常见于数组。它利用一段连续的内存空间来存储数据元素，支持快速的随机访问。由于内存地址是连续的，因此可以通过元素的索引（下标）直接访问元素，访问时间复杂度为 O(1)。
线性结构
线性结构是数据结构中最基本、最常用的一类结构，其特点是数据元素之间存在一对一的线性关系，数据元素按顺序排列。线性结构包括：
顺序表（数组）
链表
栈
队列
一、顺序表的基本概念
1. 顺序表的特点
- 连续存储：数据元素在内存中按照顺序连续存放。
- 随机访问：可以通过下标直接访问任意位置的元素，访问速度快。
- 固定容量：容量固定，初始化后大小不能改变（对于数组而言）。
- 存储类型一致：存储的元素类型必须相同。
2. 顺序表的优缺点
优点：
- 访问速度快：支持随机访问，查找元素效率高。
- 空间利用率高：不需要额外的存储空间来存放节点指针。
缺点：
- 插入和删除效率低：在中间位置插入或删除元素时，需要移动大量元素。
- 容量固定：数组的容量固定，不能动态扩容（除非手动实现扩容机制）。
二、顺序表的初始化和判空判满功能实现
1. 初始化顺序表
在 Java 中，可以使用数组或集合类来实现顺序表。下面以数组为基础，实现一个简单的顺序表。
public class SequenceList {
private int[] data; // 存储元素的数组
private int size; // 当前元素数量
private int capacity; // 顺序表容量
// 初始化顺序表
public SequenceList(int capacity) {
this.capacity = capacity;
data = new int[capacity];
size = 0;
}
}
2. 判空功能实现
判断顺序表是否为空，即判断 size 是否为 0。
// 判断顺序表是否为空
public boolean isEmpty() {
return size == 0;
}
3. 判满功能实现
判断顺序表是否已满，即判断 size 是否等于 capacity。
// 判断顺序表是否已满
public boolean isFull() {
return size == capacity;
}
三、顺序表实现之指定位置数据的增加与遍历操作
1. 在指定位置增加元素
在顺序表的指定位置插入元素，需要考虑以下情况：
-
位置合法性检查：插入位置应在
[0, size]之间。 - 顺序表是否已满：如果已满，需要先扩容（后续会介绍）。
- 元素后移：从插入位置开始，后面的元素需要依次后移一位。
// 在指定位置插入元素
public void insert(int index, int element) {
if (isFull()) {
throw new RuntimeException("顺序表已满，无法插入新元素");
}
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("插入位置不合法");
}
// 元素后移
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = element;
size++;
}
2. 遍历顺序表
遍历顺序表中的元素，依次输出或处理每个元素。
// 遍历顺序表
public void traverse() {
for (int i = 0; i < size; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
四、顺序表实现删除指定位置的元素与修改操作
1. 删除指定位置的元素
删除指定位置的元素，需要将后面的元素依次前移。
// 删除指定位置的元素
public void delete(int index) {
if (isEmpty()) {
throw new RuntimeException("顺序表为空，无法删除元素");
}
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("删除位置不合法");
}
// 元素前移
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
}
2. 修改指定位置的元素
修改指定位置的元素，即将新值赋给指定位置。
// 修改指定位置的元素
public void update(int index, int element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("修改位置不合法");
}
data[index] = element;
}
五、顺序表实现扩容操作
由于数组的容量固定，当顺序表满时，需要进行扩容。扩容的思路是创建一个更大的数组，将原数组的元素复制过去。
// 扩容操作
private void resize(int newCapacity) {
int[] newData = new int[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
capacity = newCapacity;
}
// 修改插入方法，支持自动扩容
public void insert(int index, int element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("插入位置不合法");
}
if (isFull()) {
resize(capacity * 2); // 扩容为原来的两倍
}
// 元素后移
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = element;
size++;
}
六、顺序表使用泛型适应多种类型数据
为了使顺序表适应多种类型的数据，可以使用 Java 的泛型。
public class SequenceList<T> {
private T[] data; // 存储元素的数组
private int size; // 当前元素数量
private int capacity; // 顺序表容量
// 初始化顺序表
@SuppressWarnings("unchecked")
public SequenceList(int capacity) {
this.capacity = capacity;
data = (T[]) new Object[capacity];
size = 0;
}
// 判空
public boolean isEmpty() {
return size == 0;
}
// 判满
public boolean isFull() {
return size == capacity;
}
// 插入元素
public void insert(int index, T element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("插入位置不合法");
}
if (isFull()) {
resize(capacity * 2);
}
for (int i = size -1; i >= index; i--) {
data[i +1] = data[i];
}
data[index] = element;
size++;
}
// 删除元素
public void delete(int index) {
if (isEmpty()) {
throw new RuntimeException("顺序表为空，无法删除元素");
}
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("删除位置不合法");
}
for (int i = index; i < size -1; i++) {
data[i] = data[i +1];
}
size--;
// 缩容（可选）
if (size > 0 && size == capacity / 4) {
resize(capacity / 2);
}
}
// 修改元素
public void update(int index, T element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("修改位置不合法");
}
data[index] = element;
}
// 获取元素
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("获取位置不合法");
}
return data[index];
}
// 遍历顺序表
public void traverse() {
for (int i = 0; i < size; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
// 扩容/缩容
@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
T[] newData = (T[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
capacity = newCapacity;
}
}
七、测试顺序表
编写一个测试类，验证顺序表的各项功能。
public class SequenceListTest {
public static void main(String[] args) {
SequenceList<Integer> list = new SequenceList<>(5);
// 插入元素
list.insert(0, 10);
list.insert(1, 20);
list.insert(2, 30);
list.insert(1, 15);
list.insert(3, 25);
list.insert(5, 35); // 触发扩容
System.out.print("插入元素后：");
list.traverse();
// 删除元素
list.delete(2);
System.out.print("删除索引为 2 的元素后：");
list.traverse();
// 修改元素
list.update(3, 100);
System.out.print("修改索引为 3 的元素后：");
list.traverse();
// 获取元素
int element = list.get(2);
System.out.println("索引为 2 的元素为：" + element);
// 判空
System.out.println("顺序表是否为空：" + list.isEmpty());
// 判满
System.out.println("顺序表是否已满：" + list.isFull());
}
}
运行结果：
插入元素后：10 15 20 25 30 35
删除索引为 2 的元素后：10 15 25 30 35
修改索引为 3 的元素后：10 15 25 100 35
索引为 2 的元素为：25
顺序表是否为空：false
顺序表是否已满：false
- 顺序表的基本概念：顺序表利用连续的内存空间存储数据，支持快速的随机访问。
-
初始化和判空判满：在初始化时指定容量，判空判满通过
size和capacity比较实现。 - 增加与遍历操作：在指定位置插入元素时，需要将后续元素后移；遍历时依次访问每个元素。
- 删除与修改操作：删除指定位置元素需要将后续元素前移；修改操作直接更新指定位置的值。
- 扩容操作：当顺序表满时，通过创建更大的数组并复制元素来实现扩容。
- 使用泛型适应多种类型数据：通过泛型，使顺序表可以存储任意类型的数据，提高了通用性。
