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

《2022年完整word版,C++常用经典算法及其实现要点.docx》由会员分享，可在线阅读，更多相关《2022年完整word版,C++常用经典算法及其实现要点.docx（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 常用算法经典代码（C+ 版）一、快速排序void qsortint x,int y /待排序的数据存放在a1.an数组中int h=x,r=y; int m=ax+y1; / 取中间的那个位置的值whilehr while ahm r-; / 比中间那个位置的值大,循环直到找一个比中间那个值小的ifh=r int temp=ah;/ 假如此时 hx qsortx,r;/ 留意此处,尾指针跑到前半部分了 ifhy qsorth,y; / 留意此处,头指针跑到后半部分了 调用： qsort1,n即可实现数组a 中元素有序；适用于n 比较大的排序二、

2、冒泡排序void paopaovoid /待排序的数据存放在a1.an数组中n-1 次冒泡forint i=1;in;i+ / 掌握循环（冒泡）的次数,n 个数,需要forint j=1;j=n-i;j+ /相邻的两两比较ifajaj+1 int temp=aj;aj=aj+1;aj+1=temp; 或者名师归纳总结 void paopaovoid /待排序的数据存放在a1.an数组中第 1 页,共 22 页- - - - - - -精选学习资料 - - - - - - - - - forint i=1;i=1;j- / 相邻的两两比较ifajaj+1 int temp=aj;aj=aj+1;

3、aj+1=temp; 调用： paopao,适用于n 比较小的排序三、桶排序void bucketsortvoid/a 的取值范畴已知；如 a=cmax ； memsettong,0,sizeoftong;/ 桶初始化forint i=1;ia; tonga+;/相应的桶号计数器加1 forint i=1;i0 /当桶中装的树大于0,说明 i 显现过 tongi 次,否就没显现过i while tongi.=0 tongi-; couti; 桶排序适用于那些待排序的关键字的值在已知范畴的排序；四、合（归）并排序void mergeint l,int m,int r/ 合并 l,m 和m+1,r

4、 两个已经有序的区间 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 ahatbk=ah;h+; / 抄第一个区间元素到新数组elsebk=at;t+; /

5、 抄其次个区间元素到新数组 whileh=mk+;bk=ah;h+; 组中/ 假如第一个区间没有抄终止,把剩下的抄在新数whilet=rk+;bk=at;t+; / 假如其次个区间没有抄终止,把剩下的抄在新数组中forint o=1;o=y return; 对区间 x,y 进行二路归并排序mid=x+y/2;/ 求x,y 区间,中间的那个点 mid,mid 把 x,y 区间一分为二mergesortx,mid;/ 对前一段进行二路归并mergesortmid+1,y;/ 对后一段进行二路归并mergex,mid,y;/ 把已经有序的前后两段进行合并 归并排序应用了分治思想,把一个大问题,变成两

6、个小问题；二分是分治的思想；名师归纳总结 - - - - - - -第 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 ifheadtail return 0;/ 假如 xy ,查找失败,返回 0 ifmamid / 假如 m 比中间元素大,在后半区间查找,返回后半区间

7、查找结果 return findmid+1,tail; else / 假如 m 比中间元素小,在前半区间查找,返回后前区间查找结果 return findhead,mid-1; 六、高精度加法#include #include using namespace std; int main string str1,str2; int a250,b250,len; / 数组的大小打算了运算的高精度最大位数 int i; memseta,0,sizeofa; memsetb,0,sizeofb; cinstr1str2; / 输入两个字符串a 中a0=str1.length; / 取得第一个字符串的长

8、度fori=1;i=a0;i+ / 把第一个字符串转换为整数,存放在数组ai=str1a0-i-0; 名师归纳总结 b0=str2.length; / 取得其次个字符串长度B 中第 4 页,共 22 页fori=1;ib0.a0:b0; / 取两个字符串最大的长度 fori=1;i1 len-; fori=len;i=1;i- coutai; return 0; 留意：两个数相加,结果的位数,应当比两个数中大的那个数多一位；七、高精度减法#include using namespace std; int comparestring s1,string s2; int main string s

