集合Set

article/2025/8/25 5:10:43

集合的一个关键的特点就是不能存放重复的元素，二分搜索树是一个非常好的实现集合的底层数据结构

1、二分搜索树实现集合：

在这里插入图片描述

set接口

package Set;public interface Set<E> {void add(E e);boolean contains(E e);void remove(E e);int getSize();boolean isEmpty();
}

BST.class

package Set;import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class BST<E extends Comparable<E>> {private class Node{public E e;public Node left, right;public Node(E e){this.e = e;left = null;right = null;}}private Node root;private int size;public BST(){root = null;size = 0;}public int size(){return size;}public boolean isEmpty(){return size == 0;}// 向二分搜索树中添加新的元素epublic void add(E e){root = add(root, e);}// 向以node为根的二分搜索树中插入元素e，递归算法// 返回插入新节点后二分搜索树的根private Node add(Node node, E e){if(node == null){size ++;return new Node(e);}if(e.compareTo(node.e) < 0)node.left = add(node.left, e);else if(e.compareTo(node.e) > 0)node.right = add(node.right, e);return node;}// 看二分搜索树中是否包含元素epublic boolean contains(E e){return contains(root, e);}// 看以node为根的二分搜索树中是否包含元素e, 递归算法private boolean contains(Node node, E e){if(node == null)return false;if(e.compareTo(node.e) == 0)return true;else if(e.compareTo(node.e) < 0)return contains(node.left, e);else // e.compareTo(node.e) > 0return contains(node.right, e);}// 二分搜索树的前序遍历public void preOrder(){preOrder(root);}// 前序遍历以node为根的二分搜索树, 递归算法private void preOrder(Node node){if(node == null)return;System.out.println(node.e);preOrder(node.left);preOrder(node.right);}// 二分搜索树的非递归前序遍历public void preOrderNR(){Stack<Node> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){Node cur = stack.pop();System.out.println(cur.e);if(cur.right != null)stack.push(cur.right);if(cur.left != null)stack.push(cur.left);}}// 二分搜索树的中序遍历public void inOrder(){inOrder(root);}// 中序遍历以node为根的二分搜索树, 递归算法private void inOrder(Node node){if(node == null)return;inOrder(node.left);System.out.println(node.e);inOrder(node.right);}// 二分搜索树的后序遍历public void postOrder(){postOrder(root);}// 后序遍历以node为根的二分搜索树, 递归算法private void postOrder(Node node){if(node == null)return;postOrder(node.left);postOrder(node.right);System.out.println(node.e);}// 二分搜索树的层序遍历public void levelOrder(){Queue<Node> q = new LinkedList<>();q.add(root);while(!q.isEmpty()){Node cur = q.remove();System.out.println(cur.e);if(cur.left != null)q.add(cur.left);if(cur.right != null)q.add(cur.right);}}// 寻找二分搜索树的最小元素public E minimum(){if(size == 0)throw new IllegalArgumentException("BST is empty!");return minimum(root).e;}// 返回以node为根的二分搜索树的最小值所在的节点private Node minimum(Node node){if(node.left == null)return node;return minimum(node.left);}// 寻找二分搜索树的最大元素public E maximum(){if(size == 0)throw new IllegalArgumentException("BST is empty");return maximum(root).e;}// 返回以node为根的二分搜索树的最大值所在的节点private Node maximum(Node node){if(node.right == null)return node;return maximum(node.right);}// 从二分搜索树中删除最小值所在节点, 返回最小值public E removeMin(){E ret = minimum();root = removeMin(root);return ret;}// 删除掉以node为根的二分搜索树中的最小节点// 返回删除节点后新的二分搜索树的根private Node removeMin(Node node){if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}node.left = removeMin(node.left);return node;}// 从二分搜索树中删除最大值所在节点public E removeMax(){E ret = maximum();root = removeMax(root);return ret;}// 删除掉以node为根的二分搜索树中的最大节点// 返回删除节点后新的二分搜索树的根private Node removeMax(Node node){if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}node.right = removeMax(node.right);return node;}// 从二分搜索树中删除元素为e的节点public void remove(E e){root = remove(root, e);}// 删除掉以node为根的二分搜索树中值为e的节点, 递归算法// 返回删除节点后新的二分搜索树的根private Node remove(Node node, E e){if( node == null )return null;if( e.compareTo(node.e) < 0 ){node.left = remove(node.left , e);return node;}else if(e.compareTo(node.e) > 0 ){node.right = remove(node.right, e);return node;}else{   // e.compareTo(node.e) == 0// 待删除节点左子树为空的情况if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}// 待删除节点右子树为空的情况if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}// 待删除节点左右子树均不为空的情况// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点// 用这个节点顶替待删除节点的位置Node successor = minimum(node.right);successor.right = removeMin(node.right);successor.left = node.left;node.left = node.right = null;return successor;}}@Overridepublic String toString(){StringBuilder res = new StringBuilder();generateBSTString(root, 0, res);return res.toString();}// 生成以node为根节点，深度为depth的描述二叉树的字符串private void generateBSTString(Node node, int depth, StringBuilder res){if(node == null){res.append(generateDepthString(depth) + "null\n");return;}res.append(generateDepthString(depth) + node.e +"\n");generateBSTString(node.left, depth + 1, res);generateBSTString(node.right, depth + 1, res);}private String generateDepthString(int depth){StringBuilder res = new StringBuilder();for(int i = 0 ; i < depth ; i ++)res.append("--");return res.toString();}
}

