关键字

线性表、顺序存储结构

特点

无论是物理存储还是逻辑上都是一个接一个的

插入

先理解如何用Java构造一个顺序结构线性表。

• Java中线性顺序，使用数组；但是因为创建数组对象时，必须指定长度，但是构造线性表的时候要一个不是满元素的数组（才能插入）；并且能够知道它的已经使用的长度。
• 为啥要知道它的已经使用的长度？原因是：当在进行元素移动时，移动的是已经放了的元素，进行a[j+1]=a[j]才不会出现脚标异常。

代码结构

• InsertSeqList.java
• LineInsertTest.java
  InsertSeqList构造线性表顺序结构类，LineInsertTest测试
  InsertSeqList：

public class InsertSeqList {

    /**
     * 初始化线性表空间
     */
    private static final int LIST_SIZE = 10;

    /**
     * 用来存放元素
     */
    private int[] data;

    /**
     * 当前表中实际使用长度
     */
    private int length;

    public InsertSeqList() {
    }

    /**
     * 构造一个未占满空间的数组
     *
     * @param data
     * @param length
     */
    public InsertSeqList(int[] data, int length) {
        this.data = data;
        this.length = length;
    }

    public int[] getData() {
        return data;
    }

    /**
     * 插入算法，其核心是从最后一位开始后移一位，至插入位
     * i为4，length为6；在数组的i位置替换掉node
     * @param insertSeqList 有空间的list
     * @param i             插入位置（相对于排位顺序来说）
     * @param node          插入的数数字
     */
    public void insertList(InsertSeqList insertSeqList, int i, int node) throws Throwable {
        //如果已使用的长度超出初始设定的长度，抛出异常
        if (insertSeqList.length == LIST_SIZE) {
            throw new Throwable("线性表已满");
        } else if (i > insertSeqList.length || i < 1) {
            throw new Throwable("插入位置不满足");
        } else if (i <= insertSeqList.length) {
            //从最后一位开始，最后一位后移一位，直到替换位置的元素后移一位（因为插入位置的元素也要移动，所以需要等号）；
            //j也是相对于排位顺序的。那么对应数组中的位置就是a[j-1]位
            for (int j = insertSeqList.length - 1; j >= i - 1; j--) {
                data[j + 1] = data[j];
            }
            data[i - 1] = node;
        }
        //打印元素
        for (int a : insertSeqList.getData()
        ) {
            System.out.println(a);
        }
    }
}

LineInsertTest

public class LineInsertTest {
    public static void main(String[] args) {
        int[] a = new int[10];
        int use = 6;
        a[0]=0;
        a[1]=1;
        a[2]=2;
        a[3]=3;
        a[4]=4;
        a[5]=5;
        InsertSeqList insertSeqList = new InsertSeqList(a, use);
        try {
            insertSeqList.insertList(insertSeqList,3 ,12 );
        } catch (Throwable throwable) {
            throwable.printStackTrace();
        }
    }
}

上面代码结果

在第三个位置插入12：

image.png