1.順序表的基本介紹

順序表在內存中的存儲是連續的，它是線性表中的其中一種，使用順序表可以對數據進行增刪查改。

2.順序表的模擬實現

2.1 常見的功能

// 新增元素,默認在數組最后新增
public void add(E data) { }
// 在 pos 位置新增元素
public void add(int pos, E data) { }
// 判定是否包含某個元素
public boolean contains(E toFind) { return true; }
// 查找某個元素對應的位置
public int indexOf(int toFind) { return -1; }
// 獲取 pos 位置的元素
public E get(int pos) { return null; }
// 給 pos 位置的元素設為 value
public void set(int pos, E value) { }
//刪除第?次出現的關鍵字key
public void remove(E toRemove) { }
// 獲取順序表?度
public int size() { return 0; }
// 清空順序表
public void clear() { }
// 打印順序表，注意：該?法并不是順序表中的?法，為了?便看測試結果給出的
public void display() { }

2.2 基本框架

順序表在內存中的存儲是連續的，可以理解為順序表在底層存放類似于數組的存放，所以在模擬實現時要定義一個數組，在增刪除查改的過程中數據的實際存儲會變化，可以再定義一個變量統計實際順序表中存儲的元素個數。

//順序表
public class myArrayList<E> {public Object[] arrays;//存放數據public int usedSize;//統計個數public static int initialCapacity = 5;//默認容量public myArrayList(){//創建同時定義大小arrays = new Object[initialCapacity];}//方法// 新增元素,默認在數組最后新增public void add(E data) { }// 在 pos 位置新增元素public void add(int pos, E data) { }// 判定是否包含某個元素public boolean contains(int toFind) { return true; }// 查找某個元素對應的位置public int indexOf(E toFind) { return -1; }// 獲取 pos 位置的元素public E get(int pos) { return null; }// 給 pos 位置的元素設為 valuepublic void set(int pos, E value) { }//刪除第?次出現的關鍵字keypublic void remove(int toRemove) { }// 獲取順序表?度public int size() { return 0; }// 清空順序表public void clear() { }// 打印順序表，注意：該?法并不是順序表中的?法，為了?便看測試結果給出的public void display() { }
}

2.3 方法的實現

2.3.1 add方法

 private void add_capacity(Object[] arrays){//二倍擴容arrays = Arrays.copyOf(arrays,arrays.length * 2);}// 新增元素,默認在數組最后新增public void add(E data) { //1.添加元素前需要判斷是否容量是否未滿if(usedSize == arrays.length){//如果容量已滿擴容add_capacity(arrays);}//2.增加元素arrays[usedSize] = data;usedSize++;//下次增加的下標}

2.3.2 size方法

// 獲取順序表?度public int size() { //返回usedSize,實際使用的長度return usedSize;}

2.3.3 display方法

// 打印順序表，注意：該?法并不是順序表中的?法，為了?便看測試結果給出的public void display() {//1.判斷是否為空if(usedSize == 0){return;//無需打印}//2.打印for (int i = 0; i < arrays.length; i++) {System.out.print(arrays[i] + " ");}}

2.3.4 add（int pos，E data)方法

public class PosillegalException extends RuntimeException{public PosillegalException() {}public PosillegalException(String message) {super(message);}
}

 // 在 pos 位置新增元素public void add(int pos, E data) {//1.判斷是否需要擴容if(usedSize == arrays.length){add_capacity(arrays);}//2.坐標的使用需要判斷是否合法if(pos < 0 || pos > usedSize){throw new PosillegalException("坐標非法：" + pos);}//3.增加:將pos位置后面的元素往后移動，再增加for (int i = usedSize - 1;i <= pos;i--){arrays[usedSize] = arrays[usedSize + 1];}arrays[pos] = data;usedSize++;//元素+1}

2.3.5 remove方法

 //刪除第?次出現的關鍵字keyprivate int search(E toRemove){for (int i = 0; i < arrays.length; i++) {if(arrays[i] == toRemove){return i;}}return -1;}public void remove(E toRemove) {//1.遍歷數組查詢是否存在int pos = search(toRemove)if (pos == -1) {System.out.println(toRemove + "不存在該元素！");return;}//2.在指定下標開始，從前往后覆蓋for (int i = pos; i < usedSize - 1; i++) {arrays[i] = arrays[i + 1];}//3.元素減一usedSize--;}

