线性表

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。

前驱元素

若A元素在B元素的前面，则称A为B的前驱元素

后继元素

若B元素在A元素的后面，则称B为A的后继元素

线性表的特征：数据元素之间具有一种“一对一”的逻辑关系。

1. 第一个数据元素没有前驱，这个数据元素被称为头结点；
2. 最后一个数据元素没有后继，这个数据元素被称为尾结点；
3. 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。
   如果把线性表用数学语言来定义，则可以表示为(a1,…ai-1,ai,ai+1,…an)，ai-1领先于ai,ai领先于ai+1，称ai-1是ai的
   前驱元素，ai+1是ai的后继元素

线性表的分类：

线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序
表和链表。

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存
储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元
素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

顺序表实现

顺序表API设计

类名	SequenceList
构造方法	SequenceList(int capacity)：创建容量为capacity的SequenceList对象
成员方法	1.public void clear()：空置线性表 2.publicboolean isEmpty()：判断线性表是否为空，是返回true，否返回false 3.public int length():获取线性表中元素的个数 4.public T get(int i):读取并返回线性表中的第i个元素的值 5.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。 6.public void insert(T t):向线性表中添加一个元素t 7.public T remove(int i):删除并返回线性表中第i个数据元素。 8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返 回-1。
成员变 量	1.private T[] eles：存储元素的数组 2.private int N:当前线性表的长度

顺序表代码实现

package com.jiahao.linear;

/**
 * @author HuJiahao
 * @version 1.0
 * @date 2020/11/16 20:12
 */
public class SequenceList<T> {
    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;

    //构造方法
    public SequenceList(int capacity) {
        //初始化数组
        this.eles = (T[]) new Object[capacity];
        this.N = 0;
    }

    //将一个线性表置为空表
    public void clear() {
        this.N = 0;
    }

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

    //获取线性表的元素
    public int length() {
        return N;
    }

    //获取指定位置的元素
    public T get(int i) {
        return eles[i];
    }

    //向线性表中添加元素t
    public void insert(T t) {
        eles[N++] = t;
    }

    //在i元素处插入元素t
    public void insert(int i, T t) {
        for (int index = N; index > i; index--) {
            eles[index] = eles[index - 1];
        }
        eles[i] = t;

        //表长度增一
        N++;
    }

    //删除指定位置i的元素，并返回该元素
    public T remove(int i) {
        //记录索引i处的值
        T current = eles[i];
        //索引i后面的元素依次向前移动一位
        for(int index = i;index<N-1;index++){
            eles[index]=eles[index+1];
        }
        N--;
        return current;
    }

    //查找t元素第一次出现的位置
    public int indexoOf(T t){
        for(int i=0;i<N;i++){
            if(eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }
}

测试类：

package com.jiahao.linear;

/**
 * @author HuJiahao
 * @version 1.0
 * @date 2020/11/18 16:48
 */
public class SequenceListTest {

    public static void main(String[] args) {
        //创建顺序表对象
        SequenceList<String> s1 = new SequenceList<>(10);
            //测试插入
            s1.insert("科比");
            s1.insert("詹姆斯");
            s1.insert("韦德");
            s1.insert("欧文");

            s1.insert(1,"库里");
            //测试获取
        String result = s1.get(4);
        System.out.println("获取索引1处的结果为："+result);

        String removeResult = s1.remove(0);
        System.out.println("删除的元素是："+removeResult);

        s1.clear();
        System.out.println("清空后的线性表中的元素个数"+s1.length());


    }
}