数据结构——顺序表

目录

一、什么是顺序表？

二、模拟实现顺序表 

1、添加元素

2、删除元素

3、修改指定位置的元素 

4、遍历 

5、查看是否包含某个元素 

6、查找元素下标 

7、获取指定位置的元素 

8、清空 

三、顺序表的应用 

1、杨辉三角

 2、简单的洗牌

a、定义一个牌类

b、买牌 

c、洗牌 

d、发牌 

e、效果显示 

---

一、什么是顺序表？

顺序表是数据结构的一种，是List的子类，以数组的形式进行存储。

顺序表的特点：

• 顺序表都是连续的。
• 存取速度快，依靠下标直接进行存取。
• 不适合频繁插入和删除，需移动大量元素，时间复杂度高。

二、模拟实现顺序表 

顺序表首先需要设置默认大小，以及所使用的容量，还需定义一个数组。 

 public int[] elem;
    public int usedSize;//0
    //默认容量
    private static final int DEFAULT_SIZE = 10;
 
    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
    }

1、添加元素

直接添加：需要判断是否容量已满需要扩容，再向数组已利用空间之后插入元素。

   /**
     * 判断当前的顺序表是不是满的！
     * @return true:满   false代表空
     */
    public boolean isFull() {
        if(usedSize==elem.length){
            return true;
        }
        return false;
    }
   /**
     * 扩容（实际上顺序表底层扩容为1.5倍）
     */
    public void reSize(){
        this.elem= Arrays.copyOf(elem,2*elem.length);
    }
// 新增元素,默认在数组最后新增
    public void add(int data) {
        if(isFull()){
            reSize();
        }
        elem[usedSize]=data;
        usedSize++;
    }

指定位置添加：首先需要判断位置的合法性，然后再判断是否需要扩容，最后再逐步右移，在指定位置添加元素。 

// 在 pos 位置新增元素
    public void add(int pos, int data) {
        if(checkPosInAdd(pos)&&!isFull()){
            for(int j=usedSize-1;j>=pos;j--){
                elem[j+1]=elem[j];
            }
            elem[pos]=data;
            usedSize++;
        }
    }

2、删除元素

 删除第一次出现的关键字：先对数组中的元素进行遍历，找到待查找元素的下标，然后左移进行覆盖删除。

 /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) {
        boolean flag=false;
        for(int i=0;i<usedSize;i++){
            if(elem[i]==key){
                flag=true;
                for(int j=i;j<usedSize-1;j++){
                    elem[j]=elem[j+1];
                }
                elem[usedSize-1]=0;
                usedSize--;
                break;
            }
        }
        if(flag==false){
            System.out.println("顺序表中没有此元素");
        }
 
    }

删除所有出现的关键字：利用双指针进行遍历，设置right和left指针，如果遍历到待删除的元素，则right++，否则left++，将right所指的元素赋值给left。

/**
     * 删除顺序表中所有的key
     * @param val
     */
    public void removeAll(int val){
        int left=0;
        int right=0;
        while(right<usedSize){
            if(elem[right]==val){
                right++;
            }else{
                elem[left]=elem[right];
                left++;
                right++;
            }
        }
        usedSize=left;
    }

3、修改指定位置的元素 

 判断位置合法性，然后直接进行更新。

// 获取 pos 位置的元素
    public int get(int pos) {
        if(checkPosInAdd(pos)&&pos!=usedSize){
            return elem[pos];
        }else{
            throw new PosException("位置不合法");
        }
    }
// 给 pos 位置的元素设为更新为 value
    public void set(int pos, int value) {
        if(checkPosInAdd(pos)&&pos!=usedSize){
            elem[pos]=value;
        }
    }

4、遍历 

    /**
     * 打印顺序表:
     *   根据usedSize判断即可
     */
    public void display() {
      for(int i=0;i<usedSize;i++){
          System.out.print(elem[i]+" ");
      }
        System.out.println();
    }

5、查看是否包含某个元素 

// 判定是否包含某个元素
    public boolean contains(int toFind) {
        for(int i=0;i<usedSize;i++){
            if(elem[i]==toFind){
                return true;
            }
        }
        return false;
    }

6、查找元素下标 

 // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for(int i=0;i<usedSize;i++){
            if(elem[i]==toFind){
                return i;
            }
        }
        return -1;
    }

7、获取指定位置的元素 

首先判断位置的合法性，再进行查找。

