数据结构(Java实现)：顺序表

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

2.顺序表

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

2.1自己实现一个List接口

public interface IList {
    // 新增元素,默认在数组最后新增
    void add(int data);
    // 在 pos 位置新增元素
    void add(int pos, int data);
    // 判定是否包含某个元素
    boolean contains(int toFind);
    // 查找某个元素对应的位置
    int indexOf(int toFind);
    // 获取 pos 位置的元素
    int get(int pos);
    // 给 pos 位置的元素设为 value -> 更新
    void set(int pos, int value);
    //删除第一次出现的关键字key
    void remove(int toRemove);
    //删除所有关键字key
    public void removeAll(int toRemove);
    // 获取顺序表长度
    int size();
    // 清空顺序表
    void clear();
    // 打印顺序表，
    // 注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    void display();
    //判断线性表是否满了
    boolean isFull();
}

2.2 IList接口的实现

下面是具体实现的代码

public class MyArray implements IList{
    public int[] values1;//存储具体值
    public int usedSize;//线性表中数据个数
    public MyArray(){
        usedSize=0;
        values1=new int[10];
    }
    //判满
    public boolean isFull(){
        return usedSize == values1.length;
    }
    //尾插
    @Override
    public void add(int data) {
        if(isFull()){
            values1= Arrays.copyOf(values1,usedSize*2);
        }
        values1[usedSize]=data;
        usedSize++;
    }
//判断指定位置插入数据的这个指定位置是否合法
    private void posLegal(int pos)throws PosIllegalException{
        if(pos<0||pos>usedSize){
            throw new PosIllegalException();
        }
    }
    //指定位置插入数据
    @Override
    public void add(int pos, int data) {
        if(isFull()){
            values1= Arrays.copyOf(values1,usedSize*2);
        }
        try {
            posLegal(pos);
        }catch (PosIllegalException e){
            e.printStackTrace();
        }
        for (int i=usedSize;i>pos;i--){
            values1[i]=values1[i-1];
        }
        values1[pos]=data;
        usedSize++;
    }
    //是否存在目标值
    @Override
    public boolean contains(int toFind) {
        for(int i=0;i<usedSize;i++){
            if(toFind==values1[i]){
                return true;
            }
        }
        return false;
    }
    //返回需要找到值的下标
    @Override
    public int indexOf(int toFind) {
        for(int i=0;i<usedSize;i++){
            if(toFind==values1[i]){
                return i;
            }
        }
        return -1;
    }
    //判断获取指定下标值或者修改指定位置的值的指定位置是否合法
    private void posLegal1(int pos)throws PosIllegalException{
        if(pos<0||pos>=usedSize){
            throw new PosIllegalException();
        }
    }
    //获取指定下标的值
    @Override
    public int get(int pos) {
        try {
            posLegal1(pos);
        }catch (PosIllegalException e){
            e.printStackTrace();
        }
        return values1[pos];
    }
    //修改指定下标的值
    @Override
    public void set(int pos, int value) {
        try {
            posLegal(pos);
        }catch (PosIllegalException e){
            e.printStackTrace();
        }
        values1[pos]=value;
    }
    //移除首个出现的目标值
    @Override
    public void remove(int toRemove) {
        int pos=indexOf(toRemove);
        for(int i=pos;i<usedSize-1;i++){
            values1[i]=values1[i+1];
        }
        usedSize--;
    }
    //移除所有目标值
    public void removeAll(int toRemove){
        int pos=indexOf(toRemove);
        int count=1;
        for(int i=pos,j=pos+1;j<usedSize;i++,j++){
            if(values1[j]==toRemove){
                j++;
                count++;
            }
            values1[i]=values1[j];
        }
        usedSize-=count;
    }
    //获取顺序表数据个数
    @Override
    public int size() {
        return usedSize;
    }
    //清空顺序表
    @Override
    public void clear() {
        usedSize=0;
        values1=null;
    }
    //打印顺序表
    @Override
    public void display() {
        for(int i=0;i<usedSize;i++){
            System.out.println(values1[i]);
        }
    }

}

自定义指定位置非法异常

public class PosIllegalException extends RuntimeException{
    public PosIllegalException(){

    }
    public PosIllegalException(String arg){
        super(arg);
    }
}

2.3 测试代码

实现完上面代码后可通过下方代码进行测试

public static void main(String[] args) {
        IList myArray=new MyArray();
        myArray.add(1);
        myArray.add(2);
        myArray.add(3);
        myArray.add(4);
        myArray.add(5);
        myArray.add(6);
        myArray.add(1);
        myArray.add(7);
        myArray.add(3,99);
        System.out.println( myArray.contains(99));
        System.out.println(myArray.indexOf(99));
        System.out.println(myArray.get(5));
        myArray.set(4,23);
        myArray.remove(23);
        myArray.removeAll(1);
        System.out.println(myArray.size());
        System.out.println("=======");
        myArray.display();
        myArray.clear();
        System.out.println("========");
        myArray.display();
    }