2022年完整word版,C++常用经典算法及其实现要点.docx

精选学习资料 - - - - - - - - - 常用算法经典代码（C+ 版）一、快速排序void qsortint x,int y /待排序的数据存放在a1.an数组中int h=x,r=y; int m=ax+y>>1; / 取中间的那个位置的值whileh<r while ah<m h+; / 比中间那个位置的值小,循环直到找一个比中间那个值大的while ar>m r-; / 比中间那个位置的值大,循环直到找一个比中间那个值小的ifh<=r int temp=ah;/ 假如此时 h<=r ,交换 ah 和 ar ah=ar; ar=temp; h+;r-; / 这两句必不行少哦 ifr>x qsortx,r;/ 留意此处,尾指针跑到前半部分了 ifh<y qsorth,y; / 留意此处,头指针跑到后半部分了 调用： qsort1,n即可实现数组a 中元素有序；适用于n 比较大的排序二、冒泡排序void paopaovoid /待排序的数据存放在a1.an数组中n-1 次冒泡forint i=1;i<n;i+ / 掌握循环（冒泡）的次数,n 个数,需要forint j=1;j<=n-i;j+ /相邻的两两比较ifaj<aj+1 int temp=aj;aj=aj+1;aj+1=temp; 或者名师归纳总结 void paopaovoid /待排序的数据存放在a1.an数组中第 1 页,共 22 页- - - - - - -精选学习资料 - - - - - - - - - forint i=1;i<n;i+ / 掌握循环（冒泡）的次数,n 个数,需要n-1 次冒泡forint j=n-i;j>=1;j- / 相邻的两两比较ifaj<aj+1 int temp=aj;aj=aj+1;aj+1=temp; 调用： paopao,适用于n 比较小的排序三、桶排序void bucketsortvoid/a 的取值范畴已知；如 a<=cmax ； memsettong,0,sizeoftong;/ 桶初始化forint i=1;i<=n;i+/ 读入 n 个数int a cin>>a; tonga+;/相应的桶号计数器加1 forint i=1;i<=cmax;i+ iftongi>0 /当桶中装的树大于0,说明 i 显现过 tongi 次,否就没显现过i while tongi.=0 tongi-; cout<<i<< 桶排序适用于那些待排序的关键字的值在已知范畴的排序；四、合（归）并排序void mergeint l,int m,int r/ 合并 l,m 和m+1,r 两个已经有序的区间 int b101;/ 借助一个新的数组 B,使两个有序的子区间合并成一个有序的区间,b 数组的大小要留意名师归纳总结 - - - - - - -第 2 页,共 22 页精选学习资料 - - - - - - - - - int h,t,k; k=0;/ 用于新数组 B 的指针h=l;t=m+1;/ 让 h 指向第一个区间的第一个元素,t 指向其次个区间的第一个元素；whileh<=m&&t<=r/ 中在指针 h 和 t 没有到区间尾时,把两个区间的元素抄在新数组k+; / 新数组指针加1 if ah<atbk=ah;h+; / 抄第一个区间元素到新数组elsebk=at;t+; / 抄其次个区间元素到新数组 whileh<=mk+;bk=ah;h+; 组中/ 假如第一个区间没有抄终止,把剩下的抄在新数whilet<=rk+;bk=at;t+; / 假如其次个区间没有抄终止,把剩下的抄在新数组中forint o=1;o<=k;o+/把新数组中的元素,再抄回原先的区间,这两个连续的区间变为有序的区间；al+o-1=bo; void mergesortint x,int y/ int mid; ifx>=y return; 对区间 x,y 进行二路归并排序mid=x+y/2;/ 求x,y 区间,中间的那个点 mid,mid 把 x,y 区间一分为二mergesortx,mid;/ 对前一段进行二路归并mergesortmid+1,y;/ 对后一段进行二路归并mergex,mid,y;/ 把已经有序的前后两段进行合并 归并排序应用了分治思想,把一个大问题,变成两个小问题；二分是分治的思想；名师归纳总结 - - - - - - -第 3 页,共 22 页精选学习资料 - - - - - - - - - 五、二分查找int findint x,int y,int m /在x,y 区间查找关键字等于m 的元素下标 int head,tail,mid; head=x;tail=y;mid=x+y/2;/ 取中间元素下标 ifamid=m return mid;/ 假如中间元素值为 m 返回中间元素下标 mid ifhead>tail return 0;/ 假如 x>y ,查找失败,返回 0 ifm>amid / 假如 m 比中间元素大,在后半区间查找,返回后半区间查找结果 return findmid+1,tail; else / 假如 m 比中间元素小,在前半区间查找,返回后前区间查找结果 return findhead,mid-1; 六、高精度加法#include<iostream> #include<cstring> using namespace std; int main string str1,str2; int a250,b250,len; / 数组的大小打算了运算的高精度最大位数 int i; memseta,0,sizeofa; memsetb,0,sizeofb; cin>>str1>>str2; / 输入两个字符串a 中a0=str1.length; / 取得第一个字符串的长度fori=1;i<=a0;i+ / 把第一个字符串转换为整数,存放在数组ai=str1a0-i-'0' 名师归纳总结 b0=str2.length; / 取得其次个字符串长度B 中第 4 页,共 22 页fori=1;i<=b0;i+ / 把其次个字符串中的每一位转换为整数,存放在数组- - - - - - -精选学习资料 - - - - - - - - - bi=str2b0-i-'0' len=a0>b0.a0:b0; / 取两个字符串最大的长度 fori=1;i<=len;i+ / 做按位加法,同时处理进位 ai+=bi; ai+1+=ai/10; ai%=10; len+; / 下面是去掉最高位的0,然后输出；whilealen=0&&len>1 len-; fori=len;i>=1;i- cout<<ai; return 0; 留意：两个数相加,结果的位数,应当比两个数中大的那个数多一位；七、高精度减法#include<iostream> using namespace std; int comparestring s1,string s2; int main string str1,str2; int a250,b250,len; int i; memseta,0,sizeofa; memsetb,0,sizeofb; 名师归纳总结 - - - - - - -第 5 页,共 22 页精选学习资料 - - - - - - - - - cin>>str1>>str2; a0=str1.length; fori=1;i<=a0;i+ ai=str1a0-i-'0' b0=str2.length; fori=1;i<=b0;i+ bi=str2b0-i-'0' ifcomparestr1,str2=0 fori=1;i<=a0;i+ ai-=bi; / 大于等于,做按位减,并处理借位；if ai<0 ai+1-;ai+=10; a0+; whileaa0=0&&a0>1 a0-; fori=a0;i>=1;i- cout<<ai; cout<<endl; else cout<<'-' / 小于就输出负号 fori=1;i<=b0;i+ / 做按位减,大的减小的 bi-=ai; if bi<0 bi+1-;bi+=10; b0+; whilebb0=0&&b0>1 b0-; 名师归纳总结 - - - - - - -第 6 页,共 22 页精选学习资料 - - - - - - - - - fori=b0;i>=1;i- cout<<bi; cout<<endl; return 0; int comparestring s1,string s2 / 比较字符串（两个数）数字的大小,大于等于返回0,小于返回 1； ifs1.length>s2.length return 0; ifs1.length<s2.length return 1; forint i=0;i<=s1.length;i+ ifs1i>s2i return 0; ifs1i<s2i return 1; / 先比较长度,哪个字符串长,对应的那个数就大/ 长度相同时,就一位一位比较；return 0; / 假如长度相同,每一位也一样,就返回0,说明相等 做减法时,第一要判定两个字符串的大小,打算是否输出负号,然后就是按位减法,留意 处理借位；八、高精度乘法#include<iostream> #include<cstring> using namespace std; int main 名师归纳总结 - - - - - - -第 7 页,共 22 页精选学习资料 - - - - - - - - - string str1,str2; int a250,b250,c500,len; /250位以内的两个数相乘int i,j; memseta,0,sizeofa; memsetb,0,sizeofb; cin>>str1>>str2; a0=str1.length; fori=1;i<=a0;i+ ai=str1a0-i-'0' b0=str2.length; fori=1;i<=b0;i+ bi=str2b0-i-'0' memsetc,0,sizeofc; fori=1;i<=a0;i+ / 做按位乘法同时处理进位,留意循环内语句的写法；forj=1;j<=b0;j+ ci+j-1+=ai*bj; ci+j+=ci+j-1/10; ci+j-1%=10; len=a0+b0+1; / 去掉最高位的0,然后输出len>1. whileclen=0&&len>1 len-; / 为什么此处要fori=len;i>=1;i- cout<<ci; return 0; 名师归纳总结 - - - - - - -第 8 页,共 22 页精选学习资料 - - - - - - - - - 留意：两个数相乘,结果的位数应当是这两个数的位数和减 1；优化：万进制#include<iostream> #include<cstring> using namespace std; void num1int s,string st1; int a2501,b2501,c5002;/此处可以进行2500 位万进制乘法, 即 10000 位十进制乘法；Int main string str1,str2; int len; cin>>str1>>str2; memseta,0,sizeofa; memsetb,0,sizeofb; memsetc,0,sizeofc; num1a,str1; /把 str1 从最低位开头,每4 位存放在数组a 中num1b,str2; /把 str2 从最低位开头,每4 位存放在数组b 中forint i=1;i<=a0;i+ /作按位乘法并处理进位,此处是万进制进位forint j=1;j<=b0;j+ ci+j-1+=ai*bj; ci+j+=ci+j-1/10000; ci+j-1%=10000; len=a0+b0;/a0 和 b0 存放的是每个数按 4 位处理的位数 while clen=0&&len>1 len-;/ 去掉高位的 0,并输出最高位 cout<<clen; 名师归纳总结 forint i=len-1;i>=1;i-/把剩下来的每一位仍原成4 位输出第 9 页,共 22 页- - - - - - -精选学习资料 - - - - - - - - - if ci<1000 cout<<0;if ci<100 cout<<0if ci<10 cout<<0;cout<<ci; cout<<endl; return 0; void num1int s,string st1/此函数的作用就是把字符串st1 ,按 4 位一组存放在数组s 中 int k=1,count=1; s0=st1.length;/ 存放 st1 的长度,省去一长度变量forint i=s0-1;i>=0;i- / 从最低位开头,处理每一位 if count%4=0 sk+=st1i-0*1000; ifi.=0 k+;if count%4=1 sk=st1i-0;if count%4=2 sk+=st1i-0*10;if count%4=3 sk+=st1i-0*100;count+; s0=k; /存放数组的位数,就是按4 位处理后的万进制数的位数；Return; 九、高精度除法（没讲）十、挑选法建立素数表void maketableint x/建立 X 以内的素数表prim ,primi 为 0,表示 i 为素数,为 1 表示不是质数名师归纳总结 - - - - - - -第 10 页,共 22 页精选学习资料 - - - - - - - - - memsetprim,0,sizeofprim;/初始化质数表X 以内的质数表 prim0=1;prim1=1;prim2=0;/用挑选法求 forint i=2;i<=x;i+ if primi=0 int j=2*i; whilej<=x primj=1;j=j+i; 对于那些算法中,常常要判定素数的问题,建立一个素数表,可以达到一劳永逸的目的；十一、深度优先搜寻void dfsint x 以图的深度优先遍历为例； cout<<x<<拜访 x 顶点作已拜访的标记 对与顶点 x 相邻而又没拜访过的结点 k 进行深度优先搜寻；ifaxk=1&&visitedk=0 dfsk; 十二、广度优先搜寻void bfsvoid /按广度优先非递归遍历图G,n 个顶点,编号为1.n ；注：图不肯定是连通的/ 使用帮助队列 Q 和拜访标记数组 visited ；forv=1;v<=n;v+ visitedv=0；/ 标记数组初始化 forv=1; v<=n; v+ 名师归纳总结 - - - - - - -第 11 页,共 22 页精选学习资料 - - - - - - - - - ifvisitedv=0 /v 尚未拜访int h=1,r=1; / 置空的帮助队列q visitedv=1；/ 顶点 v,作拜访标记cout<<v<<拜访顶点 v qr=v ；/v 入队列whileh<=r /当队列非空时循环 int tmp=qh; / 队头元素出队,并赋值给tmp forint j=1;j<=n;j+ ifvisitedj=0&&atmpj=1 /j 为 tmp 的尚未拜访的邻接顶点 visitedj=1; 对 j 作拜访标记cout<<j<<拜访 j r+; / 队尾指针加 1 qr=j; /j 入队 /end-if h+; /end -while 十三、 二叉树的前序、中序和后序遍历void preorderint x/ 二叉树的先序遍历 ifx=0 return; cout<<x;/ 先拜访根preorderax.ld;/ 再先序遍历根的左子树preorderax.rd;/ 最终先序遍历根的右子树 名师归纳总结 - - - - - - -第 12 页,共 22 页精选学习资料 - - - - - - - - - void inorderint x/ 二叉树的中序遍历 ifx=0 return; preorderax.ld;/ 先中序遍历根的左子树cout<<x;/ 再拜访根preorderax.rd;/ 最终中序遍历根的右子树 void reorderint x/ 二叉树的后序遍历 ifx=0 return; preorderax.ld;/ 先后序遍历根的左子树preorderax.rd;/ 再后序遍历根的右子树cout<<x;/ 最终拜访根 十四、树转换为二叉树算法十五、二叉排序树十六、哈夫曼树void haffvoid / 构建哈夫曼树 名师归纳总结 forint i=n+1;i<=2*n-1;i+ /依次生成 n-1 个结点第 13 页,共 22 页int l=fmini-1; /查找权值最小的结点的编号l ai.lchild=l; /把 l 作为结点 i 的左孩子al.father=i; /把 l 的父结点修改为i - - - - - - -精选学习资料 - - - - - - - - - int r=fmini-1; /查找次小权值的编号r ai.rchild=r; / 把 l 作为结点 i 的右孩子ar.father=i; / 把 r 的父结点修改为 i ai.da=al.da+ar.da; / 合并 l,j 结点,生成新结点 i int fminint k/ 在 1 到 K 中查找最小的权值的编号 int mins=0; forint s=1;s<=k;s+ 别个结点ifamins.da>as.da&&as.father=0 /as.father=0, 说明这个结点仍不是mins=s; / 的孩子,不等于0 说明这个结点已经用过；return mins; void inorderint x/ 递归生成哈夫曼编码 ifax.father=0 ax.code=根结点” “;/ifaax.father.lchild=x ifaax.father.rchild=x ax.code=aax.father.code+'0' ax.code=aax.father.code+'1' ifax.lchild.=0 inorderax.lchild;/ 递归生成左子树ifax.lchild=0&&ax.rchild=0/ 输出叶子结点cout<<ax.da<<':'<<ax.code<<endl; ifax.rchild.=0 inorderax.rchild;/ 递归生成右子树 十七、并查集int getfatherint x/ 非递归求 X 结点的根结点的编号whilex.=fatherx 名师归纳总结 - - - - - - -第 14 页,共 22 页精选学习资料 - - - - - - - - - x=fatherx; return x; int getfatherint x/ 递归求 X 结点的根结点的编号 ifx=fatherx return x; else return getfatherfatherx; int getfatherint x/ 非递归求 X 结点的根结点编号同时进行路径压缩 int p=x; whilep.=fatherp/ 循环终止后, P 即为根结点 p=fatherp; whilex.=fatherx/ 从 X 结点沿 X 的父结点进行路径压缩 int temp=fatherx;/ 暂存 X 没有修改前的父结点 fatherx=p;/ 把 X 的父结点指向 P x=temp; return p; int getfatherint x/ 递归求 X 结点的根结点编号同时进行路径压缩 ifx=fatherx return x; else int temp=getfatherfatherx; fatherx=temp; return temp; 名师归纳总结 - - - - - - -第 15 页,共 22 页精选学习资料 - - - - - - - - - void mergeint x,int y/ 合并 x,y 两个结点 int x1,x2; x1=getfatherx;/ 取得 X 的父结点 x2=getfathery;/ 取得 Y 的父结点 ifx1.=x2 fatherx1=x2; / 两个父结点不同的话就合并,留意：合并的是 X,Y 两个结点 的根； 十八、 Prime 算法void primevoid /prim算法求最小生成树,elisti 是边集数组, aij 为<I,j> 的权值； edge为结构体类型；for int i=1;i<=n-1;i+/初始化结点1 到其它 n-1 个结点形成的边集elisti.from=1; elisti.to=i+1; elisti.w=a1i+1; for int i=1;i<=n-1;i+/ 依次确定 n-1 条边 int m=i; forint j=i+1;j<=n-1;j+/确定第 i 条边时,依次在i+1 至 n-1 条边中找最小的那条边ifelistj.w<elistm.w m=j; ifm.=i /假如最小的边不是第i 条边就交换edge tmp=elisti;elisti=elistm;elistm=tmp; forint j=i+1;j<=n-1;j+/更新第 i+1至 n-1 条边的最小距离；ifelistj.w>aelisti.toelistj.to elistj.w=aelisti.toelistj.to; 名师归纳总结 forint i=1;i<=n-1;i+/求最小生成树的值第 16 页,共 22 页- - - - - - -精选学习资料 - - - - - - - - - ans=ans+elisti.w; 假如要求出哪些边构成最小生成树,在更新第i+1至 n-1 条边到已经生成的树中最小距离时 上面代码中加粗的部分,仍要加上elistj.from=elisti.to;语句,即在更新权值时,仍应当更新起点；Prime算法适用于顶点不是太多的稠密图,假如对于顶点数较多的稀疏图,就不太适用了；十九、 Dijkstra算法void dijkstraint x / 求结点 x 到各个结点的最短路径 memsetvis,0,sizeofvis; / 初始化, visi 0 表示源点到结点 i 未求,否就已求visx=1;prex=0; / 初始化源点；forint i=1;i<=n;i+ / 对其它各点初始化；ifi.=x disi=gxi; prei=x; forint i=1;i<=n-1;i+ / 对于 n 个结点的图,要求x 到其它 n-1 个结点的最短距离 int m=big; /虚拟一个最大的数big=99999999; int k=x; forint j=1;j<=n;j+ / 在未求出的结点中找一个源点到其距离最小的点 ifvisj=0&&m>disj m=disj; k=j; 名师归纳总结 - - - - - - -第 17 页,共 22 页精选学习资料 - - - - - - - - - visk=1; / 摸索：假如 k=X 说明什么？说明后面的点,无解； forint j=1;j<=n;j+ / 用当前找的结点更新未求结点到 X 的最短路径 ifvisj=0&&disk+gkj<disj disj=disk+gkj; / 更新 prej=k; / 储存前趋结点,以便后面求路径 说明： disi 表示 x 到 i 的最短距离, prei 表示 i 结点的前趋结点；二十、 Kruscal 算法void qsortint x,int y/ 对边集数组进行快速排序 int h=x,r=y,m=elisth+r>>1.w; whileh<r whileelisth.w<m h+; whileelistr.w>m r-; ifh<=r edge tmp=elisth;elisth=elistr;elistr=tmp;h+;r-; ifx<r qsortx,r; ifh<y qsorth,y; int getfatherint x/ 找根结点,并压缩路径,此处用递归实现的；ifx=fatherx return x; else int f=getfatherfatherx; 名师归纳总结 - - - - - - -第 18 页,共 22 页精选学习资料 - - - - - - - - - fatherx=f; return f; void mergeint x,int y/合并 x,y 结点,在此题中的x,y 为两个根结点；fatherx=y; void kruscalvoid int sum=0,ans=0; qsort1,t;/ 对 t 条边按权值大小按从小到大的次序进行快速排序 forint i=1;i<=t;i+ int x1=getfatherelisti.from;/取第 i 条边的起点所在的树的根int x2=getfatherelisti.to;/ 取第 i 条边的终点所在的树的根ifx1.=x2 sum+;mergex1,x2;ans+=elisti.w;/不在同一个集合,合并,即第i 条边可以选取；ifsum>n-1 break;/ 已经确定了n-1条边了,最小生成树已经生成了,可以提前退出循环了 ifsum<n-1 cout<<"Impossible"<<endl; /从 t 条边中无法确定n-1条边,说明无法生成最小生成树else cout<<ans<<endl; 克鲁斯卡尔算法,只用了边集数组,没有用到图的邻接矩阵,因此当图的结点数比较多的时候,输入数据又是边的信息时,就要考虑用 Kruscal 算法；对于岛国问题,我们就要选择此算法,假如用 Prim 算法,仍要开一个二维的数组来表示图的邻接矩阵,对于 10000个点的数据,明显在空间上是无法容忍的；名师归纳总结 - - - - - - -第 19 页,共 22 页精选学习资料 - - - - - - - - - 二十一、 Floyed 算法void floyedvoid/ aij表示结点i 到结点 j 的最短路径长度,初始时值为<I,J>的权值；forint k=1;k<=n;k+ /枚举中间加入的结点不超过K 时 fij最短路径长度,K 相当DP 中的阶段 forint i=1;i<=n;i+ / forint j=1;j<=n;j+ i,j 是结点 i 到结点 J,相当于 DP 中的状态 if ai