2022年完整word版,C++常用經典算法及其實現要點

《2022年完整word版,C++常用經典算法及其實現要點》由會員分享，可在線閱讀，更多相關《2022年完整word版,C++常用經典算法及其實現要點（22頁珍藏版）》請在裝配圖網上搜索。

1、常用算法經典代碼（C+版）一、快速排序void qsort(int x,int y)/待排序的數據存放在a1.an數組中int h=x,r=y;int m=a(x+y)1;/取中間的那個位置的值while(hr)while(ahm)r-;/比中間那個位置的值大，循環(huán)直到找一個比中間那個值小的if(h=r)int temp=ah;/如果此時hx)qsort(x,r);/注意此處，尾指針跑到前半部分了 if(hy)qsort(h,y);/注意此處，頭指針跑到后半部分了 調用：qsort(1,n)即可實現數組a 中元素有序。適用于n 比較大的排序二、冒泡排序void paopao(void)/待排序

2、的數據存放在a1.an數組中for(int i=1;in;i+)/控制循環(huán)（冒泡）的次數，n 個數，需要n-1 次冒泡for(int j=1;j=n-i;j+)/相鄰的兩兩比較if(ajaj+1)int temp=aj;aj=aj+1;aj+1=temp;或者void paopao(void)/待排序的數據存放在a1.an數組中精選學習資料 -名師歸納總結-第 1 頁，共 22 頁for(int i=1;i=1;j-)/相鄰的兩兩比較if(ajaj+1)int temp=aj;aj=aj+1;aj+1=temp;調用：paopao()，適用于n 比較小的排序三、桶排序void bucketso

