数据结构------手撕顺序表

文章目录

线性表
顺序表的使用及其内部方法
ArrayList 的扩容机制
顺序表的几种遍历方式
顺序表的优缺点
顺序表的模拟实现
洗牌算法

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
在这里插入图片描述

顺序表的使用及其内部方法

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

ArrayList的使用
ArrayList 的构造方法如下：
在这里插入图片描述
示例代码如下：

public static void main(String[] args) {
// ArrayList创建，推荐写法
List<Integer> list1 = new ArrayList<>();
// 构造一个具有10个容量的列表
List<Integer> list2 = new ArrayList<>(10);
list2.add(1);
list2.add(2);
list2.add(3);
// list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素
// list3构造好之后，与list中的元素一致
ArrayList<Integer> list3 = new ArrayList<>(list2);
// 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难
List list4 = new ArrayList();
list4.add("111");
list4.add(100);
}

ArrayList 中的方法
在这里插入图片描述

ArrayList 的扩容机制

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。

【总结】

默认容量为10
检测是否真正需要扩容，如果是调用grow准备扩容
预估需要扩容的大小

初步预估按照1.5倍大小扩容
如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

使用copyOf进行扩容

顺序表的几种遍历方式

 public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);System.out.println("=========for循环遍历=========");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) +" ");}System.out.println();System.out.println("=========foreach循环遍历=========");for(Integer x : list) {System.out.print(x +" ");}System.out.println();System.out.println("=========迭代器遍历1=========");Iterator<Integer> it = list.iterator();while(it.hasNext()) {System.out.print(it.next() +" ");}System.out.println();System.out.println("=========迭代器遍历2=========");ListIterator<Integer> tmpList = list.listIterator();while(tmpList.hasNext()) {System.out.print(tmpList.next() +" ");}System.out.println();System.out.println("=========迭代器遍历3=========");ListIterator<Integer> tmpList2 = list.listIterator(list.size());while(tmpList2.hasPrevious()) {System.out.print(tmpList2.previous() +" ");}System.out.println();}

顺序表的优缺点

优点：

内存连续—>物理上和逻辑上
根据下标查找元素，时间复杂度为O(1)

缺点：

插入数据和删除数据不合适，因为每次都要移动元素
时间复杂度会达到O(N)

顺序表的模拟实现

顺序表的底层使用数组实现的，所以这里模拟实现顺序表也使用数组来实现。
在实现之前，先看看ArrayList中的常用方法，后续要模拟实现这些方法，如下：

public class IList {
// 新增元素,默认在数组最后新增
public void add(int data) { }
// 在 pos 位置新增元素
public void add(int pos, int data) { }
// 判定是否包含某个元素
public boolean contains(int toFind) { return true; }
// 查找某个元素对应的位置
public int indexOf(int toFind) { return -1; }
// 获取 pos 位置的元素
public int get(int pos) { return -1; }
// 给 pos 位置的元素设为 value
public void set(int pos, int value) { }
//删除第一次出现的关键字key
public void remove(int toRemove) { }
// 获取顺序表长度
public int size() { return 0; }
// 清空顺序表
public void clear() { }
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
public void display() { }
}

【思路】：把这些ArrayList中的方法放入一个接口中（当然这些方法放入接口中暂时没有具体实现，为抽象方法），让模拟实现的MyArrayList 类实现这个接口，然后在MyArrayList 类中把这些方法全部重写并实现。

创建一个 IList 接口，接口中包含各种关于ArrayList的抽象方法,代码示例如下：

public interface IList {// 新增元素,默认在数组最后新增void add(int data);// 在 pos 位置新增元素void add(int pos, int data);// 判定是否包含某个元素boolean contains(int toFind);// 查找某个元素对应的位置int indexOf(int toFind) ;//// 获取 pos 位置的元素int get(int pos);// 给 pos 位置的元素设为 valuevoid set(int pos, int value);//删除第一次出现的关键字keyvoid remove(int toRemove);// 获取顺序表长度int size();// 清空顺序表void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的void display();//判断数组是否为空boolean isEmpty();//删除所有数据为toRemove的元素void removeAll(int toRemove);
}

创建MyArrayList 类使其实现 IList 接口，在类中重写接口中的方法

