竞赛常考的知识点大总结(四)高级数据结构

news/2024/6/15 15:39:45/文章来源:https://blog.csdn.net/m0_74000148/article/details/137248735

并查集

并查集(Disjoint Set Union,DSU)是一种数据结构,用于管理一系列不相交的集合,并支持两种操作:合并(Union)和查找(Find)。并查集可以高效地处理动态连通性问题,即判断两个元素是否属于同一个集合,以及合并两个集合。

特点:

1.动态连通性:并查集可以高效地处理动态连通性问题,即判断两个元素是否属于同一个集合。

2.合并操作:并查集支持合并操作,可以将两个集合合并为一个集合。

3.查找操作:并查集支持查找操作,可以快速判断两个元素是否属于同一个集合。

4.路径压缩:为了提高查找操作的效率,通常会使用路径压缩技术,将查找过程中访问过的所有节点直接连接到根节点。

常见用法:

1.网络连接检测:在计算机网络中,用于检测两个节点是否在同一个网络分段中。

2.社交网络分析:用于分析社交网络中的朋友关系,如判断两个人是否是朋友的朋友。

3.图的连通分量:用于找出图中的所有连通分量。

4.最小生成树:在Kruskal算法中,用于快速判断两个顶点是否已经连通。

经典C语言例题:

题目: 使用并查集解决动态连通性问题。

示例代码:

