#实验报告 Java 使用集合来组织和管理对象，本节我们重点讲解泛型和集合。主要介绍 Collection、List、ArrayList、Map、HashMap、Set 和 HashSet、Collections、算法等内容。 ##知识点 -泛型 -Collection -List -ArrayList -Map -HashMap -Set 和 HashSet -Collections -算法 1、泛类泛型即参数化类型，也就是说数据类型变成了一个可变的参数，在不使用泛型的情况下，参数的数据类型都是写死了的，使用泛型之后，可以根据程序的需要进行改变。定义泛型的规则：只能是引用类型，不能是简单数据类型。泛型参数可以有多个。可以用使用 extends 语句或者 super 语句如表示类型的上界，T 只能是 superClass 或其子类，表示类型的下界，K 只能是 childClass 或其父类。可以是通配符类型，比如常见的 Class。单独使用 ? 可以表示任意类型。也可以结合 extends 和 super 来进行限制。 ``` /* 使用T代表类型，无论何时都没有比这更具体的类型来区分它。如果有多个类型参数，我们可能使用字母表中T的临近的字母，比如S。 */ class Test { private T ob; /* 定义泛型成员变量，定义完类型参数后，可以在定义位置之后的方法的任意地方使用类型参数，就像使用普通的类型一样。注意，父类定义的类型参数不能被子类继承。 */ //构造函数 public Test(T ob) { this.ob = ob; } //getter 方法 public T getOb() { return ob; } //setter 方法 public void setOb(T ob) { this.ob = ob; } public void showType() { System.out.println("T的实际类型是: " + ob.getClass().getName()); } } public class TestDemo { public static void main(String[] args) { // 定义泛型类 Test 的一个Integer版本 Test intOb = new Test(88); intOb.showType(); int i = intOb.getOb(); System.out.println("value= " + i); System.out.println("----------------------------------"); // 定义泛型类Test的一个String版本 Test strOb = new Test("Hello Gen!"); strOb.showType(); String s = strOb.getOb(); System.out.println("value= " + s); } } ``` ![image.png](https://dn-simplecloud.shiyanlou.com/courses/uid1402862-20200611-1591835942321) 2、Collection 集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大内容：对外的接口、接口的实现和对集合运算的算法。 ![image.png](https://dn-simplecloud.shiyanlou.com/courses/uid1402862-20200611-1591836096151) Collection 接口是 Java 集合框架里的一个根接口。它也是 List、Set 和 Queue 接口的父接口。Collection 接口中定义了可用于操作 List、Set 和 Queue 的方法——增删改查。 3、List List 是一个接口，不能实例化，需要一个具体类来实现实例化。 List 集合中的对象按照一定的顺序排放，里面的内容可以重复。 List 接口实现的类有：ArrayList（实现动态数组），Vector（实现动态数组），LinkedList（实现链表），Stack（实现堆栈）。 4、ArrayList ArrayList 　类实现一个可增长的动态数组，位于 java.util.ArrayList。实现了 List 接口，它可以存储不同类型的对象（包括 null 在内），而数组则只能存放特定数据类型的值。实例：学校的教务系统会对学生进行统一的管理，每一个学生都会有一个学号和学生姓名，我们在维护整个系统的时候，大多数操作是对学生的添加、插入、删除、修改等操作。 ``` public class Student{ public String id; public String name; public Student(String id,String name){ this.id=id; this.name=name; } public String toSring(){ return "Student{"+ "id='"+id+'\''+ ",name='"+name+'\''+ '}'; } } ``` ``` import java.util.*; public class ListTest { //集合后面的<>代表泛型的意思 //泛型是规定了集合元素的类型 /** * 用于存放学生的List */ public List students; public ListTest() { this.students = new ArrayList(); } /** * 用于往students中添加学生 */ public void testAdd() { // 创建一个学生对象，并通过调用add方法，添加到学生管理List中 Student st1 = new Student("1", "张三"); students.add(st1); // 取出 List中的Student对象索引为0 也就是第一个 Student temp = students.get(0); System.out.println("添加了学生：" + temp.id + ":" + temp.name); Student st2 = new Student("2", "李四"); //添加到list中，插入到索引为0的位置，也就是第一个 students.add(0, st2); Student temp2 = students.get(0); System.out.println("添加了学生：" + temp2.id + ":" + temp2.name); // 对象数组的形式添加 Student[] student = {new Student("3", "王五"), new Student("4", "马六")}; // Arrays类包含用来操作数组（比如排序和搜索）的各种方法，asList() 方法用来返回一个受指定数组支持的固定大小的列表 students.addAll(Arrays.asList(student)); Student temp3 = students.get(2); Student temp4 = students.get(3); System.out.println("添加了学生：" + temp3.id + ":" + temp3.name); System.out.println("添加了学生：" + temp4.id + ":" + temp4.name); Student[] student2 = {new Student("5", "周七"), new Student("6", "赵八")}; students.addAll(2, Arrays.asList(student2)); Student temp5 = students.get(2); Student temp6 = students.get(3); System.out.println("添加了学生：" + temp5.id + ":" + temp5.name); System.out.println("添加了学生：" + temp6.id + ":" + temp6.name); } /** * 取得List中的元素的方法 */ public void testGet() { int size = students.size(); for (int i = 0; i < size; i++) { Student st = students.get(i); System.out.println("学生：" + st.id + ":" + st.name); } } /** * 通过迭代器来遍历 * 迭代器的工作是遍历并选择序列中的对象，Java 中 Iterator 只能单向移动 */ public void testIterator() { // 通过集合的iterator方法，取得迭代器实例 Iterator it = students.iterator(); System.out.println("有如下学生（通过迭代器访问）："); while (it.hasNext()) { Student st = it.next(); System.out.println("学生" + st.id + ":" + st.name); } } /** * 通过for each 方法访问集合元素 * */ public void testForEach() { System.out.println("有如下学生（通过for each）："); for (Student obj : students) { Student st = obj; System.out.println("学生：" + st.id + ":" + st.name); } //使用java8 Steam将学生排序后输出 students.stream()//创建Stream //通过学生id排序 .sorted(Comparator.comparing(x -> x.id)) //输出 .forEach(System.out::println); } /** * 修改List中的元素 * */ public void testModify() { students.set(4, new Student("3", "吴酒")); } /** * 删除List中的元素 * */ public void testRemove() { Student st = students.get(4); System.out.println("我是学生：" + st.id + ":" + st.name + "，我即将被删除"); students.remove(st); System.out.println("成功删除学生！"); testForEach(); } public static void main(String[] args) { ListTest lt = new ListTest(); lt.testAdd(); lt.testGet(); lt.testIterator(); lt.testModify(); lt.testForEach(); lt.testRemove(); } } ``` ``` $ javac Student.java ListTest.java $ java ListTest 添加了学生：1:张三添加了学生：2:李四添加了学生：3:王五添加了学生：4:马六添加了学生：5:周七添加了学生：6:赵八学生：2:李四学生：1:张三学生：5:周七学生：6:赵八学生：3:王五学生：4:马六有如下学生（通过迭代器访问）：学生2:李四学生1:张三学生5:周七学生6:赵八学生3:王五学生4:马六有如下学生（通过for each）：学生：2:李四学生：1:张三学生：5:周七学生：6:赵八学生：3:吴酒学生：4:马六 Student{id='1', name='张三'} Student{id='2', name='李四'} Student{id='3', name='吴酒'} Student{id='4', name='马六'} Student{id='5', name='周七'} Student{id='6', name='赵八'} 我是学生：3:吴酒，我即将被删除成功删除学生！有如下学生（通过for each）：学生：2:李四学生：1:张三学生：5:周七学生：6:赵八学生：4:马六 Student{id='1', name='张三'} Student{id='2', name='李四'} Student{id='4', name='马六'} Student{id='5', name='周七'} Student{id='6', name='赵八'} ``` 在上面的代码中，用到了 Arrays 类， Arrays 包含用来操作数组（比如排序和搜索）的各种方法，asList() 方法用来返回一个受指定数组支持的固定大小的列表。 5、Map Map 接口也是一个非常重要的集合接口，用于存储键 / 值对。Map 中的元素都是成对出现的，键值对就像数组的索引与数组的内容的关系一样，将一个键映射到一个值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。我们可以通过键去找到相应的值。 ![image.png](https://dn-simplecloud.shiyanlou.com/courses/uid1402862-20200611-1591837585455) value 可以存储任意类型的对象，我们可以根据 key 键快速查找 value。Map 中的键 / 值对以 Entry 类型的对象实例形式存在。 6、 HashMap HashMap 是基于哈希表的 Map 接口的一个重要实现类。HashMap 中的 Entry 对象是无序排列的，Key 值和 value 值都可以为 null，但是一个 HashMap 只能有一个 key 值为 null 的映射（key 值不可重复）。 7、Set 和 HashSet Set 接口也是 Collection 接口的子接口，它有一个很重要也是很常用的实现类——HashSet，Set 是元素无序并且不包含重复元素的 collection（List 可以重复），被称为集。 HashSet 由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。实例：假设现在学生们要做项目，每个项目有一个组长，由组长来组织组员，实现项目组的管理。 ``` import java.util.HashSet; import java.util.Set; /* * 项目组长类 */ public class PD { public String id; public String name; //集合后面的<>代表泛型的意思 //泛型是规定了集合元素的类型 public Set students; public PD(String id, String name){ this.id = id; this.name = name; this.students = new HashSet(); } } ``` ``` /** * 学生类 */ // Student.java public class Student { public String id; public String name; public Student(String id, String name){ this.id = id; this.name = name; } @Override public String toString() { return "Student{" + "id='" + id + '\'' + ", name='" + name + '\'' + '}'; } } ``` ```// SetTest.java import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; public class SetTest { public List students; public SetTest() { students = new ArrayList(); } /* * 用于往students中添加学生 */ public void testAdd() { //创建一个学生对象，并通过调用add方法，添加到学生管理List中 Student st1 = new Student("1", "张三"); students.add(st1); //添加到List中的类型均为Object，所以取出时还需要强转 Student st2 = new Student("2","李四"); students.add(st2); Student[] student = {new Student("3", "王五"),new Student("4", "马六")}; students.addAll(Arrays.asList(student)); Student[] student2 = {new Student("5", "周七"),new Student("6", "赵八")}; students.addAll(Arrays.asList(student2)); } /** * 通过for each 方法访问集合元素 * @param args */ public void testForEach() { System.out.println("有如下学生（通过for each）："); for(Object obj:students){ Student st = (Student)obj; System.out.println("学生：" + st.id + ":" + st.name); } } public static void main(String[] args){ SetTest st = new SetTest(); st.testAdd(); st.testForEach(); PD pd = new PD("1","张老师"); System.out.println("请：" + pd.name + "选择小组成员！"); //创建一个 Scanner 对象，用来接收从键盘输入的学生 ID Scanner console = new Scanner(System.in); for(int i = 0;i < 3; i++){ System.out.println("请输入学生 ID"); String studentID = console.next(); for(Student s:st.students){ if(s.id.equals(studentID)){ pd.students.add(s); } } } st.testForEachForSer(pd); // 关闭 Scanner 对象 console.close(); } //打印输出，老师所选的学生！Set里遍历元素只能用foreach 和 iterator //不能使用 get() 方法，因为它是无序的，不能想 List 一样查询具体索引的元素 public void testForEachForSer(PD pd){ for(Student s: pd.students) { System.out.println("选择了学生：" + s.id + ":" + s.name); } } } ``` ```$ javac PD.java SetTest.java Student.java $ java SetTest 有如下学生（通过for each）：学生：1:张三学生：2:李四学生：3:王五学生：4:马六学生：5:周七学生：6:赵八请：张老师选择小组成员！请输入学生 ID 4 请输入学生 ID 5 请输入学生 ID 6 选择了学生：4:马六选择了学生：5:周七选择了学生：6:赵八 ``` 8、Collections java.util.Collections 是一个工具类，他包含了大量对集合进行操作的静态方法。 ``` 方法名描述 void sort(List list) 按自然升序排序 void sort(List list, Comparator c) 自定义排序规则排序 void shuffle(List list) 随机排序，用于打乱顺序 void reverse(List list) 反转，将列表元素顺序反转 void swap(List list, int i , int j) 交换处于索引 i 和 j 位置的元素 int binarySearch(List list, Object key) 二分查找，列表必须有序，返回找到的元素索引位置 int max(Collection coll) 查找最大值 int min(Collection coll) 查找最小值 void fill(List list, Object obj) 使用 obj 填充 list 所有元素 boolean replaceAll(List list, Object oldVal, Object newVal) 使用用 newVal 替换所有的 oldVal。 Map synchronizedMap(Map m) 将 m 包装为线程安全的 Map List synchronizedList(List list) 将 list 包装为线程安全的 List ``` 9、算法算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，则执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量 -插入排序：从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤 2 ~ 5，直至最后一个元素。 ``` import java.util.Arrays; public class InsertSort { private static void insertSort(int[] arr) { int j; // 已排序列表下标 int t; // 待排序元素 for (int i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) { t = arr[i]; // 赋值给待排序元素 for (j = i - 1; j >= 0 && arr[j] > t; j--) { arr[j + 1] = arr[j]; // 从后往前遍历已排序列表，逐个和待排序元素比较，如果已排序元素较大，则将它后移 } arr[j + 1] = t; // 将待排序元素插入到正确的位置 } } } public static void main(String[] args) { int[] ints = {5, 3, 4, 1, 2}; insertSort(ints); System.out.println(Arrays.toString(ints)); } } ``` 冒泡排序的运行过程如下：比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 ``` import java.util.Arrays; public class BubbleSort { public static void sort(int[] arr) { for (int i = 0; i < arr.length-1; i++) { for (int j = 0; j < arr.length - i - 1; j++) { //如果当前元素比后一位元素大交换位置 if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } public static void main(String[] args) { int[] ints = {5, 3, 4, 1, 2}; sort(ints); System.out.println(Arrays.toString(ints)); } } ``` 归并排序过程： ![image.png](https://dn-simplecloud.shiyanlou.com/courses/uid1402862-20200611-1591839452095) ``` import java.util.Arrays; public class MergeSort { public static void mergeSort(int[] arrays, int left, int right) { // 如果数组还可以拆分 if (left < right) { //数组的中间位置 int middle = (left + right) / 2; //拆分左边数组 mergeSort(arrays, left, middle); //拆分右边数组 mergeSort(arrays, middle + 1, right); //合并 merge(arrays, left, middle, right); } } /** * 合并数组 */ public static void merge(int[] arr, int left, int middle, int right) { //申请合并空间大小为两个已经排序序列之和 int[] temp = new int[right - left + 1]; //i 和 j为两个已经排好序的数组的起始位置 int i = left; int j = middle + 1; int k = 0; //排序 while (i <= middle && j <= right) { //将比较小的数组放入合并空间 if (arr[i] < arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } //将左边剩余元素写入合并空间 while (i <= middle) { temp[k++] = arr[i++]; } //将右边剩余的元素写入合并空间 while (j <= right) { temp[k++] = arr[j++]; } //将排序后的数组写回原来的数组 for (int l = 0; l < temp.length; l++) { arr[l + left] = temp[l]; } } public static void main(String[] args) { int[] ints = {5, 3, 4, 1, 2}; mergeSort(ints,0,ints.length-1); System.out.println(Arrays.toString(ints)); } } ``` -快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。从数列中挑出一个元素，称为“基准”（pivot），重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。 ``` import java.util.Arrays; public class QuickSort { public static void sort(int[] arr, int head, int tail) { if (head >= tail || arr == null || arr.length <= 1) { return; } //设置数组的起始位置 i 结束位置j 基准 pivot 为数组的中间 int i = head, j = tail, pivot = arr[(head + tail) / 2]; while (i <= j) { //当数组小于基准循环结束后相当于i所处的位置的值为大于基准的元素 while (arr[i] < pivot) { ++i; } //当数组大于基准循环结束后相当于j所处的位置的值为小于于基准的元素 while (arr[j] > pivot) { --j; } //如果i

“Java 语言程序设计实验”实验报告