正式進入數據結構的學習，先從預備知識學起，戒焦戒躁戒焦戒躁...
一、泛型的引入
1、為什么需要泛型？
先來看一個題目：
實現一個類，類中包含一個數組成員，使得數組中可以存放任何類型的數據，也可以根據成員方法返回數組中某個下標的值
在沒有泛型理念的思路可能是這樣：
public class java0810 {public Object[] array = new Object[5];//成員變量public void set(int a,Object b){this.array[a] = b;}public Object get(int c){return array[c];}public static void main(String[] args) {java0810 x = new java0810();x.set(0,"哈哈");x.set(1, 2);String y1 = (String) x.get(0);int y2 = (int) x.get(1); //需要強轉，因為是object類型System.out.println(y1);System.out.println(y2);}
}我們通過Object類做到了讓一個數組中放入不同類型的數據，但在接收數據的時候需要對其進行強轉，很麻煩
于是我們想到使用泛型來解決這個問題：
public class java0810<T> { //變動1public Object[] array = new Object[5];public void set(int a,T b){this.array[a] = b;}public T get(int c){return (T)array[c]; //變動2}public static void main(String[] args) { //變動3java0810<Integer> x1 = new java0810<>();//規定了存放數據的類型x1.set(0,1);x1.set(1,2);int y1 = x1.get(0);int y2 = x1.get(1);System.out.println(y1);System.out.println(y2);java0810<String> x2 = new java0810<>();x2.set(0,"巨浪");x2.set(1,"M14大人");String y3 = x2.get(0);String y4 = x2.get(1);System.out.println(y3);System.out.println(y4);}所有的變動之處需要理解，這樣做的好處就是：
“在新建一個對象時就規定了存放數據的類型，可以讓系統幫忙檢查同時不用強轉了”
想要深入理解背后的邏輯可以搜索擦除機制和橋接方法
2、泛型類的上界
我們常常用 <? extends T> 的方式來指定約束泛型類型的上限，從而約束了‘ ？’只能是T或者其子類
來看一個題目：
寫一個泛型類，求數組中的最大值，數組的類型需要通過泛型類型來指定
//這是一個泛型類public class java0811<T extends Comparable<T>> {//泛型類的上界public T find(T[] array){int i = 0;T max = array[0];for(i = 1;i < array.length;i++){if(array[i].compareTo(max) > 0){max = array[i];}}return max;}public static void main(String[] args) {java0811<Integer> y1 = new java0811<>(); //指定數組存放的類型java0811<String> y2 = new java0811<>();Integer []array1 = { 4, 3, 2, 91, 500 };String []array2 = {"巨浪", "M14大人","騰龍"};int z = y1.find(array1); //Integer或者int都可以String w = y2.find(array2);System.out.println(z);System.out.println(w);}}這里通過實現了Comparable接口，指定了上界，從而可以使用comparaTo方法進行數字或者字符串的無差別比較
當然了，你也可以寫成是一個泛型方法：
public class java0811 {//這就是泛型方法public <T extends Comparable<T>> T find(T[] array){int i = 0;T max = array[0];for(i = 1;i < array.length;i++){if(array[i].compareTo(max) > 0){max = array[i];}}return max;}public static void main(String[] args) {java0811 x = new java0811(); //沒有指定類型，因為它不是泛型類了Integer []array1 = { 4, 3, 2, 91, 500 };int y = x.find(array1);System.out.println(y);}
}可以觀察一下里面的變動
二、通配符
1、概念：
通配符通過上下界（
extends/super）實現了比泛型類型參數更靈活的類型關系控制，并遵循PECS原則(在值設置和取出時有特定約束)。
我們先來看看通過泛型的方式存放和取出數據：
class Food{
}
class Fruit extends Food{ //先明確了繼承關系
}
class apple extends Fruit{
}
class banana extends Fruit{
}public class Plate<T>{ //設置了一個泛型類public T array;public void set(T array){this.array = array;
}public T get(){return array;
}public static void main(String[] args) {Plate<apple> x1= new Plate<>(); //表示只能放入apple對象x1.set(new apple());Plate<banana> x2 = new Plate<>(); //同理x2.set(new banana());// Plate<Food> x3 = new Plate<>();
// fun1(x3); //會失敗，因為通配符所以只能傳入Fruit的子類fun1(x1);fun1(x2);}//通配符的上界
public static void fun1(Plate<? extends Fruit> z){//指定一個容器，存放的類型是Fruit或子類System.out.println(z.get());
}這里通過fun來打印數據，接收的類型需要是Fruit或者其子類
2、通配符的上界：
采用<? extends T>的方式，在該方法中不能寫入子類，但可以接收T的子類
public static void fun1(Plate<? extends Fruit> z){//指定一個容器，存放的類型是Fruit或子類System.out.println(z.get());// z.set(new apple());
// z.set(new banana()); 設置失敗，不能知道傳入的是哪個子類Fruit fruit = z.get(); //得到的一定是Fruit的子類System.out.println(fruit); //成功了，同時打印了apple跟banana}3、通配符的下界：
采用<? super?T>的方式，在該方法中主要用于寫入，接收時要用Object類保證安全
public static void main(String[] args) {Plate<Food> x3 = new Plate<>();x3.set(new Food());fun2(x3);}
public static void fun2(Plate<? super Fruit> t){t.set(new Fruit()); //可以放自己以及子類t.set(new apple());t.set(new banana()); //會打印最后一個傳入的值// Food food = new Fruit();
// Fruit fruit2 = (Fruit) food; //這樣做就安全// Fruit fruit2=(Fruit) new Food();//但是這樣直接指向不安全,打印不出來結果// Fruit fruit3 = (Fruit) t.get(); //覺得這個寫法突兀的就向上看,也不安全Object o = t.get(); //Object來接收就安全了System.out.println(o);
}
小總結：通配符上界不能寫入子類但能接收子類
? ? ? ? ? ? ? ?通配符下界只能寫入自己以及子類，只能接收自己以及父類?
三、順序表
順序表（Sequential List）?是一種線性表，它用一段地址連續的存儲單元依次存儲線性表的數據元素
核心比喻：電影院座位
你可以把順序表想象成電影院里一排連續的座位。
連續存儲：這些座位是緊挨著的，一個接一個，擁有固定的座位號（如1排1座、1排2座...）。這就是“順序”的含義——數據在物理內存中是連續存儲的。
快速“按號找座”：如果你想找第5個座位上坐的是誰，你可以立刻計算出來并直接走過去。
“插隊”與“離場”麻煩：
插入：如果這排座位已經坐滿了，你想在中間加一個人，那么從這個位置開始以后的所有人都需要向后移動一個位置，才能空出一個新的座位。
刪除：同理，如果中間有一個人離開了，那么他后面的所有人都需要向前移動一個位置來填補空位，以保持座位的連續性。
這是一個自己實現的順序表：
public interface IList {void add(int data); // 新增元素,默認在數組最后新增void add(int pos, int data); // 在 pos 位置新增元素boolean contains(int toFind); // 判定是否包含某個元素int indexOf(int toFind); // 查找某個元素對應的位置int get(int pos); // 獲取 pos 位置的元素void set(int pos, int value); // 給 pos 位置的元素設為 valuevoid remove(int toRemove); //刪除第一次出現的關鍵字keyint size(); // 獲取順序表長度void clear(); // 清空順序表void display(); // 打印順序表，注意：該方法并不是順序表中的方法，為了方便看測試結果給出的boolean isFull();boolean isEmpty();}
import java.util.Arrays;public class MyarrayList implements IList{public int[]array;public int useside;public static final int l = 5;public MyarrayList(){array = new int[l];}//檢查是否放滿了@Overridepublic boolean isFull() {if(useside == array.length){return true;}return false;}@Overridepublic boolean isEmpty() {if(useside == 0){return true;}return false;}//自己設置的2倍擴容public void grow(){array = Arrays.copyOf(array,2 * array.length);}//在順序表中，默認在最后位置添加元素，這個沒有@Overridepublic void add(int data) {array[useside++] = data;}public void checkpos(int pos){if(pos < 0 || pos > useside){//這里在數組末尾插入是合法的throw new ArrayIndexOutOfBoundsException("pos位置不合法" + pos);} //自定義異常}public void checkpos2(int pos){ //一個典型的受檢異常if(pos < 0 || pos >= useside){throw new ListEmptyException("獲取位置不合法" + pos);}}@Overridepublic void add(int pos,int data) {checkpos(pos);if(isFull()){grow();} //移動元素for(int i = useside - 1;i >= pos;i--){array[i+1] = array[i];}array[pos] = data;useside++; //新加入了元素就更新計數}@Overridepublic boolean contains(int toFind) {for (int i = 0; i < array.length; i++) {if(array[i] == toFind){return true;}}return false;}@Overridepublic int indexOf(int toFind) {for (int i = 0; i < useside; i++) {//這里寫成了array.length會打印沒用的0if (array[i] == toFind){return i;}}return -1; //-1肯定不屬于下標}@Overridepublic int get(int pos) {if(isEmpty()){throw new ArrayIndexOutOfBoundsException("數組是空的");}checkpos2(pos);return array[pos];}@Overridepublic void set(int pos, int value) {checkpos(pos);array[pos] = value;}@Overridepublic int size() {return array.length;}@Overridepublic void clear() {
// for (int i = 0; i < array.length; i++) {
// array[i] = 0/Null;
// }useside = 0;}@Overridepublic void display() {//這里也是一樣，要寫useside而不是array.lengthfor (int i = 0; i < useside; i++) {System.out.print(array[i] + " ");}System.out.println();}@Overridepublic void remove(int toRemove) {int v = indexOf(toRemove);if(v == -1){System.out.println("找不到要刪除的值");return; //終止代碼}for (int i = v; i < useside-1; i++) {array[i] = array[i+1];}useside--;}public static void main(String[] args) {MyarrayList x = new MyarrayList();x.add(0,9); //在1位置添加一個9x.add(1,2);x.add(2,3);x.display();
// try {
// x.checkpos(100);
// }catch (ArrayIndexOutOfBoundsException e){
// e.printStackTrace();
// }int c = x.get(1);System.out.println(c);x.remove(100);x.display();}}
public class ListEmptyException extends RuntimeException{public ListEmptyException() {}public ListEmptyException(String message) {super(message);}
}自己實現過后有助于我們更好的理解順序表
完
