[1] 顺序表实现

一、引入顺序表

提出问题：

顺序表底层是一个数组，为什么不是直接操作数组就好了，还要单独写一个类，说底层是数组呢？？

因为顺序表可以有更多的操作：

比如一个数组，我们没有办法知道，里面有几个有效的数据。

 二、顺序表的实现

1、顺序表所具备的方法

public class MyArraylist {public int[] elem;public int usedSize;public MyArraylist(){this.elem = new int[10];}// 打印顺序表public void display() {}// 新增元素,默认在数组最后新增public void add(int data) {}// 在 pos 位置新增元素public void add(int pos, int data) {}// 判定是否包含某个元素public boolean contains(int toFind) { return true;}// 查找某个元素对应的位置public int indexOf(int toFind) { return -1;}// 获取 pos 位置的元素public int get(int pos) { return -1; }// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {}//删除第一次出现的关键字keypublic void remove(int key) { }// 获取顺序表长度public int size() { return 0; }// 清空顺序表public void clear() {}
}

2、实现各个方法

（1）打印顺序表

    // 打印顺序表/*根据usedSize判断，不能根据数组长度判断*/public void display() {for (int i = 0; i < usedSize; i++) {System.out.print(this.elem[i]+" ");}}

（2）新增元素,默认在数组最后新增

 /*判断当前顺序表是不是满的true：满    false：空*/public boolean isFull(){
//        if(this.usedSize == this.elem.length){
//            return true;
//        }else return false;//优化return this.usedSize == this.elem.length;}// 新增元素,默认在数组最后新增/*需要判断当前数组是否满了，为此写一个isFull方法1、不满进行插入2、满的进行扩容*/public void add(int data) {//扩容if(isFull()){this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[this.usedSize] =data;usedSize++;}

 （3）在 pos 位置新增元素

 // 在 pos 位置新增元素/*1、在数据结构当中，每次存储元素的时候，一定要有一个前驱信息，即插入数据不能跳着插2、注意事项：2.1 判断pos位置的合法性2.2 判断顺序表是否已满2.3 插入数据 -> 1.挪动数据 2.插入数据*/private boolean checkPosInAdd(int pos){ //封装起来，使得程序更安全if(pos <0 || pos >this.usedSize){return false;}return true;}public void add(int pos, int data) {//判断下标是否合法if(!checkPosInAdd(pos)){throw new MyArrayListIndexIllegal("pos位置不合法");}//判断是否满的if(isFull()){this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}//挪数据for (int i = this.usedSize-1; i <=pos ; i--) {this.elem[i+1] = this.elem[i];}this.elem[pos] = data;usedSize++;}

自定义异常：

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

（4）判定是否包含某个元素

 // 判定是否包含某个元素public boolean contains(int toFind) {for (int i = 0; i < this.usedSize; i++) {if(elem[i] == toFind){return true;}}return false;}

（5）查找某个元素对应的位置

如果数组存放的是类类型， 如Person person = new Person();

此时需要重写equals方法

    // 查找某个元素对应的位置public int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {if(elem[i] == toFind){return i;}}return -1;}

（6） 获取 pos 位置的元素

    // 获取 pos 位置的元素private boolean checkPosInGet(int pos){if(pos<0 || pos>=this.usedSize){return false;}return true;}private boolean isEmpty(){return this.usedSize == 0;}public int get(int pos) {if(!checkPosInGet(pos)){throw new MyArrayListIndexIllegal("获取pos下标时，位置不合法");}if(isEmpty()){throw new MyArrayListEmptyException("获取元素的时候，数组为空");}return this.elem[pos];}

自定义异常：

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

（7） 给 pos 位置的元素设为 value

    // 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {if(!checkPosInGet(pos)){throw new MyArrayListIndexIllegal("获取pos下标时，位置不合法");}this.elem[pos] =value;}

（8）删除第一次出现的关键字key

    //删除第一次出现的关键字key/*1.顺序表不为空2。顺序表有所要删除的元素key3.找到key的下标i4.将elem[i+1]的值覆盖elem[i]的值 即elem[i] = elem[i+1],usedSize--;5.注意：如果是引用类型的数组，就需要把elem[i] = null;*/public void remove(int key) {if(isEmpty()){throw new MyArrayListEmptyException("顺序表为空，不能删除");}int index = indexOf(key);if(index > 0){for (int i = index; i < usedSize-1; i++) {elem[i] = elem[i+1];}System.out.println("删除完成");this.usedSize--;}else {System.out.println("不存在你要删除的对象");}}

（9）获取顺序表长度

    // 获取顺序表长度public int size() {return this.usedSize;}

（10）清空顺序表

    // 清空顺序表public void clear() {this.usedSize = 0;/*如果是引用数据类型，需要一个一个置为空for (int i = 0; i < this.usedSize;i++) {elem[i] = null;}this.usedSize = 0;*//*或者直接把elem置为空,但这样太粗暴了，直接把elem回收了，就不能对elem进行操作了this.elem =null;*/}

三、源码

_20230409 · benxiangsj/java learning - 码云 - 开源中国 (gitee.com)https://gitee.com/benxiangsj/java-learning/tree/fe7ae6e425c4a0ed5bd886a923630e2293c90ff8/_20230409/