一、什么是顺序表？
顺序表是数据结构的一种，是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<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); } }
运行结果：
