数据结构-顺序表

简介

顺序表应该是最简单的数据结构了吧，顺序表逻辑上是一个线性表，同时在物理存储上也是线性存储的结构，同样相对应的有一个链表，链表逻辑上线性存储上不满足线性的存储结构。java 数组就是一个顺序表，由于 java 用不了 C 和 C++ 的指针，所以下面只能用数组来替代了

顺序表优势在于查找，劣势在于插入和删除，因为查找直接可以找到值，插入和删除则需要通过遍历重新调整表结构

Java 实现

逻辑思路：

顺序表的插入会将数据一个个的后移，顺序表删除会把数据一个个前移，顺序表依据下标查询会很简单，但是依据值查询还是逃不了遍历，其就是一个数组结构

代码实现：

// 顺序表
public class SequenceList {
    // 顺序表节点
    private int[] arr;
    // 顺序表默认长度
    private static final int DEFAULT_CAPACITY = 10;
    // 顺序表中元素个数
    private int count;
    
    // 初始化顺序表存储（未指明大小）
    public SequenceList() {
        count = 0;
        arr = new int[DEFAULT_CAPACITY];
    }
    // 初始化顺序表存储（指明大小）
    public SequenceList(int capacity) throws Exception {
        if (capacity < 0)
            throw new Exception("顺序表大小不允许小于0！");
        count = 0;
        arr = new int[capacity];
    }
    
    // 顺序表尾部新增
    public void add(int e) throws Exception {
        if (count >= arr.length)
            throw new Exception("顺序表存满，不允许再存入！");
        arr[count++] = e;
    }
    
    // 顺序表根据下标查找值
    public int getValue(int index) throws Exception {
        if (index < 0)
            throw new Exception("下标不允许小于0！");
        if (index >= count)
            throw new Exception("下标超出了，没有数据存入！");
        return arr[index];
    }
    // 顺序表根据值查找下标
    public int getIndex(int value) {
        for (int i = 0; i < count; i++)
            if (arr[i] == value)
                return i;
        return -1;
    }
    
    // 顺序表依据下标插入，其他数据后移
    public void insert(int index, int e) throws Exception {
        if (index < 0)
            throw new Exception("下标不允许小于0！");
        if (index >= count)
            throw new Exception("下标超出了，没有数据存入！");
        if (count >= arr.length)
            throw new Exception("顺序表存满，不允许再存入！");
        for (int i = count - 2; i >= index; i--)
            arr[i+1] = arr[i];
        arr[index] = e;
    }
    
    // 顺序表依据下标删除
    public int delete(int index) throws Exception {
        if (index < 0)
            throw new Exception("下标不允许小于0！");
        if (index >= count)
            throw new Exception("下标超出了，没有数据存入！");
        int e = arr[index];
        for (int i = index + 1; i <= count - 1; i++)
            arr[i-1] = arr[i];
        count--;
        return e;
    }
}