2.3.6 get方法

// 獲取 pos 位置的元素public E get(int pos) { //1.判斷坐標是否合法if(pos < 0 || pos >= usedSize){throw new PosillegalException("坐標非法：" + pos);}//2.返回return (E)arrays[pos]; }

2.3.7 contain方法

    // 判定是否包含某個元素public boolean contains(E toFind) {//1.判斷是否為空if(usedSize == 0) return false;//2.調用search方法int pos = search(toFind);//3.判斷if(pos == -1) return false;else return true;}

2.3.8 indexOf方法

 // 查找某個元素對應的位置private boolean isEmpty(){return usedSize == 0;}public int indexOf(E toFind) { //1.判斷是否為空if(isEmpty()) return -1;//2.使用searchreturn search(toFind);}

2.3.9 set方法

   // 給 pos 位置的元素設為 valuepublic void set(int pos, E value) {//1.判斷坐標是否合法if(pos < 0 || pos >= usedSize){throw new PosillegalException("坐標非法："+ pos);}//2.考慮是否擴容if(usedSize == arrays.length){add_capacity(arrays);}//3.設置arrays[pos] = value;}

2.3.10 clear方法

 // 清空順序表public void clear() {//數組中的元素是E類型（泛型），有可能是引用數據類型//需要將元素設置為nullfor (int i = 0; i < usedSize; i++) {arrays[i] = null;}//將數組引用設置為nullarrays = null;}

2.4方法的使用

public class Main{public static void main(String[] args) {myArrayList<Integer> myArrayList = new myArrayList<>();myArrayList.add(1);//增加myArrayList.add(1,2);myArrayList.display();//展示System.out.println("=====");myArrayList.remove(2);//移除myArrayList.set(0,3);//設置boolean ret = myArrayList.contains(1);//查詢是否包含System.out.println(ret);int pos = myArrayList.indexOf(0);//查找位置System.out.println(pos);int e = myArrayList.get(0);//獲取System.out.println(e);myArrayList.clear();//回收順序表myArrayList.display();}
}

3.順序表的應用

順序表是連續存儲的一塊內存空間，在游戲中使用比較廣泛，利用順序表可以實現簡單的洗牌算法

3.1 創建卡牌

//牌
public class Card {public int rank;//牌值public String suit;//花色//重寫toString方法@Overridepublic String toString() {return  String.format("%s %d",suit,rank);}
}

3.2 牌的實現

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;/**/
public class CardDemo {//花色public static String[] Suit = {"?","?","?","?"};//使用順序表實現一副牌（不包含大小王）public List<Card> buyDeck(){List<Card> deck = new ArrayList<>(52);for (int i = 0; i < 4; i++) {//花色for (int j = 1; j <= 13; j++) {//牌值String suit = Suit[i];int rank = j;Card card = new Card();card.suit = suit;card.rank = rank;deck.add(card);}}return deck;}//打亂順序:生成隨機坐標，與指定坐標交換private static void swap(List<Card> deck,int i,int j ){Card card = deck.get(i);deck.set(i,deck.get(j));deck.set(j,card);}private static List<Card> shuffle(List<Card> deck){Random random = new Random();int j = random.nextInt(52);//0 - 51for (int i = deck.size() - 1; i >= 0 ; i--) {swap(deck,i,j);}return deck;}}

簡單測試實現的排序

 public static void main(String[] args) {CardDemo cardDemo = new CardDemo();List<Card> deck = cardDemo.buyDeck();System.out.println(deck);//洗牌前deck = CardDemo.shuffle(deck);System.out.println(deck);//洗牌后}

3.3 發牌

 public static void main(String[] args) {CardDemo cardDemo = new CardDemo();List<Card> deck = cardDemo.buyDeck();System.out.println(deck);//洗牌前deck = CardDemo.shuffle(deck);System.out.println(deck);//洗牌后List<List<Card>> hand = new ArrayList<>();hand.add(new ArrayList<>());hand.add(new ArrayList<>());hand.add(new ArrayList<>());//發牌:一共發5輪，一輪每人發一張for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {hand.get(j).add(deck.remove(0));}}//第一個人的牌System.out.println(hand.get(0));//第二個人的牌System.out.println(hand.get(1));//第三個人的牌System.out.println(hand.get(2));//剩余的牌System.out.println(deck);}}

4.代碼鏈接

順序表的使用