数据结构 —— Java自定义代码实现顺序表，包含测试用例以及ArrayList的使用以及相关算法题

顺序表简介

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改

自定义顺序表

    以下是顺序表的类以及相关方法，接下来我将带着你**手把手**地将里面的方法**补充完**并**讲解代码逻辑**，只想看完整源码的下拉到最下面或点击目录中的完整源码，即可直接到对应位置

    首先，此处顺序表我们选择底层是由数组来实现，并定义一个变量存放数组有效元素个数，一个常量用来初始化数组的内存空间

public class SeqList {
    private int[] array;
    private int size;
    // 默认构造方法
    SeqList(){ }
    // 判断是否满了，如果满了，自动扩容
    public void fullResize(){   }
    // 新增元素,默认在数组最后新增
    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 位置的元素设为 value
    public void set(int pos, int value) { }
    //删除第一次出现的关键字key
    public void remove(int toRemove) { }
    // 获取顺序表长度
    public int size() { return 0; }
    // 清空顺序表
    public void clear() { }
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    public void display() { }
}

SeqList —— 构造方法

定义构造方法，初始化数组长度/空间，长度为上面定义的常量

    // 构造方法，初始化5个空间
    public SeqList(){
        this.elem = new int[DEFAULT_CAPACITY];
    }

display —— 打印顺序表

