[数据结构与算法] Day16

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Day16 -> 正文阅读

[数据结构与算法]Day16

一、集合接口

集合是Java API所提供的一系列类，可以用于动态存放多个对象 (集合只能存对象)

集合与数组的不同在于，集合是大小可变的序列，而且元素类型可以不受限定，只要是引用类型。(集合中不能放基本数据类型，但可以放基本数据类型的包装类)

集合类全部支持泛型，是一种数据安全的用法。

Collection接口规范了list和set子类的方法规范，即集合的基本使用方法，与Map接口不同的是Collection的子类实现类是存储的单个值，可以获取迭代器进行遍历；Map存储的是Key - value键值对，不可以获取迭代器，不能遍历（Map可以间接遍历）。

List接口的子类主要是有下标的集合实现类，数据存储是有序的；Set的实现类没有下标，是无序的（无序：存入顺序和取出顺序不一致，无序不等于随机），但是 LinkedHashSet 是有序的，因为底层是相似链表结构。

总结：List接口有序且可重复（因为List接口中添加了许多针对下标操作的方法），实现类：ArrayList，LinkedList，Vector；Set接口特点：无序且不可重复，实现类：HashSet，LinkedHashSet，TreeSet，Stack。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sSZ4Od81-1628512183007)(C:\Users\DELL\AppData\Roaming\Typora\typora-user-images\image-20210809190537428.png)]

二、ArrayList类

1、了解ArrayList

		ArrayList list = new ArrayList();
		
		//添加元素
		list.add("字符串");
		list.add(100);//Integer.valueOf(100);
		list.add(123.123);//Double.valueOf(123.123);

使用 ArrayList 方法 + 泛型
泛型：数据安全的作法，规定集合应该存储什么样的数据类型

		ArrayList<String> list = new ArrayList<>();
		
		//添加元素
		list.add("麻生希");
		list.add("椎名空");
		list.add("爱田奈奈");
		list.add("三上悠亚");
		list.add("明日花绮罗");
		
		//获取元素的个数
		int size = list.size();
		System.out.println("获取元素的个数：" + size);//5
		
		//设置指定下标上的元素
		list.set(0, "林成");
		
		//获取指定下标上的元素
		String elment = list.get(0);
		System.out.println("获取指定下标上的元素：" + elment);//林成
		
		//在指定下标上插入元素
		list.add(1, "卢永刚");
		
		ArrayList<String> newList1 = new ArrayList<>();
		Collections.addAll(newList1, "aaa","bbb","ccc","明日花绮罗");//利用集合工具类进行批量添加
		list.addAll(newList1);//将新集合中所有的元素添加到指定集合的末尾
		
		ArrayList<String> newList2 = new ArrayList<>();
		Collections.addAll(newList2, "ddd","eee","fff");//利用集合工具类进行批量添加
		list.addAll(3, newList2);//将新集合中所有的元素添加到指定集合上指定下标的位置
		
		//清空集合中所有的元素
		//list.clear();
		
		System.out.println("判断集合中是否包含某个元素：" + list.contains("椎名空"));//true
		
		ArrayList<String> newList3 = new ArrayList<>();
		Collections.addAll(newList3, "eee","ddd","fff","ggg");//利用集合工具类进行批量添加
		System.out.println("判断集合中是否包含某个集合中所有元素：" + list.containsAll(newList3));//false
		
		int index = list.indexOf("椎名空");
		System.out.println("获取元素在集合中的下标：" + index);
		
		boolean empty = list.isEmpty();//有元素-false 没有元素-true
		System.out.println("判断集合中是否没有元素：" + empty);//false
		
		//删除
		list.remove(3);//依据下标删除元素
		list.remove("eee");//依据元素删除元素
		
		//删除 - 去交集
		ArrayList<String> newList4 = new ArrayList<>();
		Collections.addAll(newList4, "fff","aaa","bbb","xxx");//利用集合工具类进行批量添加
		list.removeAll(newList4);
		
		//保留交集	
		ArrayList<String> newList5 = new ArrayList<>();
		Collections.addAll(newList5, "林成","卢永刚","椎名空","爱田奈奈","三上悠亚","yyy");//利用集合工具类进行批量添加
		list.retainAll(newList5);
		
		//替换指定下标上的元素
		list.set(2, "深田咏美");
		
		//获取开始下标(包含)到结束下标(不包含)的元素，返回新的集合	
		List<String> subList = list.subList(1, 3);
		
		//将集合转换为数组
		Object[] array = subList.toArray();
		System.out.println(Arrays.toString(array));
		
		System.out.println("-------------");
		
		//遍历 - for
		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
		
		System.out.println("-------------");
		
		//遍历 - foreach
		for (String element : list) {
			System.out.println(element);
		}
		
		System.out.println("-------------");
		
		//遍历 - Iterator迭代器
		Iterator<String> it = list.iterator();//获取Iterator迭代器对象
		while(it.hasNext()){//判断是否有可迭代的元素
			String e = it.next();//返回下一个元素
			System.out.println(e);
		}
		
		System.out.println("-------------");
		
		//遍历 - ListIterator迭代器
		ListIterator<String> listIterator = list.listIterator();//获取ListIterator迭代器对象
		while(listIterator.hasNext()){//判断是否有可迭代的元素
			String e = listIterator.next();//返回下一个元素
			System.out.println(e);
		}