#include <stdio.h>// 并查集结构体
typedef struct {int* parent;int* rank;int count;
} DisjointSet;// 创建并查集
DisjointSet* createDisjointSet(int n) {DisjointSet* ds = (DisjointSet*)malloc(sizeof(DisjointSet));ds->parent = (int*)malloc(n * sizeof(int));ds->rank = (int*)calloc(n, sizeof(int));ds->count = n;for (int i = 0; i < n; i++) {ds->parent[i] = i;}return ds;
}// 查找操作
int find(DisjointSet* ds, int x) {if (ds->parent[x] != x) {ds->parent[x] = find(ds, ds->parent[x]); // 路径压缩}return ds->parent[x];
}// 合并操作
void unionSets(DisjointSet* ds, int x, int y) {int xroot = find(ds, x);int yroot = find(ds, y);if (xroot != yroot) {if (ds->rank[xroot] < ds->rank[yroot]) {ds->parent[xroot] = yroot;} else if (ds->rank[xroot] > ds->rank[yroot]) {ds->parent[yroot] = xroot;} else {ds->parent[yroot] = xroot;ds->rank[xroot]++;}ds->count--;}
}// 主函数
int main() {DisjointSet* ds = createDisjointSet(10);unionSets(ds, 4, 3);unionSets(ds, 3, 8);unionSets(ds, 6, 5);unionSets(ds, 9, 4);unionSets(ds, 2, 1);unionSets(ds, 8, 9);unionSets(ds, 5, 0);unionSets(ds, 7, 2);unionSets(ds, 6, 1);unionSets(ds, 7, 3);printf("Number of disjoint sets: %d\n", ds->count);return 0;
}

例题分析:

1.创建并查集createDisjointSet函数创建一个并查集结构体,包括父数组、秩数组和集合数量。

2.查找操作find函数用于查找元素的根节点,同时使用路径压缩技术,将查找过程中访问过的所有节点直接连接到根节点。

3.合并操作unionSets函数用于合并两个集合,如果两个元素的根节点不同,则将它们合并为一个集合,并更新秩数组。

4.主函数:在main函数中,创建了一个并查集,并执行了一系列合并操作。最后,打印出并查集中集合的数量。

这个例题展示了如何在C语言中使用并查集解决动态连通性问题。通过这个例子,可以更好地理解并查集在动态连通性问题中的应用,以及如何使用并查集来高效地处理集合的合并和查找操作。并查集通过路径压缩和秩优化,使得查找和合并操作的时间复杂度接近于常数时间,是一种非常高效的动态连通性数据结构。

线段树

线段树(Segment Tree)是一种二叉树结构,用于高效地解决区间查询和区间更新问题。线段树将一个区间分成若干个线段,并将这些线段存储在树中,使得可以快速地查询和更新区间的信息。

特点:

1.区间查询:线段树可以快速查询任意区间的信息,如区间和、区间最大值、区间最小值等。

2.区间更新:线段树可以快速更新区间的信息,如将区间内的值全部增加某个数。

3.动态数据结构:线段树是一个动态数据结构,可以动态地插入和删除元素。

4.空间复杂度:线段树的空间复杂度为O(n),其中n是区间内元素的数量。

常见用法:

1.区间求和:在线段树中存储区间内元素的和,可以快速求出任意区间的和。

2.区间最大值/最小值:在线段树中存储区间内元素的最大值或最小值,可以快速求出任意区间的最大值或最小值。

3.区间更新:在线段树中存储区间内元素的其他信息,可以快速更新区间的信息。

4.动态数据处理:在线段树中动态地插入和删除元素,可以处理动态数据。

经典C语言例题:

题目: 使用线段树解决区间求和问题。

示例代码:

#include <stdio.h>
#include <stdlib.h>// 定义线段树节点结构体
typedef struct Node {int start, end;int sum;struct Node* left;struct Node* right;
} Node;// 创建线段树节点
Node* createNode(int start, int end) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->start = start;newNode->end = end;newNode->sum = 0;newNode->left = NULL;newNode->right = NULL;return newNode;
}// 构建线段树
Node* buildTree(int arr[], int start, int end) {Node* node = createNode(start, end);if (start == end) {node->sum = arr[start];return node;}int mid = (start + end) / 2;node->left = buildTree(arr, start, mid);node->right = buildTree(arr, mid + 1, end);node->sum = node->left->sum + node->right->sum;return node;
}// 查询区间和
int query(Node* node, int start, int end) {if (node->start == start && node->end == end) {return node->sum;}int mid = (node->start + node->end) / 2;if (end <= mid) {return query(node->left, start, end);} else if (start > mid) {return query(node->right, start, end);} else {return query(node->left, start, mid) + query(node->right, mid + 1, end);}
}// 更新区间和
void update(Node* node, int start, int end, int value) {if (node->start == start && node->end == end) {node->sum = value;return;}int mid = (node->start + node->end) / 2;if (end <= mid) {update(node->left, start, end, value);} else if (start > mid) {update(node->right, start, end, value);} else {update(node->left, start, mid, value);update(node->right, mid + 1, end, value);}node->sum = node->left->sum + node->right->sum;
}// 主函数
int main() {int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};int n = sizeof(arr) / sizeof(arr[0]);Node* root = buildTree(arr, 0, n - 1);printf("Sum of elements from index 1 to 3 is: %d\n", query(root, 1, 3));update(root, 1, 3, 10);printf("Sum of elements from index 1 to 3 after update is: %d\n", query(root, 1, 3));return 0;
}
 
}

例题分析:

1.创建线段树节点createNode函数创建一个线段树节点,并初始化区间和子节点指针。

2.构建线段树buildTree函数递归地构建线段树,将区间分为左右子区间,并计算区间和。

3.查询区间和query函数递归地查询线段树中指定区间的和。

4.更新区间和update函数递归地更新线段树中指定区间的和,并更新父节点的区间和。

5.主函数:在main函数中,定义了一个数组arr,构建了一个线段树,并查询和更新了指定区间的和。

这个例题展示了如何在C语言中使用线段树解决区间求和问题。通过这个例子,可以更好地理解线段树在区间查询和更新问题中的应用,以及如何使用线段树来高效地处理区间信息。线段树通过将区间分成若干个线段,并将这些线段存储在树中,使得可以快速地查询和更新区间的信息,是一种非常高效的区间数据结构。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1033232.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Vue使用高德地图(快速上手)

1.在高德平台注册账号 2.我的 > 管理管理中添加Key 3.安装依赖 npm i amap/amap-jsapi-loader --save 或 yarn add amap/amap-jsapi-loader --save 4.导入 AMapLoade import AMapLoader from amap/amap-jsapi-loader; 5.直接上代码&#xff0c;做好了注释&#xff08;初…

