数据结构（二）线性表的顺序存储（顺序表）

发表于 更新于 分类于

顺序表就是顺序存储的线性表。
顺序存储是用一组地址连续的存储空间依次存放线性表中的各个元素的存储结构。

特点

  • 逻辑上相邻的数据元素，在物理存储上也相邻
  • 存储密度高，需要预先分配空间，容易造成空间浪费
  • 便于随机存取
  • 不便于插入和删除，会引起大量数据元素的移动

描述

定义类，实现IList接口。（参见：https://chenzhihao.cc/archives/394#title-1）

类定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class SqList implements IList {
    /**
     * 列表元素。
     */
    private Object[] listElems;
 
    /**
     * 记录当前链表的长度
     */
    private Integer length;
 
    /**
     * 构建指定存储空间大小的线性表
     *
     * @param size 存储空间大小
     */
    public SqList(Integer size) {
        this.length = 0;
        this.listElems = new Object[size];
    }
 
    // and other methods
}

置空

置空链表，只需要将标示长度设为0即可。

1
2
3
public void clear() {
    this.length = 0;
}

叛空

1
2
3
public boolean isEmpty() {
    return this.length == 0;
}

求长度

1
2
3
public int length() {
    return this.length;
}

某位置插入元素

  • 第一步：判满。判断当前顺序表是否已满，若满则抛出异常。
  • 第二步：临界点。判断插入点是否超出临界点，若超出则抛出异常。
  • 第三步：窜位置。将插入点之后的所有元素向后窜一位。
  • 第四步：插入。将元素放入插入点位置。
  • 第五步：重置长度。长度加一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void insert(int i, Object o) throws Exception {
    // 判满
    if (this.length == this.listElems.length) {
        throw new Exception("线性表已满");
    }
    // 判断插入位置的合法性
    if (i < 0 || i > this.length) {
        throw new Exception("插入位置不合法");
    }
    // 插入点之后的元素向后窜一位
    for (int j = this.length; j > i; j--) {
        this.listElems[j] = this.listElems[j - 1];
    }
    // 插入
    this.listElems[i] = o;
    // 长度+1
    this.length++;
}

某位置删除元素

  • 第一步：判空。判断线性表是否为空。
  • 第二步：临界点。判断删除位置是否超出临界点。若是则抛出异常。
  • 第三步：删除。将删除元素后的所有元素前移。
  • 第四步：重置长度。长度减一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void remove(int i) throws Exception {
    // 叛空
    if (isEmpty()) {
        throw new Exception("线性表为空");
    }
    // 判断删除位置的合法性
    if (i < 0 || i >= this.length) {
        throw new Exception("删除位置不合法");
    }
    // 从删除点之后向前移动元素
    for (int j = i; j < this.length - 1; j++) {
        this.listElems[j] = this.listElems[j + 1];
    }
    // 长度减一
    this.length--;
}

根据位置获取元素内容

1
2
3
4
5
6
7
8
9
10
11
public Object get(int i) throws Exception {
    // 叛空
    if (isEmpty()) {
        return null;
    }
    // 临界点判断
    if (i < 0 || i > this.length - 1) {
        throw new Exception("查找位置不合法");
    }
    return this.listElems[i];
}

根据元素内容获取位置

1
2
3
4
5
6
7
8
9
10
11
12
13
public int indexOf(Object o) {
    // 叛空
    if (isEmpty()) {
        return -1;
    }
    // 查找并返回
    for (int i = 0; i < this.length; i++) {
        if (this.listElems[i].equals(o)) {
            return i;
        }
    }
    return -1;
}

遍历

1
2
3
4
5
public void display() {
    for (int i = 0; i < this.length; i++) {
        System.out.println(this.listElems[i].toString());
    }
}

总结

  1. 顺序表是线性表的顺序存储结构的实现，底层实现常用数组。
  2. 对于顺序表，便于随机存取，不便于插入和删除，因插入和删除会造成大量数据元素的移动。
  3. 对于有n个元素的顺序表来说：插入“叛满”，删除“叛空”。
  4. 顺序表的合法操作区域：0 ≤ i ≤ length-1
  5. 对于有n个元素的顺序表来说，在第i位置插入元素，会引起n-i个元素移动，所以时间复杂度为O(n)。
  6. 对于有n个元素的顺序表来说，删除第i位置的元素，会引起n-i-1个元素移动，所以时间复杂度是O(n)。
  7. 对于查找指定位置上的元素的值，使用随机存取的方式，时间复杂度为O(1)。
  8. 对于查找指定内容的元素在顺序表上的位置，使用遍历操作。若要查找顺序表中第i个位置上的数据元素值为x的元素，需要比较i+1次；若
  9. 序表中不存在值为x的元素，此时为最坏情况，需要比较n次。因此对于该操作的平均时间复杂度为O(n)。

经过线性表的顺序存储结构的学习，我对线性表的实现和关键操作的逻辑有了更深入的理解。顺序表在Java类库中也有出现，就是ArrayList类。该类有多个构造方法，其中默认构造方法会初始化一个容量为为10的数组，超出该容量后会自动构建一个新的数组，并将就数组内的元素全部克隆到新数组中。新数组的大小是动态分配的，根据调试可知，ArrayList内部数组容量超出10之后，会以以下顺序增长10->16->25->38->58->88->..，然而在这个示例中我并没有这样的设计，只为清晰的描述顺序表的存储结构和存取逻辑。

数据结构系列的下一篇会记录线性表的链式存储结构的实现过程。