当前位置:   article > 正文

数据结构的一些小结和板子

数据结构的一些小结和板子

链表

  1. //定义
  2. int head=-1,e[N],ne[N],idx=0;
  3. //头插
  4. void add(int x)
  5. {
  6. e[idx]=x;
  7. ne[idx]=head;
  8. head=idx++;
  9. }
  10. //在第k位后插入
  11. void insert(int k,int x)
  12. {
  13. e[idx]=x;
  14. ne[idx]=ne[k];
  15. ne[k]=idx++;
  16. }
  17. //删除第k位
  18. void del(int k)
  19. {
  20. ne[k]=ne[ne[k]];
  21. }

后进先出

  1. //定义
  2. int q[N],tt;
  3. //入栈
  4. q[tt++]=x;
  5. //取栈顶元素
  6. q[tt]
  7. //出栈
  8. tt--;

队列

先进先出

  1. //定义
  2. int q[N],hh=0,tt=-1;
  3. //入队
  4. q[++tt]=x;
  5. //出队
  6. q[hh++]
  7. //判断是否为空
  8. tt-hh>=0

Trie数

字典树:高效地存储字符串

  1. //定义
  2. int son[N][26],idx=0,cnt[N];
  3. //插入
  4. void insert(char str[])
  5. {
  6. int p=0;
  7. for(int i=0;str[i];i++)
  8. {
  9. int x=str[i]-'a';
  10. if(!son[p][x]) son[p][x]=++idx;
  11. p=son[p][x];
  12. }
  13. }
  14. //查询
  15. int query(char str[])
  16. {
  17. int p=0;
  18. for(int i=0;str[i];i++)
  19. {
  20. int x=str[i]-'a';
  21. if(!son[p][x]) return 0;
  22. p=son[p][x];
  23. }
  24. return cnt[p];
  25. }

并查集

并查集的主要操作是合并和查找,这两个操作的核心是find根节点。

合并是将一个集合的根节点直接指向另一个集合的根节点。

查找是从当前结点开始往上,判断父节点是否为根节点,查找过程中进行路径压缩,将当前遍历到的结点直接指向根节点。

  1. //初始化
  2. for(int i=1;i<=n;i++) p[i]=i;
  3. //find(带路径压缩)
  4. int find(int x)
  5. {
  6. if(p[x]!=x) p[x]=find(p[x]);
  7. return p[x];
  8. }
  9. //合并
  10. int pu=find(u),pv=find(v);
  11. if(pu!=pv) p[pu]=pv;

以小根堆为例。

每插入一个数,需要堆堆进行down或up,down表示使大数往下,up表示使小数往上,通过这两个操作,可以维持小根堆堆顶元素最大的性质。

需要注意的是,当我们要删除堆中的某个元素时,并不是直接删去,因为删去数组中特定位置的数是非常困难的,而删去数组末尾的数非常容易,因此采用的方式是先将元素和堆尾元素互换,删去堆尾元素,再执行down或up。

  1. //插入元素
  2. heap[++idx]=x;
  3. up(idx);
  4. //删除元素
  5. swap(heap[1],heap[idx--]);
  6. down(1);
  7. void down(int u)
  8. {
  9. int t=u;
  10. if(2*u<=idx&&heap[2*u]<heap[t]) t=2*u;
  11. if(2*u+1<=idx&&heap[2*u+1]<heap[t]) t=2*u+1;
  12. if(u!=t)
  13. {
  14. swap(heap[t],heap[u]);
  15. down(t);
  16. }
  17. }
  18. void up(int u)
  19. {
  20. while(u/2&&heap[u/2]>heap[u])
  21. {
  22. swap(heap[u/2],heap[u]);
  23. u/=2;
  24. }
  25. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小舞很执着/article/detail/913711
推荐阅读
相关标签
  

闽ICP备14008679号