简介

顺序表（Sequential List）是一种基于数组实现的数据结构，用于存储一组具有顺序关系的元素。顺序表的特点是将元素按照一定的顺序存储在连续的内存空间中，通常使用数组来实现。顺序表支持随机访问，即可以通过下标直接访问任意位置的元素。

顺序表的主要特点：

  1. 连续存储：顺序表中的元素存储在连续的内存空间中，这使得访问任意元素的时间复杂度为 O(1)。
  2. 固定大小（静态顺序表）：在静态顺序表中，存储空间的大小是固定的，通常通过静态数组实现。
  3. 动态扩展（动态顺序表）：在动态顺序表中，存储空间可以根据需要进行扩展，通常通过动态数组或链表实现。
  4. 随机访问：由于元素是连续存储的，可以通过下标直接访问任意位置的元素，时间复杂度为 O(1)。
  5. 插入和删除效率较低：在顺序表中插入或删除元素时，可能需要移动其他元素，导致时间复杂度为 O(n)。

顺序表类型

  1. 静态顺序表：静态顺序表使用静态数组来存储数据，数组的大小在编译时确定，无法动态扩展。
  2. 动态顺序表：动态顺序表使用动态数组或链表来存储数据，可以根据需要动态扩展存储空间。

顺序表的操作

  1. 初始化：创建一个空的顺序表。
  2. 插入：在指定位置插入一个元素。
  3. 删除：删除指定位置的元素。
  4. 查找：查找指定元素的位置。
  5. 修改：修改指定位置的元素。

使用Rust实现顺序表（SeqList）

定义顺序表结构

首先，定义一个名为 SeqList 的结构体，它包含两个字段： data 是一个动态数组 Vec<T>，用于存储实际的数据元素； length 是一个 usize 类型的字段，用于记录当前顺序表中元素的数量。

#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct SeqList<T> {
    data: Vec<T>,
    length: usize,
}

derive 宏主要是简化一些操作，比如 Debug 用于调试打印，Clone 用于克隆，PartialEq 和 Eq 用于比较，Default 用于默认初始化。

自定义错误类型

为了处理顺序表操作中的错误情况，定义了一个枚举类型 SeqListError，它包含了两种可能的错误： IndexOutOfBounds 表示索引越界，NotEnoughCapacity 表示容量不足（虽然在本实现中并未使用）。

#[derive(Debug, PartialEq, Eq)]
pub enum SeqListError {
    IndexOutOfBounds,
    NotEnoughCapacity,
}

实现顺序表的基本操作

初始化

new 函数用于初始化一个顺序表。默认情况下，顺序表的容量为 16，并且初始化为 T::default() 的值，T 必须实现 Default trait。 这里使用Vec::with_capacity创建一个新的Vec，并预分配16个元素的空间，然后使用for循环将每个元素初始化为T::default()的值。 注意，push操作是必须的，因为Vec::with_capacity只是预分配了空间，并没有实际创建元素。

impl<T: Clone + Default + Copy> SeqList<T> {
    pub fn new() -> Self {
        let mut d = Vec::with_capacity(16);
        for _ in 0..16 {
            d.push(T::default());
        }

        SeqList { data: d, length: 0 }
    }
}

信息

信息: 后续函数都默认被同一个impl包裹，因此不再重复。

获取长度和判断是否为空

len 函数返回当前顺序表的长度，is_empty 函数判断顺序表是否为空。

pub fn len(&self) -> usize {
    self.length
}

pub fn is_empty(&self) -> bool {
    self.length == 0
}

获取元素

get 函数根据索引获取元素，如果索引越界，则返回 SeqListError::IndexOutOfBounds 错误。

提示

提示: 这里对Resule的用法进行简单说明，其原型为Result<T,E>，其中T表示成功时返回的类型，E表示失败时返回的类型（文中为SeqListError）。

Ok(self.data[index].clone()) 表示成功时返回元素的克隆，即为T

Err(SeqListError::IndexOutOfBounds) 表示失败时返回索引越界错误，即为E

更多信息请查阅 Rust Result

pub fn get(&self, index: usize) -> Result<T, SeqListError> {
    if index < self.length {
        Ok(self.data[index].clone())
    } else {
        Err(SeqListError::IndexOutOfBounds)
    }
}

添加元素

add 函数在顺序表末尾添加一个元素。如果当前容量不足，则自动扩容。

pub fn add(&mut self, item: T) {
    if self.length >= self.data.len() {
        self.data.resize(self.data.len() * 2, T::default());
    }
    self.data[self.length] = item;
    self.length += 1;
}

设置元素

set 函数根据索引设置元素的值，如果索引越界，则返回 SeqListError::IndexOutOfBounds 错误。

pub fn set(&mut self, index: usize, item: T) -> Result<(), SeqListError> {
    if index >= self.length {
        return Err(SeqListError::IndexOutOfBounds);
    }
    self.data[index] = item;
    Ok(())
}

删除元素

del 函数根据索引删除元素，并返回被删除的元素。如果索引越界，则返回 SeqListError::IndexOutOfBounds 错误。

pub fn del(&mut self, index: usize) -> Result<T, SeqListError> {
    if index >= self.length {
        return Err(SeqListError::IndexOutOfBounds);
    }

    let ret = self
        .data
        .get(index)
        .cloned()
        .ok_or(SeqListError::IndexOutOfBounds)?; // 获取被删除元素

    // 将后面的元素向前移动
    self.data.copy_within(index + 1..self.length, index);

    self.length -= 1;
    Ok(ret)
}

插入元素

insert 函数在指定的索引位置插入一个元素。如果索引越界，则返回 SeqListError::IndexOutOfBounds 错误。如果容量不足，则自动扩容。

pub fn insert(&mut self, index: usize, item: T) -> Result<(), SeqListError> {
    if index > self.length {
        return Err(SeqListError::IndexOutOfBounds);
    }

    // 如果需要扩容
    if self.length >= self.data.len() {
        self.data.resize(self.data.len() * 2, T::default());
    }

    // 将元素后移
    self.data.copy_within(index..self.length, index + 1);

    // 插入新元素
    self.data[index] = item;
    self.length += 1;

    Ok(())
}