顺序表模拟实现与洗牌算法应用

2. MyArrayList 类

创建 MyArrayList 类，实现 MyList 接口中的方法。ArrayList 通常采用数组存储，需要定义变量来管理数据增删查改：

import java.util.Arrays;

public class MyArrayList implements MyList {
    private int[] array; // 数组
    private static final int capacity = 10; // 数组默认容量
    private int usedSize; // 数组中已经存储的元素个数

    // 构造无给定大小的数组
    public MyArrayList() {
        array = new int[capacity];
        usedSize = 0;
    }

    // 构造给定大小的数组
    public MyArrayList(int size) {
        array = new int[size];
        usedSize = 0;
    }
}

3. 实现 MyArrayList 中的方法

(1). add(int value)

添加元素前需判断数组空间是否已满，满了则扩容。

@Override
public void add(int value) {
    if (isFull()) {
        expansion();
    }
    array[usedSize] = value;
    usedSize++;
}

// 扩容
private void expansion() {
    this.array = Arrays.copyOf(this.array, this.array.length << 1);
}

// 判断是否满
private boolean isFull() {
    return array.length == usedSize;
}

(2). add(int index, int value)

注意事项：

1. 判断插入位置是否合法（不能小于 0 或者大于 usedSize）。
2. 判断数组空间是否已满。

@Override
public void add(int index, int value) {
    if (index < 0 || index > usedSize) {
        throw new IndexOutOfBoundsException("插入下标不合法！");
    }
    if (isFull()) {
        expansion();
    }
    for (int i = usedSize - 1; i >= index; i--) {
        array[i + 1] = array[i];
    }
    array[index] = value;
    usedSize++;
}

测试运行结果见下图：

(3). remove(int index)

注意事项：

1. 判断删除位置下标是否合法。
2. 删除后元素个数减 1。

@Override
public void remove(int index) {
    if (index < 0 || index >= usedSize) {
        throw new IndexOutOfBoundsException("下标不合法");
    }
    for (int i = index; i < usedSize - 1; i++) {
        array[i] = array[i + 1];
    }
    usedSize--;
}

(4). remove(Object value)

删除第一次出现的指定元素：

@Override
public void remove(Object value) {
    if (!contains((int) value)) {
        return;
    }
    int index = 0;
    for (int i = 0; i < usedSize; i++) {
        if (array[i] == (int) value) {
            index = i;
            break;
        }
    }
    for (int i = index; i < usedSize - 1; i++) {
        array[i] = array[i + 1];
    }
    usedSize--;
}

@Override
public boolean contains(int value) {
    for (int i = 0; i < usedSize; i++) {
        if (array[i] == value) {
            return true;
        }
    }
    return false;
}

(5). get(int index)

@Override
public int get(int index) {
    if (index < 0 || index >= usedSize) {
        throw new IndexOutOfBoundsException("下标不合法！");
    }
    return array[index];
}

(6). set(int index, int value)

@Override
public void set(int index, int value) {
    if (index < 0 || index >= usedSize) {
        throw new IndexOutOfBoundsException("下标不合法！");
    }
    this.array[index] = value;
}

(7). clear()

@Override
public void clear() {
    this.usedSize = 0;
}

(8). contains(int value)

@Override
public boolean contains(int value) {
    for (int i = 0; i < usedSize; i++) {
        if (array[i] == value) {
            return true;
        }
    }
    return false;
}

(9). indexOf(int value)

@Override
public int indexOf(int value) {
    if (contains(value)) {
        for (int i = 0; i < usedSize; i++) {
            if (array[i] == value) {
                return i;
            }
        }
    }
    return -1;
}

(10). lastindexOf(int value)

@Override
public int lastindexOf(int value) {
    if (contains(value)) {
        for (int i = usedSize - 1; i >= 0; i--) {
            if (array[i] == value) {
                return i;
            }
        }
    }
    return -1;
}

(11). isEmpty()

@Override
public boolean isEmpty() {
    return usedSize == 0;
}

测试代码：

public class Main {
    public static void main(String[] args) {
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.add(8);
        list.add(9);
        list.add(10);
        System.out.print("顺序表初始元素：");
        display(list);

        list.add(11);
        list.add(6, 0);
        System.out.print("顺序表插入后的元素：");
        display(list);

        list.remove((Object) 10);
        list.remove(5);
        System.out.print("顺序表删除后的元素：");
        display(list);

        System.out.println("获取顺序表中下标为 5 的元素：" + list.get(5));
        System.out.println("改变前，7 下标的元素：" + list.get(7));
        list.set(7, 55);
        System.out.println("改变后，7 下标的元素：" + list.get(7));
        System.out.print("改变后的顺序表：");
        display(list);

        System.out.println("10 在不在顺序表中：" + list.contains(10));
        System.out.println("顺序表中第一个 10 的下标是：" + list.indexOf(10));
        System.out.println("顺序表是否为空：" + list.isEmpty());
        list.clear();
        System.out.println("清空顺序表后，顺序表是否为空:" + list.isEmpty());
    }

    private static void display(MyArrayList list) {
        for (int i = 0; i < list.usedSize; i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
    }
}

运行结果：

二、简单的洗牌算法

结合顺序表制作一个简单的洗牌算法。

实现思想：

1. 一副牌共 54 张（包含大小王）。
2. 洗牌：打乱牌的顺序。
3. 发牌：三个人，每人每轮摸一张牌，摸 5 轮。

1. Card 类

定义 Card 类描述每张牌的花色和大小：

public class Card {
    public String suit; // 花色
    public int size; // 大小

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

    @Override
    public String toString() {
        return "{" + suit + size + "}";
    }
}

2. CardDemo 类

创建一副牌：

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

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

    public static List<Card> buydeck() {
        List<Card> cardlist = new ArrayList<>();
        String str[] = {"A", "K", "Q", "J"};
        for (int i = 2; i <= 10; i++) {
            for (int j = 0; j < 4; j++) {
                Card card = new Card(Suits[j], String.valueOf(i));
                cardlist.add(card);
            }
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < str.length; j++) {
                Card card = new Card(Suits[i], str[j]);
                cardlist.add(card);
            }
        }
        Card card = new Card("", "大王");
        cardlist.add(card);
        Card card2 = new Card("", "小王");
        cardlist.add(card2);
        return cardlist;
    }

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

最终结果：

3. shuffleCard（洗牌）

利用随机数生成器打乱顺序：

import java.util.Random;

public static void shuffleCard(List<Card> cards) {
    Random rand = new Random(1000000);
    for (int i = cards.size() - 1; i > 0; i--) {
        int index = rand.nextInt(i);
        swap(cards, index, i);
    }
}

private static void swap(List<Card> cards, int j, int i) {
    Card tmp = cards.get(i);
    cards.set(i, cards.get(j));
    cards.set(j, tmp);
}

运行结果：

4. 发牌

最后一步发牌：

public static void main(String[] args) {
    List<Card> card = buydeck();
    System.out.print("刚初始化的牌：");
    System.out.println(card);
    shuffleCard(card);
    System.out.print("洗过后的牌：");
    System.out.println(card);

    List<List<Card>> hand = new ArrayList<>();
    List<Card> hand1 = new ArrayList<>();
    List<Card> hand2 = new ArrayList<>();
    List<Card> hand3 = new ArrayList<>();
    hand.add(hand1);
    hand.add(hand2);
    hand.add(hand3);

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 3; j++) {
            hand.get(j).add(card.remove(0));
        }
    }
    for (int i = 0; i < 3; i++) {
        System.out.println("第" + (i + 1) + "个人的牌：" + hand.get(i));
    }
}

运行结果：