数据结构《顺序表》

文章目录

前言
一、什么是顺序表？
- 1.1 顺序表的概念
- 1.2 顺序表的建立
二、MyArrayList的实现
三、顺序表的方法
四、关于顺序表的例子
总结

前言

提示：这里涉及到的ArrayList类是一个泛型类，同时后面的很多内容都会涉及到泛型，如果不了解泛型，可以在我给出的链接中查看了解一下，比较简单>>JAVA泛型<<

一、什么是顺序表？

1.1 顺序表的概念

概念的内容来源于>>ArrayList
ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。

它的本质就是一个数组。只不过这个数组在容量达到上限后会自动将数组进行扩容，但是，不是在同一个数组上而是返回一个扩容后的新数组，将原来数组上的内容复制到新的数组上，给我们一种直接扩容的感觉
在这里插入图片描述

在这里插入图片描述

1.2 顺序表的建立

java">import java.util.ArrayList; // 引入 ArrayList 类

java">ArrayList<E> objectName = new ArrayList<>();　 // 初始化

在这里插入图片描述
补充内容

我当时想直接用original这个对象进行clone发现是不行的，List是个接口，不是个类，没有实现Cloneable接口，无法克隆。
同时Array.asList,这个方法返回的是一个固定的视图，
当我们想在这个对象中加数据时我们会发现
在这里插入图片描述
这是为什么呢？
解释：

Arrays.asList(1, 2, 3)返回的是一个java.util.Arrays.ArrayList类型的对象，它并不是java.util.ArrayList类型。虽然它们都实现了List接口，但不能直接进行强制类型转换。同时因为它们都实现了List接口，所以，以List 为类型的引用可以接收Arrays.asList的返回值
在这里插入图片描述

二、MyArrayList的实现

将需要实现的方法放在一个接口中，在通过自定义类实现这个接口

java">public interface IList {// 新增元素,默认在数组最后新增public void add(int data);// 在 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 位置的元素设为 valuepublic void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove);// 获取顺序表长度public int size();// 清空顺序表public void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display();
}

自定义的顺序表

java">import java.util.Arrays;public class MyArrayList implements IList{public int[] array;private static final int DEFAULT_CAPACITY = 10;public MyArrayList(){this.array = new int[DEFAULT_CAPACITY];}private int useSide;//判断数组是否满了private boolean isFull(int[] array){if(array.length == DEFAULT_CAPACITY){//如果长度等于初始容量，说明数组满了return true;}return false;}//扩容数组private int[] grow(int[] array){return Arrays.copyOf(this.array,array.length*2);}@Override// 新增元素,默认在数组最后新增public void add(int data) {if (isFull(this.array)){this.array = grow(this.array);}array[useSide] = data;useSide++;}//判断pos是否正确private void checkpos(int pos){try {if(pos < 0 || pos > this.useSide){throw new OutOfArrayException("越界异常");}}catch (OutOfArrayException e){e.printStackTrace();}}@Override// 在 pos 位置新增元素public void add(int pos, int data) {try {checkpos(pos);if (isFull(this.array)){this.array = grow(this.array);}for (int i = this.useSide - 1; i >= pos; i--) {array[i+1] = array[i];}array[pos] = data;this.useSide++;}catch (OutOfArrayException e){e.printStackTrace();}}@Override// 判定是否包含某个元素public boolean contains(int toFind) {for (int i = 0; i < this.useSide; i++) {if(toFind == this.array[i]){return true;}}return false;}@Override// 查找某个元素对应的位置public int indexOf(int toFind) {for (int i = 0; i < this.useSide; i++) {if(toFind == this.array[i]){return i;}}return -1;}private void isEmpty(int[] array){if(empty(array)){throw new IsEmptyException("空数组越界访问");}}private boolean empty(int[] array){return array.length == 0;}@Override// 获取 pos 位置的元素public int get(int pos) {try {checkpos(pos);isEmpty(this.array);return this.array[pos];}catch (OutOfArrayException | IsEmptyException e){e.printStackTrace();}return -1;}@Override// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {try {checkpos(pos);isEmpty(this.array);array[pos] = value;}catch (OutOfArrayException | IsEmptyException e){e.printStackTrace();}}@Override//删除第一次出现的关键字keypublic void remove(int toRemove) {try {isEmpty(this.array);int m = indexOf(toRemove);for (int i = m; i < this.useSide - 1; i++) {array[i] = array[i+1];}this.useSide--;}catch (IsEmptyException e){e.printStackTrace();}}@Override// 获取顺序表长度public int size() {return this.useSide;}@Override// 清空顺序表public void clear() {this.useSide = 0;}@Override// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() {for (int i = 0; i < this.useSide; i++) {System.out.print(array[i] + " ");}System.out.println();}
}

自定义的异常OutOfArrayException，超出数组范围

java">public class OutOfArrayException extends RuntimeException{public OutOfArrayException(){super();}public OutOfArrayException(String m){super(m);}
}

自定义异常，数组为空

java">public class IsEmptyException extends RuntimeException{public IsEmptyException(){super();}public IsEmptyException(String m){super(m);}
}

测试类

java">public class Test {public static void main(String[] args) {MyArrayList myArrayList = new MyArrayList();myArrayList.add(10);myArrayList.add(10);myArrayList.add(2,99);myArrayList.add(10);myArrayList.add(10);myArrayList.display();System.out.println(myArrayList.get(2));System.out.println(myArrayList.indexOf(10));}
}

三、顺序表的方法

在这里插入图片描述

四、关于顺序表的例子

题目来源>>杨辉三角<<
在这里插入图片描述

java">public class Test {public static List<List<Integer>> generate(int numRows) {if(numRows <= 0){return null;}List<List<Integer>> array = new ArrayList<>();for(int i = 0;i < numRows;i++){array.add(new ArrayList<>());}array.get(0).add(1);for(int i = 1 ; i < numRows ;i++){array.get(i).add(1);for(int j = 1; j < i; j++){array.get(i).add(array.get(i-1).get(j)+array.get(i-1).get(j-1));}array.get(i).add(1);}return array;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int s = scanner.nextInt();List<List<Integer>> array = generate(s);for (int i = 0; i < s; i++) {System.out.println(array.get(i));}}
}