企业查询入口免费_成都旅游住哪里便宜又方便_怎样推广app别人才愿意下载_培训公司排名

一、顺序表的定义

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

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

二、顺序表的实现

在 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() {//默认初始容量为10data = 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<>();//还可以通过类似“二维数组”的方式，创建一个二维的 ArrayListArrayList<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);}}

感谢阅读