import java.util.Arrays;
public class MyArrayList implements IList{public int[] elem;public int usedSize;public MyArrayList() {this.elem = new int[10];}//判断数组是否满了public boolean isFull() {return elem.length == usedSize;}//数组满了，进行扩容private void grow() {elem = Arrays.copyOf(elem,2*elem.length);}/*** 对数组的 最后一个位置 新增data* @param data*/@Overridepublic void add(int data) {if(isFull()) {grow();}elem[usedSize] = data;usedSize++;}/*** 在pos位置 新增 元素data* @param pos* @param data*/@Overridepublic void add(int pos, int data) {if(isFull()) {grow();}if(pos < 0 || pos > usedSize) {throw new PosOutOfException("pos位置不合法");}for (int i = usedSize-1; i >= pos; i--) {elem[i+1] = elem[i];}elem[pos] = data;usedSize++;}/*** 查找一个数据，返回true或false* @param toFind* @return*/@Overridepublic boolean contains(int toFind) {if(isEmpty()) {return false;}for (int i = 0; i < usedSize; i++) {if(elem[i] == toFind) {return true;}}return false;}/*** 查找一个数据，返回其下标* @param toFind* @return*/@Overridepublic int indexOf(int toFind) {for (int i = 0; i < usedSize; i++) {if(elem[i] == toFind) {return i;}}return -1;}/*** 查找下标为pos的元素，返回其数值* @param pos* @return*/@Overridepublic int get(int pos) {if(isEmpty()) {throw new EmptyArrayListException("顺序表为空");}if(pos < 0 || pos >= usedSize) {throw new RuntimeException("pos位置不合法");}return elem[pos];}/*** pos位置 设置成 value* @param pos* @param value*/@Overridepublic void set(int pos, int value) {if(pos < 0 || pos >= usedSize) {throw new PosOutOfException("pos位置不合法");}elem[pos] = value;}/*** 删除数组中的一个元素 toMove* @param toRemove*/@Overridepublic void remove(int toRemove) {int index = indexOf(toRemove);if(index == -1) {return;}for (int i = index; i < usedSize-1; i++) {elem[i] = elem[i+1];}usedSize--;}@Overridepublic int size() {return usedSize;}@Overridepublic void clear() {usedSize = 0;}@Overridepublic void display() {for (int i = 0; i < usedSize; i++) {System.out.print(elem[i] +" ");}System.out.println();}@Overridepublic boolean isEmpty() {if(usedSize == 0) {return true;}return false;}@Overridepublic void removeAll(int toRemove) {while(contains(toRemove)) {int index = indexOf(toRemove);for (int i = index; i < usedSize-1; i++) {elem[i] = elem[i+1];}usedSize--;}}
}

测试类Test

    public static void main1(String[] args) {MyArrayList myArrayList = new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(1,19);myArrayList.display();myArrayList.set(0,100);myArrayList.display();boolean ret = myArrayList.contains(100);System.out.println(ret);myArrayList.set(1,33);myArrayList.display();myArrayList.add(0,1);myArrayList.add(1,2);myArrayList.add(2,1);myArrayList.add(3,4);myArrayList.add(4,1);myArrayList.display();myArrayList.removeAll(1);myArrayList.display();}

洗牌算法

实现效果：能够完成创建扑克牌、洗牌、发牌操作
思路：
完成洗牌和发牌操作，需要先拿到一副扑克牌，所以先创建一副扑克牌(共52张牌，没有大小王)
一副扑克牌由 13张红桃♥、13张黑桃♠、13张方片♦、13张梅花♣ 组成。
创建 Card类，内部定义变量 suit 花色、rank 数字，重写toString方法，便于观察每张牌的信息
创建 Game类，内部实现创建一副牌、洗牌、发牌操作.
Card类的代码示例如下：

public class Card {public String suit;//花色--红桃、黑桃、方块、梅花public int rank;//数字public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}@Overridepublic String toString() {
//        return "Card{" +
//                "suit='" + suit + '\'' +
//                ", rank=" + rank +
//                '}';return "{ "+suit+rank+" }";}
}