echarts实现炫酷科技感的流光效果

前言&#xff1a; echarts实现炫酷科技感的流光效果 效果图&#xff1a; 实现步骤&#xff1a; 1、引入echarts,直接安装或者cdn引入 npm i echarts https://cdn.jsdelivr.net/npm/echarts5.4.3/dist/echarts.min.js 2、封装 option方法&#xff0c;第一个数据是折线数据&a…

STM32之HAL开发——不同系列SPI功能对比(附STM32Cube配置)

不同系列STM32——SPI框图 F1系列框图 F4系列框图 TI模式时序图特性 F7系列框图 H7系列框图 注意&#xff1a;F7系列以及H7系列支持Quad-SPI模式&#xff0c;可以连接单&#xff0c;双或者四条数据线的Flash存储介质。 SPI——Cube配置流程 RCC时钟源配置 SYS系统调试模式配…

3.Labview字符串与路径精讲(下) — 字符串及路径的使用

本章讲解labview中的字符串和路径具体实践用例&#xff0c;从前面板字符串属性到后面板字符串函数应用做出详细概述&#xff0c;通过本文的学习希望大家了解到字符串及路径在labview编程中的重要地位。 本系列文章为labview 从基础到强化到精通的学习文章&#xff0c;大家可以随…

vscode通过ssh连接服务器(吐血总结)

一、通过ssh连接服务器 1、打开vscode&#xff0c;进入拓展&#xff08;CtrlShiftX&#xff09;&#xff0c;下载拓展Remote - SSH。 2、点击远程资源管理器选项卡&#xff0c;选择远程&#xff08;隧道/SSH&#xff09;类别。 3、点击SSH配置。 4、在中间上部分弹出的配置文件…

Linux系统下安装ElasticSearch

一、228环境ES使用安装 1、检验ES服务是否安装成功的方法 &#xff08;1&#xff09;查看Elasticsearch进程是否成功 ps -ef|grep elasticsearch &#xff08;2&#xff09;linux elasticsearch下访问&#xff08;curl带认证访问&#xff09; curl --user elastic:Zhes.13…

docker 部署 gitlab-ce 16.9.1

文章目录 [toc]拉取 gitlab-ce 镜像创建 gitlab-ce 持久化目录启停脚本配置配置 gitlab-ce编辑 gitlab-ce 配置文件重启 gitlab-ce配置 root 密码 设置中文 gitlab/gitlab-ce(需要科学上网) 拉取 gitlab-ce 镜像 docker pull gitlab/gitlab-ce:16.9.1-ce.0查看镜像是不是有 Vo…

在 Three.js 中,`USDZExporter` 类用于将场景导出为 USDZ 格式,这是一种用于在 iOS 平台上显示增强现实(AR)内容的格式。

demo 案例 在 Three.js 中&#xff0c;USDZExporter 类用于将场景导出为 USDZ 格式&#xff0c;这是一种用于在 iOS 平台上显示增强现实&#xff08;AR&#xff09;内容的格式。下面是关于 USDZExporter 的入参、出参、方法和属性的讲解&#xff1a; 入参 (Parameters): sc…

element-ui message 组件源码分享

今日简单分享 message 组件的源码&#xff0c;主要从以下四个方面来分享&#xff1a; 1、message 组件的页面结构 2、message 组件的 options 配置 3、mesage 组件的方法 4、个人总结 一、message 组件的页面结构 二、message 组件的 options 配置 前置说明&#xff1a;m…

家庭网络防御系统搭建-配置流量镜像到NDR系统

由于需要将家庭网络中的全部流量送到NDR分析系统进行分析&#xff0c;因此需要一个具备流量镜像功能的交换机或者路由器。在前面文章所提及的家庭网络架构中&#xff0c;需要一台交换机即可拷贝东西向流量以及南北向流量。当然如果家庭中的路由器或者其他设备具备交换机镜像功能…

element跑马灯/轮播图,第一页隐藏左边按钮,最后一页隐藏右边按钮(vue 开箱即用)

