什麼是泛型?,Set集合,TreeSet集合自然排序和比較器排序,數據結構-二叉樹,數據結構-平衡二叉樹
- 2020 年 12 月 26 日
- 筆記
- JAVA, Java進階基礎學習筆記, 基礎
1.泛型
2.Set集合
3.TreeSet
4.數據結構-二叉樹
5.數據結構-平衡二叉樹
==用到的單詞==
1.element[ˈelɪmənt]
要素 元素（軟)
2.key[kiː]
3.type[taɪp]
類型;
4.value[ˈvæljuː]
值
5.genericity
泛型
6.comparable[ˈkɒmpərəbl]
可比較的;
7.compare[kəmˈpeə(r)]
比較
8.comparator[kəmˈpɜrətər]
比較器
==重難點梳理==
==超詳細講義及源程式碼==
1.泛型
1.1泛型概述【了解】(影片01) （5『』）
1.為什麼要使用泛型(泛型的好處)
-
它提供了編譯時類型安全檢測機制,把運行時期的問題提前到了編譯期間
-
避免了強制類型轉換
package com.itheima.genericitysummarize;
import java.util.ArrayList;
import java.util.Iterator;
/**
* 不寫泛型的弊端
*/
public class GenericitySummarize {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("aaa");
list.add3("bbb");
list.add("ccc");
list.add(123);
Iterator it = list.iterator();
while(it.hasNext()){
String next = (String) it.next();
int len = next.length();
System.out.println(len);
}
}
}
1.2泛型類的使用【重點】（影片02）
1.泛型用在什麼地方(泛型可以使用的地方)
2.什麼是泛型類（ArrayList<E>）
如果一個類的後面有<E> ，表示這個類是一個泛型類
public class ArrayList<E>
3.如何使用泛型類
創建泛型類對象時,必須要給這個泛型確定具體的數據類型
ArrayList<String> list=new ArrayList<>();
1.3 泛型-自定義泛型類(了解)（影片03）
1.如何定義泛型(泛型的定義格式)
-
<類型>: 指定一種類型的格式.
例如: <E> <T><Q><M>
-
<類型1,類型2…>: 指定多種類型的格式,多種類型之間用逗號隔開.
例如: <E,T> <K,V><Q,M>
2.如何定義泛型類(泛型類格式)
定義格式
修飾符 class 類名<類型> { }
範例:
public class Generic<T> {},此處的T可以推薦使用常見的T,E,K,V等形式參數來表示泛型
示例程式碼
package com.itheima.genericityclass;
//就是一個泛型類
public class Box<E> {
private E element;
public E getElement() {
return element;
}
public void setElement(E element) {
this.element = element;
}
}
測試類
package com.itheima.genericityclass;
/**
* 自定義泛型類
*/
public class MyGenericityClass {
public static void main(String[] args) {
Box<String> box1 = new Box<>();
box1.setElement("給小麗的土味情話");
String element1 = box1.getElement();
System.out.println(element1);
Box<Integer> box2 = new Box<>();
box2.setElement(19);
Integer element2 = box2.getElement();
System.out.println(element2);
}
}
1.3泛型-泛型方法的使用【難點】(影片04)
1.什麼是泛型方法
方法定義中在返回類型之前有泛型定義的方法，就是一個泛型方法
-
泛型方法的格式
public <T> T[] toArray•(T[] a){}
測試類
package com.itheima.genericitymethod;
import java.util.ArrayList;
import java.util.Arrays;
/**
* 使用Java中的泛型方法
*/
public class GenericityMethod1 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("給小花同學的土味情話");
list.add("給小麗同學的土味情話");
list.add("給小路同學的土味情話");
//將list集合轉成一個數組並返回
//如果是空參的,那麼返回的數組類型為Object類型的.
Object[] objects = list.toArray();
System.out.println(Arrays.toString(objects));
String[] strings = list.toArray(new String[list.size()]);
System.out.println(Arrays.toString(strings));
}
}
1.4 自定義泛型方法【了解】（影片05）
1.定義格式
修飾符 <類型> 返回值類型 方法名(類型 變數名) { }
範例: public <T> void show(){}
示例程式碼:
package com.itheima.genericitymethod;
import java.util.ArrayList;
/**
* 自定義泛型方法
* 定義一個泛型方法，傳遞一個集合和四個元素，將元素添加到集合中並返回
*/
public class GenericityMethod2 {
public static void main(String[] args) {
ArrayList<String> list1 = addElement(new ArrayList<String>(), "a", "b", "c", "d");
System.out.println(list1);
ArrayList<Integer> list2 = addElement(new ArrayList<Integer>(), 1, 2, 3, 4);
System.out.println(list2);
}
public static <T> ArrayList<T> addElement(ArrayList<T> list , T t1 ,T t2 ,T t3 ,T t4){
list.add(t1);
list.add(t2);
list.add(t3);
list.add(t4);
return list;
}
}
1.5泛型介面【難點】(影片06)
-
定義格式
修飾符 interface 介面名<類型> { } -
示例程式碼
package com.itheima.genericityinterface;
public class GenericityInterface {
public static void main(String[] args) {
GenericityImpl1<String> genericity = new GenericityImpl1<>();
genericity.method("小麗給我的土味情話");
GenericityImpl2 genericityImpl2 = new GenericityImpl2();
genericityImpl2.method(19);
}
}
interface Genericity<E>{
public abstract void method(E e);
}
class GenericityImpl2 implements Genericity<Integer>{
1.5類型通配符【記憶】(影片07)
1.類型通配符的格式
<?>
2.泛型通配符的使用
1.類型通配符: <?>
ArrayList<?>: 表示元素類型未知的ArrayList,它的元素可以匹配任何的類型,但是並不能把元素添加到ArrayList中了,獲取出來的也是父類類型
2.類型通配符上限: <? extends 類型>
ArrayList <? extends Number>: 它表示的類型是Number或者其子類型
3.類型通配符下限: <? super 類型>
ArrayListList <? super Number>: 它表示的類型是Number或者其父類型
public class Genericbobing{
public static void main(String[] args) {
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<String> list2 = new ArrayList<>();
ArrayList<Number> list3 = new ArrayList<>();
ArrayList<Object> list4 = new ArrayList<>();
printList(list1);
printList(list2);
method1(list1);
method1(list2);
method1(list3);
method1(list4);
method2(list1);
method2(list2);
method3(list3);
method4(list4);
}
// 泛型通配符: 此時的泛型?,可以是任意類型
public static void printList(ArrayList<?> list){}
// 泛型的上限: 此時的泛型?,必須是Number類型或者Number類型的子類
public static void method1(ArrayList<? extends Number> list){}
// 泛型的下限: 此時的泛型?,必須是Number類型或者Number類型的父類
public static void method2(ArrayList<? super Number> list){}
}
小結
1.為什麼要使用泛型
使用泛型的目的就是為了類型安全，將類型問題從運行時提到編譯時進行處理
2.什麼是泛型
參數化類型，在使用用時，需要給具體的數據類型
3.怎麼使用？
在創建聲明或創建時給泛型類型指定具體的類型
4.用在哪裡？
泛型類、泛型方法、泛型介面
5.泛型通配符
? 、? extends 父類或介面 （下限） ? super 父類或介面 （上限）
6.多態遇到泛型會怎麼樣?(擴展不需要講)
ArrayList<Animal> alist= ArrayList<Dog> 對象？
ArrayList<Animal> alist=List<Animal>對象?
List<Animal> llist= ArrayList<Dog> 對象?
List<Animal> llist=ArrayList<Animal> 對象?
public static print(ArrayList<Animal> list) 是可否可以傳ArrayList<Dog>對象?
2.Set集合
2.1Set概述【了解】(影片08)
2.2Set集合的基本使用【重點】（影片09）
1.Set集合的特點
不可以存儲重複元素
存取順序不一致
沒有索引
2.Set集合的使用
package com.itheima.myset;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
/**
* Set集合的基本使用
*/
public class MySet1 {
public static void main(String[] args) {
Set<String> set = new TreeSet<>();
set.add("ccc");
set.add("aaa");
set.add("aaa");
set.add("bbb");
// for (int i = 0; i < set.size(); i++) {
// //Set集合是沒有索引的，所以不能使用通過索引獲取元素的方法
// }
Iterator<String> it = set.iterator();
while (it.hasNext()){
String s = it.next();
System.out.println(s);
}
System.out.println("-----------------------------------");
for (String s : set) {
System.out.println(s);
}
}
}
3.TreeSet集合
3.1TreeSet-基本使用【重點】（影片10）
1.TreeSet的特點
-
不可以存儲重複元素
-
沒有索引
-
可以將元素按照規則進行排序
2.TreeSet的使用
package com.itheima.mytreeset;
import java.util.TreeSet;
/**
* TreeSet集合來存儲Integer類型
*/
public class MyTreeSet1 {
public static void main(String[] args) {
TreeSet<Integer> ts = new TreeSet<>();
ts.add(5);//自動裝箱
ts.add(3);
ts.add(4);
ts.add(1);
ts.add(2);
System.out.println(ts);
}
}
存儲Student對象
package com.itheima.mytreeset;
import java.util.TreeSet;
/**
* TreeSet集合來存儲Student類型
*/
public class MyTreeSet2 {
public static void main(String[] args) {
TreeSet<Student> ts = new TreeSet<>();
Student s1 = new Student("zhangsan",28);
Student s2 = new Student("lisi",27);
Student s3 = new Student("wangwu",29);
Student s4 = new Student("zhaoliu",28);
Student s5 = new Student("qianqi",30);
ts.add(s1);
ts.add(s2);
ts.add(s3);
ts.add(s4);
ts.add(s5);
System.out.println(ts);
}
}
Student對象
package com.itheima.mytreeset;
public class Student {
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
Exception in thread "main" java.lang.ClassCastException: class com.itheima.mytreeset.Student cannot be cast to class java.lang.Comparable (com.itheima.mytreeset.Student is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap') at java.base/java.util.TreeMap.compare(TreeMap.java:1291) at java.base/java.util.TreeMap.put(TreeMap.java:536) at java.base/java.util.TreeSet.add(TreeSet.java:255) at com.itheima.mytreeset.MyTreeSet2.main(MyTreeSet2.java:18)
3.3自然排序Comparable的使用【重點】(影片11)
-
案例需求
-
存儲學生對象並遍歷，創建TreeSet集合使用無參構造方法
-
要求：按照年齡從小到大排序
提示:
//o - 要比較的對象 //將此對象與指定的對象進行比較以進行排序。 返回一個負整數，零或正整數，因為該對象小於，等於或大於指定對象 public int compareTo(T o);
-
實現步驟
-
使用空參構造創建TreeSet集合
-
用TreeSet集合存儲自定義對象，無參構造方法使用的是自然排序對元素進行排序的
-
-
自定義的Student類實現Comparable介面
-
自然排序，就是讓元素所屬的類實現Comparable介面，重寫compareTo(T o)方法
-
-
重寫介面中的compareTo方法
-
重寫方法時，一定要注意排序規則必須按照要求的主要條件和次要條件來寫
-
程式碼實現
學生類
public class Student implements Comparable<Student>{
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
/***
* 比較兩個對象的大小
* @param o 表示集合中的元素
* @return 如果是正值，表示要存入的當前對象大，放右邊
* 如果是負值，表示要存入的當前對象小，入左邊
* 如果返回0, 表示兩個對象相等，不存
*/
@Override
public int compareTo(Student o) {
//按照對象的年齡進行排序
//主要判斷條件
int result = this.age - o.age;//年齡小的放前面，年齡大的放後面，從小到大排
return result;
}
}
測試類
public class MyTreeSet2 {
public static void main(String[] args) {
//創建集合對象
TreeSet<Student> ts = new TreeSet<>();
//創建學生對象
Student s1 = new Student("zhangsan",28);
Student s2 = new Student("lisi",27);
Student s3 = new Student("wangwu",29);
Student s4 = new Student("zhaoliu",28);
Student s5 = new Student("qianqi",30);
//把學生添加到集合
ts.add(s1);
ts.add(s2);
ts.add(s3);
ts.add(s4);
ts.add(s5);
//遍歷集合
for (Student student : ts) {
System.out.println(student);
}
}
}
3.4 自然排序練習(影片12)【重點】
案例需求
-
存儲學生對象並遍歷，創建TreeSet集合使用無參構造方法
-
要求：按照年齡從小到大排序，如果年齡相同，將按姓名的首字母來進行排序
package com.itheima.mytreeset;
public class Student implements Comparable<Student>{
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
/***
* 比較兩個對象的大小
* @param o 表示集合中的元素
* @return 如果是正值，表示要存入的當前對象大，放右邊
* 如果是負值，表示要存入的當前對象小，入左邊
* 如果返回0, 表示兩個對象相等，不存
*/
@Override
public int compareTo(Student o) {
//按照對象的年齡進行排序
//主要判斷條件
int result = this.age - o.age;
//次要判斷條件
//如果result==0的結果為真，result=this.name.compareTo(o.getName())
//如果result==0的結果為假 result=result;
result = result == 0 ? this.name.compareTo(o.getName()) : result;
//返回result的結果
return result;
}
}
測試類
package com.itheima.mytreeset;
import java.util.TreeSet;
/**
* TreeSet集合來存儲Student類型
*/
public class MyTreeSet2 {
public static void main(String[] args) {
TreeSet<Student> ts = new TreeSet<>();
Student s1 = new Student("zhangsan",28);
Student s2 = new Student("lisi",27);
Student s3 = new Student("wangwu",29);
Student s4 = new Student("zhaoliu",28);
Student s5 = new Student("qianqi",30);
ts.add(s1);
ts.add(s2);
ts.add(s3);
ts.add(s4);
ts.add(s5);
System.out.println(ts);
}
}
3.5比較器排序Comparator的使用【重點】(影片13)
-
案例需求
-
存儲老師對象並遍歷，創建TreeSet集合使用帶參構造方法
-
要求：按照年齡從小到大排序，年齡相同時，按照姓名的字母順序排序
-
-
提示
int compare(T o1,T o2)
比較其兩個參數的順序。 返回負整數，零或正整數，因為第一個參數小於，等於或大於第二個參數
-
實現步驟
-
用TreeSet集合存儲自定義對象，帶參構造方法使用的是比較器排序對元素進行排序的
-
比較器排序，就是讓集合構造方法接收Comparator的實現類對象，重寫compare(T o1,T o2)方法
-
重寫方法時，一定要注意排序規則必須按照要求的主要條件和次要條件來寫
-
-
程式碼實現
老師類
public class Teacher { private String name; private int age; public Teacher() { } public Teacher(String name, int age) { this.name = name; this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public String toString() { return "Teacher{" + "name='" + name + '\'' + ", age=" + age + '}'; } }測試類
package com.itheima.mytreeset; import java.util.Comparator; import java.util.TreeSet; public class MyTreeSet4 { public static void main(String[] args) { TreeSet<Teacher> ts = new TreeSet<>( new Comparator<Teacher>() { /*** * 比較兩個對象的大小 * @param o1 表示要存入的元素 * @param o2 表示已經存入到集合中的元素 * @return 如果是正值，表示要存入的當前對象大，放右邊 * 如果是負值，表示要存入的當前對象小，入左邊 * 如果返回0, 表示兩個對象相等，不存 */ @Override public int compare(Teacher o1, Teacher o2) { //o1表示現在要存入的那個元素 //o2表示已經存入到集合中的元素 //主要條件 int result = o1.getAge() - o2.getAge(); //次要條件 result = result == 0 ? o1.getName().compareTo(o2.getName()) : result; return result; } }); Teacher t1 = new Teacher("zhangsan",23); Teacher t2 = new Teacher("lisi",22); Teacher t3 = new Teacher("wangwu",24); Teacher t4 = new Teacher("zhaoliu",24); ts.add(t1); ts.add(t2); ts.add(t3); ts.add(t4); System.out.println(ts); } }
3.5兩種比較方式總結【了解】（影片14）
1.不同點
1.用到的介面不同
自然排序: 自定義類實現Comparable介面,重寫compareTo方法,根據返回值進行排序
比較器排序: 創建TreeSet對象的時候傳遞Comparator的實現類對象,重寫compare方法,根據返回值進行排序
2.使用場景不同
自然排序能滿足大部分情況
當存儲的元素類型中的比較規則 ，不滿足需要，但是沒法重寫compareTo方法時可以使用(例如:改變包裝類Integer的比較規則，讓其從大到小)比較器排序
2.相同點
返回值的規則:
-
如果返回值為負數，表示當前存入的元素是較小值，存左邊
-
如果返回值為0，表示當前存入的元素跟集合中元素重複了，不存
-
如果返回值為正數，表示當前存入的元素是較大值，存右邊
package com.itheima.mytreeset;
import java.util.Comparator;
import java.util.TreeSet;
public class MyTreeSet5 {
public static void main(String[] args) {
// TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
// @Override
// public int compare(String o1, String o2) {
// int result = o1.length() - o2.length();
// result = result == 0 ? o1.compareTo(o2) : result;
// return result;
// }
// });
TreeSet<String> ts = new TreeSet<>(
(String o1, String o2) -> {
int result = o1.length() - o2.length();
result = result == 0 ? o1.compareTo(o2) : result;
return result;
}
);
ts.add("c");
ts.add("ab");
ts.add("df");
ts.add("qwer");
System.out.println(ts);
}
}
4.數據結構
4.1二叉樹【了解】(影片15)
1.二叉樹中的專業名司(共5個)
1.節點
2.度
3.什麼是二叉樹
4.什麼是二叉樹的樹高
二叉樹的層高就是二叉樹的樹高
5.二叉樹中的其它專業名詞
4.2二叉查找樹【了解】（影片16）
(共三點)
1.什麼是二叉查找樹
2.節點到二叉樹再到二叉查找樹的演進
3.二叉查找樹結構圖
4.3 數據結構-二叉查找樹添加節點（了解）(影片17)
1.添加規則
小的存左邊
大的存右邊
一樣的不存
4.4平衡二叉樹【了解】(影片18)
-
什麼是平衡叉樹
4.5 平衡二叉樹-左旋 （影片19）【了解】
1.平衡二叉樹旋轉觸發的時機
當添加一個節點之後,該樹不再是一顆平衡二叉樹
2.左旋
-
就是將根節點的右側往左拉,原先的右子節點變成新的父節點,並把多餘的左子節點出讓,給已經降級的根節點當右子節點
4.6 平衡二叉樹-右旋 (影片20) 【了解】
-
就是將根節點的左側往右拉,左子節點變成了新的父節點,並把多餘的右子節點出讓,給已經降級根節點當左子節點
4.7 平衡二叉樹-小結(了解) (影片21)
（共3點）
1.二叉查找樹和平衡二叉樹
平衡二叉樹和二叉查找樹對比結構圖
2.左旋
3.右旋
4.8 平衡二叉樹-左左和左右（影片22）【了解】
-
左左
-
左左: 當根節點左子樹的左子樹有節點插入,導致二叉樹不平衡
-
如何旋轉: 直接對整體進行右旋即可
-
-
左右
-
左右: 當根節點左子樹的右子樹有節點插入,導致二叉樹不平衡
-
如何旋轉: 先在左子樹對應的節點位置進行左旋,在對整體進行右旋
-
4.9 平衡二叉樹-右右和右左 (影片23) 【了解】
-
右右
-
右右: 當根節點右子樹的右子樹有節點插入,導致二叉樹不平衡
-
如何旋轉: 直接對整體進行左旋即可
-
-
右左
-
右左:當根節點右子樹的左子樹有節點插入,導致二叉樹不平衡
-
如何旋轉: 先在右子樹對應的節點位置進行右旋,在對整體進行左旋
-
4.10 小結(影片24) 【了解】
==擴展練習==
編程題【Set介面】
題目1
已知數組資訊如下:
{2.2,5.5,6.6,2.2,8.8,1.1,2.2,8.8,5.5,2.2,6.6}
請使用程式碼找出上面數組中的所有的數據,要求重複的數據只能保留一份;
要求:
使用HashSet集合實現;
效果:
參考答案:
public static void main(String[] args) {
double[] arr = {2.2,5.5,6.6,2.2,8.8,1.1,2.2,8.8,5.5,2.2,6.6};
HashSet<Double> set = new HashSet<>();
for (double v : arr) {
set.add(v);
}
System.out.println("去除重複的元素後,結果是:"+set);
}
題目2
隨機生成8個不重複的10至20之間的隨機數並保存Set集合中,然後列印出集合中所有的數據;
要求:
使用TreeSet集合實現;
效果:
(由於是隨機的,所以每次運行結果都不一樣是正常的!!!)
參考答案:
public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet<>();
Random r = new Random();
int count =1;
while (set.size()<8){
int i = r.nextInt(20 - 10 + 1) + 10;
System.out.println("第"+count++ +"次生成的隨機數是:"+i);
set.add(i);
}
System.out.println("集合中保存的8個不重複的隨機數是:"+set);
}
題目3
鍵盤輸入3本書按照價格從低到高排序後輸出,如果價格相同則按照書名的自然順序排序;
要求:
1:書以對象形式存在,包含書名和價格(int類型)兩個屬性;
2:要求即使直接列印書對象的時候,也能看到書的名稱和價格,而不是書對象的地址值;
3:分別使用自然排序和比較器排序實現效果;
效果:
參考答案:
package day8.No_3.test2;
import java.text.Collator;
import java.util.Comparator;
import java.util.Locale;
import java.util.Scanner;
import java.util.TreeSet;
public class Demo {
public static void main(String[] args) {
TreeSet<Book> ts = new TreeSet<>(new Comparator<Book>() {
@Override
public int compare(Book o1, Book o2) {
int i = o1.getPrice() - o2.getPrice();
Collator instance = Collator.getInstance(Locale.CHINESE);
i=i==0?instance.compare(o1.getName(),o2.getName()):i;
return i;
}
});
Scanner sc = new Scanner(System.in);
int count = 1;
L:while (true) {
sc = new Scanner(System.in);
System.out.println("請輸入第" + count + "本書名:");
String name = sc.next();
int jiage;
while (true){
sc = new Scanner(System.in);
System.out.println("請輸入價格:");
try {
jiage = sc.nextInt();
break;
} catch (Exception e) {
System.out.println("必須為整數!");
continue;
}
}
Book book = new Book(name, jiage);
ts.add(book);
System.out.println("第" + count + "本書添加成功,輸入1繼續,其他退出");
count++;
int i = 0;
try {
i = sc.nextInt();
} catch (Exception e) {
}
if (i != 1) {
break L;
}
}
System.out.println("你一共添加" + ts.size() + "本書:");
for (Book t : ts) {
System.out.println(t);
}
}
}
類文件:
package day8.No_3.test2;
import java.text.Collator;
import java.util.Locale;
public class Book {
private String name;
private int price;
public Book() {
}
public Book(String name, int price) {
this.name = name;
this.price = price;
}
@Override
public String toString() {
return "Book{" +
"name='" + name + '\'' +
", price=" + price +
'}';
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getPrice() {
return price;
}
public void setPrice(int price) {
this.price = price;
}
}