9、tr1,str2; int a250,b250,len; int i; memseta,0,sizeofa; memsetb,0,sizeofb; 名师归纳总结 - - - - - - -第 5 页,共 22 页精选学习资料 - - - - - - - - - cinstr1str2; 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

10、 ai1 a0-; fori=a0;i=1;i- coutai; coutendl; else cout-; / 小于就输出负号 fori=1;i=b0;i+ / 做按位减,大的减小的 bi-=ai; if bi1 b0-; 名师归纳总结 - - - - - - -第 6 页,共 22 页精选学习资料 - - - - - - - - - fori=b0;i=1;i- coutbi; couts2.length return 0; ifs1.lengths2.length return 1; forint i=0;is2i return 0; ifs1is2i return 1; / 先比较长度

11、,哪个字符串长,对应的那个数就大/ 长度相同时,就一位一位比较；return 0; / 假如长度相同,每一位也一样,就返回0,说明相等 做减法时,第一要判定两个字符串的大小,打算是否输出负号,然后就是按位减法,留意 处理借位；八、高精度乘法#include #include using namespace std; int main 名师归纳总结 - - - - - - -第 7 页,共 22 页精选学习资料 - - - - - - - - - string str1,str2; int a250,b250,c500,len; /250位以内的两个数相乘int i,j; memseta,0,s

12、izeofa; memsetb,0,sizeofb; cinstr1str2; 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;j1. whileclen=0&len1 len-; / 为什么此处要fori=len;i=1;i- coutci; return 0; 名师归纳总结 - - - - - - -第 8 页,共 22 页精

13、选学习资料 - - - - - - - - - 留意：两个数相乘,结果的位数应当是这两个数的位数和减 1；优化：万进制#include #include using namespace std; void num1int s,string st1; int a2501,b2501,c5002;/此处可以进行2500 位万进制乘法, 即 10000 位十进制乘法；Int main string str1,str2; int len; cinstr1str2; memseta,0,sizeofa; memsetb,0,sizeofb; memsetc,0,sizeofc; num1a,str1;

14、/把 str1 从最低位开头,每4 位存放在数组a 中num1b,str2; /把 str2 从最低位开头,每4 位存放在数组b 中forint i=1;i=a0;i+ /作按位乘法并处理进位,此处是万进制进位forint j=1;j1 len-;/ 去掉高位的 0,并输出最高位 cout=1;i-/把剩下来的每一位仍原成4 位输出第 9 页,共 22 页- - - - - - -精选学习资料 - - - - - - - - - if ci1000 cout0;if ci100 cout0if ci10 cout0;coutci; cout=0;i- / 从最低位开头,处理每一位 if cou

15、nt%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 页精选学习资料 - - - - - -

16、- - - 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 以图的深度优先遍历为例； coutx拜访 x 顶点作已拜访的标记 对与顶点 x 相邻而又没拜访过的结点 k 进行深度优先搜寻；ifaxk=1&visitedk=0 dfsk; 十二、广度优先搜寻

17、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,作拜访标记coutv拜访顶点 v qr=v ；/v 入队列whileh=r /当队列非空时循环 in

18、t tmp=qh; / 队头元素出队,并赋值给tmp forint j=1;j=n;j+ ifvisitedj=0&atmpj=1 /j 为 tmp 的尚未拜访的邻接顶点 visitedj=1; 对 j 作拜访标记coutj拜访 j r+; / 队尾指针加 1 qr=j; /j 入队 /end-if h+; /end -while 十三、 二叉树的前序、中序和后序遍历void preorderint x/ 二叉树的先序遍历 ifx=0 return; coutx;/ 先拜访根preorderax.ld;/ 再先序遍历根的左子树preorderax.rd;/ 最终先序遍历根的右子树 名师归纳总结

