文章目录

• 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 的大小就是元素的个数

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

不搭配