1.创建一副牌，使用顺序表作为容器，将每一张牌放入这个容器中
如何把每一张牌放入顺序表中？–> 四种不同花色分别有13张牌，所以使用两个 for 循环，将卡牌放入顺序表
内部循环13次，把放入同一花色的13张牌放入顺序表，外部循环4次，每次都是不同的花色。代码示例如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class Game {public String[] suits = {"♥","♠","♦","♣"};public List<Card> cardsList = new ArrayList<>();//作为扑克牌的容器//创建一副扑克牌public List<Card> createCards() {for (int i = 0; i < suits.length; i++) {for (int j = 1; j <= 13 ; j++) {Card card = new Card(suits[i],j);cardsList.add(card);}}return cardsList;}

2.洗牌操作，现实中洗牌是将任意不同的卡牌交换位置，转换为代码层面，可以把任意不同下标的卡牌进行交换，for(i)循环遍历顺序表，每次生成一个i下标后面的随机数（i+1，51），但是这样生成随机数的实现比较麻烦，因此可以从最后面即下标为 51 的位置向前遍历顺序表，每次生成 [0,i) 的随机数，然后交换下标为i 和下标为randIndex的元素。代码示例如下：

    //洗牌操作public void shuffle(List<Card> cardsList) {Random random = new Random();for (int i = 51; i > 0; i--) {int randIndex = random.nextInt(i);//生成 [0,i-1] 区间的随机数//i下标位置 与 randIndex下标位置元素进行交换swap(i,randIndex);}}//i下标位置 与 randIndex下标位置元素进行交换private void swap(int i,int randIndex) {Card tmp = cardsList.get(i);cardsList.set(i,cardsList.get(randIndex));cardsList.set(randIndex,tmp);}

3.发牌操作
要求：三人依次取牌，每人每次取牌一张，进行五次轮回取牌，最终每人手中有五张牌
三个人取出的牌，也需要一个容器容纳扑克牌，可以为每个人创建一个顺序表容纳取出的扑克牌
三人依次取牌，每次一张，进行五次轮回，就可以使用两个for循环，完成取牌和牌进入入顺序表的操作
每次取牌都要把取出的这张牌从顺序表中删除，避免其他人重复取这张牌（现实中也是如此，取出一张牌，那么这张牌就不会存在于待取的那摊扑克牌中，谁取的这张牌，这张牌就在谁手上），转换为代码层面，就是调用 cardsList.remove(0)方法。将cardsList.remove(0)方法的返回值传给每个人的手中

【注意】这里cardsList.remove(0)方法中的参数一直都是0，因为每次取牌都是最上面的牌，而顺序表删除已取出的牌之后，第二张牌又会称为新的下标为 0 的新的元素。
代码示例如下：

//发牌，三个人轮流取牌，一次取一张，最终每个人五张牌public List<List<Card>> play(List<Card> cardsList) {List<List<Card>> cardLists = new ArrayList<>();List<Card> hand0 = new ArrayList<>();List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();cardLists.add(hand0);cardLists.add(hand1);cardLists.add(hand2);for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {Card card = cardsList.remove(0);cardLists.get(j).add(card);}}return cardLists;}

Test测试类，代码示例如下：

import java.util.List;public class Test {public static void main(String[] args) {Game game = new Game();List<Card> cardsList = game.createCards();System.out.println("初始牌："+cardsList);game.shuffle(cardsList);System.out.println("洗过后的牌："+cardsList);System.out.println("发牌后，每人手中的牌："+game.play(cardsList));}
}

运行结果：

“C:\Program Files\Java\jdk-17\bin\java.exe” “-javaagent:D:\softstall\idea\IntelliJ IDEA Community Edition 2021.3.3\lib\idea_rt.jar=63623:D:\softstall\idea\IntelliJ IDEA Community Edition 2021.3.3\bin” -Dfile.encoding=UTF-8 -classpath D:\javacode\J20241025_CardGame\out\production\J20241025_CardGame Test
初始牌：[{ ♥1 }, { ♥2 }, { ♥3 }, { ♥4 }, { ♥5 }, { ♥6 }, { ♥7 }, { ♥8 }, { ♥9 }, { ♥10 }, { ♥11 }, { ♥12 }, { ♥13 }, { ♠1 }, { ♠2 }, { ♠3 }, { ♠4 }, { ♠5 }, { ♠6 }, { ♠7 }, { ♠8 }, { ♠9 }, { ♠10 }, { ♠11 }, { ♠12 }, { ♠13 }, { ♦1 }, { ♦2 }, { ♦3 }, { ♦4 }, { ♦5 }, { ♦6 }, { ♦7 }, { ♦8 }, { ♦9 }, { ♦10 }, { ♦11 }, { ♦12 }, { ♦13 }, { ♣1 }, { ♣2 }, { ♣3 }, { ♣4 }, { ♣5 }, { ♣6 }, { ♣7 }, { ♣8 }, { ♣9 }, { ♣10 }, { ♣11 }, { ♣12 }, { ♣13 }]
洗过后的牌：[{ ♣13 }, { ♥13 }, { ♠5 }, { ♦10 }, { ♠13 }, { ♦12 }, { ♥4 }, { ♦6 }, { ♣5 }, { ♣3 }, { ♣1 }, { ♠12 }, { ♣11 }, { ♣2 }, { ♣7 }, { ♥5 }, { ♦9 }, { ♥11 }, { ♥2 }, { ♦2 }, { ♥7 }, { ♦5 }, { ♣12 }, { ♠7 }, { ♠11 }, { ♦11 }, { ♥1 }, { ♠8 }, { ♥10 }, { ♣8 }, { ♥8 }, { ♥3 }, { ♠4 }, { ♣10 }, { ♦4 }, { ♠2 }, { ♠1 }, { ♥9 }, { ♠3 }, { ♣6 }, { ♠6 }, { ♦7 }, { ♥12 }, { ♦8 }, { ♣4 }, { ♠10 }, { ♦13 }, { ♠9 }, { ♦1 }, { ♣9 }, { ♥6 }, { ♦3 }]
发牌后，每人手中的牌：[[{ ♣13 }, { ♦10 }, { ♥4 }, { ♣3 }, { ♣11 }], [{ ♥13 }, { ♠13 }, { ♦6 }, { ♣1 }, { ♣2 }], [{ ♠5 }, { ♦12 }, { ♣5 }, { ♠12 }, { ♣7 }]]

在这里插入图片描述