devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

ArrayList与顺序表

作者：繁依Fanyi0 | 2024-08-18 13:02:35

赞

踩

ArrayList与顺序表

目录：

 一.线性表 

二.顺序表

三.ArrayList的简介
    四.ArrayList自我实现和使用
    五.ArrayList的扩容机制
    六.简易的洗牌算法

 一.线性表 ： 

1.线性表（linear list）是n个 具有相同特性的数据元素的有限序列 。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在 物理结构上 并 不一定是连续 的，线性表在 物理上存储时 ，通常以 数组和链式 结构的形式存储。
二.顺序表：
顺序表是用一段物理地址连续的存储单元，依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表底层就是数组。学习时可以画图理解学习。

三.ArrayList的简介 ：

1.在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：

 2. ArrayList是以泛型方式实现的，使用时必须要先实例化 ，ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问，

ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
ArrayList实现了Serializable接口，表明ArrayList是支持序列化的 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList
ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

 上图我们可以看出ArrayList，继承了很多类，并且扩展了很多接口使用，自身也有很多方法。

  四.ArrayList自我实现和使用（这里我们没有用泛型类实现）：

我们可以仿照源码自己去实现，这里我们实现几个常见的方法，（注意ArrayList不止这些方法），自己的ArrayList

下面先来说明一下，自己模仿的每一个类的分配如图：

1.这里是IList接口里的方法：

  1. package listtest;
  2.  
  3. /**
  4.  * Created with IntelliJ IDEA.
  5.  * Description:
  6.  * User: 苏
  7.  * Date: 2024-06-09
  8.  * Time: 20:23
  9.  */
  10. public interface IList {
  11.     //判满
  12.     public boolean isFull();
  13.     // 新增元素,默认在数组最后新增
  14.     public void add(int data);
  15.     // 在 pos 位置新增元素
  16.     public void add(int pos, int data);
  17.     // 判定是否包含某个元素
  18.     public boolean contains(int toFind);
  19.     // 查找某个元素对应的位置
  20.     public int indexOf(int toFind);
  21.     // 获取 pos 位置的元素
  22.     public int get(int pos);
  23.     // 给 pos 位置的元素设为 value
  24.     public void set(int pos, int value);
  25.     //删除第一次出现的关键字key
  26.     public void remove(int toRemove);
  27.     // 获取顺序表长度
  28.     public int size();
  29.     // 清空顺序表
  30.     public void clear();
  31.     // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
  32.     public void display();
  33. }

