【Java】--顺序表的使用模拟实现

一、顺序表的定义

顺序表是一种线性表的存储结构，它将线性表的数据元素按照其逻辑顺序依次存储在一片连续的存储空间中。数组也是连续的存储空间，但是顺序表需要在此之上增加增删改查等功能。

顺序表的优点是支持快速的随机访问，但缺点是插入和删除操作可能需要移动大量元素。

二、顺序表的实现

在 Java 中通过 ArrayList 类完成了对顺序表的具体实现同时提供增删改查等方法

2.1创建顺序表

//指定泛型参数 import java.util.ArrayList; import java.util.List; public class text1 { public static void main(String[] args) { //创建一个空的顺序表，没有保存任何元素 ArrayList<Integer> arrayList1 = new ArrayList<>(); //向上转型的写法 List<Integer> arrayList2 = new ArrayList<>(); //通过构造方法的参数，指定顺序表的初始容量 ArrayList<Integer> arrayList3 = new ArrayList<>(10); } }

模拟实现顺序表初始化

public class MyArrayList { //通过这个数组来表述顺序表的元素 private String[] data = null; //表示顺序表中有效的元素个数 private int size = 0; public MyArrayList() { //默认初始容量为10 data = new String[10]; } public MyArrayList(int size){ //如果指定容量就按照指定的容量创建 data = new String[size]; } } 2.1 增加元素

在增加元素之前先考虑当元素溢出时的扩容操作，而扩容的本质是创建一个新数组并将旧数组的元素移到新数组中

扩容

//扩容模拟实现 private void resize(){ //创建新数组，新的数组长度为原来的1.5倍 String[] newData = new String[data.length + (data.length>>1)]; //将旧数组的复制到新数组中 for(int i = 0;i<size;i++){ newData[i] = data[i]; } //用新数组代替旧数组 data = newData; }

头插

//代码示例 list.add(0,"3"); //模拟实现 public void add(int index,String elem){ data[size++] = elem; //判断下标是否合法 if(index >=0 && index < size){ for(int i = size ; i >=index;i--){ //将下标之前的元素后移 data[i+1] = data[i]; } data[index] = elem; size++; } //如果元素个数超出就扩容 if(size>=data.length){ resize(); } }

尾插

//代码示例 list.add("hallo"); //模拟实现 public void add(String elem){ data[size] = elem; size++; //如果元素个数超出就扩容 if(size>=data.length){ resize(); } } 2.2 删除元素

指定下标删除

//代码示例 //删除下标为2的元素 list.remove(2); //模拟实现 public String remove(int index){ String elem = data[index]; for (int i = index;i<size-1;i++){ data[i] = data[i+1]; } size--; return elem; }

删除遇到的第一个元素

//代码示例 list.remove("abc"); //模拟实现 public boolean remove(String elem){ int removepos = 0; for(;removepos<size;removepos++){ if(data[removepos].equals(elem)){ break; } } if (removepos == size){ return false; } for(int i = removepos;i<size;i++){ data[i] = data[i+1]; } size--; return true; }

2.3 修改元素

获取元素

//代码示例 list.get(3); //模拟实现 public String get(int index){ return data[index]; }

修改元素

//代码示例 list.set(1,"10"); //模拟实现 public String set(int index,String elem){ data[index] = elem; return elem; }

清空

//代码示例 list.clear(); //模拟实现 public void clear(){ size = 0; } 2.4 查找元素

判断元素是否在顺序表中

//代码示例 list.contains("hallo") //模拟实现 public boolean contains(String elem){ for(int i=0;i<size;i++){ if(data[i].equals(elem)){ return true; } } return false; }

返回第一个元素所在的下标

//代码示例 list.indexOf("2"); //模拟实现 public int indexOf(String elem){ int i = 0; for(;i<size;i++){ if(data[i].equals(elem)){ return i; } } return -1; }

返回最后一个元素所在的下标

//代码示例 list.lastIndexOf("2"); //模拟实现 public int lastIndexOf(String elem){ int i = size-1; for(;i>=0;i--){ if(data[i].equals(elem)){ return i; } } return -1; }

截取部分顺序表中的元素

//代码示例 list.subList(1,3); //模拟实现 public MyArrayList subList(int fromIndex,int toIndex){ MyArrayList subList = new MyArrayList(toIndex - fromIndex); for(int i=fromIndex;i<toIndex;i++){ String elem = this.get(i); subList.add(elem); } return subList; }

打印顺序表的内容

//代码示例 System.out.println(list); //模拟实现 public String toString(){ StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("["); for(int i = 0;i<size;i++){ stringBuilder.append(data[i]); if(i<size-1) { stringBuilder.append(","); } } stringBuilder.append("]"); return stringBuilder.toString(); }

三、ArrayList 的具体应用

一个简单的洗牌算法

首先创建一张牌

class Card{ public String rank; //点数 public String suit; //花色 public Card(String rank,String suit){ this.rank=rank; this.suit=suit; } //创建打印方法，方便后续查看 public String toString(){ return "("+ suit + rank +")"; } }

再利用这张牌去创建一副牌

private static ArrayList<Card> createDeck(){ //创建ArrayList来存放每一张牌 ArrayList<Card> deck = new ArrayList<>(); //创建四种花色 String[] suits = {"♠","♥","♣","♦"}; //双重循环创建好数字牌 for (String suit:suits){ for(int i = 2;i<=10;i++){ Card card = new Card("" + i,suit); //添加到顺序表deck中 deck.add(card); } //额外的A、J、Q、K的牌 deck.add(new Card("J",suit)); deck.add(new Card("Q",suit)); deck.add(new Card("K",suit)); deck.add(new Card("A",suit)); } //最后返回顺序表 return deck; }

测试一下

public static void main(String[] args) { ArrayList<Card> deck = createDeck(); System.out.println(deck); }

可以看到所有牌都顺利创建完成

接下来的洗牌就通过标准库中的现成的方法 shuffle 来打乱顺序

//Collections是一个特殊的工具类，提供了许多方法给集合类使用 Collections.shuffle(deck);

最后对玩家进行发牌

//发牌，假设有3个玩家，每人发5张牌 //用3个ArrayList表示三个玩家 // ArrayList<Card> player1 = new ArrayList<>(); // ArrayList<Card> player2 = new ArrayList<>(); // ArrayList<Card> player3 = new ArrayList<>(); //还可以通过类似“二维数组”的方式，创建一个二维的 ArrayList ArrayList<ArrayList<Card>> players = new ArrayList<>(); for (int i = 0;i<3;i++){ //在一个顺序表里创建三个顺序表表示三名玩家 players.add(new ArrayList<>()); } //对3名玩家轮流发牌，一共发5轮 for(int round=0;round<5;round++){ for (int i=0;i<3;i++){ //取出牌堆里的第一张牌，保存并删除 Card card = deck.remove(0); //从 players 中取出对应的玩家 ArrayList<Card> player = players.get(i); //将这张牌放到对应玩家的手中 player.add(card); } } //打印3名玩家手中的牌 for(int i = 0;i<3;i++){ ArrayList<Card> player = players.get(i); System.out.println("玩家" +(i+1) + "的牌是："+ player); } }

感谢阅读