文章目录
- 泛型
- 什么是泛型?
- 常见的泛型标识符
- 泛型类
- 泛型方法
- 泛型接口
- 通配符
- 树
- 树的基本概念
- 什么是二叉树?
- 二叉树--普通二叉树
- 二叉树--二叉查找树
- 定义规则
- 优缺点
- 二叉树--平衡二叉树
- 定义规则
- 旋转机制
- 二叉树--红黑树
- 定义规则
- 红黑规则
- 常见数据结构
- 总体特点
- 结构图
泛型
什么是泛型?
含义的理解还不够深入
泛型:指广泛的数据类型
本质:是参数化类型,即操作的数据类型被指定为一个参数。
用途:泛型可以用在类、接口、方法中,分别称为:泛型类、泛型接口、泛型方法。
版本信息:于JDK5版本引入
常见的泛型标识符
E | T | K | V | N | ? |
---|---|---|---|---|---|
Element | Type | Key | Value | Number | 通配符 |
集合元素 | 表示任意Java类的类型 | 键类型 | 值类型 | 数值类型 | 表示任意类型 |
- 通配符
?
:可以理解为所有类的父类
泛型类
示例
package com.itheima.day10.generics;import java.util.ArrayList;public class GenericsDemo2 {public static void main(String[] args) {Student<Integer> stu = new Student<>(); // 正确Student<int> stu = new Student<>(); // 错误,泛型类只能是引用数据类型}
}class Student<E> {private E e;public E getE() {return e;}public void setE(E e) {this.e = e;}
}
特点
- 泛型类只能写引用数据类型!!
- 泛型类,只有创建对象的时候,才能确定泛型具体的类型
泛型方法
非静态的泛型方法
特点:根据类的泛型去匹配:类的泛型传入什么类型,方法就传入什么类型
泛型类型确定的时机:类创建实例对象的时候
举例:上述的get()
、set()
方法
静态的泛型方法
特点:必须声明出自己独立的泛型
- 因为:静态方法随着类的加载而加载,此时类还没创建,就没有具体类型,静态方法就会有问题,所以要声明自己独立的泛型
泛型类型确定的时机:该方法被调用的时候
举例:
package com.itheima.day10.generics;public class GenericsDemo3 {public static void main(String[] args) {String[] arr1 = {"张三", "李四", "王五"};Integer[] arr2 = {11, 22, 33};Double[] arr3 = {11.1, 22.2, 33.3};printArray(arr1);printArray(arr2);printArray(arr3);}public static <T> void printArray(T[] arr) {System.out.print("[");for (int i = 0; i < arr.length - 1; i++) {System.out.print(arr[i] + ", ");}System.out.println(arr[arr.length - 1] + "]");}
}
泛型接口
特点:类实现接口的时候,可以有两种选择:确定泛型类型;保留泛型类型
interface Inter<E> {void show(E e);
}
示例1:类实现接口的时候,直接确定类型(就变成普通类了)
class InterAImpl implements Inter<String> {@Overridepublic void show(String s) {}
}
示例2:延续接口的泛型,等创建对象的时候确定(变成泛型类)
class InterBImpl<E> implements Inter<E>{@Overridepublic void show(E e) {}
}
通配符
这部分的概念也有点难理解
通配符的类别
? | ? extends xxx | ? super xxx |
---|---|---|
无边际通配符 | 固定上边界统配符 | 固定下边界统配符 |
<?> | <? extends E> | <? super E> |
泛型可以接受未知类型的数据(任意类型) | 限制泛型可以接受的类型为:xxx及xxx的子类、实现接口xxx的类 | 限制泛型 可以接受的类型为:xxx及xxx的父类 |
示例
// 父类
@Data
abstract class Employee {private String name;private double salary;public abstract void work();
}
// 继承的子类
class Coder extends Employee {@Overridepublic void work() {System.out.println("程序员写代码...");}
}class Manager extends Employee {@Overridepublic void work() {System.out.println("项目经理分配任务...");}
}
// 调用
public class GenericsDemo5 {public static void main(String[] args) {ArrayList<Coder> list1 = new ArrayList<>();list1.add(new Coder());ArrayList<Manager> list2 = new ArrayList<>();list2.add(new Manager());method(list1); // 固定上界统配符method(list2); // 固定下界统配符}public static void method(ArrayList<? extends Employee> list){for (Employee o : list) {o.work();}}public static void method1(ArrayList<? super Employee> list){for (Object A : list) {Employee o = (Employee)A;o.work();}}
}
树
树的基本概念
概念 | 理解 |
---|---|
节点(结点、Node) | 上边的每一个圈圈都是一个节点【节点内部存储有:父节点地址、节点数据值、左子节点地址、右子节点地址】 |
度 | 每一个节点的子节点数量【在二叉数中,任意节点的度<=2】 |
树高 | 整棵树的层数【上边数的树高=4】 |
根节点 | 最顶层的节点【节点值为22的这个节点,其左子节点为18,右子节点为26,没有父节点】 |
左子节点 | 【22的左子节点是18】 |
右子节点 | 【22的右子节点是26】 |
根节点的左子树 | 【18节点及其所有子节点】 |
根节点的右子树 | 【26节点及其所有子节点】 |
什么是二叉树?
二叉树是每个节点最多有两个子树的树结构。
下边相关二叉树,先学习基本特点和优缺点,后续做题的时候,再学习相关原理、方法,写出代码
二叉树–普通二叉树
仅满足二叉树的规则,没有多余的特点
二叉树–二叉查找树
二叉排序树,又称二叉查找树,亦称二叉搜索树
定义规则
- 若左子树不为空,则左子树上所有节点的值均小于或等于它的根节点的值
- 若右子树不为空,则右子树上所有节点的值均大于或等于它的根节点的值
- 任意节点的左右子树,也都是二叉查找树
优缺点
-
优点:常规情况下,元素查找速度快,每一次查找,筛选掉剩余元素的一半
-
不足:特殊二叉查找树(所有节点仅有右节点或仅有左节点),每次查找只能过滤掉一个元素,查找速度变得跟数组一样
二叉树–平衡二叉树
定义规则
1、平衡二叉树由若干个节点组成
2、如果一颗二叉树不为空,那么至少拥有一个根节点,且根节点没有父节点
3、每个子节点都符合如下规范:
-
节点的数值限制:没有键值相等的节点
-
节点的子节点数量限制:每个节点可以拥有最多两个子节点
-
节点的左子树数值限制:若任意节点的左子树不空,则左子树上所有的节点值均小于该节点的值
-
节点的右子树数值限制:若任意节点的右子树不空,则右子树上所有节点的值均大于该节点的值
-
节点的左、右子树高度限制:节点左树和右树的高度差的绝对值小于等于1
旋转机制
挺巧妙地,用到了再说
二叉树–红黑树
定义规则
用到再说
红黑规则
用到再说
常见数据结构
总体特点
数据结构 | 结构 | 操作 | 特点 | 补充 |
---|---|---|---|---|
栈 | 一端开口(栈顶) 一端封闭(栈底) | 从栈顶到栈底:进栈/压栈 从栈底到栈顶:出栈/弹栈 | 后进先出,先进后出 | |
队列 | 一端开口(后端) 一端开口(前端) | 入队列(后端)、出队列(前端) | 先进先出,后进后出 | |
数组 | 起始地址值、索引 | 根据地址值和索引定位数据 | 查询速度快(且一致):索引+地址值定位; 增、删效率低:增删过程大概率伴随大量数据移动 | |
链表 | 基本组成:节点 本身地址、数据、下一个节点的地址 | 查询慢:查询任何数据都要从头开始查 增删相对快:查到对应元素,更改节点存储内容即可,不需要多余的移动 | 存储内存不连续 | |
双向链表 | 基本组成:节点 前一个节点地址、数据、下一个节点的地址 | 同【链表】 | 存储内存不连续 | |
树 | 见【补充知识-树】 |
结构图
栈
队列
链表(单向链表和双向链表)
节点结构
单项链表和双向链表