// 获取 pos 位置的元素
    public int get(int pos) {
        if(checkPosInAdd(pos)&&pos!=usedSize){
            return elem[pos];
        }else{
            throw new PosException("位置不合法");
        }
    }

8、清空 

将数组中的元素全部置为0，便于回收，修改数组的当前使用长度为0。

// 清空顺序表
    public void clear() {
        for (int i=0;i<usedSize;i++){
            elem[i]=0;
        }
        usedSize=0;
 
    }

三、顺序表的应用 

1、杨辉三角

                             

利用二维数组的思想：定义一个泛型为顺序表的顺序表，将每一行的第一个元素和最后一个元素置为1，再利用杨辉三角的特点，当前元素的值=上一行这一列的元素+上一行前一列的元素，之后再将每一行都添加进去。

public static List<List<Integer>> yangHuiTriangle(int n){
        List<List<Integer>> list = new ArrayList();
        List<Integer> row = new ArrayList();
        row.add(1);
        list.add(row);
        for(int i=1;i<n;i++){
            List<Integer> preRow = list.get(i-1);
            List<Integer> currentRow = new ArrayList();
            currentRow.add(1);
            for(int j=1;j<i;j++ ){
                Integer m=preRow.get(new Integer(j))+preRow.get(j-1);
                currentRow.add(m);
            }
            currentRow.add(1);
            list.add(currentRow);
        }
        return list;
    }

 2、简单的洗牌

a、定义一个牌类

首先需要定义一个牌类，有花色和大小两个属性。 

public class Card {
    private char design;
    private int size;
 
    public Card(char design, int size) {
        this.design = design;
        this.size = size;
    }
 
    public char getDesign() {
        return design;
    }
 
    public void setDesign(char design) {
        this.design = design;
    }
 
    public int getSize() {
        return size;
    }
 
    public void setSize(int size) {
        this.size = size;
    }
 
    @Override
    public String toString() {
        return "{" + design +
                " " + size +
                '}';
    }
}

b、买牌 

定义一个指定泛型为Card牌类的顺序表，然后再将52张牌（大小王除外）添加进去。

 /**
     * 买牌
     * 将52张牌（除大小王）加入到集合中
     * J、Q、K用11、12、13替代
     * @return
     */
    public List<Card> buyCard(){
        char[] design={'♥','♦','♣','♠'};
        List<Card> list=new ArrayList<>();
        for(int i=0;i<4;i++){
            for(int j=0;j<13;j++){
                list.add(new Card(design[i],j));
            }
        }
        return list;
    }

c、洗牌 

将顺序表中存放的牌打乱：利用for循环，Random类生成一个随机数，然后与指定位置元素交换。

    /**
     * 洗牌：保证牌是乱序的
     */
    public List<Card> shuffle(List<Card> list){
        for(int i=list.size()-1;i>0;i--){
            Random random = new Random();
            int num=random.nextInt(i);
            swap(list,i,num);
        }
        return list;
    }
 
    /**
     * 将牌进行交换
     */
    private void swap(List<Card> list,int i,int j){
        Card card=list.get(i);
        list.set(i,list.get(j));
        list.set(j,card);
    }

d、发牌 

假设有三个玩家，依次每人取五张牌：定义一个泛型为牌类顺序表的顺序表，每次从牌顺序表中移除牌向玩家顺序表中添加。

    /**
     * 发牌：三个人轮流连续发五张牌
     * @param list
     * @return
     */
    public List<List<Card>> deal(List list){
        List<List<Card>> player =new ArrayList<>();
        List<Card> player1=new ArrayList<>();
        List<Card> player2=new ArrayList<>();
        List<Card> player3=new ArrayList<>();
        player.add(player1);
        player.add(player2);
        player.add(player3);
        for(int i=0;i<5;i++){
            for(int j=0;j<3;j++){
                Card card =list.remove(0);
                player.get(j).add(card);
            }
        }
        return player;
    }

e、效果显示 

public class Test {
    public static void main(String[] args) {
        Game game = new Game();
        List<Card> list = game.buyCard();
        System.out.println(list);
        System.out.println("洗牌：");
        game.shuffle(list);
        System.out.println(list);
        List<List<Card>> player=game.deal(list);
        List<Card> player1=player.get(0);
        List<Card> player2=player.get(1);
        List<Card> player3=player.get(2);
        System.out.println("玩家1:"+player1);
        System.out.println("玩家2:"+player2);
        System.out.println("玩家3:"+player3);
 
    }
}

运行结果：