2、泛型在集合中的使用

含义：数据安全的作用

public class A {

}

public class B extends A {

}

public class MyArrayList<E> {

	public boolean add(E e){
		return true;
	}
}

泛型限定：

?表示什么类型都可以

? extends A 表示元素必须是A类或A的子类

? super A 表示元素必须是A类或A的父类

		MyArrayList<String> list1 = new MyArrayList<>();
		list1.add("abc");
		
		MyArrayList<Integer> list2 = new MyArrayList<>();
		list2.add(123);

		//?：任何类型
        public ArrayList<?> method01(){
            ArrayList<String> list = new ArrayList<>();
            return list;
        }

        //? extends A
        //?：表示A的子类或者A类
        public ArrayList<? extends A> method02(){
		//	ArrayList<B> list = new ArrayList<>();
            ArrayList<A> list = new ArrayList<>();
            return list;
        }

        //? super A
        //?：表示A的父类或A类
        public ArrayList<? super A> method03(){
    	//	ArrayList<Object> list = new ArrayList<>();
            ArrayList<A> list = new ArrayList<>();
            return list;
        }

三、LinkedList 类

LinkedList 的用法基本上与 ArrayList 相同，但是多了俩个用法

1、LinkedList 队列模式

特点：先进先出

		LinkedList<String> list = new LinkedList<>();
		
		list.add("1");
		list.add("2");
		list.add("3");
		list.add("4");
		list.add("5");
		
		while(!list.isEmpty()){
			
			//删除第一个元素，并返回
			String element = list.removeFirst();
			System.out.println(element);
		}//1  2  3  4  5
		
		System.out.println("集合中元素的个数：" + list.size());//0

2、LinkedList 栈模式

特点：先进后出

		LinkedList<String> list = new LinkedList<>();
		
		list.add("林成1");
		list.add("林成2");
		list.add("林成3");
		list.add("林成4");
		list.add("林成5");
		
		while(!list.isEmpty()){
			
			//删除最后一个元素，并返回
			String element = list.removeLast();
			System.out.println(element);
		}//5  4  3  2  1
		
		System.out.println("集合中元素的个数：" + list.size());//0

四、迭代器

含义：遍历集合中的数据

foreach底层原理 : foreach底层由迭代器实现

		for (String e : list) {
			System.out.println(e);
		}
		
		//底层实现：
//		String e;
//		for(Iterator<String> it = list.iterator();it.hasNext();System.out.println(e)){
//			e = it.next();
//		}

分类：Iterator 和 ListIterator

Iterator 和 ListIterator 区别：

