数据结构之顺序表

目录

一、概念

二、构造方法

三、常见操作

四、扩容机制

五、ArrayList的具体使用

1、简单洗牌算法

2、杨辉三角

一、概念

是一段物理地址连续存储元素的线性结构，采用数组存储，实现了List接口。

二、构造方法

无参构造时，第一次add时会默认容量为10.

三、常见操作

四、扩容机制

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

会先按照原来容量的1.5倍扩容，若用户所需容量已经大于1.5倍扩容结果，则以用户指定大小扩容。若扩容后的空间大于MAX_ARRAY_SIZE，则重新计算容量大小。使用Arrays的copyOf方法扩容。

五、ArrayList的具体使用

1、简单洗牌算法

实现买牌（展示牌）、洗牌、三人轮流接五回牌

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

class card{
    private String flower;  //牌的花色
    private int number;    // 牌的数字

    public String getFlower() {
        return flower;
    }

    public void setFlower(String flower) {
        this.flower = flower;
    }

    public int getNumber() {
        return number;
    }

    public void setNumber(int number) {
        this.number = number;
    }
    public card(String flower,int number){
        this.flower=flower;
        this.number=number;
    }

    @Override
    public String toString() {
        return flower+":"+number;
    }
}
class cardDo {
    public static final String[] flowers=new String[]{"♥","♠","♦","♣"};

    //买牌
    public List<card> buyCards(){
        List<card> cardList=new ArrayList<>();
        for (int i=0;i<4;i++){
            for(int j=0;j<13;j++){
                card temp=new card(flowers[i],j+1);
                cardList.add(temp);
            }
        }
        return cardList;
    }

    //洗牌
    public List<card> washCards(List<card> cardList){
        Random random=new Random();
        for(int i=cardList.size()-1;i>0;i--){
            int index=random.nextInt(i);
            swap(cardList,i,index);
        }
        return cardList;
    }
    public void swap(List<card> cardList,int index1,int index2){
        card temp=cardList.get(index1);
        cardList.set(index1,cardList.get(index2));
        cardList.set(index2,temp);
    }

    //接牌
    public void getCards(List<card> cardList){
        List<List<card>> hands=new ArrayList<>();
        List<card> hand1=new ArrayList<>();
        List<card> hand2=new ArrayList<>();
        List<card> hand3=new ArrayList<>();
        hands.add(hand1);
        hands.add(hand2);
        hands.add(hand3);
        for(int i=0;i<5;i++){
            for(int j=0;j<3;j++){
                card temp=cardList.remove(0);
                hands.get(j).add(temp);
            }
        }
        System.out.print("第一个人接的牌如下：");
        System.out.println(hand1); //默认调用toString
        System.out.print("第二个人接的牌如下：");
        System.out.println(hand2);
        System.out.print("第三个人接的牌如下：");
        System.out.println(hand3);
        System.out.print("剩下的牌如下：");
        System.out.println(cardList);
    }
}
public class test {
    public static void main(String[] args) {
        cardDo carddo=new cardDo();
        System.out.println("买的牌如下：");
        List<card> cards=carddo.buyCards();
        System.out.println(cards);  
        System.out.println("洗的牌如下：");
        List<card> newCards=carddo.washCards(cards);
        System.out.println(newCards);
        carddo.getCards(newCards);
    }
}

2、杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> numbers=new ArrayList<>();
        List<Integer> number1=new ArrayList<>();
        number1.add(1);
        numbers.add(number1);
        if(numRows==1) return numbers;
        for(int i=1;i<numRows;i++){
            List<Integer> number=new ArrayList<>();
            number.add(1);
            for(int j=1;j<i;j++){
                number.add(numbers.get(i-1).get(j)+numbers.get(i-1).get(j-1));
            }
            number.add(1);
            numbers.add(number);
        }
        return numbers;
    }
}