图示&#xff1a; 第一步&#xff1a; <el-carousel :class"changeIndex0?leftBtnNone:changeIndeximgDataList.length-1? rightBtnNone:" height"546px" :autoplay"false" change"changeNext"><el-carousel-item v-for…

Windows Server 2022 使用ApacheDS用户远程桌面登录服务器

Windows Server 2022 使用ApacheDS用户远程桌面登录服务器 1、接上篇 Windows Server 2022 使用ApacheDS用户认证 使用Administrator用户远程登录192.168.1.100windows server&#xff0c;打开pGina软件 2、输入刚刚在ApacheDS中的新添加的用户测试一下&#xff0c;会自动添加…

Dapr(一) 基于云原生了解Dapr

(这期先了解Dapr&#xff0c;之后在推出如何搭建Dapr&#xff0c;以及如何使用。) 目录 引言&#xff1a; Service Mesh定义 Service Mesh解决的痛点 Istio介绍 Service Mesh遇到的挑战 分布式应用的需求 Multiple Runtime 理念推导 Dapr 介绍 Dapr 特性 Dapr 核心…

计网数据链路层的透明传输技术——字节填充、字符填充和零比特填充

字节填充&#xff08;Byte Stuffing&#xff09; 字节填充是数据链路层的一种透明传输技术&#xff0c;主要用于处理以字节为单位的异步通信中的特殊控制字符&#xff08;如ESC、SOH、EOT等&#xff09;。其主要思想是在数据字段中出现控制字符的前面插入一个特殊的转义字符&a…

学透Spring Boot 003 —— Spring 和 Spring Boot 常用注解(附面试题和思维导图)

这是 学透 Spring Boot 专栏 的第三篇&#xff0c;欢迎关注我&#xff0c;与我一起学习和探讨 Spring Boot 相关知识&#xff0c;学透 Spring Boot。 从面试题说起 今天我们通过一道和Spring Boot有关的常见面试题入手。 面试题&#xff1a;说说 Spring Boot 中有哪些常用注解…

【漏洞复现】通天星CMSV6车载视频监控平台Login弱口令漏洞

Nx01 产品简介 通天星车载视频监控平台软件拥有多种语言版本&#xff0c;应用于公交车车载视频监控、校车车载视频监控、大巴车车载视频监控、物流车载监控、油品运输车载监控等公共交通上。 Nx02 漏洞描述 通天星车载视频监控平台存在login弱口令漏洞&#xff0c;攻击者可以通…

Coursera自然语言处理专项课程04:Natural Language Processing with Attention Models笔记 Week02

Natural Language Processing with Attention Models Course Certificate 本文是学习这门课 Natural Language Processing with Attention Models的学习笔记&#xff0c;如有侵权&#xff0c;请联系删除。 文章目录 Natural Language Processing with Attention ModelsText Su…

【前缀和差分】详细使用方法

前缀和 前缀和的作用&#xff1a; 快速求出元素组中某段区间的和 为什么下标要从1 开始&#xff1a;为了方便后面的计算&#xff0c;避免下标转换&#xff0c;设为零&#xff0c;不影响结果 定义两个数组&#xff0c;第一个为原始数组(a[])&#xff0c;第二个为前缀和数组(s[…

智能工具柜-RFID智能工具柜管理系统

智能工具柜-RFID智能工具柜管理系统 RFID工具柜管理系统是一种便捷化的工具管理系统&#xff0c;它采用RFID技术实现信息化&#xff0c;可以大大提高工具管理的效率和准确性。 日常的工具管理也确实存在一定的管理问题&#xff0c;如工具管理效率低、管理不准确等。因此&…

提升企业组网效率:如何彻底解决网络卡顿问题

在当今这个互联网高速发展的时代&#xff0c;企业的办公模式正经历着翻天覆地的变化。服务器可能位于内网或是迁移到云端&#xff0c;而这意味着员工日常工作的大部分活动都依赖于稳定的网络连接。然而&#xff0c;一个不容忽视的现实是&#xff0c;网络卡顿成为了办公室常见的…