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接口里的方法：

package listtest;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏
 * Date: 2024-06-09
 * Time: 20:23
 */
public interface IList {
    //判满
    public boolean isFull();
    // 新增元素,默认在数组最后新增
    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();
}

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

package listtest;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏
 * Date: 2024-06-09
 * Time: 20:10
 */

public class My_ArrayList implements IList {
    public int[] array;
    public int usedSize;//大小默认就是0，数组的有效长度
    public static final int DEFAULT_CAPACITY = 10;//数组的默认长度

    public My_ArrayList() {
        this.array = new int[DEFAULT_CAPACITY];
    }

    public boolean isFull() {
        return this.usedSize == this.array.length; //满了
    }

    //扩容
    private void grow() {
        //2倍扩容
        this.array = Arrays.copyOf(this.array, 2*this.array.length);
    }

    //检查pos位置下标，是否合法
    private void checkPosOf(int pos) throws IllegalPos {
        if (pos < 0 || pos > this.usedSize) {
            throw new IllegalPos("pos位置不合法");
        }
    }


    @Override
    public void add(int data) {
        if (isFull()) {
            //扩容
            grow();
        }

        this.array[this.usedSize++] = data;
    }

    @Override
    public void add(int pos, int data) {

        try {
            checkPosOf(pos);

            if (isFull()) {
                //扩容
                grow();
            }


            /**注意以下：
             * 要在某位置插入，这个位置的，前驱一定不能为空
             */
            //挪动元素
            for (int i = 0; i >= pos ; i--) {
                this.array[i+1] = this.array[i];
            }

            //插入
            this.array[pos] = data;
            usedSize++;

        }catch (IllegalPos e) {
            e.printStackTrace();
        }

    }

    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            //这里如果是自己，定义的引用类型，那么要用equal比较
            if (array[i] == toFind) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            //这里如果是自己，定义的引用类型，那么要用equal比较
            if (array[i] == toFind) {
                return i;
            }
        }
        return -1;
    }


    private void checkPosOf2(int pos) throws IllegalPos {
        if (pos < 0 || pos >= this.usedSize) {
            throw new IllegalPos("pos位置不合法");
        }
    }

    //顺序表判空
    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    private void checkOfList() {
        if (this.isEmpty()) {
            throw new EmptyException("顺序表为空");
        }
    }

    @Override
    public int get(int pos) {
        try {
            //顺序表本来就为空时
            this.checkOfList();
            checkPosOf2(pos);

            return array[pos];
        }catch (IllegalPos e) {
            e.printStackTrace();
        }catch (EmptyException e) {
            e.printStackTrace();
        }

        return -1;
    }

    //更新
    @Override
    public void set(int pos, int value) {

        try {
            //顺序表本来就为空时
            this.checkOfList();
            checkPosOf2(pos);

            array[pos] = value;
        }catch (IllegalPos e) {
            e.printStackTrace();
        }catch (EmptyException e) {
            e.printStackTrace();
        }

    }

    @Override
    public void remove(int toRemove) {
        try {
            //判空
            this.checkOfList();
            //找到要删除的下标
            int pos = this.indexOf(toRemove);

            if (pos == -1) {
                System.out.println("找不到你要删除的元素");
                return;
            }

            for (int i = pos; i < usedSize-1/*这里注意,因为是array[i] = array[i+1]*/; i++) {
                this.array[i] = array[i+1];
            }
            this.usedSize--;

        }catch (EmptyException e) {
            e.printStackTrace();
        }

    }

    @Override
    public int size() {
        return this.usedSize;
    }

    @Override
    public void clear() {
        //如果是引用类型，要把，引用置为空
        /*for (int i = 0; i < this.usedSize; i++) {
            this.array[i] = null;
        }
        this.usedSize = 0;*/


        //基本类型直接这样写
        this.usedSize = 0;
    }

    @Override
    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(array[i] +" ");
        }
    }

}

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

package listtest;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏
 * Date: 2024-06-09
 * Time: 22:41
 */
public class IllegalPos extends RuntimeException {
    public IllegalPos() {
        super();
    }

    public IllegalPos(String msg) {
        super(msg);
    }
}

package listtest;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏
 * Date: 2024-06-10
 * Time: 12:22
 */
public class EmptyException extends RuntimeException {
    public EmptyException() {
        super();
    }

    public EmptyException(String msg) {
        super(msg);
    }
}

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

使用注意二：ArrayList的遍历：

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

1.for循环+下标遍历：

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

//for循环打印
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
}

2.foreach遍历：

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