2.这里是继承了My_ArrayList的类，具体方法构架界面：这里注意：要在某位置插入，这个位置的，前驱一定不能为空

  1. package listtest;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * Created with IntelliJ IDEA.
  7.  * Description:
  8.  * User: 苏
  9.  * Date: 2024-06-09
  10.  * Time: 20:10
  11.  */
  12.  
  13. public class My_ArrayList implements IList {
  14.     public int[] array;
  15.     public int usedSize;//大小默认就是0，数组的有效长度
  16.     public static final int DEFAULT_CAPACITY = 10;//数组的默认长度
  17.  
  18.     public My_ArrayList() {
  19.         this.array = new int[DEFAULT_CAPACITY];
  20.     }
  21.  
  22.     public boolean isFull() {
  23.         return this.usedSize == this.array.length; //满了
  24.     }
  25.  
  26.     //扩容
  27.     private void grow() {
  28.         //2倍扩容
  29.         this.array = Arrays.copyOf(this.array, 2*this.array.length);
  30.     }
  31.  
  32.     //检查pos位置下标，是否合法
  33.     private void checkPosOf(int pos) throws IllegalPos {
  34.         if (pos < 0 || pos > this.usedSize) {
  35.             throw new IllegalPos("pos位置不合法");
  36.         }
  37.     }
  38.  
  39.  
  40.     @Override
  41.     public void add(int data) {
  42.         if (isFull()) {
  43.             //扩容
  44.             grow();
  45.         }
  46.  
  47.         this.array[this.usedSize++] = data;
  48.     }
  49.  
  50.     @Override
  51.     public void add(int pos, int data) {
  52.  
  53.         try {
  54.             checkPosOf(pos);
  55.  
  56.             if (isFull()) {
  57.                 //扩容
  58.                 grow();
  59.             }
  60.  
  61.  
  62.             /**注意以下：
  63.              * 要在某位置插入，这个位置的，前驱一定不能为空
  64.              */
  65.             //挪动元素
  66.             for (int i = 0; i >= pos ; i--) {
  67.                 this.array[i+1] = this.array[i];
  68.             }
  69.  
  70.             //插入
  71.             this.array[pos] = data;
  72.             usedSize++;
  73.  
  74.         }catch (IllegalPos e) {
  75.             e.printStackTrace();
  76.         }
  77.  
  78.     }
  79.  
  80.     @Override
  81.     public boolean contains(int toFind) {
  82.         for (int i = 0; i < usedSize; i++) {
  83.             //这里如果是自己，定义的引用类型，那么要用equal比较
  84.             if (array[i] == toFind) {
  85.                 return true;
  86.             }
  87.         }
  88.         return false;
  89.     }
  90.  
  91.     @Override
  92.     public int indexOf(int toFind) {
  93.         for (int i = 0; i < usedSize; i++) {
  94.             //这里如果是自己，定义的引用类型，那么要用equal比较
  95.             if (array[i] == toFind) {
  96.                 return i;
  97.             }
  98.         }
  99.         return -1;
  100.     }
  101.  
  102.  
  103.     private void checkPosOf2(int pos) throws IllegalPos {
  104.         if (pos < 0 || pos >= this.usedSize) {
  105.             throw new IllegalPos("pos位置不合法");
  106.         }
  107.     }
  108.  
  109.     //顺序表判空
  110.     public boolean isEmpty() {
  111.         return this.usedSize == 0;
  112.     }
  113.  
  114.     private void checkOfList() {
  115.         if (this.isEmpty()) {
  116.             throw new EmptyException("顺序表为空");
  117.         }
  118.     }
  119.  
  120.     @Override
  121.     public int get(int pos) {
  122.         try {
  123.             //顺序表本来就为空时
  124.             this.checkOfList();
  125.             checkPosOf2(pos);
  126.  
  127.             return array[pos];
  128.         }catch (IllegalPos e) {
  129.             e.printStackTrace();
  130.         }catch (EmptyException e) {
  131.             e.printStackTrace();
  132.         }
  133.  
  134.         return -1;
  135.     }
  136.  
  137.     //更新
  138.     @Override
  139.     public void set(int pos, int value) {
  140.  
  141.         try {
  142.             //顺序表本来就为空时
  143.             this.checkOfList();
  144.             checkPosOf2(pos);
  145.  
  146.             array[pos] = value;
  147.         }catch (IllegalPos e) {
  148.             e.printStackTrace();
  149.         }catch (EmptyException e) {
  150.             e.printStackTrace();
  151.         }
  152.  
  153.     }
  154.  
  155.     @Override
  156.     public void remove(int toRemove) {
  157.         try {
  158.             //判空
  159.             this.checkOfList();
  160.             //找到要删除的下标
  161.             int pos = this.indexOf(toRemove);
  162.  
  163.             if (pos == -1) {
  164.                 System.out.println("找不到你要删除的元素");
  165.                 return;
  166.             }
  167.  
  168.             for (int i = pos; i < usedSize-1/*这里注意,因为是array[i] = array[i+1]*/; i++) {
  169.                 this.array[i] = array[i+1];
  170.             }
  171.             this.usedSize--;
  172.  
  173.         }catch (EmptyException e) {
  174.             e.printStackTrace();
  175.         }
  176.  
  177.     }
  178.  
  179.     @Override
  180.     public int size() {
  181.         return this.usedSize;
  182.     }
  183.  
  184.     @Override
  185.     public void clear() {
  186.         //如果是引用类型，要把，引用置为空
  187.         /*for (int i = 0; i < this.usedSize; i++) {
  188.             this.array[i] = null;
  189.         }
  190.         this.usedSize = 0;*/
  191.  
  192.  
  193.         //基本类型直接这样写
  194.         this.usedSize = 0;
  195.     }
  196.  
  197.     @Override
  198.     public void display() {
  199.         for (int i = 0; i < usedSize; i++) {
  200.             System.out.print(array[i] +" ");
  201.         }
  202.     }
  203.  
  204. }

3.这里是两个自定义异常EmptyException（检查顺序表是否为空）和IllegalPos（检查下标是否合法）：

  1. package listtest;
  2.  
  3. /**
  4.  * Created with IntelliJ IDEA.
  5.  * Description:
  6.  * User: 苏
  7.  * Date: 2024-06-09
  8.  * Time: 22:41
  9.  */
  10. public class IllegalPos extends RuntimeException {
  11.     public IllegalPos() {
  12.         super();
  13.     }
  14.  
  15.     public IllegalPos(String msg) {
  16.         super(msg);
  17.     }
  18. }

  1. package listtest;
  2.  
  3. /**
  4.  * Created with IntelliJ IDEA.
  5.  * Description:
  6.  * User: 苏
  7.  * Date: 2024-06-10
  8.  * Time: 12:22
  9.  */
  10. public class EmptyException extends RuntimeException {
  11.     public EmptyException() {
  12.         super();
  13.     }
  14.  
  15.     public EmptyException(String msg) {
  16.         super(msg);
  17.     }
  18. }

