Java实现数据结构——顺序表

目录

一、前言

二、实现

2.1 增

2.2 删

2.3 查 

 2.4 改

 2.5 销毁顺序表

三、Arraylist

3.1 构造方法

 3.2 常用操作

3.3 ArrayList遍历

四、 ArrayList具体使用  

4.1 杨辉三角

4.2 简单洗牌算法

---

一、前言

笔者在以前的文章中实现过顺序表

本文在理论上不会有太详细的讲述

如有需要可以翻看笔者之前的文章

http://t.csdnimg.cn/G5TpF

---

Java 中已经封装好了顺序表的类

但在使用之前

先自己实现一遍 

二、实现

将顺序表作为一个类进行实现

public class MyArrayList {private int[] array ;//以整形数组示例private static int defaultspace = 10;//默认数组大小private int usespace = 0;//顺序表有效数据个数// 构造方法public MyArrayList() {this.array = new int[defaultspace];//不指定大小就默认大小}public MyArrayList(int size) {this.array = new int[size] ;//用户自己指定大小}
}

再给一个方法让用户可以知晓表中有效数据个数

  public int size(){return this.usespace;}

2.1 增

这里进行一个方法的重载

   public void add(int data){
//     不指定位置就默认是数组尾插入数据}public void add(int data ,int pos){
//指定位置就插入到指定位置

在进行数据插入时

需要判断顺序表中是否还有足够的空间

给一个方法

检查操作不需要用户来使用

那就用 private 来修饰

   private boolean IsFull() {
//        检查顺序表空间是否还有剩余return usespace == this.array.length;}

如果顺序表空间没有剩余

就需要扩容这个顺序表

这里选择使用 Arrays 类中的 copyOf 方法

    public void add(int data) {
//     不指定位置就默认是数组尾插入数据if (IsFull(array)) {this.array = Arrays.copyOf(array, array.length * 2);}array[usespace] =  data;usespace++;

 将上述操作封装进一个方法 checkspace 中

 private void checkspace() {if (IsFull()) {array = Arrays.copyOf(array, array.length * 2);}}

   public void add(int data) {
//     不指定位置就默认是数组尾插入数据checkspace();this.array[usespace++] = data;}

---

而在指定位置的 add 方法中

 则是需要检查插入位置是否合法

这个下标的合法区间是 0~顺序表有效数据个数

那么不止在增删查改中都会有操作涉及到检查要进行操作的位置是否合法

不妨将操作位置不合法作为异常处理

自定义一个异常类

public class Pos_IllegalityException extends RuntimeException{public Pos_IllegalityException(String message) {super(message);}
}

检查操作不需要用户来使用

那就用 private 来修饰

  private void checkPos(int pos) throws Pos_IllegalityException {//检查插入位置是否合法if(pos < 0 || pos > usespace){throw new Pos_IllegalityException("输入的下标不合法："+pos);}}

指定位置插入数据后

需要将原 pos及其以后得数据向后移动

    public void add(int data, int pos) {
//指定位置就插入到指定位置try {checkPos_add(pos);} catch (Pos_IllegalityException e) {e.printStackTrace();}checkspace();for (int i = usespace; i >= pos; i--) {this.array[i + 1] = this.array[i];}this.array[pos] = data;this.usespace++;}

在实现一个打印方法

便于测试

  public void print() {for (int i = 0; i < usespace; i++) {System.out.println(array[i]);}}

---

测试

  public static void main(String[] args) {MyArrayList arr1 = new MyArrayList();arr1.add(1);arr1.add(2,0);arr1.add(3,1);arr1.add(4);arr1.add(5);arr1.print();}
}

---

测试是否能捕捉到异常

 public static void main(String[] args) {MyArrayList arr1 = new MyArrayList();arr1.add(1);arr1.add(2,0);arr1.add(3,10);arr1.add(4);arr1.add(5);arr1.print();}

 

 符合预期

2.2 删

在进行删除操作的时候

这个顺序表肯定不能为空

就要先判断

   private boolean IsEmpty() {return this.usespace == 0;}

public void remove(int pos){}

在进行指定位置删除时，同样需要判断进行操作的位置是否合法

删除操作中

pos 合法范围是[0,usespace)

  private void chechPos_remove(int pos) throws Pos_IllegalityException {//检查删除位置是否合法if (pos < 0 || pos >= this.usespace) {throw new Pos_IllegalityException("输入的下标不合法：" + pos);}}

删除 pos 位置的数据就是将 pos 位置后的数据向前移动一位

从 pos + 1 位置开始向前覆盖

public void remove(int pos) {//删除指定位置的数据if (IsEmpty()) {System.out.println("当前没有可以删除的数据");}try {chechPos_remove(pos);} catch (Pos_IllegalityException e) {e.printStackTrace();}for (int i = pos; i < this.usespace - 1; i++) {this.array[i] = this.array[i + 1];}this.usespace--;}

---

测试

public static void main(String[] args) {MyArrayList arr1 = new MyArrayList();arr1.add(1);arr1.add(2);arr1.add(3);arr1.add(4);arr1.add(5);arr1.print();System.out.println("===========================");arr1.remove(0);arr1.remove(arr1.size() - 1);arr1.print();}

---

测试是否能捕捉异常

public static void main(String[] args) {MyArrayList arr1 = new MyArrayList();arr1.add(1);arr1.add(2);arr1.add(3);arr1.add(4);arr1.add(5);arr1.print();System.out.println("===========================");arr1.remove(0);arr1.remove(arr1.size() );arr1.print();}

符合预期

2.3 查 

用两个方法

一个叫 indexOf 

  public int indexOf(int data)

找到对应数据返回对应下标

找不到返回 -1

一个叫 get

public int get(int pos)

查找对应下标的数据

---

先说 indexOf

同样的

在查找时

也需要判断顺序表中是否有数据

public int indexOf(int data) {if (IsEmpty()) {}return -1;}

为空或者表中没这个数据都返回-1

找到了就返回对应的下标

   public int indexOf(int data) {
//        查找数据对应的下标if (IsEmpty()) {return -1;}for (int i = 0; i < this.usespace; i++) {if (this.array[i] == data) {return i;}}return -1;}

---

现在说 get

public int get(int pos)throws {
//        查找对应下标的数据if (IsEmpty()) {}}

那么在这里遇到了一个小问题

在这个顺序表为空的情况下

返回值该是什么呢

似乎任意一个整数都不太适合进行返回

那么干脆将顺序表为空作为一种异常处理

public class MyArrayListEmptyException extends RuntimeException{public MyArrayListEmptyException(String message) {super(message);}
}

---

再将前文中删操作时也应用这个异常

 public void remove(int pos) throws MyArrayListEmptyException {//删除指定位置的数据if (IsEmpty()) {throw new MyArrayListEmptyException("当前顺序表为空！");}try {chechPos_remove(pos);} catch (Pos_IllegalityException e) {e.printStackTrace();}for (int i = pos; i < this.usespace - 1; i++) {this.array[i] = this.array[i + 1];}this.usespace--;}

---

然后完成 get 的逻辑

同样的

需要检查传入下标的合法性

这里传入下标的合法性与删除操作的合法范围相同

那么就可以调用 chechPos_remove 这个方法

为了方便就改个名

 private void chechPos_remove_and_get(int pos) throws Pos_IllegalityException {//检查删除位置是否合法if (pos < 0 || pos >= this.usespace) {throw new Pos_IllegalityException("输入的下标不合法：" + pos);}}

   public int get(int pos) throws MyArrayListEmptyException {
//        查找对应下标的数据chechPos_remove_and_get(pos);if (IsEmpty()) {throw new MyArrayListEmptyException("当前顺序表为空");}return this.array[pos];}

---

测试

 public static void main(String[] args) {MyArrayList arr1 = new MyArrayList();arr1.add(99);arr1.add(2);arr1.add(3);System.out.println(arr1.indexOf(3));System.out.println(arr1.indexOf(4));System.out.println(arr1.get(0));}

这里看起来好像没问题

需要注意的是

如果是顺序表中所存数据是引用数据类型

那么

就不能使用 == 号判断

需要重写 equals 方法

 2.4 改

通过一个 set 方法来实现

public void set(int data ,int pos){}

类似的

顺序表不能为空

判断 pos 是否合法

合法区间也是[0,usespace)

那再改个名

private void checkPos_remove_get_set(int pos) throws Pos_IllegalityException {//检查删除位置是否合法if (pos < 0 || pos >= this.usespace) {throw new Pos_IllegalityException("输入的下标不合法：" + pos);}}

---

完成 set 的实现

public void set(int data, int pos) throws MyArrayListEmptyException{//修改表中数据if(IsEmpty()){throw new MyArrayListEmptyException("当前顺序表为空");}checkPos_remove_get_set(pos);this.array[pos] = data;}

---

测试

 public static void main(String[] args) {MyArrayList arr1 = new MyArrayList();arr1.add(99);arr1.add(2);arr1.add(3);arr1.set(199,0);arr1.set(299,1);arr1.print();}

 2.5 销毁顺序表

顺序表在使用完成之后需要进行销毁

如果顺序表存的是基本数据类型

可以直接让 usespace = 0

 public void clear(){this.usespace = 0;}

但是如果是引用数据类型

采用这种方法会造成内存泄漏

JVM 中的自动回收算法有一个要求便是没引用这个数据

而这里虽然将 usespacez 置为0了

但数组中的对象仍然是存储在内存当中的

0下标确实还在引用这个对象

那么最粗暴的方法

就是直接将数组置空

  public void clear(){this.array = null;}

平和一点就是写一个循环

让每一项都置空

public void clear(){for (int i = 0; i <this. usespace; i++) {this.array[i] = null;}}

那为什么基本数据类型不需要回收呢

比如这里的 int

就算不主动向表中插入数据

表中对应下标位置仍会有默认的 0

到这里

自己实现的一个简单顺序表就完成了

下面来看看 Java 中实现的 Arraylist

三、Arraylist

接下来来看一下 Java 中已经封装好的 Arraylist

这里只展示部分方法

---

3.1 构造方法

 来看看提供的构造方法

---

其中这个构造方法是由使用者指定顺序表大小

指定空间大小不合法就抛出一个异常

---

现在来看看这个无参构造方法 

可以看到的是

如果调用无参构造方法

并没有给数组分配内存空间

public static void main(String[] args) {ArrayList arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);for (int i = 0; i < arrayList.size(); i++) {System.out.println(arrayList.get(i));}}

 

但是可以看到的是

往这个表中插入数据

还是可以成功插入

这时候就去看看方法 add 中是怎么执行的

 就是通过上述步骤

给 elementData 指定了一片内存空间

能够完成 add 操作

---

 

public static void main(String[] args) {ArrayList<Integer> arrayList1 = new ArrayList<>();ArrayList<Number> arrayList2 = new ArrayList<>(arrayList1);}

 

 public static void main(String[] args) {ArrayList<Integer> arrayList1 = new ArrayList<>();ArrayList<Number> arrayList2 = new ArrayList<>(arrayList1);LinkedList<Number> linkedList = new LinkedList<>(arrayList1);Vector<Number> vector = new Vector<>(arrayList1);}

 

都是可以的

而不满足上述条件

如

  public static void main(String[] args) {ArrayList<String> arrayList1 = new ArrayList<>();ArrayList<Number> arrayList2 = new ArrayList<>(arrayList1);}

 

 3.2 常用操作

方法	作用
boolean add (E e)	尾插 e
void add (int index, E element)	将 e 插入到 index 位置
boolean addAll (Collection<? extends E> c)	尾插 c 中的元素
E remove (int index)	删除 index 位置元素
boolean remove (Object o)	删除遇到的第一个 o
E set (int index, E element)	将下标 index 位置元素设置为 element
void clear ()	清空
boolean contains (Object o)	判断 o 是否在线性表中
int indexOf (Object o)	返回第一个 o 所在下标
int lastIndexOf (Object o)	返回最后一个 o 的下标
List<E> subList (int fromIndex, int toIndex)	截取部分list
……	……

这里主要说说重载的 remove 方法

    public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i)+" ");}arrayList.remove(3);System.out.println();for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i)+" ");}}

如果只传一个整形数字

删除的是对应下标的值 

如果想要具体删除某一个数据

那就要 new 一个对象

  public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i)+" ");}arrayList.remove(new Integer(3));System.out.println();for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i)+" ");}}