Iterator ：Collection接口下所有的实现类都可以获取的迭代器，可以在遍历时删除元素

		/**
		 *       向ArrayList中添加元素("林成1","林成2","林成3","林成4")，
		 * 	     使用Iterator迭代器遍历，遍历到林成2时，删除该元素
		 */
		
		ArrayList<String> list = new ArrayList<>();
		
		list.add("林成1");
		list.add("林成2");
		list.add("林成3");
		list.add("林成4");
		
		Iterator<String> it = list.iterator();
		while (it.hasNext()) {
			String element = it.next();
			if(element.equals("林成2")){
				//list.remove(element);
				it.remove();
			}
		}
		
		for (String element : list) {
			System.out.println(element);
		}//会抛出异常

Iterator底层实现有一个操作数记录，如果在遍历时，对集合的操作都会使得操作数增加 1 ，调用it.hasNext()会检查操作数是否变化，如果变化则会抛出异常。

ListIterator ：List接口下所有的实现类可以获取的迭代器，可以在遍历时删除、替换、添加元素，也可以指定下标开始遍历，还可以倒叙遍历

		/**
		 *     需求：向ArrayList中添加元素("林成1","林成2","林成3","林成4")，
		 * 	   
		 */
		
		ArrayList<String> list = new ArrayList<>();
		
		list.add("林成1");
		list.add("林成2");
		list.add("林成3");
		list.add("林成4");
		
		ListIterator<String> listIterator = list.listIterator();
		/**
		 * 	   使用ListIterator迭代器遍历，遍历到林成2时，替换该元素
		 */
		while(listIterator.hasNext()){
			String element = listIterator.next();
			if(element.equals("林成2")){
				listIterator.set("卢永刚");
			}
		}
		
		/**
		 * 	        使用ListIterator迭代器遍历，遍历到林成2时，添加元素
		 */
		while(listIterator.hasNext()){
			String element = listIterator.next();
			if(element.equals("林成2")){
				listIterator.add("卢永刚");
			}
		}

		
		for (String element : list) {
			System.out.println(element);
		}

		/**
		 * 	   从林成2开始遍历（指定下标开始遍历）
		 */
		ListIterator<String> listIterator = list.listIterator(1);
		while(listIterator.hasNext()){
			String element = listIterator.next();
			System.out.println(element);
		}

		/**
		 * 	   	倒叙输出
		 */		
		ListIterator<String> listIterator = list.listIterator(list.size());
		while(listIterator.hasPrevious()){//判断前面是否有可迭代的元素
			String element = listIterator.previous();//返回上一个元素
			System.out.println(element);
		}

用 ListIterator 自带的方法修改数据不会抛出异常

五、Vector 和 Stack类

了解：Vector是元老级别的集合类，在JDK1.0开始。JDK1.2开始才推出集合框架的概念，考虑到当时很多

程序员习惯使用Vector，就让Vector多实现了List接口，这样才将其保留下来。

public class Test01 {

