大佬教程收集整理的这篇文章主要介绍了Acwing Arithmetic Learning:数据结构（2），大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

数据结构(2)acwing

1.trie树

• 快速存储和查找字符串的集合
• 结构特征：

  

• 例题：Trie字符串统计 ？

2.并查集（近乎O（1））

• 思路

1. 将两个集合合并
2. 询问两个元素是否在一个集合中

• 基本原理：

  每个集合用一颗树来表示，树根的编号就是整个集合的编号。每个节点存储他的父节点，p[x]表示x的父节点

• 问题：

1. 问题1:如何判断树根:if(p[x] == X)
2. 问题2:如何求x的集合编号：while(p[x] != X) x = p[x];
3. 问题3:如何合并两个集合：px是x的集合编号，py是y的集合编号。p[x] = y，直接上图

   

优化：

1.路径压缩

2. scanf使用%s会默认忽略“空格”和"回车"，不用%c

• 上代码：

  

3.堆

• 概念：”小根堆“（顾名思义{根小于左右儿子}）----》为“完全二叉树”（最后一行可以不满，以上全满），上图

• 存储方式（一维数组存储）

  

  • x的左儿子：2x
  • x的右儿子：2x+1

• 如何手写一个堆？

  1. 插入一个数

     heap[ ++ size] = x;up(sizE);
     

  2. 求集合中最小值

     heap[1];
     

  3. 删除最小值

     heap[1] = heap[size];size --;down(1);
     

  4. 删除任意一个元素

     heap[k] = heap[size];size --; down(k);up(k);
     

  5. 修改任意一个元素

     heap[k] = x;down(k);up(k);
     

大佬总结

以上是大佬教程为你收集整理的Acwing Arithmetic Learning:数据结构（2）全部内容，希望文章能够帮你解决Acwing Arithmetic Learning:数据结构（2）所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。