BSTSet.class

package Set;public class BSTSet<E extends Comparable<E>> implements Set<E> {private BST<E> bst;public BSTSet() {bst = new BST<E>();}@Overridepublic int getSize() {return bst.size();}@Overridepublic boolean isEmpty() {return bst.isEmpty();}@Overridepublic void add(E e) {bst.add(e);}@Overridepublic boolean contains(E e) {return bst.contains(e);}@Overridepublic void remove(E e) {bst.remove(e);}
}

例：词汇量统计 相同的词汇量只统计一次

实现原理：

我们先读取《傲慢与偏见》这本书的所有单词，然后将它存放在一个数组里，这个数组里面的单词是包括重复的，然后我们再建一个以二分搜索树实现的集合Set,遍历数组，将里面的所有单词再放在集合set中，因为二分搜索树不允许包括重复的元素，所以这时就可以实现相同的统计量只统计一次了。

FileOperation.class

package Set;import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Locale;
import java.util.Scanner;// 文件相关操作
public class FileOperation {// 读取文件名称为filename中的内容，并将其中包含的所有词语放进words中public static boolean readFile(String filename, ArrayList<String> words) {if (filename == null || words == null) {System.out.println("filename is null or words is null");return false;}// 文件读取Scanner scanner;try {File file = new File(filename);if (file.exists()) {FileInputStream fis = new FileInputStream(file);scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");scanner.useLocale(Locale.ENGLISH);} elsereturn false;} catch (IOException ioe) {System.out.println("Cannot open " + filename);return false;}// 简单分词// 这个分词方式相对简陋, 没有考虑很多文本处理中的特殊问题// 在这里只做demo展示用if (scanner.hasNextLine()) {String contents = scanner.useDelimiter("\\A").next();int start = firstCharacterIndex(contents, 0);for (int i = start + 1; i <= contents.length(); )if (i == contents.length() || !Character.isLetter(contents.charAt(i))) {String word = contents.substring(start, i).toLowerCase();words.add(word);start = firstCharacterIndex(contents, i);i = start + 1;} elsei++;}return true;}// 寻找字符串s中，从start的位置开始的第一个字母字符的位置private static int firstCharacterIndex(String s, int start) {for (int i = start; i < s.length(); i++)if (Character.isLetter(s.charAt(i)))return i;return s.length();}
}