	public static void main(String[] args) {
		/**
		 * 知识点：使用Vector实现List接口的方法
		 * 
		 */		
		Vector<String> list = new Vector<>();
		
		//添加元素
		list.add("麻生希");
		list.add("椎名空");
		list.add("爱田奈奈");
		list.add("三上悠亚");
		list.add("明日花绮罗");
		
		//获取元素的个数
		int size = list.size();
		System.out.println("获取元素的个数：" + size);//5
		
		//设置指定下标上的元素
		list.set(0, "林成");
		
		//获取指定下标上的元素
		String elment = list.get(0);
		System.out.println("获取指定下标上的元素：" + elment);//林成
		
		//在指定下标上插入元素
		list.add(1, "卢永刚");
		
		Vector<String> newList1 = new Vector<>();
		Collections.addAll(newList1, "aaa","bbb","ccc","明日花绮罗");//利用集合工具类进行批量添加
		list.addAll(newList1);//将新集合中所有的元素添加到指定集合的末尾
		
		Vector<String> newList2 = new Vector<>();
		Collections.addAll(newList2, "ddd","eee","fff");//利用集合工具类进行批量添加
		list.addAll(3, newList2);//将新集合中所有的元素添加到指定集合上指定下标的位置
		
		//清空集合中所有的元素
		//list.clear();
		
		System.out.println("判断集合中是否包含某个元素：" + list.contains("椎名空"));//true
		
		Vector<String> newList3 = new Vector<>();
		Collections.addAll(newList3, "eee","ddd","fff","ggg");//利用集合工具类进行批量添加
		System.out.println("判断集合中是否包含某个集合中所有元素：" + list.containsAll(newList3));//false
		
		int index = list.indexOf("椎名空");
		System.out.println("获取元素在集合中的下标：" + index);
		
		boolean empty = list.isEmpty();//有元素-false 没有元素-true
		System.out.println("判断集合中是否没有元素：" + empty);//false
		
		//删除
		list.remove(3);//依据下标删除元素
		list.remove("eee");//依据元素删除元素
		
		//删除 - 去交集
		Vector<String> newList4 = new Vector<>();
		Collections.addAll(newList4, "fff","aaa","bbb","xxx");//利用集合工具类进行批量添加
		list.removeAll(newList4);
		
		//保留交集	
		Vector<String> newList5 = new Vector<>();
		Collections.addAll(newList5, "林成","卢永刚","椎名空","爱田奈奈","三上悠亚","yyy");//利用集合工具类进行批量添加
		list.retainAll(newList5);
		
		//替换指定下标上的元素
		list.set(2, "深田咏美");
		
		//获取开始下标(包含)到结束下标(不包含)的元素，返回新的集合	
		List<String> subList = list.subList(1, 3);
		
		//将集合转换为数组
		Object[] array = subList.toArray();
		System.out.println(Arrays.toString(array));
		
		System.out.println("-------------");
		
		//遍历 - for
		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
		
		System.out.println("-------------");
		
		//遍历 - foreach
		for (String element : list) {
			System.out.println(element);
		}
		
		System.out.println("-------------");
		
		//遍历 - Iterator迭代器
		Iterator<String> it = list.iterator();//获取Iterator迭代器对象
		while(it.hasNext()){//判断是否有可迭代的元素
			String e = it.next();//返回下一个元素
			System.out.println(e);
		}
		
		System.out.println("-------------");
		
		//遍历 - ListIterator迭代器
		ListIterator<String> listIterator = list.listIterator();//获取ListIterator迭代器对象
		while(listIterator.hasNext()){//判断是否有可迭代的元素
			String e = listIterator.next();//返回下一个元素
			System.out.println(e);
		}
		
	}
}

		//删除
		v.removeElement("林成2");//依据元素删除元素
		v.removeElementAt(2);//依据下标山存储元素
		
		//遍历
		Enumeration<String> elements = v.elements();
		while(elements.hasMoreElements()){
			String nextElement = elements.nextElement();
			System.out.println(nextElement);
		}

Stack 特点：栈模式 - 先进后出

		Stack<String> stack = new Stack<>();
		
		//添加元素 - 将元素压入栈顶
		stack.push("林成1");
		stack.push("林成2");
		stack.push("林成3");
		stack.push("林成4");
		stack.push("林成5");
		
		System.out.println("距离栈顶的位置(从1开始)：" + stack.search("林成2"));
		
		while(!stack.empty()){
			//获取栈顶第一个元素，并返回
			//String element = stack.peek();
			
			//删除栈顶第一个元素，并返回
			String element = stack.pop();
			System.out.println(element);
		}
		
		System.out.println(stack.size());

六、HashSet 类

特点：去重+无序

