一、什么是顺序表？

二、模拟实现顺序表

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 位置的元素设为更新为 valuepublic 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;}@Overridepublic 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<Card> 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);}
}

运行结果：