Java--ArrayList(数据结构顺序表)

前言：

        Java中有线性表存储上数据，线性表分为：顺序表和链表(ArrayList、LinkedList)。

        当然Java中也会模拟实现一遍顺序表(ArrayList)，包括里面的所有的方法

        但是我的重心会放在对Java中自带的ArrayList中方法的使用，以及如何测试一些题目是否正确！

ArrayList的模拟实现：

创建自己的接口：

        我们知道不论是顺序表还是链表都扩展了List接口，之后再顺序表或者链表中重写接口中的方法！

        首先我们可以先看看Java中ArrayList的源代码：

1、Java中的ArrayList用的是泛型类(因为我们不知道该顺序表不知道要存放什么类型的数据！)

2、 接口和父类的继承Java中做的比较全面，我们只需要模仿List接口即可。

我们做到以上两点即可。

MyList接口如下：

public interface MyList<T> {public void display();// 新增元素,默认在数组最后新增public void add(T data);/*** 判断当前的顺序表是不是满的！* @return true:满   false代表空*/public boolean isFull();public boolean checkPosInAdd(int pos);// 判定是否包含某个元素public boolean contains(T toFind);// 查找某个元素对应的位置public int indexOf(T toFind);// 获取 pos 位置的元素public int get(int pos);public boolean isEmpty();// 给 pos 位置的元素设为【更新为】 valuepublic void set(int pos, T val);/*** 删除第一次出现的关键字key* @param key*/public void remove(T key) ;// 获取顺序表长度public int size() ;// 清空顺序表public void clear() ;
}

创建自己的MyArrayList：

public class MyArrayList<T> implements MyList<T>{private Object[] arrays;int size;private static final int DEFAULT_CAPACITY = 10;public MyArrayList() {super();arrays = new Object[DEFAULT_CAPACITY];size = 0;}@Overridepublic void display() {for(int i = 0;i<size;i++) {System.out.print(arrays[i]+" ");}System.out.println();}@Overridepublic void add(T data) {//第一步检查是否需要扩容if(isFull()) {Object[] newArrays = new Object[size+size>>1];//1.5倍扩容newArrays = Arrays.copyOf(arrays,size);arrays = newArrays;}arrays[size++] = data;}@Overridepublic boolean isFull() {if(size == arrays.length) {return true;}return false;}@Overridepublic boolean checkPosInAdd(int pos) {if(pos >= 0 && pos < arrays.length) {return true;}else {return false;}}@Overridepublic boolean contains(T toFind) {for(int i = 0;i<size;i++) {if(arrays[i].equals(toFind)) {return true;}}return false;}@Overridepublic int indexOf(T toFind) {for(int i = 0;i<size;i++) {if(arrays[i].equals(toFind)) {return i;}}return -1;}@Overridepublic T get(int pos) {if(pos<0 || pos>=size) {return null;}return (T)arrays[pos];}@Overridepublic boolean isEmpty() {if(size >0) return false;else return true;}@Overridepublic void set(int pos, T data) {if(isFull()) {Object[] newArrays = new Object[size+size>>1];//1.5倍扩容newArrays = Arrays.copyOf(arrays,size);arrays = newArrays;}arrays[pos] = data;}@Overridepublic void remove(T key) {int pos = indexOf(key);if(pos == -1) {return ;} else{for(int i = pos;i<size-1;i++) {arrays[i] = arrays[i-1];}}}@Overridepublic int size() {return size;}@Overridepublic void clear() {arrays = null;}
}

main方法中使用：

可以传不同的包装类：

Integer类：

public class Main {public static void main(String[] args) {MyArrayList<Integer> list = new MyArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(7);list.set(2,9);System.out.println(list.contains(7));list.display();}
}

Character类：

    public static void main(String[] args) {MyArrayList<Character> list = new MyArrayList<>();list.add('a');list.add('b');list.add('c');list.add('d');list.add('e');list.display();}

大家写好可以自己去测！！                 

 洗牌算法：

规则：

        不算大小王，一共有52张牌，每种花色有12张，有三个人，需要摸牌。一共摸5轮，每轮每人摸一张。(注意52张牌需要打乱顺序)。

 创建Card类：

        我们应该先描述一张牌的特性：

public class Card {private int val;private String ch;public Card(int val, String ch) {this.val = val;this.ch = ch;}@Overridepublic String toString() {return ch+""+val;}
}

注意：

我在这里重写了toString方法，方便等会打印的时候打印对应的内容。

创建CardDemo类：

        里面包含了初始化52张牌，洗牌等操作：

public class CardDemo {public static final String[] SUITS = {"♠", "♥", "♣", "♦"};private static final int DEFAULT = 52;public static List<Card> buyCards() {List<Card> deck = new ArrayList<>(DEFAULT);for(int i = 0;i< 4;i++) {for (int j = 1; j <= 13; j++) {String tmp = SUITS[i];Card card = new Card(j,tmp);deck.add(card);}}return deck;}public static void swap(List<Card> deck,int cur,int tmp){Card card = deck.get(cur);deck.set(cur,deck.get(tmp));deck.set(tmp,card);}public static void randCards(List<Card> deck){Random r = new Random(100);for(int i = deck.size()-1;i>0;i--) {int tmp = r.nextInt(i);swap(deck,i,tmp);}}
}

测试类Main：

包括初始化牌，三个人轮流摸牌等操作：

public class Main {public static void main(String[] args) {List<Card> deck = CardDemo.buyCards();System.out.println("买回来牌");System.out.println(deck);System.out.println();CardDemo.randCards(deck);System.out.println("洗过的牌");System.out.println(deck);List<List<Card>> hands = new ArrayList<>();hands.add(new ArrayList<>());hands.add(new ArrayList<>());hands.add(new ArrayList<>());for(int i = 0;i<5;i++) {for (int j = 0; j <3 ; j++) {hands.get(j).add(deck.remove(0));}}System.out.println("剩余的牌:");System.out.println(deck);System.out.println("A 手中的牌:");System.out.println(hands.get(0));System.out.println("B 手中的牌:");System.out.println(hands.get(1));System.out.println("C 手中的牌:");System.out.println(hands.get(2));}
}