数据结构-集合
一.集合的表示

一个重要的操作是查某个元素属于哪个集合,另一个操作是合并操作
从这个树的节点去找树根也就是从下往上找,要把树并起来只需把两个根并在一起就可以了
不存在已知一个节点去找孩子节点,根重要的是已知一个节点找它的父亲节点,与之前的二叉树一个节点指向孩子,不同这个是一个节点指向父亲

Data是值Parent是父节点的下标
二.集合运算

if(i>=MaxSize)return -1;
表示没有找到
for(;s[i].Parent>=0;i=s[i].Parent);
找父亲到Parent等于-1时找到,退出了i等于父亲节点的下标


不断做并这个操作树会越来越大越来越高,会导致查找效率变低,因为需要从下往上找
如果在结构体里增加一个记录个数,只有根节点需要记录元素个数,别的无所谓,导致空间浪费
根节点的Parent用负数表示,可以利用这一点比如一个集合元素有3个根节点的Parent用-3表示三个
#include<iostream>
using namespace std;
typedef int ElementType;
#define MaxSize 1000
typedef struct {ElementType Data;//存值int Parent;//指向父亲结点
}SetType;
int Find(SetType s[], ElementType X) {/*在数组s中查找值为x的元素所属的集合*//*MaxSize是全局变量,为数组s的最大长度*/int i;for (i = 0; i < MaxSize && s[i].Data != X; i++);if (i >= MaxSize)return -1;/*未找到X,返回-1*/for (; s[i].Parent >= 0; i = s[i].Parent);return i;/*找到X所属集合,返回树根结点在数组s中的下标*/
}
void Union(SetType s[], ElementType X1, ElementType X2) {int Root1, Root2;Root1 = Find(s, X1);//找到X1的根节点下标Root2 = Find(s, X2);//找到X2的根节点下标//如果根节点的下标不同,说明是一个集合if (Root1 != Root2) {if (s[Root1].Parent >s[ Root2].Parent) {//将小集合挂载到大集合s[Root1].Parent = Root2;//x1挂载到x2的集合s[Root2].Parent += -1;}elses[Root2].Parent = Root1; // x2挂载到x1的集合s[Root1].Parent += -1;}}
int main()
{SetType s[MaxSize];//初始化集合,所有结点都是父节点for (int i = 0; i < MaxSize; i++) {s[i].Data = i + 1;s[i].Parent = -1;}cout << Find(s, 5) << endl;Union(s, 3, 5);cout << Find(s, 4) << endl;cout << Find(s, 3) << endl;Union(s, 1, 3);Union(s, 2, 4);Union(s, 8, 6);cout << Find(s, 6) << endl;cout << Find(s, 8) << endl;return 0;
}
相关文章:
数据结构-集合
一.集合的表示 一个重要的操作是查某个元素属于哪个集合,另一个操作是合并操作 从这个树的节点去找树根也就是从下往上找,要把树并起来只需把两个根并在一起就可以了 不存在已知一个节点去找孩子节点,根重要的是已知一个节点找它的父亲节点,与之前的二…...
前端 JS面向对象 原型 prototype
目录 一、问题引出 二、prototype原型对象 三、小结 四、constructor 五、__proto__对象原型 六、原型链 一、问题引出 由于JS的构造函数存在内存浪费问题: function Star(name,age){this.namenamethis.ageagethis.singfunction () {console.log("唱歌&…...
Java中的不可变集合:性能与安全并重的最佳实践
Java中的不可变集合:性能与安全并重的最佳实践 在现代软件开发中,集合类(如List、Set和Map)是Java开发者的日常工具。它们用于存储和操作数据,能极大地简化开发工作。但随着并发编程和大规模应用的广泛使用࿰…...
RandomWords随机生成单词
from random_words import RandomWords rw RandomWords() r rw.random_word() print(r) 更多How to use — random_words documentation (randomwords.readthedocs.io) li LoremIpsum()# 这行代码创建了一个 LoremIpsum 类的实例。li.get_sentence()# 这个方法返回一个随机…...
从零开始使用Intel的AIPC使用xpu加速comfyui
Intel的AIPC使用xpu加速跑comfyui 环境安装python环境搭建驱动及oneAPI安装创建python环境验证环境是否生效 ComfyUI的安装下载、汉化comfyui下载checkpoint 测试使用xpu加速测试使用cpu执行测试 环境安装 python环境搭建 直接下载Anaconda 下载地址 安装好后,通…...
PyQt入门指南五十二 版本控制与协作开发
在开发PyQt应用程序时,版本控制和协作开发是提高开发效率和项目可维护性的重要手段。本指南将介绍如何使用Git进行版本控制,以及如何使用GitHub进行协作开发。 版本控制基础 Git简介:Git是一种分布式版本控制系统,用于跟踪代码变…...
思考:linux Vi Vim 编辑器的简明原理,与快速用法之《 7 字真言 》@ “鱼爱返 说 温泉啊“ (**)
Linux vi/vim | 菜鸟教程 https://zhuanlan.zhihu.com/p/602675406 Linux Vim编辑器的基本使用_vim文本编辑器-CSDN博客 这里提出使用 vi / vim 进行简单的编辑操作的原因,主要是在容器镜像中,普遍都是使用这个。 在 linux 服务器应用场景&#x…...
共筑开源技术新篇章 | 2024 CCF中国开源大会盛大开幕
在这个技术革新日新月异的时代,开源精神如同点燃创新火焰的火种,照亮了无数技术探索者的征途。2024年11月9日,备受瞩目的2024 CCF中国开源大会在深圳这座充满活力的创新之城盛大开幕。这场开源领域的顶级盛事,以“湾区聚力 开源启…...
SpringBoot(十八)SpringBoot集成Minio
项目上传文件集成一下Minio,下面是我在项目中集成Minio的全过程。 首先介绍一下Minio:MinIO是高性能的对象存储,单个对象最大可达5TB。适合存储图片、视频、文档、备份数据、安装包等一系列文件。是一款主要采用Golang语言实现发开的高性能、分布式的对象存储系统。客户端支…...
ODOO学习笔记(3):Odoo和Django的区别是什么?
Odoo和Django都是基于Python的开源框架,但它们的设计目标和用途有所不同: 设计目标和用途: Odoo:Odoo是一个企业资源规划(ERP)系统,它提供了一套完整的商业管理软件,包括会计、库存…...
持续收集解决VCcode各种报错的方法
在学习中我们经常会发生各种各样的报错, 1、pip 安装失败的报错 类似下面的 我们有时候纠结在上面会纠结好久,浪费很多时间。(什么轮子我不知道) 常见的解决方法: s-1:先uninstall packing,再重新装一次(有时候会重…...
Windows下使用adb实现在模拟器中ping
文章目录 前言安装adb执行adb命令查找模拟器设备链接模拟器命令行执行ping命令 总结 前言 有时在模拟器中测试应用不像在Windows这种开发环境中那么方便,毕竟Windows或者Linux下的工具五花八门,可以满足各种测试需求,比如应用在模拟器中无法…...
c++之deque和priority_queue
Deque 文档:https://legacy.cplusplus.com/reference/deque/deque/?kwdeque 相关接口: push_back():在尾部插入 #include <iostream> #include <deque>int main () {std::deque<int> mydeque;int myint;std::cout << "…...
SDL渲染器和纹理
文章目录 渲染器 (SDL_Renderer)纹理 (SDL_Texture)代码 渲染器 (SDL_Renderer) :它是渲染内容的接口,负责将内容绘制到窗口中。通过SDL_CreateRenderer创建,可以设置渲染器的背景颜色、绘图颜色、透明度等。所有绘图操作(如绘制…...
基于Matlab 火焰识别技术
课题介绍 森林承担着为人类提供氧气以及回收二氧化碳等废弃气体的作用,森林保护显得尤其重要。但是每年由于火灾引起的事故不计其数,造成重大的损失。如果有一款监测软件,从硬件处获得的图像中监测是否有火焰,从而报警࿰…...
Qt 监控USB设备的插入和移除
Qt 监控USB设备的插入和移除 flyfish Ubuntu22.04 Qt 6.2.4 CMakeLists.txt 内容 # 指定 CMake 的最低版本要求 cmake_minimum_required(VERSION 3.16)# 定义项目的名称和使用的编程语言 project(USBMonitor LANGUAGES CXX)# 开启自动 UIC,MOC 和 RCC 工具 set(…...
终于弄懂了Python自定义模块与代码复用
自定义模块与代码复用 在编写Python代码时,很多时候我们会遇到需要多次使用相同功能的情况。这时候,模块化编程就显得尤为重要。通过将常用的功能代码放入单独的模块中,我们可以轻松地进行代码复用,避免重复编写相同的代码&#…...
从无音响Windows 端到 有音响macOS 端实时音频传输播放
以下是从 Windows 端到 macOS 端传输音频的优化方案,基于上述链接中的思路进行调整: Windows 端操作 安装必要软件 安装 Python(确保版本兼容且已正确配置环境变量)。安装 PyAudio 库,可通过 pip install pyaudio 命令…...
直方图均衡化及Matlab实现
文章目录 直方图均衡化关键点及思路Matlab实现 直方图均衡化 直方图均衡化是一种图像增强技术,主要用于增强图像的对比度,特别是当图像的有用数据的对比度接近时效果显著。通过改变图像的直方图分布,直方图均衡化能够使图像的灰度值更加接近…...
设备接入到NVR管理平台EasyNVR多品牌NVR管理工具/设备的音视频配置参考
NVR管理平台EasyNVR是一款功能强大的安防视频监控平台,能够轻松实现视频流的导入、录像、存储和回放等功能。在将设备接入到海康NVR管理平台EasyNVR时,视音频配置是确保视频监控效果的重要步骤。本文将详细介绍如何将设备接入到EasyNVR平台,并…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
