【java数据结构】顺序表-二、顺序表

时间：2024-10-04 07:44:24

2.1 线性表

线性表是n个具有相同特征的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表，链表，栈，队列…
线性表在逻辑上时线性结构，也就是说连续的一条直线。但是在物理结构上并不一定是连续的。线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.2 顺序表

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

2.2.1 顺序表接口的实现

顺序表的接口包含以下方法：

public interface IList {
    //给数组增加新元素
    public void add(int data);
    //判断数组数据是否为满
    boolean isFull();
    // 在 pos 位置新增元素
    public void add(int pos, int data);
    // 判定是否包含某个元素
    public boolean contains(int toFind);
    // 查找某个元素对应的位置
    public int indexOf(int toFind);
    // 获取 pos 位置的元素
    public int get(int pos);
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value);
    //删除第一次出现的关键字key
    public void remove(int toRemove);
    // 获取顺序表长度
    public int size() ;
    // 清空顺序表
    public void clear();
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    public void display() ;
}
给数组增加新元素
    public void add(int data) {
        //首先需要先判断数组是否已经存满
        if(isFull()){
            grow();
        }
        array[useSize]=data;
        useSize++;
    }
判断数组数据是否为满
    @Override
    public boolean isFull() {
        //相等返回true；反之，返回false
        return useSize== array.length;
    }
在 pos 位置新增元素

这里需要先考虑插入数组下标是否合理，所以需要自己写一个自定义异常！

//自定义的数组下标插入异常
class PosExpection extends RuntimeException{
    public PosExpection(String message){
        super(message);
    }
}
//自定义的异常：判断数组是否为空
class EmptyException extends RuntimeException{
    public EmptyException(String message){
        super(message);
    }
}

    //这个是私有方法，只是为了在这个类中检查数组下标是否合理，
    // 所以用private修饰
    private void checkPos(int pos) throws PosExpection{
        if(pos < 0 || pos >= useSize){
            throw new PosExpection("数组下标异常");
        }
    }
    @Override
    public void add(int pos, int data) {
      try {
          checkPos(pos);
          //如果插入数组下表没问题，则判断是否需要扩容
          if(isFull()){
              grow();
          }
      }catch (PosExpection e){
          System.out.println("插入数组下标不合理...");
          e.printStackTrace();
      }
      //这里挪动数组，将Pos下标之后的数组往后挪
        for (int i = useSize-1; i >=pos ; i--) {
            array[i+1]= array[i];
        }
        array[pos]=data;
    }
判定是否包含某个元素
    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < useSize; i++) {
            if(array[i]==toFind){
                return true;
            }
        }
        return false;
    }
查找某个元素对应的位置
    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < useSize; i++) {
            if(array[i]==toFind){
                return i;
            }
        }
        return 0;
    }
获取 pos 位置的元素
    @Override
    public int get(int pos) {
        try {
            checkPos(pos);
            return array[pos];
        }catch (PosExpection e){
            System.out.println("数组下标不合理...");
            e.printStackTrace();
        }
        return 0;
    }
给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        try {
            checkPos(pos);
            array[pos]=value;
        }catch (PosExpection e){
            System.out.println("数组下标不合理...");
            e.printStackTrace();
        }
    }
删除第一次出现的关键字key
    @Override
    public void remove(int toRemove) {
        int pos=indexOf(toRemove);
        if(pos==-1){
            return;
        }
        for (int i = pos; i <useSize-1 ; i++) {
            array[i]=array[i+1];
        }
        useSize--;
    }
获取顺序表长度
    @Override
    public int size() {
        return useSize;
    }
清空顺序表
    @Override
    public void clear() {
         useSize=0;
    }
打印顺序表
    @Override
    public void display() {
        for (int i = 0; i < useSize; i++) {
            System.out.print(array[i]+" ");
        }
        //这里不能for-each遍历,
        // 用for-each遍历不管数组里面有没有数据，都会遍历出和数组大小一样的元素，对应下标没有元素会用0来代替。
//        for (int x:
//             array) {
//            System.out.println(x+" ");
//        }
    }

相关文章