Java顺序表（1）

🐵本篇文章将对顺序表中的方法进行模拟实现

---

一、线性表

线性表是指在逻辑结构上呈连续的线性结构，而在物理结构上不一定是连续的结构，常见的线性表有：顺序表、链表、栈、队列等

二、顺序表

顺序表一般采用数组来存储数据，因此它是一种逻辑结构上连续，在物理结构上也连续的数据结构，下面对顺序表的增删查改等操作用Java进行具体实现

先实现一个接口，在这个接口写上要实现的方法：

public interface IList {
    
    void add(int data); // 新增元素,默认在数组最后新增

    void add(int pos, int data); // 在 pos 位置插入元素

    boolean contains(int toFind); // 判定是否包含某个元素

    int indexOf(int toFind); // 查找某个元素对应的位置

    int get(int pos); // 获取 pos 位置的元素

    void set(int pos, int value); // 给 pos 位置的元素设为 value

    void remove(int toRemove); //删除第一次出现的关键字toRemove
 
    int size(); // 获取顺序表长度

    void clear(); // 清空顺序表

    void display(); // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
}

之后再创建一个MyArrayList类实现上述接口并重写接口中所有的方法

public class MyArrayList implements IList{
    public int[] elem; //存储数据

    public int usedSize; //已经放入顺序表中数据的个数

    public static final int DEFAULT_CAPACITY = 5; //顺序表中默认容量的大小为5
    
    public MyArrayList() {
        elem = new int[DEFAULT_CAPACITY];
    }

    /*以下是要重写IList接口中的方法*/
    ...

}

2.1 方法的实现

void add(int data); // 新增元素,默认在数组尾部新增

在数组的尾部新增一个元素，之前的ArrayList类中有一个变量为usedSize，用于记录顺序表中已存数据的个数，刚开始存入数据的时候usedSize为0，那么每次向数组中存入一个数据，usedSize就加1

public void add(int data) {
    elem[usedSize] = data;
    usedSize++;
}

写到这里还要考虑一个问题：如果数组满了怎么办，我们前面定义了数组的默认大小为5，如果已经向数组中存入了5个数据在存数据的话，就会抛出数组越界异常，所以在向数组中新增元素时要先判断一下数组满没满，如果满了则要扩容，然后再新增元素

public void add(int data) {
    if (usedSize == elem.length) {
        elem = Arrays.copyOf(elem, elem.length * 2);
    }

    elem[usedSize] = data;
    usedSize++;
}

Arrays.copyOf的方法定义如下：

public static int[] copyOf(int[] original, int newLength)

int[] original为源数组，newLength为该数组的新长度

---

void add(int pos, int data); // 在 pos 位置插入元素

那么接下来有一个问题，这些元素怎么移动？是从后往前移动还是从前往后移动，答案是从后往前移动，因为如果从前往后移动的话，先将2放在了3的位置处，如果再要将3移动到4位置时发现3已经被2覆盖了，所以要从5开始倒着依次向后移动

public void add(int pos, int data) {

    for (int i = usedSize; i >= pos; i--) {
               //循环条件为i >= pos，因为pos位置处的元素也要往后移动
        elem[i] = elem[i - 1];
    }

    elem[pos] = data; //移动完后，直接再pos位置处插入新增元素
}

写到这里后还要考虑两点：1.pos位置是否合法；2. 此时数组有没有满

先来看第一个：pos位置是否合法，这个很简单，我们可以在第一句加上一个判断pos的方法，如果pos不合法则抛出一个异常使程序终止

public class EmptyException extends RuntimeException{
    public EmptyException(String message) {
        super(message);
    }
}

========================================================

private void checkPosAdd(int pos) {
    if (pos < 0 || pos >= usedSize + 1) {
    //数组的下标不能为0；在一个位置插入后，必须是连续的因为前面说过顺序表在物理结构上也是连续的
        throw new PosException("下标错误");
    }
}

判断数组满没满跟之前一样，以下是该方法的最终实现：

public void add(int pos, int data) {
    checkPosAdd(pos);

    if (usedSize == elem.length) {
        elem = Arrays.copyOf(elem, 2 * elem.length);
    }

    for (int i = usedSize; i >= pos; i--) {
        elem[i] = elem[i - 1];
    }

    elem[pos] = data;
    usedSize++;
}

---

boolean contains(int toFind); // 判定数组中是否包含某个元素

实现这个方法很简单，只需要遍历一遍数组即可

public boolean contains(int toFind) {

    for (int i = 0; i < usedSize; i++) {
        if (elem[i] == toFind) {
            return true;
        }
    }

    return false;
}

---

int indexOf(int toFind); // 查找某个元素对应的位置

同样，这个方法也遍历一遍数组即可

public int indexOf(int toFind) {
    for (int i = 0; i < usedSize; i++) {
        if (elem[i] == toFind) {
            return i;
        }
    }

    return -1; //如果没有这个元素，返回-1
}

---

int get(int pos); // 获取 pos 位置的元素

要先判断一下pos位置是否合法

private void checkPosGet(int pos) {
    if (pos < 0 || pos >= usedSize) {
              //这里pos >= usedSize 的原因是usedSize代表当前已存数据的个数，该位置还没有放元素
        throw new PosException("下标错误");
    }
}

get方法的最终实现：

public int get(int pos) {
    checkPosGet(pos);
    return elem[pos];
}

---

void set(int pos, int value); // 给 pos 位置的元素设为 value

该方法的实现和get方法几乎一致

public void set(int pos, int value) {
    checkPosGet(pos);
    elem[pos] = value
}

---

void remove(int toRemove); //删除第一次出现的关键字toRemove

在移动元素之前，要先得到toRemove的下标，可以直接利用刚刚实现的indexOf方法，得到下标后开始移动元素，移动完元素就相当于已经将toRemove删除了，那么让usedSize减1

public void remove(int toRemove) {

    int pos = indexOf(toRemove);
    for (int i = pos; i < usedSize - 1; i++) {
        elem[i] = elem[i + 1];
    }

    usedSize--;
}

在方法的开始还要判断一下数组是否为空，如果为空则不能删除，可以抛出一个异常

public class EmptyException extends RuntimeException{
    public EmptyException(String message) {
        super(message);
    }
}

=======================================================

public void remove(int toRemove) {
    if (usedSize == elem.length) {
        throw new EmptyException("顺序表为空");
    }

    int pos = indexOf(toRemove);

    for (int i = pos; i < usedSize - 1; i++) {
        elem[i] = elem[i + 1];
    }

    usedSize--;
}

---

int size(); // 获取顺序表长度

直接返回usedSize即可

int size() {
    return usedSize;
}

---

void clear(); // 清空顺序表

具体实现：

    public void clear() {
        usedSize = 0; //这里的顺序表中放的都是int类型而非引用类型，所以，不用将每个元素置空
                //如果顺序表中的元素都是引用类型则应遍历数组，将每个元素置空，再将usedSize置为0                                                         
    }

---

void display(); // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的

遍历数组并打印即可：

public void display() {
    for (int i = 0; i < usedSize; i++) {
        System.out.print(elem[i] +" ");
    }
    System.out.println();
}

---

🙉本篇文章到此结束，下一篇文章将对ArrayList进行讲解