---

以及 subList 方法

public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);List<Integer> list = arrayList.subList(0,3);for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}arrayList.set(0,99);System.out.println();for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}}

截取后并不是产生新的对象

而是将截取的地址返回

所以在修改 arraylist 的值后

list 也会被修改

3.3 ArrayList遍历

ArrayList 可以使用三方方式遍历： for循环+ 下标、 foreach 、使用迭代器

for循环+ 下标在前文已经使用，这里就不再赘述

public  static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);for (Integer integer:arrayList){System.out.println(integer);}}

---

迭代器

使用方法

  public  static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);Iterator<Integer> integerIterator = arrayList.iterator();while (integerIterator.hasNext()){System.out.println(integerIterator.next());}}

 

四、 ArrayList具体使用  

4.1 杨辉三角

题目来源

https://leetcode.cn/problems/pascals-triangle/description/

---

 这段代码表示

指定 对象 list 中存放的类型是 List<Integer>

 public static void main(String[] args) {List<List<Integer>> list = new ArrayList<>();ArrayList<Integer> arrayList = new ArrayList<>();ArrayList<Integer> arrayList2 = new ArrayList<>();list.add(arrayList);list.add(arrayList2);System.out.println();}

打个断点观察一下

可以看到其中存放的确实是 ArrayList 类型的对象

