在Java中实现顺序表

在Java中实现顺序表

文章目录

• 1.什么是顺序表
• 2.顺序表的实现

1.什么是顺序表

顺序表：是线性表的存储结构，指在一组地址连续的存储单元中依次的存储每个元素，使逻辑相邻的元素存储在物理相邻的存储单元的线性表中。

2.顺序表的实现

（1）创建一个MyArrayList类

public class MyArrayList {
    private long[] array;
    private int size;

    //创建该类的构造方法
    public MyArrayList() {
        array = new long[2];  // 1) 存元素的空间  2) 空间的容量
        size = 0;             // 元素的个数
        Arrays.fill(array, Long.MIN_VALUE); //将 Long.MIN_VALUE 假定为无效值
    }
}

（2）获取数组长度

public int size() {
      return size;
   }

（3）检查对象的正确性

public void check() {
        if (array == null) {    //表不能为空否则抛出异常
            throw new RuntimeException();
        }
        if (array.length == 0) {    //表的容量不能为0
            throw new RuntimeException();
        }
        if (size < 0) {    //元素个数不能小于0
            throw new RuntimeException();
        }
        if (size > array.length) {    //元素个数不能大于容量
            throw new RuntimeException();
        }
        for (int i = 0; i < size; i++) {    //[0,size)为有效元素，不是无效值 Long.MIN_VALUE
            if (array[i] == Long.MIN_VALUE) {
                throw new RuntimeException();
            }
        }
        for (int i = size; i < array.length; i++) {    //[size,arrya.length)都是无效值 Long.MIN_VALUE
            if (array[i] != Long.MIN_VALUE) {
                throw new RuntimeException();
            }
        }
    }

（3）定义add方法用来插入元素

尾插 *** 作（pushBack）

//e为需要插入的元素
public void add(long e) {
        enSureCapacity();   //该方法用来判断需不需要对表进行扩容
        array[size] = e;
        size++;
    }

在指定位置进行插入

//index为需插入的位置   e为需要插入的元素
public void add(int index, long e) {
        if (index < 0 || index >= size) {    //判断传入的下标是否合法
            throw new ArrayIndexOutOfBoundsException("输入下标不符合[0,size） index:" + index);
        }
        enSureCapacity();    //判断需不需要对表进行扩容
        for (int i = size - 1; i >= index; i--) {    //从后往前遍历到待插入位置
            int j = i + 1;                           
            array[j] = array[i];                     //将元素统一后移
        }
        array[index] = e;                            //将待插入元素插入
        size++;                                      //插入完成后元素个数加1
    }

enSureCapacity方法 判断是否需要扩容

private void enSureCapacity() {
        if (size < array.length) {    //元素个数小于表的容量可以继续放值，不用进行扩容
            return;
        }
        //一定放不下了，需要扩容
        int newLength = array.length * 2;    //新容量至少是array.length + 1，一般扩容至原容量的1.5~2倍
        long[] newArray = Arrays.copyOf(array, newLength);      //将原数组的newLength容量的元素复制给新数组
        Arrays.fill(newArray, size, newLength, Long.MIN_VALUE); //将新数组的无效区域赋为无效值 Long.MIN_VALUE 
        array = newArray;    //将新数组赋给原数组
    }

（4）定义delete方法用来删除元素

传入下标进行删除

 public void delete(int index) {
        if (index < 0 || index > size) {    //判断下标是否合法
            throw new ArrayIndexOutOfBoundsException("输入下标不符合[0,size] index:" + index);
        }
        for (int i = index; i < size - 1; i++) {    //从前往后遍历到待删除位置
            int j = i + 1;
            array[i] = array[j];                    //将元素整体前移
        }
        array[size - 1] = Long.MIN_VALUE;           //给无效区域赋无效值 Long.MIN_VALUE
        size--;                                     //删除元素后元素个数减1    
    }

传入值删除与值相同的元素

public void delete(long e) {
        boolean flag = false;    //判断表中是否存在要删除的元素（定义一个查找结果标志flag，默认为flase）
        for (int i = 0; i < size; i++) {
            if (array[i] == e) {    //判断表中元素是否与传入值相同
                flag = true;        //一旦找到，flag变为true，并退出循环
                break;
            }
        }
        if (flag) {      
            int j = 0;    //j一开始指向第一个元素位置    
            for (int i = 0; i < size; i++) {    //i也从第一个位置开始到最后一个元素
                if (array[i] != e) {            //不是要删除的元素就移动到j位置的元素上
                    array[j] = array[i];
                    j++;     //j的位置向后移动
                }
            }
            size = j;        //j的大小就是元素的个数
            Arrays.fill(array, size, array.length, Long.MIN_VALUE);  //将无效区域赋值为无效值 Long.MIN_VALUE
        } else {
            throw new RuntimeException("表中没有该元素无法进行删除 element:" + e);  //表中没有该元素抛出异常
        }
    }

思想：将在 i 位置上元素的移动到 j 位置的元素上
1.如果还没有碰到要删除的元素就进行元素移动

2.如果碰到了要删除的元素就跳过该元素

3.重复 1 和 2 的 *** 作

最后 j 的大小就是元素的个数

以上就是顺序表中一些基本的 *** 作，例如：遍历、元素添加、元素删除、获取数组长度、检查对象正确性。
如有错误，欢迎指正！