3、rt(void)/a的取值范圍已知。如a=cmax。memset(tong,0,sizeof(tong);/桶初始化for(int i=1;ia;tonga+;/相應的桶號計數器加1 for(int i=1;i0)/當桶中裝的樹大于0，說明 i 出現過 tongi 次，否則沒出現過i while(tongi!=0)tongi-;couti ;桶排序適用于那些待排序的關鍵字的值在已知范圍的排序。四、合（歸）并排序void merge(int l,int m,int r)/合并 l,m 和m+1,r兩個已經有序的區(qū)間 int b101;/借助一個新的數組B，使兩個有序的子區(qū)間合并成一個有序的區(qū)間，

4、b 數組的大小要注意精選學習資料 -名師歸納總結-第 2 頁，共 22 頁int h,t,k;k=0;/用于新數組B 的指針h=l;t=m+1;/讓 h 指向第一個區(qū)間的第一個元素，t 指向第二個區(qū)間的第一個元素。while(h=m)&(t=r)/在指針 h 和 t 沒有到區(qū)間尾時，把兩個區(qū)間的元素抄在新數組中k+;/新數組指針加1 if(ahat)bk=ah;h+;/抄第一個區(qū)間元素到新數組elsebk=at;t+;/抄第二個區(qū)間元素到新數組 while(h=m)k+;bk=ah;h+;/如果第一個區(qū)間沒有抄結束，把剩下的抄在新數組中while(t=r)k+;bk=at;t+;/如果第二個區(qū)

5、間沒有抄結束，把剩下的抄在新數組中for(int o=1;o=y)return;mid=(x+y)/2;/求x,y 區(qū)間，中間的那個點mid,mid把 x,y 區(qū)間一分為二mergesort(x,mid);/對前一段進行二路歸并mergesort(mid+1,y);/對后一段進行二路歸并merge(x,mid,y);/把已經有序的前后兩段進行合并 歸并排序應用了分治思想，把一個大問題，變成兩個小問題。二分是分治的思想。精選學習資料 -名師歸納總結-第 3 頁，共 22 頁五、二分查找int find(int x,int y,int m)/在x,y 區(qū)間查找關鍵字等于m 的元素下標 int he

6、ad,tail,mid;head=x;tail=y;mid=(x+y)/2);/取中間元素下標if(amid=m)return mid;/如果中間元素值為m 返回中間元素下標mid if(headtail)return 0;/如果 xy，查找失敗，返回0 if(mamid)/如果 m 比中間元素大，在后半區(qū)間查找，返回后半區(qū)間查找結果return find(mid+1,tail);else/如果 m 比中間元素小，在前半區(qū)間查找，返回后前區(qū)間查找結果return find(head,mid-1);六、高精度加法#include#include using namespace std;int m

7、ain()string str1,str2;int a250,b250,len;/數組的大小決定了計算的高精度最大位數int i;memset(a,0,sizeof(a);memset(b,0,sizeof(b);cinstr1str2;/輸入兩個字符串a0=str1.length();/取得第一個字符串的長度for(i=1;i=a0;i+)/把第一個字符串轉換為整數，存放在數組a 中ai=str1a0-i-0;b0=str2.length();/取得第二個字符串長度for(i=1;ib0?a0:b0);/取兩個字符串最大的長度for(i=1;i1)len-;for(i=len;i=1;i-)

8、coutai;return 0;注意：兩個數相加，結果的位數，應該比兩個數中大的那個數多一位。七、高精度減法#include using namespace std;int compare(string s1,string s2);int main()string str1,str2;int a250,b250,len;int i;memset(a,0,sizeof(a);memset(b,0,sizeof(b);精選學習資料 -名師歸納總結-第 5 頁，共 22 頁cinstr1str2;a0=str1.length();for(i=1;i=a0;i+)ai=str1a0-i-0;b0=st

9、r2.length();for(i=1;i=b0;i+)bi=str2b0-i-0;if(compare(str1,str2)=0)/大于等于，做按位減，并處理借位。for(i=1;i=a0;i+)ai-=bi;if(ai1)a0-;for(i=a0;i=1;i-)coutai;coutendl;else cout-;/小于就輸出負號for(i=1;i=b0;i+)/做按位減，大的減小的bi-=ai;if(bi1)b0-;精選學習資料 -名師歸納總結-第 6 頁，共 22 頁for(i=b0;i=1;i-)coutbi;couts2.length()return 0;/先比較長度，哪個字符串長

10、，對應的那個數就大if(s1.length()s2.length()return 1;for(int i=0;is2i)return 0;if(s1is2i)return 1;return 0;/如果長度相同，每一位也一樣，就返回0，說明相等 做減法時，首先要判斷兩個字符串的大小，決定是否輸出負號，然后就是按位減法，注意處理借位。八、高精度乘法#include#include using namespace std;int main()精選學習資料 -名師歸納總結-第 7 頁，共 22 頁 string str1,str2;int a250,b250,c500,len;/250位以內的兩個數相

11、乘int i,j;memset(a,0,sizeof(a);memset(b,0,sizeof(b);cinstr1str2;a0=str1.length();for(i=1;i=a0;i+)ai=str1a0-i-0;b0=str2.length();for(i=1;i=b0;i+)bi=str2b0-i-0;memset(c,0,sizeof(c);for(i=1;i=a0;i+)/做按位乘法同時處理進位，注意循環(huán)內語句的寫法。for(j=1;j1)len-;/為什么此處要len1?for(i=len;i=1;i-)coutci;return 0;精選學習資料 -名師歸納總結-第 8 頁，

12、共 22 頁注意：兩個數相乘，結果的位數應該是這兩個數的位數和減1。優(yōu)化：萬進制#include#include using namespace std;void num1(int s,string st1);int a2501,b2501,c5002;/此處可以進行2500 位萬進制乘法，即 10000 位十進制乘法。Int main()string str1,str2;int len;cinstr1str2;memset(a,0,sizeof(a);memset(b,0,sizeof(b);memset(c,0,sizeof(c);num1(a,str1);/把 str1 從最低位開始，每

13、4 位存放在數組a 中num1(b,str2);/把 str2 從最低位開始，每4 位存放在數組b 中for(int i=1;i=a0;i+)/作按位乘法并處理進位，此處是萬進制進位for(int j=1;j1)len-;/去掉高位的0，并輸出最高位 cout=1;i-)/把剩下來的每一位還原成4 位輸出精選學習資料 -名師歸納總結-第 9 頁，共 22 頁 if(ci1000)cout 0;if(ci100)cout 0;if(ci10)cout 0;coutci;cout=0;i-)/從最低位開始，處理每一位 if(count%4=0)sk+=(st1i-0)*1000;if(i!=0)k

14、+;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 maketable(int x)/建立 X 以內的素數表prim，primi 為 0，表示 i 為素數，為1 表示不是質數精選學習資料 -名師歸納總結-第 10 頁，共 22 頁 memset(prim,0,sizeof(prim);/初始化質數表 prim0=1;prim1=1;p

15、rim2=0;/用篩選法求X 以內的質數表 for(int i=2;i=x;i+)if(primi=0)int j=2*i;while(j=x)primj=1;j=j+i;對于那些算法中，經常要判斷素數的問題，建立一個素數表，可以達到一勞永逸的目的。十一、深度優(yōu)先搜索void dfs(int x)以圖的深度優(yōu)先遍歷為例。coutx ;訪問 x 頂點作已訪問的標記對與頂點x 相鄰而又沒訪問過的結點k 進行深度優(yōu)先搜索。if(axk=1)&(visitedk=0)dfs(k);十二、廣度優(yōu)先搜索void bfs(void)/按廣度優(yōu)先非遞歸遍歷圖G，n 個頂點，編號為1.n。注：圖不一定是連通的/

16、使用輔助隊列Q 和訪問標記數組visited。for(v=1;v=n;v+)visitedv=0；/標記數組初始化for(v=1;v=n;v+)精選學習資料 -名師歸納總結-第 11 頁，共 22 頁if(visitedv=0)/v 尚未訪問int h=1,r=1;/置空的輔助隊列q visitedv=1；/頂點 v,作訪問標記coutv ;/訪問頂點v qr=v；/v 入隊列while(h=r)/當隊列非空時循環(huán) int tmp=qh;/隊頭元素出隊，并賦值給tmp for(int j=1;j=n;j+)if(visitedj=0)&(atmpj=1)/j為 tmp 的尚未訪問的鄰接頂點 v

17、isitedj=1;對 j 作訪問標記coutj ;訪問 j r+;/隊尾指針加1 qr=j;/j入隊 /end-if h+;/end-while 十三、二叉樹的前序、中序和后序遍歷void preorder(int x)/二叉樹的先序遍歷 if(x=0)return;coutx;/先訪問根preorder(ax.ld);/再先序遍歷根的左子樹preorder(ax.rd);/最后先序遍歷根的右子樹 精選學習資料 -名師歸納總結-第 12 頁，共 22 頁void inorder(int x)/二叉樹的中序遍歷 if(x=0)return;preorder(ax.ld);/先中序遍歷根的左子樹

18、coutx;/再訪問根preorder(ax.rd);/最后中序遍歷根的右子樹 void reorder(int x)/二叉樹的后序遍歷 if(x=0)return;preorder(ax.ld);/先后序遍歷根的左子樹preorder(ax.rd);/再后序遍歷根的右子樹coutx;/最后訪問根 十四、樹轉換為二叉樹算法十五、二叉排序樹十六、哈夫曼樹void haff(void)/構建哈夫曼樹 for(int i=n+1;i=2*n-1;i+)/依次生成 n-1 個結點int l=fmin(i-1);/查找權值最小的結點的編號l ai.lchild=l;/把 l 作為結點i 的左孩子al.f

19、ather=i;/把 l 的父結點修改為i 精選學習資料 -名師歸納總結-第 13 頁，共 22 頁int r=fmin(i-1);/查找次小權值的編號r ai.rchild=r;/把 l 作為結點i 的右孩子ar.father=i;/把 r 的父結點修改為i ai.da=al.da+ar.da;/合并 l,j 結點，生成新結點i int fmin(int k)/在 1 到 K 中尋找最小的權值的編號 int mins=0;for(int s=1;sas.da)&(as.father=0)/as.father=0,說明這個結點還不是別個結點mins=s;/的孩子，不等于0 說明這個結點已經用過

20、。return mins;void inorder(int x)/遞歸生成哈夫曼編碼 if(ax.father=0)ax.code=”“;/根結點if(aax.father.lchild=x)ax.code=aax.father.code+0;if(aax.father.rchild=x)ax.code=aax.father.code+1;if(ax.lchild!=0)inorder(ax.lchild);/遞歸生成左子樹if(ax.lchild=0)&(ax.rchild=0)/輸出葉子結點coutax.da:ax.codeendl;if(ax.rchild!=0)inorder(ax.r

21、child);/遞歸生成右子樹 十七、并查集int getfather(int x)/非遞歸求 X 結點的根結點的編號while(x!=fatherx)精選學習資料 -名師歸納總結-第 14 頁，共 22 頁x=fatherx;return x;int getfather(int x)/遞歸求 X 結點的根結點的編號if(x=fatherx)return x;else return getfather(fatherx);int getfather(int x)/非遞歸求 X 結點的根結點編號同時進行路徑壓縮int p=x;while(p!=fatherp)/循環(huán)結束后，P即為根結點p=fath

22、erp;while(x!=fatherx)/從 X 結點沿 X 的父結點進行路徑壓縮int temp=fatherx;/暫存 X沒有修改前的父結點fatherx=p;/把 X 的父結點指向P x=temp;return p;int getfather(int x)/遞歸求 X 結點的根結點編號同時進行路徑壓縮if(x=fatherx)return x;else int temp=getfather(fatherx);fatherx=temp;return temp;精選學習資料 -名師歸納總結-第 15 頁，共 22 頁 void merge(int x,int y)/合并 x,y 兩個結點

23、int x1,x2;x1=getfather(x);/取得 X 的父結點x2=getfather(y);/取得 Y 的父結點if(x1!=x2)fatherx1=x2;/兩個父結點不同的話就合并，注意：合并的是X，Y 兩個結點的根。十八、Prime算法void prime(void)/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+)/

24、依次確定n-1 條邊int m=i;for(int j=i+1;j=n-1;j+)/確定第 i 條邊時，依次在i+1 至 n-1 條邊中找最小的那條邊if(elistj.welistm.w)m=j;if(m!=i)/如果最小的邊不是第i 條邊就交換edge tmp=elisti;elisti=elistm;elistm=tmp;for(int j=i+1;jaelisti.toelistj.to)elistj.w=aelisti.toelistj.to;for(int i=1;i=n-1;i+)/求最小生成樹的值精選學習資料 -名師歸納總結-第 16 頁，共 22 頁ans=ans+elist

25、i.w;如果要求出哪些邊構成最小生成樹，在更新第i+1至 n-1 條邊到已經生成的樹中最小距離時(上面代碼中加粗的部分)，還要加上elistj.from=elisti.to;語句，即在更新權值時，還應該更新起點。Prime算法適用于頂點不是太多的稠密圖，如果對于頂點數較多的稀疏圖，就不太適用了。十九、Dijkstra算法void dijkstra(int x)/求結點 x 到各個結點的最短路徑 memset(vis,0,sizeof(vis);/初始化，visi 0 表示源點到結點i 未求，否則已求visx=1;prex=0;/初始化源點。for(int i=1;i=n;i+)/對其它各點初始

26、化。if(i!=x)disi=gxi;prei=x;for(int i=1;i=n-1;i+)/對于 n 個結點的圖，要求x 到其它 n-1 個結點的最短距離 int m=big;/虛擬一個最大的數big=99999999;int k=x;for(int j=1;jdisj)m=disj;k=j;精選學習資料 -名師歸納總結-第 17 頁，共 22 頁 visk=1;/思考：如果k=X 說明什么？說明后面的點，無解。for(int j=1;j=n;j+)/用當前找的結點更新未求結點到X 的最短路徑 if(visj=0)&(disk+gkj1.w;while(hr)while(elisth.wm

27、)r-;if(h=r)edge tmp=elisth;elisth=elistr;elistr=tmp;h+;r-;if(xr)qsort(x,r);if(hy)qsort(h,y);int getfather(int x)/找根結點，并壓縮路徑，此處用遞歸實現的。if(x=fatherx)return x;else int f=getfather(fatherx);精選學習資料 -名師歸納總結-第 18 頁，共 22 頁fatherx=f;return f;void merge(int x,int y)/合并 x,y 結點，在此題中的x,y 為兩個根結點。fatherx=y;void kru

28、scal(void)int sum=0,ans=0;qsort(1,t);/對 t 條邊按權值大小按從小到大的次序進行快速排序for(int i=1;in-1)break;/已經確定了n-1條邊了，最小生成樹已經生成了，可以提前退出循環(huán)了 if(sumn-1)coutImpossibleendl;/從 t 條邊中無法確定n-1條邊，說明無法生成最小生成樹else coutansendl;克魯斯卡爾算法，只用了邊集數組，沒有用到圖的鄰接矩陣，因此當圖的結點數比較多的時候，輸入數據又是邊的信息時，就要考慮用Kruscal算法。對于島國問題，我們就要選擇此算法，如果用Prim算法，還要開一個二維的數

29、組來表示圖的鄰接矩陣，對于10000個點的數據，顯然在空間上是無法容忍的。精選學習資料 -名師歸納總結-第 19 頁，共 22 頁二十一、Floyed算法void floyed(void)/aij表示結點i 到結點 j 的最短路徑長度，初始時值為的權值。for(int k=1;k=n;k+)/枚舉中間加入的結點不超過K 時 fij最短路徑長度，K 相當DP 中的階段 for(int i=1;i=n;i+)/i，j 是結點 i 到結點 J，相當于DP 中的狀態(tài)for(int j=1;jaik+akj)aij=aik+akj;/這是決策，加和不加中間點，取最小的值 弗洛伊德算法適合于求沒有負權回路

30、的圖的最短路徑長度，利用FLOYED 算法，可寫出判斷結點 i 和結點 J 是否連通的算法。二十二、01 背包問題n 為物品的數量，wi 表示第 i 個物品的重量，ci 表示第 i 個物品的價值，v 為背包的最大重量。有狀態(tài)轉移方程fij=maxfi-1j,fi-1j-wi+ci。fij表示前 i 個物品，在背包載重為 j 時獲得的最大價值。顯然fnv即為所求。邊界條件為f0s=0,s=0,1,v。for(int i=1;i=n;i+)/枚舉階段 for(int j=0;j=0;j-)fij=fi-1j;/不選第 i 個物品if(fijfi-1j-wi+ci)fij=fi-1j-wi+ci;/

31、選第 i 個物品 coutfnvendl;/輸出結果。優(yōu)化：用一維數組實現，把第i-1 階段和第i 階段數據存在一塊。for(int i=1;i=0;j-)/枚舉狀態(tài)，當然此處也可寫成:for(int j=v;j=0;j-)精選學習資料 -名師歸納總結-第 20 頁，共 22 頁 fj=fj;/不選第 i 個物品，可省略此語句。if(jwi)&(fjfj-wi+ci)fj=fj-wi+ci;/選第 i 個物品 coutfv=wi;j-)，此時下面的判斷條件j=wi就可以省略了。二十三、完全背包問題和 01 背包問題不同的是，完全背包，對于任何一個物品i，只要背包重量允許，可以多次選取，也就是在

32、決策上，可以選0 個，1 個，2 個，v/wi 個。狀態(tài)轉移方程fij=maxfi-1j,fi-1j-wi+ci，fi-1j-2*wi+2*ci，fi-1j-k*wi+k*ci。k=0，1，2，v/wi。fij表示前 i 個物品，在背包載重為j時獲得的最大價值。顯然fnv即為所求。邊界條件為f0s=0,s=0,1,v。for(int i=1;i=n;i+)/枚舉階段 for(int j=0;j=0;j-)fij=fi-1j;/k=0的情況作為fij的初始值，然后在 k=1,2,v/wi中找最大值for(int k=1;k=v/wi;k+)if(fijfi-1j-k*wi+k*ci)fij=fi

33、-1j-k*wi+k*ci;/選第 i 個物品 coutfnvendl;/輸出結果。二十四、多屬性背包問題精選學習資料 -名師歸納總結-第 21 頁，共 22 頁二十五、多背包問題二十六、最長不降（上升）子序列問題 fi 表示從第1 個數開始，以第i 個數結尾的最長遞增子序列。狀態(tài)轉移方程：fi=maxfj+1（1j i-1，1i n，ai aj）臨界狀態(tài)：f1=1;二十七、最長公共子序列問題fij 表示第一個串前i 個字符和第二個串前j 個字符的最長公共子序列數。狀態(tài)轉移方程：fi-1j-1 (若 ai=bj)fij=maxfi-1j,fij-1+1 (若 ai bj)臨界狀態(tài):f0j=0，fi0=0 精選學習資料 -名師歸納總結-第 22 頁，共 22 頁