Javajava算法
顺序表模拟实现与洗牌算法应用
本文使用 Java 语言模拟实现了顺序表（ArrayList），包含动态扩容及增删改查等核心功能。通过定义 MyList 接口与 MyArrayList 类，详细展示了数组存储数据的底层逻辑。此外，结合顺序表实现了扑克牌洗牌与发牌算法，演示了随机数生成与列表操作的实际应用场景。
本文使用 Java 语言模拟实现了顺序表（ArrayList），包含动态扩容及增删改查等核心功能。通过定义 MyList 接口与 MyArrayList 类，详细展示了数组存储数据的底层逻辑。此外，结合顺序表实现了扑克牌洗牌与发牌算法，演示了随机数生成与列表操作的实际应用场景。
回顾上篇内容，ArrayList 实现了 List 接口。本次我们简单模拟实现一下 ArrayList，定义一些常见方法。
MyList 接口中的方法：
| 方法 | 解释 |
|---|---|
| boolean add (E e) | 在数组最后添加元素 e |
| void add(int index, E e) | 将 e 插入数组下标为 index 的位置 |
| E remove(int index) | 删除数组下标为 index 位置的元素 |
| boolean remove(Object o) | 删除遇到的第一个 o |
| E get(int index) | 获取下标 index 位置元素 |
| E set(int index, E element) | 将下标 index 位置元素设置为 element |
| void clear() | 清空 |
| boolean contains(Object o ) | 判断 o 是否在线性表中 |
| int indexOf(Object o) | 返回第一个 o 所在下标 |
| int lastindexOf(Object o) | 获取数组中最后出现的指定元素下标 |
| boolean isEmpty() | 判断数组是否为空 |
基于上述需求，定义 MyList 接口：
public interface MyList {
public void add(int value); // 尾插
public void add(int index, int value); // 在指定位置插入
public void remove(int index); // 删除指定下标位置的元素
public void remove(Object value); // 删除第一次出现的指定元素
public int get(int index); // 获取下标 index 位置的元素
public void set(int index, int value); // 将下标 index 位置的元素设置为 value
public void clear(); // 清空顺序表
public boolean contains(int value); // 判断 value 是否存在顺序表中
public int indexOf(int value); // 返回第一个 value 的下标
public int lastindexOf(int value); // 返回顺序表中最后出现的 value 的下标
public boolean isEmpty(); // 判断顺序表是否为空
}
创建 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;
}
}
添加元素前需判断数组空间是否已满，满了则扩容。
@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;
}
注意事项：
- 判断插入位置是否合法（不能小于 0 或者大于 usedSize）。
- 判断数组空间是否已满。
@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++;
}
测试运行结果见下图：
注意事项：
- 判断删除位置下标是否合法。
- 删除后元素个数减 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--;
}
删除第一次出现的指定元素：
@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;
}
@Override
public int get(int index) {
if (index < 0 || index >= usedSize) {
throw new IndexOutOfBoundsException("下标不合法！");
}
return array[index];
}
@Override
public void set(int index, int value) {
if (index < 0 || index >= usedSize) {
throw new IndexOutOfBoundsException("下标不合法！");
}
this.array[index] = value;
}
@Override
public void clear() {
this.usedSize = 0;
}
@Override
public boolean contains(int value) {
for (int i = 0; i < usedSize; i++) {
if (array[i] == value) {
return true;
}
}
return false;
}
@Override
public int indexOf(int value) {
if (contains(value)) {
for (int i = 0; i < usedSize; i++) {
if (array[i] == value) {
return i;
}
}
}
return -1;
}
@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;
}
@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();
}
}
运行结果：
结合顺序表制作一个简单的洗牌算法。
实现思想：
- 一副牌共 54 张（包含大小王）。
- 洗牌：打乱牌的顺序。
- 发牌：三个人，每人每轮摸一张牌，摸 5 轮。
定义 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 + "}";
}
}
创建一副牌：
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);
}
}
最终结果：
利用随机数生成器打乱顺序：
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);
}
运行结果：
最后一步发牌：
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));
}
}
运行结果：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online