//for each循环打印
        for(Integer x/*每一个元素的类型*/: list/*对象引用类型*/) {
            System.out.print(x +" ");
        }
}

3.使用迭代器遍历：

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

 //使用迭代器输出
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
}

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

1. 检测是否真正需要扩容，如果是调用grow准备扩容

2. 预估需要库容的大小，初步 预估按照 1.5倍 大小扩容

如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容

3.真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

4. 使用copyOf进行扩容

六.简易的洗牌算法:

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

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

3.具体实现：

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

package card;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-06-13
 * Time: 20:45
 */
public class Card {
    public int rank;//牌的面值
    public String suit;//牌的花色

    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }

    @Override
    public String toString() {
        /*return "Card{" +
                "rank=" + rank +
                ", suit='" + suit + '\'' +
                '}';*/

        return "{" + suit + rank + "}";
    }
}

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

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

public class CardDemo {
    public static final String[] suits = new String[]{"♥", "♠", "♣", "♦"};

    //1.买52张牌
    public List<Card> buyCard() {
        List<Card> cardList = new ArrayList<>();

        //1.买52张牌

        for (int i = 1; i <= 13; i++) {
            for (int j = 0; j < 4; j++) {
                //赋值，增加代码可读
                String suit = suits[j];
                int rank = i;

                //初始化构造方法
                Card card = new Card(rank, suit);
                cardList.add(card);
            }
        }
        return cardList;
    }

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

//2.洗牌
    /**
     * 生成随机数，区间也是"[)"这样的，
     * 所以我们用 i 值，的前面生成随机数，然后和i位置交换
     * @return
     */
    public List<Card> shuffle(List<Card> cardList ) {
        Random random = new Random();
        for (int i = cardList.size()-1; i>0; i--) {
            int pre = random.nextInt(i);
            //这里会有，开区间数，index，这个数每次和随机数交换

            //i是下面index的值，也就是开区间的值
            swap(cardList, pre, i);
        }
        return cardList;
    }

    private void swap(List<Card> cardList, int i/*这个i是生产随机数值的，下标*/, int index/*是开区间下标*/) {
        /**注意不能注意写：因为cardList不是数组，是集合里面有数组
         *
         * cardList tmp = cardList[i]
         * index就是，生成随机数的，开区间下标 i
         * cardList[i] = cardList[index];
         * cardList[index] = tmp
         */

        //这个tmp就是，cardList.get(i)里元素的类型
        Card tmp = cardList.get(i);
        //把生成随机数下标的值，换成，随机数,开区间下标的值
        cardList.set(i, cardList.get(index));
        cardList.set(index, tmp);

    }

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

  //3.揭牌
    public List<List<Card>> playCard(List<Card> cardList) {
        List<List<Card>> ret = new ArrayList<>();//存放一维数组的二维数组

        //下面是三个存放玩家，抽的牌，的一维数组
       List<Card> hand0 = new ArrayList<>();
       List<Card> hand1 = new ArrayList<>();
       List<Card> hand2 = new ArrayList<>();

       ret.add(hand0);
       ret.add(hand1);
       ret.add(hand2);


        //每个人每次，抽一张，每人抽5张
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                //从上往下抽，一个删除一个，放到一维数组中，用二维数（ List<List<Card>>）组访问。
                /**
                 * 注意这里的删除，应该是，顺序表中remove,这个删除是以覆盖的形式
                 */

                //删除扑克牌对象
                Card card = cardList.remove(0);//从0位置开始覆盖

                 //把删除（覆盖）的扑克牌，放到二维数组中
                ret.get(j).add(card);
            }
        }

        return ret;//返回二维数组，用二维数组访问一维数组
    }

CardTest测试类：

import card.Card;
import card.CardDemo;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-06-13
 * Time: 20:45
 */

public class CardTest {
    public static void main(String[] args) {
        //1.买52张牌
        CardDemo cardDemo = new CardDemo();

        //调用返回值为List<Card>的，泛型方法
        List<Card> cardList = cardDemo.buyCard();
        System.out.println(cardList);

        System.out.println();
        System.out.println();

        //2.洗牌
        List<Card> cardList1 = cardDemo.shuffle(cardList);
        System.out.println(cardList1);

        System.out.println();
        System.out.println();

        //3.揭牌
        //注意：揭牌的删除是，顺序表里的覆盖
        List<List<Card>> cardList2 = cardDemo.playCard(cardList);
        for (int i = 0; i < cardList2.size(); i++) {
            System.out.println("玩家"+ (i+1) + "的牌: " + cardList2.get(i));
        }

    }
}

来看一下输出：

相关推荐

最近更新

热门阅读