---

在本题中可以将整个杨辉三角看成是一个 List< List<Integer>> 对象

每一行就是单独的一个 Arraylist 对象 

就可以将 numRows 个 Arraylist 对象增加到 List< List<Integer>> 对象中

完成这个杨辉三角

---

每一个 Arraylist 对象首元素和尾元素都是 1

就只需要给 (0,Arraylist 对象.length()) 下标处进行计算赋值

  public List<List<Integer>> generate(int numRows) {List<List<Integer>> list = new ArrayList<>();//        第一行只有一个元素 1List<Integer> firstrow = new ArrayList<>();firstrow.add(1);list.add(firstrow);//插入listfor (int i = 1; i < numRows; i++) {List<Integer> currow = new ArrayList<>();//当前行currow.add(1);//当前行的首元素for (int j = 1; j < i; j++) {
//                只进行(0,尾元素下标)之间的值赋值}currow.add(1);//尾元素赋值list.add(currow);//插入list}return list;}

而处于这个范围内的值等于

上一行同一列的值+上一行前一列的值

而对于当前代码来说

以第三行为例

是 list 中的第二个存储的对象

通过 get 方法将他获取

public List<List<Integer>> generate(int numRows) {List<List<Integer>> list = new ArrayList<>();//        第一行只有一个元素 1List<Integer> firstrow = new ArrayList<>();firstrow.add(1);list.add(firstrow);//插入listfor (int i = 1; i < numRows; i++) {List<Integer> currow = new ArrayList<>();//当前行currow.add(1);//当前行的首元素for (int j = 1; j < i; j++) {
//                只进行(0,尾元素下标)之间的值赋值List<Integer> lastrow = list.get(i - 1);//上一行int num = lastrow.get(j) + lastrow.get(j - 1);currow.add(num);}currow.add(1);//尾元素赋值list.add(currow);//插入list}return list;}

现在来提交一下

可以看到是可行的

4.2 简单洗牌算法

假设有三人正在玩扑克牌

设计一个洗牌算法

这里不计入大小王

总共有五十二张牌

花色有四种

♠(黑桃)、♥(红桃)、♦(方块)、♣(梅花)

每种花色各有13张

J Q K A 用数字 11,12,13,1代替

大概逻辑如下

---

可以把每一张牌看成是一个对象

那就需要一个牌类

public class Card {private String color;//花色 ♠(黑桃)、♥(红桃)、♦(方块)、♣(梅花)private int point;//点数 1,2,3,4,5,6,7,8,9,10,11,12,13public  Card(){}public Card(String color, int point) {this.color = color;this.point = point;}public void setColor(String color) {this.color = color;}public void setPoint(int point) {this.point = point;}@Overridepublic String toString() {return "[" +color + '\''+ point +"]";}
}

那么 Card 类实例化出来的 52 个对象放到一个牌组 CardList 中

public class CardList {
//牌组public static List<Card> BuyCard(){List<Card> cardList = new ArrayList<>();return cardList;}
}

再创建一个 Colors 类表示花色

Points 类表示点数

public class Colors {//花色private static String[] colors = {"♠","♥","♦","♣"};public static String getColors(int index) {return colors[index];}public static int size(){return colors.length;}}

public class Points {//点数private static int[] points = {1,2,3,4,5,6,7,8,9,10,11,12,13};public static int getPoints(int index) {return points[index];}public static int size(){return points.length;}
}

通过这个类的静态方法返回一个 List<Card> 类对象

public static List<Card> BuyCard(){List<Card> cardList = new ArrayList<>();for (int i = 0; i < Colors.size(); i++) {for (int j = 0; j < Points.size(); j++) {Card card = new Card(Colors.getColors(i),Points.getPoints(j));cardList.add(card);}}return cardList;}

在通过循环给每张牌进行 color 和 point 的赋值

public static List<Card> BuyCard(){List<Card> cardList = new ArrayList<>();for (int i = 0; i < Colors.size(); i++) {for (int j = 0; j < Points.size(); j++) {Card card = new Card(Colors.getColors(i),Points.getPoints(j));cardList.add(card);}}return cardList;}

再将牌放入数组中

打印出来看看

public static void main(String[] args) {List<Card> cardList = CardList.BuyCard();System.out.println(cardList);}

 （仅展示部分）

那么生成一副牌的逻辑就完成了

---

现在要洗乱这副牌

其实就是交换 cardlist 中存放的牌的位置

即两个下标的数据互换

而要随机洗乱就要生成随机数

可以使用 Random 类

Random random = new Random();random.nextInt();

random.nextInt() 传入一个整形 n 可以限制只生成 0~n 之间的整数

那么可以遍历 cardlist 

将遍历过程中的下标作为限制传入

这里选择从尾部开始遍历

private static void shuffle(List<Card> cardList) {Random random = new Random();for (int i = cardList.size() - 1; i > 0; i--) {int index = random.nextInt(i);}}

然后需要有一个交换的操作

可以通过 List 中的 set 方法

将交换的操作封装成一个方法

  private static void swap(List<Card> cardList, int index1, int index2) {Card tmp = new Card();tmp = cardList.get(index1);cardList.set(index1, cardList.get(index2));cardList.set(index2, tmp);}

放到生成牌的方法中 

   public static List<Card> BuyCard() {List<Card> cardList = new ArrayList<>();for (int i = 0; i < Colors.size(); i++) {for (int j = 0; j < Points.size(); j++) {Card card = new Card(Colors.getColors(i), Points.getPoints(j));cardList.add(card);}}shuffle(cardList);return cardList;}

测试一下看下行不行

public static void main(String[] args) {List<Card> cardList = CardList.BuyCard();System.out.println(cardList);}

（仅展示部分）

可以看到顺序确实是被洗乱了

---

发给三个人，每人一开始有五张

可以把玩家看成是一个专门存放 List<Card> 类对象的 List

从 cardlist 中摸牌就是 add

    public static void main(String[] args) {List<Card> cardList = CardList.BuyCard();List<List<Card>> player= new ArrayList<>();//人for (int i = 0; i < 3 ; i++) {//i表示人List<Card> list = new ArrayList<>();for (int j = i * 5; j < i * 5 + 5; j++) {list.add(cardList.get(j));}player.add(list);System.out.println(player.get(i));}}

感谢观看