(2021年整理)数据结构模板

1、数据结构模板 - 1 - 数据结构模板 编辑整理： 尊敬的读者朋友们： 这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们 对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（数据结构模板）的内容能 够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉， 前进的动力。 本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以 下为数据结构模板的全部内容。 数据结构模板 - 2 - 数数 据据 结结 构构 数数 据据 结结 构构.1 1 哈希函数 .2 并查集 .3 二叉堆 .4 离散化 .

2、5 rmq 问题（st 算法） .6 lca 问题（st 算法） .7 字典树（trie） .9 树状数组 .10 数据结构模板 - 3 - 哈希函数哈希函数 /字符串哈希 intint elfhashelfhash（charchar k)k) unsignedunsigned longlong h=0,g;h=0,g; whilewhile（*k)*k) h=(h4)+*k+h=(h24h=g24； hg; returnreturn h h； /数组哈希 intint hashcodehashcode（intint *v*v，intint k k） intint i i，p=0;p=0; f

3、or(i=0;for(i=0; ikik； i+i+） p=(p2)+(vp=(p2)+(vi4i4）)（v vi10);i10); p p = = p pprime;prime; 数据结构模板 - 4 - ifif（p0)p0) p+=primep+=prime； returnreturn p;p; 数据结构模板 - 5 - 并查集并查集 intint parentparent3001030010; ; intint findfind（intint x x） /寻找根节点 和 路径压缩 if(parentx0if(parentx1next=pre1； whilewhile（nextnext

4、theapnexttheapnext ） /大根堆为 heapheapprepre=heap=heapnext;next; pre=next;pre=next; next=pre1next=pre1； heapheapprepre=t=t； voidvoid sink(intsink(int pre)pre) /向下调整 intint t=heapt=heappre,next=pre1pre,next=pre1； while(next=hs)while(next=hs) ifif（nexthsnexths next+; /大根堆为 if(heapif(heapnextnext=t=t） bre

5、ak;break; /大根堆为 = heapheappre=heapnext;pre=heapnext; pre=nextpre=next； next=pre1next=pre0i=hs/2;i0；i i) ) sink(isink(i）; ; 数据结构模板 - 9 - 离散化离散化 #includealgorithm#includealgorithm usingusing namespacenamespace stdstd； definedefine maxnmaxn 4100041000 structstruct nodenode intint value;value; /原数据的值原数据

6、的值 intint index1,index2index1,index2； /原数据的下标原数据的下标 orgmaxnorgmaxn22； /存储原数据的数组存储原数据的数组 intint hashmaxnhashmaxn2,hn2,hn； /hash/hashii为为 i i 在离散化前的值在离散化前的值 intint nownow22maxnmaxn; ; /存储离散化后的值存储离散化后的值 boolbool cmp(structcmp(struct nodenode a a，structstruct nodenode b)b) returnreturn a.valueba.valueb。

7、value;value; voidvoid discrete(intdiscrete(int n n） intint i,ai,a，b;b; for(i=0for(i=0；in;i+in;i+） scanf(”scanf(”d dd”d” ， ; orgorgi i 。value=a;value=a; orgorgi i 。index1=0;index1=0; orgorgi.index2=i;i.index2=i; orgorgi+ni+n.value=b.value=b； orgi+norgi+n.index1=1;.index1=1; orgi+norgi+n。index2=i;inde

8、x2=i; 数据结构模板 - 10 - sortsort（org,org+n*2org,org+n*2，cmp)cmp)； for(hn=0for(hn=0，i=0i=0；inin2;i+)2;i+) ifif（i=0i=0 orgorgi i.value!=orgi-1.value!=orgi-1。value)value) hn+;hn+; noworgnoworgii。index1index1orgiorgi.index2.index2=hn;=hn; hashhn=orgi.value;hashhn=orgi.value; 数据结构模板 - 11 - rmqrmq 问题（问题（stst

9、算法）算法） /时间复杂度（o(nlogn+q）) includemathincludemath。hh definedefine n n 6000060000 intint d d4040； /2 的 i 次方 intint n,valn,valnn，ststnn3030; ; /顶点数，n 从 1 开始 intint themax(intthemax(int x,intx,int y)y) ifif（xy)xy) returnreturn x;x; returnreturn y y； voidvoid init_rmq()init_rmq() intint i i，j j，k k； forf

10、or（d0d0=1=1，i=1;i30;i+)i=1;i30;i+) d di i=d=di-11;i-11; /初始化 d 值 forfor（i=1;i=ni=1;i=n；i+i+） ststi0i0=val=vali;i; k=int(logk=int(log（(double(double）n n）/log/log（2.00)2.00)； forfor（j=1;j=kj=1;j=k；j+j+） forfor（i=1i=1；i=n;i+)i=n;i+) if(i+dif(i+dj-1j-1-1=n-1=n） 数据结构模板 - 12 - ststijij=themax=themax（ststi

11、 i j-1j-1 ，sti+dsti+dj j1 1 j j1 1 ） ； elseelse breakbreak； intint query(intquery(int x x，intint y)y) intint k=intk=int（ loglog（doubledouble（y yx+1x+1） ） / / log(2.00)log(2.00) ）; ; returnreturn themax(stthemax(stx x kk，sty-dksty-dk+1+1 kk）; ; 数据结构模板 - 13 - lcalca 问题问题(st(st 算法）算法） /时间复杂度（o(n*logn+q

12、）) #includemath.h#includemath.h #define#define maxptmaxpt 10001000 definedefine maxegmaxeg 10001000 definedefine n n maxpt*3maxpt*3 structstruct edgesedges intint v,next;v,next; emaxeg;emaxeg; intint m m，n;n; /树的边数和节点数 intint gmaxptgmaxpt； intint d d40,stn40,stn30;30; intint idid； /待 rmq 数组大小 intint

13、 deepdeepn;n; /待 rmq 的数组 intint posmaxptposmaxpt ； /树中顶点在 rmq 数组中的位置 intint fnfn； /rmq 数组元素在树中的顶点编号 boolbool vismaxptvismaxpt ； intint theminthemin（intint x,intx,int y y） 数据结构模板 - 14 - ifif（deepxdeepydeepxdeepy) ) returnreturn x;x; returnreturn y y； voidvoid init_rmqinit_rmq（) ) intint i i，j j，k;k;

14、forfor（d d0=1,i=10=1,i=1；i30i30；i+i+） d di i=d=di i1 111； /初始化 d 值 forfor（i=1;i=idi=1;i=id；i+)i+) ststii0 0=i;=i; k=int(logk=int(log（doubledouble）idid）/log/log（2.00)2.00)） ； for(j=1for(j=1；j=kj=k；j+j+） for(i=1for(i=1；i=id;i+i=id;i+） ifif（i+dj-1i+dj-1-1=id)-1=id) stisti j j=themin=themin（stijstij11，s

15、tsti+di+dj j1 1 j-1j-1) )； elseelse break;break; intint queryquery（intint u,intu,int v v） intint t t，k k，x=posx=posu,y=posvu,y=posv ； 数据结构模板 - 15 - ifif（xyxy） t=xt=x； x=yx=y； y=t;y=t; k=int(k=int( loglog（double(y-x+1double(y-x+1）) ) / / loglog（2 2。0000） );); returnreturn fthemin(stxk,stfthemin(stxk,

16、sty-dky-dk+1k+1k ）; voidvoid dfsdfs（intint u,intu,int d)d) visuvisu=true;=true; f+idf+id=u=u； posposu u=id;=id; deepiddeepid=d=d； forfor（intint i=gi=gu u;i;i=ei.next);i;i=ei.next) ifif（！（！visei.vvisei.v) ) dfs(edfs(ei i 。v,d+1v,d+1） ； f+idf+id=u=u； deepdeepid=d;id=d; voidvoid initinit（) ) m=0m=0； me

17、msetmemset（g g，0 0，sizeofsizeof（g g）);); memset(vismemset(vis，0,sizeof(vis)0,sizeof(vis)） ； id=0;id=0; 数据结构模板 - 16 - 数据结构模板 - 17 - 字典树（字典树（trietrie） definedefine n n 1000010000 /n 最大节点个数 intint toptop，treetreen n2727; ; voidvoid initinit（）（） top=0top=0； memsetmemset（treetree0 0,0,sizeof(tree,0,sizeo

18、f(tree0 0) )） ； intint searchsearch（charchar s s） for(intfor(int root=0root=0；root=treerootroot=treeroot s-as-a ;);) if(if(+s)=0(+s)=0） returnreturn treeroot26treeroot26； returnreturn 0 0； voidvoid insert(charinsert(char *s,int*s,int value)value) intint i i，rootroot，next;next; forfor（root=0root=0，i=0;si=0;si i！=0=0；root=next,i+)root=next,i+) next=treerootnext=treeroots si i-a-a ; ; if(if(！next)next) 数据结构模板 - 18 - top+top+； memsetmemset（treetreetoptop ，0 0，sizeof(treesizeof(treetoptop） ） ； treetreerootroot