测试Main.class

package Set;import java.util.ArrayList;public class Main {public static void main(String[] args) {System.out.println("Pride and Prejudice");ArrayList<String> words1 = new ArrayList<>();if (FileOperation.readFile("pride-and-prejudice.txt", words1)) {System.out.println("Total words 包含重复的: " + words1.size());BSTSet<String> set1 = new BSTSet<String>();for (String word : words1) {set1.add(word);}System.out.println("Total different words: " + set1.getSize());}System.out.println();System.out.println("A Tale of Two Cities");ArrayList<String> words2 = new ArrayList<>();if (FileOperation.readFile("a-tale-of-two-cities.txt", words2)) {System.out.println("Total words: " + words2.size());BSTSet<String> set2 = new BSTSet<String>();for (String word : words2)set2.add(word);System.out.println("Total different words: " + set2.getSize());}}
}

测试结果：
在这里插入图片描述

2、链表实现集合：

在这里插入图片描述
LinkedList.class

package Set;public class LinkedList<E> {private class Node{public E e;public Node next;public Node(E e, Node next){this.e = e;this.next = next;}public Node(E e){this(e, null);}public Node(){this(null, null);}@Overridepublic String toString(){return e.toString();}}private Node dummyHead;private int size;public LinkedList(){dummyHead = new Node();size = 0;}// 获取链表中的元素个数public int getSize(){return size;}// 返回链表是否为空public boolean isEmpty(){return size == 0;}// 在链表的index(0-based)位置添加新的元素e// 在链表中不是一个常用的操作，练习用：）public void add(int index, E e){if(index < 0 || index > size)throw new IllegalArgumentException("Add failed. Illegal index.");Node prev = dummyHead;for(int i = 0 ; i < index ; i ++)prev = prev.next;prev.next = new Node(e, prev.next);size ++;}// 在链表头添加新的元素epublic void addFirst(E e){add(0, e);}// 在链表末尾添加新的元素epublic void addLast(E e){add(size, e);}// 获得链表的第index(0-based)个位置的元素// 在链表中不是一个常用的操作，练习用：）public E get(int index){if(index < 0 || index >= size)throw new IllegalArgumentException("Get failed. Illegal index.");Node cur = dummyHead.next;for(int i = 0 ; i < index ; i ++)cur = cur.next;return cur.e;}// 获得链表的第一个元素public E getFirst(){return get(0);}// 获得链表的最后一个元素public E getLast(){return get(size - 1);}// 修改链表的第index(0-based)个位置的元素为e// 在链表中不是一个常用的操作，练习用：）public void set(int index, E e){if(index < 0 || index >= size)throw new IllegalArgumentException("Set failed. Illegal index.");Node cur = dummyHead.next;for(int i = 0 ; i < index ; i ++)cur = cur.next;cur.e = e;}// 查找链表中是否有元素epublic boolean contains(E e){Node cur = dummyHead.next;while(cur != null){if(cur.e.equals(e))return true;cur = cur.next;}return false;}// 从链表中删除index(0-based)位置的元素, 返回删除的元素// 在链表中不是一个常用的操作，练习用：）public E remove(int index){if(index < 0 || index >= size)throw new IllegalArgumentException("Remove failed. Index is illegal.");Node prev = dummyHead;for(int i = 0 ; i < index ; i ++)prev = prev.next;Node retNode = prev.next;prev.next = retNode.next;retNode.next = null;size --;return retNode.e;}// 从链表中删除第一个元素, 返回删除的元素public E removeFirst(){return remove(0);}// 从链表中删除最后一个元素, 返回删除的元素public E removeLast(){return remove(size - 1);}// 从链表中删除元素epublic void removeElement(E e){Node prev = dummyHead;while(prev.next != null){if(prev.next.e.equals(e))break;prev = prev.next;}if(prev.next != null){Node delNode = prev.next;prev.next = delNode.next;delNode.next = null;size --;}}@Overridepublic String toString(){StringBuilder res = new StringBuilder();Node cur = dummyHead.next;while(cur != null){res.append(cur + "->");cur = cur.next;}res.append("NULL");return res.toString();}
}