使用 HashSet 方法，list所有的与下标有关的不能用，其他相同

		HashSet<String> set = new HashSet<>();
		
		//添加元素
		set.add("麻生希");
		set.add("椎名空");
		set.add("爱田奈奈");
		set.add("三上悠亚");
		set.add("明日花绮罗");
		
		//获取元素的个数
		int size = set.size();
		System.out.println("获取元素的个数：" + size);//5

		HashSet<String> newSet1 = new HashSet<>();
		Collections.addAll(newSet1, "aaa","bbb","ccc","明日花绮罗");//利用集合工具类进行批量添加
		set.addAll(newSet1);//将新集合中所有的元素添加到指定集合的末尾
		
		//清空集合中所有的元素
		//set.clear();
		
		System.out.println("判断集合中是否包含某个元素：" + set.contains("椎名空"));//true
		
		HashSet<String> newSet2 = new HashSet<>();
		Collections.addAll(newSet2, "eee","ddd","fff","ggg");//利用集合工具类进行批量添加
		System.out.println("判断集合中是否包含某个集合中所有元素：" + set.containsAll(newSet2));//false
		
		boolean empty = set.isEmpty();//有元素-false 没有元素-true
		System.out.println("判断集合中是否没有元素：" + empty);//false
		
		//删除
		set.remove("爱田奈奈");//依据元素删除元素
		
		//删除 - 去交集
		HashSet<String> newSet3 = new HashSet<>();
		Collections.addAll(newSet3, "fff","aaa","bbb","xxx");//利用集合工具类进行批量添加
		set.removeAll(newSet3);
		
		//保留交集	
		HashSet<String> newSet4 = new HashSet<>();
		Collections.addAll(newSet4, "林成","卢永刚","椎名空","爱田奈奈","三上悠亚","yyy");//利用集合工具类进行批量添加
		set.retainAll(newSet4);
		
		//将集合转换为数组
		Object[] array = set.toArray();
		System.out.println(Arrays.toString(array));
		
		System.out.println("-------------");
		
		//遍历 - foreach
		for (String element : set) {
			System.out.println(element);
		}
		
		System.out.println("-------------");
		
		//遍历 - Iterator迭代器
		Iterator<String> it = set.iterator();//获取Iterator迭代器对象
		while(it.hasNext()){//判断是否有可迭代的元素
			String e = it.next();//返回下一个元素
			System.out.println(e);
		}

七、TreeSet 类

特点：自然排序

知识点：使用TreeSet方法

		TreeSet<String> set = new TreeSet<>();
		
		//添加元素
		set.add("麻生希");
		set.add("椎名空");
		set.add("爱田奈奈");
		set.add("三上悠亚");
		set.add("明日花绮罗");
		
		//获取元素的个数
		int size = set.size();
		System.out.println("获取元素的个数：" + size);//5

		TreeSet<String> newSet1 = new TreeSet<>();
		Collections.addAll(newSet1, "aaa","bbb","ccc","明日花绮罗");//利用集合工具类进行批量添加
		set.addAll(newSet1);//将新集合中所有的元素添加到指定集合的末尾
		
		//清空集合中所有的元素
		//set.clear();
		
		System.out.println("判断集合中是否包含某个元素：" + set.contains("椎名空"));//true
		
		TreeSet<String> newSet2 = new TreeSet<>();
		Collections.addAll(newSet2, "eee","ddd","fff","ggg");//利用集合工具类进行批量添加
		System.out.println("判断集合中是否包含某个集合中所有元素：" + set.containsAll(newSet2));//false
		
		boolean empty = set.isEmpty();//有元素-false 没有元素-true
		System.out.println("判断集合中是否没有元素：" + empty);//false
		
		//删除
		set.remove("爱田奈奈");//依据元素删除元素
		
		//删除 - 去交集
		TreeSet<String> newSet3 = new TreeSet<>();
		Collections.addAll(newSet3, "fff","aaa","bbb","xxx");//利用集合工具类进行批量添加
		set.removeAll(newSet3);
		
		//保留交集	
		TreeSet<String> newSet4 = new TreeSet<>();
		Collections.addAll(newSet4, "林成","卢永刚","椎名空","爱田奈奈","三上悠亚","yyy");//利用集合工具类进行批量添加
		set.retainAll(newSet4);
		
		//将集合转换为数组
		Object[] array = set.toArray();
		System.out.println(Arrays.toString(array));
		
		System.out.println("-------------");
		
		//遍历 - foreach
		for (String element : set) {
			System.out.println(element);
		}
		
		System.out.println("-------------");
		
		//遍历 - Iterator迭代器
		Iterator<String> it = set.iterator();//获取Iterator迭代器对象
		while(it.hasNext()){//判断是否有可迭代的元素
			String e = it.next();//返回下一个元素
			System.out.println(e);
		}