使用注意一：使用时ArrayList不传参数，他会Add给你分配内存，可以传另一个定义的顺序表（list）不过需要是，该泛型或泛型子类

 

 

 

使用注意二：ArrayList的遍历：

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

1.for循环+下标遍历：

  1. public static void main(String[] args) {
  2.         ArrayList<Integer> list = new ArrayList<>();
  3.         list.add(1);
  4.         list.add(2);
  5.         list.add(3);
  6.         list.add(4);
  7.  
  8. //for循环打印
  9.         for (int i = 0; i < list.size(); i++) {
  10.             System.out.print(list.get(i) + " ");
  11.         }
  12. }

 

2.foreach遍历：

 

  1. public static void main(String[] args) {
  2.         ArrayList<Integer> list = new ArrayList<>();
  3.         list.add(1);
  4.         list.add(2);
  5.         list.add(3);
  6.         list.add(4);
  7.  
  8. //for each循环打印
  9.         for(Integer x/*每一个元素的类型*/: list/*对象引用类型*/) {
  10.             System.out.print(x +" ");
  11.         }
  12. }

3.使用迭代器遍历：

  1. public static void main(String[] args) {
  2.         ArrayList<Integer> list = new ArrayList<>();
  3.         list.add(1);
  4.         list.add(2);
  5.         list.add(3);
  6.         list.add(4);
  7.  
  8.  //使用迭代器输出
  9.         Iterator<Integer> it = list.iterator();
  10.         while (it.hasNext()) {
  11.             System.out.print(it.next() + " ");
  12.         }
  13. }

    五.ArrayList的扩容机制（略）： 有兴趣可以去看看源码，jdk17被一层一层封装看起来麻烦，可以看jdk8

1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要库容的大小，初步 预估按照 1.5倍 大小扩容
如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
3.真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
4. 使用copyOf进行扩容

  六.简易的洗牌算法:

1.学了ArrayLisy之后，来看一下其应用，这里的洗牌算法，会用集合来定义二维数组，来把牌分别放到不同玩家手中，接下来有我娓娓到来：

 2.老规矩，来看一下，定义的，类的结构：

3.具体实现：

Card类，定义基本的对象和构造方法：

  1. package card;
  2.  
  3. /**
  4.  * Created with IntelliJ IDEA.
  5.  * Description:
  6.  * User: 苏李涛
  7.  * Date: 2024-06-13
  8.  * Time: 20:45
  9.  */
  10. public class Card {
  11.     public int rank;//牌的面值
  12.     public String suit;//牌的花色
  13.  
  14.     public Card(int rank, String suit) {
  15.         this.rank = rank;
  16.         this.suit = suit;
  17.     }
  18.  
  19.     @Override
  20.     public String toString() {
  21.         /*return "Card{" +
  22.                 "rank=" + rank +
  23.                 ", suit='" + suit + '\'' +
  24.                 '}';*/
  25.  
  26.         return "{" + suit + rank + "}";
  27.     }
  28. }

cardDemo类定义，买牌，洗牌，揭牌方法具体如下： 