LinkedListSet.class

package Set;import java.util.ArrayList;public class LinkedListSet<E> implements Set<E> {private LinkedList<E> list;public LinkedListSet() {list = new LinkedList<E>();}@Overridepublic int getSize() {return list.getSize();}@Overridepublic boolean isEmpty() {return list.isEmpty();}@Overridepublic void add(E e) {if (!list.contains(e))list.addFirst(e);}@Overridepublic boolean contains(E e) {return list.contains(e);}@Overridepublic void remove(E e) {list.removeElement(e);}public static void main(String[] args) {System.out.println("Pride and Prejudice");ArrayList<String> words1 = new ArrayList<>();if (FileOperation.readFile("pride-and-prejudice.txt", words1)) {System.out.println("Total words: " + words1.size());LinkedListSet<String> set1 = new LinkedListSet<String>();for (String word : words1)set1.add(word);System.out.println("Total different words: " + set1.getSize());}System.out.println();System.out.println("A Tale of Two Cities");ArrayList<String> words2 = new ArrayList<>();if (FileOperation.readFile("a-tale-of-two-cities.txt", words2)) {System.out.println("Total words: " + words2.size());LinkedListSet<String> set2 = new LinkedListSet<String>();for (String word : words2)set2.add(word);System.out.println("Total different words: " + set2.getSize());}}
}

3、两种实现方式时间复杂度的对比

package Set;import java.util.ArrayList;//时间复杂度对比
public class TimeComplexityofSet {private static double testSet(Set<String> set, String filename){long startTime = System.nanoTime();System.out.println(filename);ArrayList<String> words = new ArrayList<>();if(FileOperation.readFile(filename, words)) {System.out.println("Total words: " + words.size());for (String word : words)set.add(word);System.out.println("Total different words: " + set.getSize());}long endTime = System.nanoTime();return (endTime - startTime) / 1000000000.0;}public static void main(String[] args) {String filename = "pride-and-prejudice.txt";BSTSet<String> bstSet = new BSTSet<String>();double time1 = testSet(bstSet, filename);System.out.println("BST Set: " + time1 + " s");System.out.println();LinkedListSet<String> linkedListSet = new LinkedListSet<String>();double time2 = testSet(linkedListSet, filename);System.out.println("Linked List Set: " + time2 + " s");}
}

在这里插入图片描述

通过测试可以看出二分搜索树是高效的

在这里插入图片描述
在这里插入图片描述

二分搜索树的最坏情况，这样的二分搜索树和链表是无异的。换句话来说，二分搜索树可能退化成链表。如下：

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述


http://chatgpt.dhexx.cn/article/8C81RVWh.shtml

相关文章

C++ 集合set 详解

C++ 集合set 详解

1.关于set C STL 之所以得到广泛的赞誉&#xff0c;也被很多人使用&#xff0c;不只是提供了像vector, string, list等方便的容器&#xff0c;更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组&#xff0c;list封装了链表&#xff0c;map和se…
阅读更多...
set集合使用详解

set集合使用详解

set集合使用详解 “曾经年少爱追梦&#xff0c;一心只想往前飞。”那会高二&#xff0c;刚刚接触c语言&#xff0c;一发不可收拾&#xff0c;还记得当时为了一个想法和朋友一起想到半夜。现在我还是那个少年&#xff0c;那个又菜又爱玩的少年。 咳咳&#xff0c;set集合容器&am…
阅读更多...
OBS录屏如何设置录制窗口大小？

OBS录屏如何设置录制窗口大小？