知识点：TreeSet排序

需求：创建两个TreeSet对象，分别存Integer、String，感受排序

TreeSet：自然排序（根据不同的类型，选择不同排序规则）

TreeSet 存 Integer：数字排序

TreeSet 存 String：字典排序

		TreeSet<Integer> set1 = new TreeSet<>();
		set1.add(5);//Integer.valueOf(5);
		set1.add(1);//Integer.valueOf(1);
		set1.add(4);//Integer.valueOf(4);
		set1.add(2);//Integer.valueOf(2);
		set1.add(6);//Integer.valueOf(6);
		set1.add(3);//Integer.valueOf(3);
		set1.add(3);//Integer.valueOf(3);
		for (Integer integer : set1) {
			System.out.println(integer);
		}
		
		TreeSet<String> set2 = new TreeSet<>();
		set2.add("c");
		set2.add("d");
		set2.add("a");
		set2.add("b");
		for (String string : set2) {
			System.out.println(string);
		}

知识点：TreeSet排序

理解二叉树的网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

需求：创建TreeSet对象，存储Student

Comparable - 内置比较器 : 排序的类需要实现Comparable接口，重写compareTo方法，制定排序规则和重复判断规则。

package com.dream.treeset_class;

public class Student implements Comparable<Student>{
	
	private String name;
	private char sex;
	private int age;
	private String classId;
	private String id;
	
    ............

	//比较规则
	//需求：按照年龄排序
	@Override
	public int compareTo(Student o) {
		return this.age - o.age;
	}
}

需求：创建TreeSet对象，存储Student，按照名字长度排序，长度一致按照年龄排序

Comparator - 外置比较器：TreeSet 通过匿名类实现 Comparator 接口，实现比较规则的制定。

		TreeSet<Student> set = new TreeSet<>(new Comparator<Student>() {

			@Override
			public int compare(Student o1, Student o2) {
				if(o1.equals(o2)){
					return 0;
				}
				if(o1.getName().length() != o2.getName().length()){
					return o1.getName().length() - o2.getName().length();
				}
				if(o1.getAge() != o2.getAge()){
					return o1.getAge() - o2.getAge();
				}
				return 1;
			}
		});

作用：排序时使用

使用场景：

内置比较器：对象要想存入TreeSet、TreeMap中，对象所属的类必须要实现内置比较器

外置比较器：当内置比较的规则不满足现在的需求，但又不能改动内置比较器规则时

) {

  return this.age - o.age;
}
}
需求：创建TreeSet对象，存储Student，按照名字长度排序，长度一致按照年龄排序

Comparator - 外置比较器 ：TreeSet 通过匿名类实现 Comparator 接口，实现比较规则的制定。

```java
		TreeSet<Student> set = new TreeSet<>(new Comparator<Student>() {

			@Override
			public int compare(Student o1, Student o2) {
				if(o1.equals(o2)){
					return 0;
				}
				if(o1.getName().length() != o2.getName().length()){
					return o1.getName().length() - o2.getName().length();
				}
				if(o1.getAge() != o2.getAge()){
					return o1.getAge() - o2.getAge();
				}
				return 1;
			}
		});
作用：排序时使用

使用场景：

内置比较器：对象要想存入TreeSet、TreeMap中，对象所属的类必须要实现内置比较器

外置比较器：当内置比较的规则不满足现在的需求，但又不能改动内置比较器规则时

优先级别：外置比较器 > 内置比较器