《大话数据结构》第三章 线性表(一) 顺序表

1.线性表定义

零个或多个数据元素的有限序列

2.线性表逻辑特性

• 除第一个和最后一个元素外,每个元素只有一个前驱和一个后继
• 第一个元素没有前驱元素
• 最后一个元素没有后继元素

3.线性表抽象数据类型

4.线性表存储结构

• 顺序存储
• 链式存储

本文先总结顺序存储及其代码实现,链式存储放在下一篇文章中。

5.顺序存储

用一段地址连续的存储单元一次存储线性表的数据元素

5.1 插入数据

5.2 删除数据

6.代码实现

public class SequenceList<T> {
    // 默认长度
    private final int DEFAULT_SIZE = 16;

    // 保存数组的长度
    private int capacity;

    // 数组,保存顺序线性表
    private Object[] elementData;

    // 顺序线性表中当前元素个数
    private int size = 0;

    // 默认长度创建空线性表
    public SequenceList() {
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }

    // 以一个初始化元素创建顺序线性表
    public SequenceList(T element) {
        this();
        elementData[0] = element;
        size++;
    }

    // 以指定长度创建顺序线性表
    public SequenceList(T element, int initSize) {
        capacity = 1;
        // 把capacity设置为大于initSize的最小的2的n次方
        while (capacity < initSize) {
            capacity <<= 1;
        }

        elementData = new Object[capacity];
        elementData[0] = element;
        size++;
    }

    // 获取线性表的大小
    public int length() {
        return size;
    }

    // 获取索引i的元素
    public T get(int i) {
        if (i < 0 || i > size - 1) {
            throw new IndexOutOfBoundsException("索引超出线性表范围");
        }
        return (T) elementData[i];
    }

    // 根据元素查找在线性表中的位置
    public int indexOf(T element) {
        for (int i = 0; i < size; i++) {
            if (elementData[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

    // 向顺序表中指定位置插入元素
    public void insert(T element, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("索引超出线性表范围");
        }
        ensureCapacity(size + 1);

        // 将指定索引处之后的所有元素后移
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }
    private void ensureCapacity(int minCapacity) {
        // 如果数组的原有长度小于目前所需的长度
        if (minCapacity > capacity) {
            // 不断的将capacity*2,知道capacity大于minCapacity
            while (capacity < minCapacity) {
                capacity <<= 1;
            }
            elementData = Arrays.copyOf(elementData, capacity);

        }
    }

    // 在线性表的末端增加一个元素
    public void add(T element) {
        insert(element, size);
    }

    // 删除指定索引处的元素
    public T delete(int index) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("索引超过线性表范围");
        }
        T oldValue = (T) elementData[index];
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }

        elementData[--size] = null;
        return oldValue;
    }

    // 删除最后一个元素
    public T remove() {
        return delete(size - 1);
    }

    // 判断线性表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空线性表
    public void clear() {
        Arrays.fill(elementData, null);
        size = 0;
    }

    public String toString(){
        if(size == 0){
            return "[]";
        }
        else{
            StringBuilder sb = new StringBuilder("[");

            for(int i=0;i<size;i++){
                sb.append(elementData[i].toString() + ", ");
            }

            int len = sb.length();

            return sb.delete(len-2, len).append("]").toString();
        }
    }

}

public class SequenceTest {
    public static void main(String[] args) {
        SequenceList<String> sequenceList = new SequenceList<>();
        sequenceList.add("hello");
        sequenceList.add("lu");
        sequenceList.add("jia");
        sequenceList.add("hao");

        System.out.println(sequenceList.toString());
        System.out.println("长度:" + sequenceList.length());
        System.out.println("获取第一个元素:" + sequenceList.get(0));
        System.out.println("查看lu的索引:" + sequenceList.indexOf("lu"));

        sequenceList.insert("lifan", 4);
        System.out.println("新的顺序表:" + sequenceList.toString());
    }
}

代码详见: GitHub

---

欢迎大家关注😁