1、在显示录制窗口区右键→滤镜→添加一个裁剪/填充→调整左右顶底部里的数字进行裁剪&#xff0c;调整到合适的录屏大小即可。
阅读更多...
如何使用OBS 进行屏幕录制

如何使用OBS 进行屏幕录制

软件界面 默认的保存位置 C:\Users\XXXX\Videos 如何对屏幕进行录制&#xff08;默认也录制了音频信号&#xff09;
阅读更多...
obs屏幕录制暂停

obs屏幕录制暂停

OBS Studio 24.0 RC1 发布 – 有大惊喜OBS Studio 24.0 RC1 发布 – 有大惊喜 OBS Studio 24.0 RC1于今天下午发布&#xff0c;增加了在录制时暂停的功能&#xff0c;允许“无缝地实时删除视频片段”。OBS Studio 24.0 RC1还支持在发生拥塞时自动调整比特率&#xff0c;而不是丢…
阅读更多...
OBS录屏软件使用指南

OBS录屏软件使用指南

OBS录屏软件使用指南 1 简介2 录屏使用步骤2.1 来源2.2 设置2.2.1 输出2.2.2 视频 2.3 录制 3 总结 1 简介 2 录屏使用步骤 2.1 来源 在来源标签&#xff0c;添加显示器捕获。 2.2 设置 在录屏时&#xff0c;需要进行录屏设置&#xff0c;点击菜单栏文件->设置 2.2.1…
阅读更多...
【录屏】OBS如何区域录制

【录屏】OBS如何区域录制

OBS如何区域录制 按住alt拖动红色边框即可隐藏拖动的区域
阅读更多...
OBS 录制简单操作说明

OBS 录制简单操作说明

把从B站Sky灬素颜看到的关于OBS录制视频的部分文字记录下 视频地址 录制界面捕获 1.首先&#xff0c;新建一个场景。 2.在新建的场景下&#xff0c;点击右边的来源窗口&#xff0c;新建一个捕获方式。 &#xff08;此处注意被捕获的窗口不能最小化&#xff0c;需要浮在桌…
阅读更多...
OBS录制黑屏的解决办法

OBS录制黑屏的解决办法

前些时间打开下载了好久一直没打开的obs录屏软件&#xff0c;想把老师的直播网课录下来重复看&#xff0c;但是发现&#xff0c;无论是用显示器捕获还是窗口捕获都是黑屏&#xff0c;然后就百度找了挺多关键词的&#xff0c;有的方法奏效有的不行有的不全面&#xff0c;为了方便…
阅读更多...
obs直播录屏软件下载使用教程-制作短视频录制视频教程

obs直播录屏软件下载使用教程-制作短视频录制视频教程

现在是短视频的时代&#xff0c;我们需要学一点视频处理技术&#xff0c;录屏也是一项基本能力 下载软件 这里我下载的是obs软件&#xff0c;可以录屏可以直播 https://obsproject.com/ 因为网络原因&#xff0c;一直没有下载成功&#xff0c;开启特殊上网&#xff0c;才算一点…
阅读更多...
OBS录制设置基本介绍(1)

OBS录制设置基本介绍(1)

1.OBS OBS&#xff08;Open Broadcasting Software&#xff09;是一款免费且开源的跨平台直播和录制软件&#xff0c;它可以将电脑屏幕、摄像头、麦克风和音频源等多种内容混合在一起并进行直播或录制。 1)基本操作介绍&#xff1a; 下载 OBS官网 在OBS官网&#xff08;htt…
阅读更多...
直播、录屏软件OBS Studio下载安装操作教程

直播、录屏软件OBS Studio下载安装操作教程

直播、录屏软件OBS Studio下载安装操作教程 OBS Studio是一款非常强大的免费开源无广告&#xff0c;国外开发的软件&#xff0c;录屏只是它的一部分功能&#xff0c;对于需要录制屏幕又要录制摄像头的也很适合&#xff0c;比如现在的直播行业&#xff0c;这款软件是一个不二之…
阅读更多...
录屏软件OBS录屏时噪声大的解决办法

