数据结构《顺序表》
文章目录
- 前言
- 一、什么是顺序表？
- 1.1 顺序表的概念
- 1.2 顺序表的建立
- 二、MyArrayList的实现
- 三、顺序表的方法
- 四、关于顺序表的例子
- 总结
前言
提示：这里涉及到的ArrayList类是一个泛型类，同时后面的很多内容都会涉及到泛型，如果不了解泛型，可以在我给出的链接中查看了解一下，比较简单>>JAVA泛型<<
一、什么是顺序表？
1.1 顺序表的概念
概念的内容来源于>>ArrayList
ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。
它的本质就是一个数组。只不过这个数组在容量达到上限后会自动将数组进行扩容，但是，不是在同一个数组上而是返回一个扩容后的新数组，将原来数组上的内容复制到新的数组上，给我们一种直接扩容的感觉
1.2 顺序表的建立
import java.util.ArrayList; // 引入 ArrayList 类
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的实现
将需要实现的方法放在一个接口中，在通过自定义类实现这个接口
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 位置的元素设为 value
public void set(int pos, int value);
//删除第一次出现的关键字key
public void remove(int toRemove);
// 获取顺序表长度
public int size();
// 清空顺序表
public void clear();
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
public void display();
}
自定义的顺序表
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 位置的元素设为 value
public void set(int pos, int value) {
try {
checkpos(pos);
isEmpty(this.array);
array[pos] = value;
}catch (OutOfArrayException | IsEmptyException e){
e.printStackTrace();
}
}
@Override
//删除第一次出现的关键字key
public 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，超出数组范围
public class OutOfArrayException extends RuntimeException{
public OutOfArrayException(){
super();
}
public OutOfArrayException(String m){
super(m);
}
}
自定义异常，数组为空
public class IsEmptyException extends RuntimeException{
public IsEmptyException(){
super();
}
public IsEmptyException(String m){
super(m);
}
}
测试类
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));
}
}
三、顺序表的方法
四、关于顺序表的例子
题目来源>>杨辉三角<<
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));
}
}
}
总结
本篇文章，介绍了有关顺序表的内容，包括什么是顺序表、如何实现自己的顺序表、以及使用顺序表解决问题的例子。