遍历顺序表，打印每个有效元素

    // 打印顺序表
    public void display(){
        for(int i = 0; i < this.count; i++){
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }

fullResize —— 判断是否满了，满了则扩容

判断是否满了，如果满了，自动扩容

    // 判断是否满了，如果满了，自动扩容
    public void fullResize(){
        if(this.elem.length == count){
            elem = Arrays.copyOf(elem, 2*elem.length);
        }
    }

add —— 新增元素，默认在数据最后

    新增元素，**默认在数据最后**，add执行开始，先调用fullResize判断顺序表是否满了，满了则先扩容，再添加元素，因为满了的情况下，没有位置可添加元素

    // 新增元素，默认在数据最后
    public void add(int data){
        fullResize();
        elem[count] = data;
        count++;
    }

add —— 在任意位置新增元素

    **在pos位置新增元素**，先判断pos是否合法，比如插入下标位置为-1或超出数组有效元素个数范围，那肯定不合法，不合法即抛出异常，这里的异常是**我们自己定义的**，目录中点击 **自定义异常类** 即可跳转，也可手动往下翻看

如果合法则挪动数据并插入

为什么有两个add？

这里属于方法的重载，会根据传递的参数自动选择对应的add方法

    // 在 pos 位置新增元素
    public void add(int pos, int data){
        fullResize();
        if(pos < 0 || pos > this.count){
            throw new PosOutBoundsException("add 数据时，位置不合法！");
        }
        // 挪动数据
        for(int i = this.count; i > pos; i--){
            this.elem[i] = this.elem[i-1];
        }
        // 存数据
        this.elem[pos] = data;
        this.count++;
    }

contains —— 判断是否包含某个元素

遍历顺序表，依次比较

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

indexOf —— 查找某个元素对应的位置下标

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

checkPos —— 判断参数是否合法

此处的是否合法范围的右边界是按有效元素个数来计算的

    // 判断参数是否合法(按有效元素算)
    public boolean checkPos(int pos){
        if(pos < 0 || pos >= this.count){
            return false;
        }
        return true;
    }

get —— 获取 pos 位置的元素

如果pos不合法，则抛出异常

    // 获取pos位置的元素
    public int get(int pos){
        if(!checkPos(pos)){
            throw new PosOutBoundsException("get 数据时，位置不合法!");
        }
        return this.elem[pos];
    }

set —— 修改/更新元素

给pos位置的元素设置为value [修改/更新]

    // 给pos位置的元素设置为value [修改、更新]
    public void set(int pos, int value){
        if(!checkPos(pos)){
            throw new PosOutBoundsException("set 数据时，位置不合法! ");
        }
        this.elem[pos] = value;
    }

size —— 获取顺序表的长度

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

remove —— 删除第一次出现的关键字key

    // 删除第一次出现的关键字key
    public void remove(int toRemove){
        // 如果列表为空，直接返回
        if(this.count == 0){
            return;
        }
        int index = indexOf(toRemove);
        if(index == -1){
            return;  //没有要删除的关键字
        }
        for(int i = index; i < this.count-1; i++){
            this.elem[i] = this.elem[i+1];
        }
        this.count--;
    }

clear —— 清空顺序表

    // 清空顺序表
    public void clear(){
        this.count = 0;
    }

自定义顺序表全部代码

下面的代码在上面都有，只是下面将其完整的展示了出来，供您更有效地复制和阅读代码

友情提示：下面中的 PosOutBoundsException 是我们自定义的异常，目录中点击 自定义异常类 即可跳转，也可手动往下翻看

import java.util.Arrays;

// 顺序表
public class SeqList {
    private int[] elem;
    private int count;   // 计算当前存储有效元素个数

    private static final int DEFAULT_CAPACITY = 5;  // 初始化内存空间

    // 构造方法，初始化5个空间
    public SeqList(){
        this.elem = new int[DEFAULT_CAPACITY];
    }

    // 打印顺序表
    public void display(){
        for(int i = 0; i < this.count; i++){
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }

    // 判断是否满了，如果满了，自动扩容
    public void fullResize(){
        if(this.elem.length == count){
            elem = Arrays.copyOf(elem, 2*elem.length);
        }
    }
    // 新增元素，默认在数据最后
    public void add(int data){
        fullResize();
        elem[count] = data;
        count++;
    }


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

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

    // 判断参数是否合法(按有效元素算)
    public boolean checkPos(int pos){
        if(pos < 0 || pos >= this.count){
            return false;
        }
        return true;
    }

    // 获取pos位置的元素
    public int get(int pos){
        if(!checkPos(pos)){
            throw new PosOutBoundsException("get 数据时，位置不合法!");
        }
        return this.elem[pos];
    }

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

    // 给pos位置的元素设置为value [修改、更新]
    public void set(int pos, int value){
        if(!checkPos(pos)){
            throw new PosOutBoundsException("set 数据时，位置不合法! ");
        }
        this.elem[pos] = value;
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data){
        fullResize();
        if(pos < 0 || pos > this.count){
            throw new PosOutBoundsException("add 数据时，位置不合法！");
        }
        // 挪动数据
        for(int i = this.count; i > pos; i--){
            this.elem[i] = this.elem[i-1];
        }
        // 存数据
        this.elem[pos] = data;
        this.count++;
    }

    // 删除第一次出现的关键字key
    public void remove(int toRemove){
        // 如果列表为空，直接返回
        if(this.count == 0){
            return;
        }
        int index = indexOf(toRemove);
        if(index == -1){
            return;  //没有要删除的关键字
        }
        for(int i = index; i < this.count-1; i++){
            this.elem[i] = this.elem[i+1];
        }
        this.count--;
    }


    // 清空顺序表
    public void clear(){
        this.count = 0;
    }
}

自定义异常类

单独定义一个.Java文件存写该代码

    用来在下标不合法等情况下抛出异常，第二个构造方法的意思是抛出异常时会打印出message中的信息

// 自定义异常类
public class PosOutBoundsException extends RuntimeException{
    public PosOutBoundsException(){

    }

    public PosOutBoundsException(String message){
        super(message);
    }
}

自定义顺序表的测试用例

    此段代码用来验证我们写的自定义顺序表是否正确以及功能完整程度，从测试可以看出我们写的代码非常Good

public class Main {
    public static void main(String[] args) {
//        SeqList seqList = new SeqList();
//        for(int i = 0; i < 10; i++){
//            seqList.add(i,i*10);
//        }
//        seqList.display();

        SeqList list = new SeqList();

        // 添加元素并打印列表
        list.add(1);
        list.add(2);
        list.add(3);
        list.display(); // 应该打印 "1 2 3 "

        // 判断是否包含某个元素
        System.out.println(list.contains(2)); // 应该打印 true
        System.out.println(list.contains(4)); // 应该打印 false

        // 查找元素的位置下标
        System.out.println(list.indexOf(3)); // 应该打印 2
        System.out.println(list.indexOf(4)); // 应该打印 -1

        // 获取元素
        System.out.println(list.get(0)); // 应该打印 1
        System.out.println(list.get(2)); // 应该打印 3

        // 获取列表长度
        System.out.println(list.size()); // 应该打印 3

        // 设置元素
        list.set(1, 5);
        list.display(); // 应该打印 "1 5 3 "

        // 在指定位置插入元素
        list.add(1, 4);
        list.display(); // 应该打印 "1 4 5 3 "

        // 删除第一次出现的元素
        list.remove(4);
        list.display(); // 应该打印 "1 5 3 "

        // 清空列表
        list.clear();
        list.display(); // 应该打印空行
        System.out.println(list.size()); // 应该打印 0
    }
}

控制台输出结果如下：(完全正确)

Java中自带的顺序表 —— ArrayList

📜ArrayList简介及使用全方位手把手教学(带源码)，用ArrayList实现洗牌算法，3个人轮流拿牌(带全部源码)

🧸至此，感谢您阅读这篇博客，祝您生活愉快！ o (ˉ▽ˉ；)