录屏软件OBS录屏时噪声大的解决办法

1、选择麦克风的滤镜 2、点击右下角号&#xff0c;选择噪声抑制 3、点击确定即可&#xff0c;这样设置就完成了&#xff0c;最后关闭滤镜就可以无噪声录制视频了 你的点赞、评论、收藏和关注是我创作的动力。 感谢各位看官老爷
阅读更多...
解决OBS录屏软件窗口采集不全的问题

解决OBS录屏软件窗口采集不全的问题

问题描述 使用OBS录屏软件的窗口采集功能的时候&#xff0c;有时候窗口对象只能捕获到一部分&#xff0c;不能全屏都是目标对象。 解决办法
阅读更多...
OBS视频录制及其直播推流教程（超详细，非硬核）

OBS视频录制及其直播推流教程（超详细，非硬核）

录制软件&#xff1a; OBS &#xff08;我用过很多录制软件&#xff0c;OBS是最好用的&#xff0c;没有之一&#xff0c;而且完全免费&#xff09; 功能&#xff1a;直播&#xff0c;录像&#xff08;录制游戏或者网课等等&#xff09; 我准备将我的教程分为多个部分&#xf…
阅读更多...
OBS 安装与考试参数设置及屏幕无法完全捕获、录屏不完整的解决方法

OBS 安装与考试参数设置及屏幕无法完全捕获、录屏不完整的解决方法

目录 一、OBS 的下载与安装 二、OBS 考试参数设置 三、问题解决 &#xff08;1&#xff09;屏幕无法完全捕获 &#xff08;2&#xff09;录屏不完整 一、OBS 的下载与安装 官网&#xff08;Open Broadcaster Software | OBS&#xff09;选择对应的版本下载&#xff0c;自…
阅读更多...
OBS 录制没有声音怎么办？

OBS 录制没有声音怎么办？

1.检查obs设置- 音频 -是否是默认选项 2.检查win10 是否允许使用麦克风 1&#xff09;右下角出现麦克风标识 2&#xff09;设置-隐私-麦克风&#xff0c;查看允许放开你的麦克风是否打开 如果上述还是为解决问题&#xff0c;那么接下来的就是关键 3. 控制面板 - 硬件和声音 …
阅读更多...
20221130如何修改OBS录屏的存储路径？

20221130如何修改OBS录屏的存储路径？

obs https://obsproject.com/ OBS OBS Open Broadcaster Software OBS Studio Latest Release 28.1.2 - November 5th obs 录屏 更换保存位置 https://jingyan.baidu.com/article/67508eb4c854fbddca1ce481.html 20221130如何修改OBS录屏的存储路径&#xff1f; 如何修改OBS录…
阅读更多...
CSP在线考试环境 | OBS录屏软件下载安装和设置教程

CSP在线考试环境 | OBS录屏软件下载安装和设置教程

今年由于疫情原因&#xff0c;很多省份都申请在线参加CCF CSP-J/S考试。 本次在线考试采用双重保险方式&#xff0c;不仅要求有腾讯会议端的监考&#xff0c;还要求在考试电脑上要安装OBS录屏软件&#xff0c;进行全程录屏。最后&#xff0c;将两份录制的视频文档传回给CCF&am…
阅读更多...
开源免费录屏和直播软件OBS Studio教程

开源免费录屏和直播软件OBS Studio教程

转载于&#xff1a;https://zhuanlan.zhihu.com/p/107720665 OBS Studio是目前比较主流的免费开源录屏和直播软件&#xff0c;它提供了丰富的功能特性&#xff0c;可以媲美一些受欢迎的同类商业软件。如果你正在考虑使用低成本方案来录屏或进行直播&#xff0c;那么这将是一个…
阅读更多...
推荐文章

Copyright @ 2022~2023