（1）买52张牌：这里注意要，声明Card对象，来通过构造方法来，初始化，每一张牌，每一张牌又有四种花色。

  1. public class CardDemo {
  2.     public static final String[] suits = new String[]{"♥", "♠", "♣", "♦"};
  3.  
  4.     //1.买52张牌
  5.     public List<Card> buyCard() {
  6.         List<Card> cardList = new ArrayList<>();
  7.  
  8.         //1.买52张牌
  9.  
  10.         for (int i = 1; i <= 13; i++) {
  11.             for (int j = 0; j < 4; j++) {
  12.                 //赋值，增加代码可读
  13.                 String suit = suits[j];
  14.                 int rank = i;
  15.  
  16.                 //初始化构造方法
  17.                 Card card = new Card(rank, suit);
  18.                 cardList.add(card);
  19.             }
  20.         }
  21.         return cardList;
  22.     }

（2）洗牌：这里巧妙，利用生产随机数，这里也要注意，交换牌时的Swap方法，通过集合来交换，会有一个开区间下标，不在生成随机数的范围内，通过这来打乱牌，我画了一个图来理解：

  1. //2.洗牌
  2.     /**
  3.      * 生成随机数，区间也是"[)"这样的，
  4.      * 所以我们用 i 值，的前面生成随机数，然后和i位置交换
  5.      * @return
  6.      */
  7.     public List<Card> shuffle(List<Card> cardList ) {
  8.         Random random = new Random();
  9.         for (int i = cardList.size()-1; i>0; i--) {
  10.             int pre = random.nextInt(i);
  11.             //这里会有，开区间数，index，这个数每次和随机数交换
  12.  
  13.             //i是下面index的值，也就是开区间的值
  14.             swap(cardList, pre, i);
  15.         }
  16.         return cardList;
  17.     }
  18.  
  19.     private void swap(List<Card> cardList, int i/*这个i是生产随机数值的，下标*/, int index/*是开区间下标*/) {
  20.         /**注意不能注意写：因为cardList不是数组，是集合里面有数组
  21.          *
  22.          * cardList tmp = cardList[i]
  23.          * index就是，生成随机数的，开区间下标 i
  24.          * cardList[i] = cardList[index];
  25.          * cardList[index] = tmp
  26.          */
  27.  
  28.         //这个tmp就是，cardList.get(i)里元素的类型
  29.         Card tmp = cardList.get(i);
  30.         //把生成随机数下标的值，换成，随机数,开区间下标的值
  31.         cardList.set(i, cardList.get(index));
  32.         cardList.set(index, tmp);
  33.  
  34.     }

揭牌：这里注意：定义了一个二维数组，存放玩家揭的牌，也要注意，删除是以集合中覆盖的形式，如图：

  1.   //3.揭牌
  2.     public List<List<Card>> playCard(List<Card> cardList) {
  3.         List<List<Card>> ret = new ArrayList<>();//存放一维数组的二维数组
  4.  
  5.         //下面是三个存放玩家，抽的牌，的一维数组
  6.        List<Card> hand0 = new ArrayList<>();
  7.        List<Card> hand1 = new ArrayList<>();
  8.        List<Card> hand2 = new ArrayList<>();
  9.  
  10.        ret.add(hand0);
  11.        ret.add(hand1);
  12.        ret.add(hand2);
  13.  
  14.  
  15.         //每个人每次，抽一张，每人抽5张
  16.         for (int i = 0; i < 5; i++) {
  17.             for (int j = 0; j < 3; j++) {
  18.                 //从上往下抽，一个删除一个，放到一维数组中，用二维数（ List<List<Card>>）组访问。
  19.                 /**
  20.                  * 注意这里的删除，应该是，顺序表中remove,这个删除是以覆盖的形式
  21.                  */
  22.  
  23.                 //删除扑克牌对象
  24.                 Card card = cardList.remove(0);//从0位置开始覆盖
  25.  
  26.                  //把删除（覆盖）的扑克牌，放到二维数组中
  27.                 ret.get(j).add(card);
  28.             }
  29.         }
  30.  
  31.         return ret;//返回二维数组，用二维数组访问一维数组
  32.     }

CardTest测试类：

  1. import card.Card;
  2. import card.CardDemo;
  3.  
  4. import java.util.ArrayList;
  5. import java.util.List;
  6.  
  7. /**
  8.  * Created with IntelliJ IDEA.
  9.  * Description:
  10.  * User: 苏李涛
  11.  * Date: 2024-06-13
  12.  * Time: 20:45
  13.  */
  14.  
  15. public class CardTest {
  16.     public static void main(String[] args) {
  17.         //1.买52张牌
  18.         CardDemo cardDemo = new CardDemo();
  19.  
  20.         //调用返回值为List<Card>的，泛型方法
  21.         List<Card> cardList = cardDemo.buyCard();
  22.         System.out.println(cardList);
  23.  
  24.         System.out.println();
  25.         System.out.println();
  26.  
  27.         //2.洗牌
  28.         List<Card> cardList1 = cardDemo.shuffle(cardList);
  29.         System.out.println(cardList1);
  30.  
  31.         System.out.println();
  32.         System.out.println();
  33.  
  34.         //3.揭牌
  35.         //注意：揭牌的删除是，顺序表里的覆盖
  36.         List<List<Card>> cardList2 = cardDemo.playCard(cardList);
  37.         for (int i = 0; i < cardList2.size(); i++) {
  38.             System.out.println("玩家"+ (i+1) + "的牌: " + cardList2.get(i));
  39.         }
  40.  
  41.     }
  42. }

来看一下输出：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/997570
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号