当前位置: 首页 > news >正文

建设一个视频网站公众平台网站开发哪家好

建设一个视频网站,公众平台网站开发哪家好,怎么开发一款小程序,展会布置效果图文章目录 前言代码仓库代码说明main.cppMakefile 结果总结参考资料作者的话 前言 C 代码实例:并查集简单创建工具。 代码仓库 yezhening/Programming-examples: 编程实例 (github.com)Programming-examples: 编程实例 (gitee.com) 代码 说明 简单地创建并查集注…

文章目录

  • 前言
  • 代码仓库
  • 代码
    • 说明
    • main.cpp
    • Makefile
  • 结果
  • 总结
  • 参考资料
  • 作者的话

前言

C++ 代码实例:并查集简单创建工具。


代码仓库

  • yezhening/Programming-examples: 编程实例 (github.com)
  • Programming-examples: 编程实例 (gitee.com)

代码

说明

  • 简单地创建并查集
  • 注释有详细的步骤解析
  • 还可优化的点:使用cmake;使用右值传递复杂容器减小开销

注:半个晚上完成,大概测试了下


main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>using std::cout;
using std::endl;
using std::pair;
using std::sort;
using std::unordered_map;
using std::vector;// 并查集类
class DisjointSet
{
public:// 构造并查集// 参数:等价关系元素值的大小/范围,等价关系集合向量DisjointSet(const int &e_q_s, const vector<pair<int, int>> &e_r_v) : eq_rel_size(e_q_s), eq_rel_vec(e_r_v){// 1. 初始化元素父节点向量,大小是等价关系元素值的大小/范围,每个元素的父节点约定为自身this->parent_vec.resize(this->eq_rel_size); // 元素父节点的向量的大小是等价关系元素值的大小/范围for (int i = 0; i < this->eq_rel_size; ++i){parent_vec[i] = i;}// 2. 初始化元素深度向量,大小是等价关系元素值的大小/范围,每个元素作为根节点约定为0即第0层// 合并操作依据树的深度优化,即优先将深度大的树的根挂接到深度小的树的根this->depth_vec.resize(this->eq_rel_size, 0);// 3. 按照字典序排序等价关系集合向量sort(this->eq_rel_vec.begin(), this->eq_rel_vec.end());// 4. 合并集合for (const auto &eq_rel_pair : eq_rel_vec) // 对每一个等价关系集合,如:{1, 2}{// 4.1 分别查找两关系元素的根节点int first_root = this->find_parent(eq_rel_pair.first);int second_root = this->find_parent(eq_rel_pair.second);// 4.2 依据根节点情况合并挂接if (first_root == second_root) // 相等不操作{continue;}else // first_root != second_root{if (this->depth_vec[first_root] < this->depth_vec[second_root]) // 优先将深度大的树的根挂接到深度小的树的根{this->parent_vec[first_root] = second_root;}else if (this->depth_vec[first_root] > this->depth_vec[second_root]){this->parent_vec[second_root] = first_root;}else // == 树的深度相等,约定将第二个根挂接到第一个根,第一个根的深度加深一层{this->parent_vec[second_root] = first_root;++this->depth_vec[first_root];}}}// 5. 构建结果unordered_map<int, vector<int>> root_vec{}; // 哈希表,记录 根节点值-该根节点下的元素向量,一个向量是一棵新树for (int i = 0; i < this->eq_rel_size; ++i) // 遍历元素值{int root = this->find_parent(i); // 取根节点root_vec[root].push_back(i);}for (const pair<int, vector<int>> &pair_tree : root_vec) // 遍历每棵树,加入到结果集{this->disjoint_set.insert(this->disjoint_set.begin(), pair_tree.second);}}// 获取并查集inline vector<vector<int>> get_disjoint_set() const{return this->disjoint_set;}// 打印并查集inline void print_disjoint_set() const{cout << "并查集: " << endl;for (const vector<int> set : this->disjoint_set){for (const int num : set){cout << num << " ";}cout << endl;}return;}private:const int eq_rel_size;             // 等价关系元素值的大小/范围vector<pair<int, int>> eq_rel_vec; // 等价关系集合向量vector<int> parent_vec; // 记录元素父节点的向量vector<int> depth_vec;  // 记录元素深度的向量,约定元素值/树的根是索引,根的深度从0、1往上加vector<vector<int>> disjoint_set; // 并查集,并查集类固有的本质内容// 递归查找当前元素值的根节点int find_parent(int x){// 1. 递归逻辑// 如果不是,parent[x] != x,则使用当前节点的父节点作为参数,调用当前函数,递归继续找爷节点:find_parent(parent[x])// 把找到的根节点记录在查找路径中每个节点的 元素父节点的向量 中:parent_vec[x] =// 相当于把该些节点,都挂接到根节点上,树变得扁平// 即路径压缩优化:在并查集中,每个元素都有一个父节点,通常在查找操作中,我们会沿着父节点链一直向上找到根节点// 这个过程就是在寻找元素所在集合的过程。但是,在普通的查找操作中,路径的长度可能会很长,导致后续的查找操作效率较低。// 路径压缩是一种优化技术,它的思想是:当我们在进行查找操作时,不仅找到元素所在集合的根节点,// 还顺便将经过的所有节点的父节点都设置为根节点。这样,当下次再次查找这些节点时,路径就会更短,查找效率就会更高。// 如:1为根节点,23为子节点,有1 - 2 - 3的三层树,从叶节点3开始找,找到1根节点,然后依次递归返回把2、3的根节点设置为1// 成为1 - 2,1 - 3的两层树if (parent_vec[x] != x){parent_vec[x] = find_parent(parent_vec[x]);}// 1. 递归出口// 如果x的父节点是自己,说明它是根节点,返回// parent_vec[x] == x// 把return放在if会有到不了该条件if的警告:control reaches end of non-void function [-Wreturn-type]return parent_vec[x];}
};int main()
{const int eq_rel_size = 9;                                                                          // 等价关系元素值的大小/范围const vector<pair<int, int>> eq_rel_vec = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {0, 2}, {4, 6}, {0, 8}}; // 等价关系集合向量,内容必须是0~ eq_rel_size - 1(并查集类的逻辑定义了)DisjointSet ds(eq_rel_size, eq_rel_vec); // 并查集对象ds.print_disjoint_set();                 // 打印并查集return 0;
}