19、 - - - - - - -第 12 页,共 22 页精选学习资料 - - - - - - - - - void inorderint x/ 二叉树的中序遍历 ifx=0 return; preorderax.ld;/ 先中序遍历根的左子树coutx;/ 再拜访根preorderax.rd;/ 最终中序遍历根的右子树 void reorderint x/ 二叉树的后序遍历 ifx=0 return; preorderax.ld;/ 先后序遍历根的左子树preorderax.rd;/ 再后序遍历根的右子树coutx;/ 最终拜访根 十四、树转换为二叉树算法十五、二叉排序树十六、哈夫曼树void

20、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.

21、da; / 合并 l,j 结点,生成新结点 i int fminint k/ 在 1 到 K 中查找最小的权值的编号 int mins=0; forint s=1;sas.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.

22、code=aax.father.code+1; ifax.lchild.=0 inorderax.lchild;/ 递归生成左子树ifax.lchild=0&ax.rchild=0/ 输出叶子结点coutax.da:ax.codeendl; ifax.rchild.=0 inorderax.rchild;/ 递归生成右子树 十七、并查集int getfatherint x/ 非递归求 X 结点的根结点的编号whilex.=fatherx 名师归纳总结 - - - - - - -第 14 页,共 22 页精选学习资料 - - - - - - - - - x=fatherx; return x;

23、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; i

24、nt 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;

25、 / 两个父结点不同的话就合并,留意：合并的是 X,Y 两个结点 的根； 十八、 Prime 算法void primevoid /prim算法求最小生成树,elisti 是边集数组, aij 为 的权值； 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 条边中找最小的那

26、条边ifelistj.welistm.w m=j; ifm.=i /假如最小的边不是第i 条边就交换edge tmp=elisti;elisti=elistm;elistm=tmp; forint j=i+1;jaelisti.toelistj.to elistj.w=aelisti.toelistj.to; 名师归纳总结 forint i=1;i=n-1;i+/求最小生成树的值第 16 页,共 22 页- - - - - - -精选学习资料 - - - - - - - - - ans=ans+elisti.w; 假如要求出哪些边构成最小生成树,在更新第i+1至 n-1 条边到已经生成的树中最

27、小距离时 上面代码中加粗的部分,仍要加上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

28、-1;i+ / 对于 n 个结点的图,要求x 到其它 n-1 个结点的最短距离 int m=big; /虚拟一个最大的数big=99999999; int k=x; forint j=1;jdisj m=disj; k=j; 名师归纳总结 - - - - - - -第 17 页,共 22 页精选学习资料 - - - - - - - - - visk=1; / 摸索：假如 k=X 说明什么？说明后面的点,无解； forint j=1;j=n;j+ / 用当前找的结点更新未求结点到 X 的最短路径 ifvisj=0&disk+gkj1.w; whilehr whileelisth.wm r-; i

29、fh=r edge tmp=elisth;elisth=elistr;elistr=tmp;h+;r-; ifxr qsortx,r; ifhy 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 为两个根结点

30、；fatherx=y; void kruscalvoid int sum=0,ans=0; qsort1,t;/ 对 t 条边按权值大小按从小到大的次序进行快速排序 forint i=1;in-1 break;/ 已经确定了n-1条边了,最小生成树已经生成了,可以提前退出循环了 ifsumn-1 coutImpossibleendl; /从 t 条边中无法确定n-1条边,说明无法生成最小生成树else coutansendl; 克鲁斯卡尔算法,只用了边集数组,没有用到图的邻接矩阵,因此当图的结点数比较多的时候,输入数据又是边的信息时,就要考虑用 Kruscal 算法；对于岛国问题,我们就要选择

31、此算法,假如用 Prim 算法,仍要开一个二维的数组来表示图的邻接矩阵,对于 10000个点的数据,明显在空间上是无法容忍的；名师归纳总结 - - - - - - -第 19 页,共 22 页精选学习资料 - - - - - - - - - 二十一、 Floyed 算法void floyedvoid/ aij表示结点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