Makefile

.PHONY : all
all : main.exemain.exe : main.cppg++ -o $@ $^.PHONY : clean
clean :del *.exe

结果

在这里插入图片描述


总结

C++ 代码实例:并查集简单创建工具。


参考资料

  • 学校《高级算法设计与分析》课程课件的算法思路

作者的话

  • 感谢参考资料的作者/博主
  • 作者:夜悊
  • 版权所有,转载请注明出处,谢谢~
  • 如果文章对你有帮助,请点个赞或加个粉丝吧,你的支持就是作者的动力~
  • 文章在描述时有疑惑的地方,请留言,定会一一耐心讨论、解答
  • 文章在认识上有错误的地方, 敬请批评指正
  • 望读者们都能有所收获

http://www.yayakq.cn/news/112049/

相关文章:

  • 手机网站怎么解析网站开发什么语言比较好
  • 安徽建设厅网站官网返利系统网站开发
  • 做网站什么数据库用的多海尔集团网站的网络营销是什么
  • 上海专业网站建设服务门户网站信息流广告怎么做
  • 网站设计注意因素安卓系统优化大师
  • 如何申请免费空间和域名seo任务
  • 技术支持 创思佳网站建设腾讯免费网站空间
  • 福清建设局网站网站图片验证码出不来
  • 贵阳网站建设咨询wordpress 更新网站
  • 古镇 网站建设网站内页收录
  • 能搜任何网站的浏览器wordpress打赏后插件
  • 潍坊网站开发招聘信息网站提速
  • 大气的个人网站网站怎么编辑
  • 北京网站备案拍照地址鼓楼静态网页设计公司报价
  • 室内设计网站推荐知乎网站基本配置
  • 聊城网站建设优化东莞东智通人才招聘网
  • 长沙优化网站厂家简易网页
  • 网站设计网站类型wordpress内容分享微信
  • 网站标题写什么作用是什么seo产品
  • 行情软件免费下载的网站制作书签的作文
  • wordpress批量生成文章沈阳黑酷做网站建设优化公司怎么样
  • 做网站得多长时间类似qq空间的网站
  • 在哪里找个人做网站的夸克网页版
  • 网站买卖免费网络推广有哪些方式
  • 站长网站模板教育机构举报电话
  • 部门网站建设情况总结东直门小学的网站建设
  • 南通城乡建设局网站首页如何在自己网站开发互动视频
  • cms网站栏目介绍免费手机app制作软件
  • 什么网站做电子元器件建设网站对于电商的作用是?
  • 郑州网站建设到诺然河南锦源建设有限公司网站