常用算法經(jīng)典程序C++

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

2、存放在a1.an數(shù)組中for(int i=1;in;i+) /控制循環(huán)（冒泡）的次數(shù)，n個(gè)數(shù)，需要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) /待排序的數(shù)據(jù)存放在a1.an數(shù)組中for(int i=1;i=1;j-) /相鄰的兩兩比較 if(ajaj+1) int temp=aj;aj=aj+1;aj+1=temp;調(diào)用：paopao()，適用于n比較小的排序三、桶排序void bucketsort(void)/a的取值范圍已知。如a=cma

3、x。memset(tong,0,sizeof(tong);/桶初始化for(int i=1;ia;tonga+;/相應(yīng)的桶號(hào)計(jì)數(shù)器加1 for(int i=1;i0) /當(dāng)桶中裝的樹(shù)大于0，說(shuō)明i出現(xiàn)過(guò)tongi次，否則沒(méi)出現(xiàn)過(guò)i while (tongi!=0) tongi-;couti ;桶排序適用于那些待排序的關(guān)鍵字的值在已知范圍的排序。四、合（歸）并排序void merge(int l,int m,int r)/合并l,m和m+1,r兩個(gè)已經(jīng)有序的區(qū)間 int b101;/借助一個(gè)新的數(shù)組B，使兩個(gè)有序的子區(qū)間合并成一個(gè)有序的區(qū)間，b數(shù)組的大小要注意 int h,t,k; k=0;/用

4、于新數(shù)組B的指針 h=l;t=m+1;/讓h指向第一個(gè)區(qū)間的第一個(gè)元素，t指向第二個(gè)區(qū)間的第一個(gè)元素。 while(h=m)&(t=r)/在指針h和t沒(méi)有到區(qū)間尾時(shí)，把兩個(gè)區(qū)間的元素抄在新數(shù)組中 k+; /新數(shù)組指針加1 if (ahat)bk=ah;h+; /抄第一個(gè)區(qū)間元素到新數(shù)組 elsebk=at;t+; /抄第二個(gè)區(qū)間元素到新數(shù)組 while(h=m)k+;bk=ah;h+; /如果第一個(gè)區(qū)間沒(méi)有抄結(jié)束，把剩下的抄在新數(shù)組中 while(t=r)k+;bk=at;t+; /如果第二個(gè)區(qū)間沒(méi)有抄結(jié)束，把剩下的抄在新數(shù)組中 for(int o=1;o=y) return; mid=(x+

5、y)/2;/求x,y區(qū)間，中間的那個(gè)點(diǎn)mid,mid把x,y區(qū)間一分為二 mergesort(x,mid);/對(duì)前一段進(jìn)行二路歸并 mergesort(mid+1,y);/對(duì)后一段進(jìn)行二路歸并 merge(x,mid,y);/把已經(jīng)有序的前后兩段進(jìn)行合并歸并排序應(yīng)用了分治思想，把一個(gè)大問(wèn)題，變成兩個(gè)小問(wèn)題。二分是分治的思想。五、二分查找int find(int x,int y,int m) /在x,y區(qū)間查找關(guān)鍵字等于m的元素下標(biāo) int head,tail,mid; head=x;tail=y;mid=(x+y)/2);/取中間元素下標(biāo) if(amid=m) return mid;/如果中間

6、元素值為m返回中間元素下標(biāo)mid if(headtail) return 0;/如果xy，查找失敗，返回0 if(mamid) /如果m比中間元素大，在后半?yún)^(qū)間查找，返回后半?yún)^(qū)間查找結(jié)果 return find(mid+1,tail); else /如果m比中間元素小，在前半?yún)^(qū)間查找，返回后前區(qū)間查找結(jié)果 return find(head,mid-1);六、高精度加法#include#includeusing namespace std;int main() string str1,str2; int a250,b250,len; /數(shù)組的大小決定了計(jì)算的高精度最大位數(shù) int i; mems

7、et(a,0,sizeof(a); memset(b,0,sizeof(b); cinstr1str2; /輸入兩個(gè)字符串 a0=str1.length(); /取得第一個(gè)字符串的長(zhǎng)度 for(i=1;i=a0;i+) /把第一個(gè)字符串轉(zhuǎn)換為整數(shù)，存放在數(shù)組a中 ai=str1a0-i-0; b0=str2.length(); /取得第二個(gè)字符串長(zhǎng)度 for(i=1;ib0?a0:b0); /取兩個(gè)字符串最大的長(zhǎng)度 for(i=1;i1) len-; for(i=len;i=1;i-) coutai; return 0;注意：兩個(gè)數(shù)相加，結(jié)果的位數(shù)，應(yīng)該比兩個(gè)數(shù)中大的那個(gè)數(shù)多一位。七、高精度減

8、法#includeusing 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); 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; if(compare(str1,str2)=0) /

9、大于等于，做按位減，并處理借位。 for(i=1;i=a0;i+) ai-=bi; if (ai1) a0-; for(i=a0;i=1;i-) coutai; coutendl; else cout-; /小于就輸出負(fù)號(hào) for(i=1;i=b0;i+) /做按位減，大的減小的 bi-=ai; if (bi1) b0-; for(i=b0;i=1;i-) coutbi; couts2.length() return 0; /先比較長(zhǎng)度，哪個(gè)字符串長(zhǎng)，對(duì)應(yīng)的那個(gè)數(shù)就大 if(s1.length()s2.length() return 1; for(int i=0;is2i) return 0;

10、 if(s1is2i) return 1; return 0; /如果長(zhǎng)度相同，每一位也一樣，就返回0，說(shuō)明相等做減法時(shí)，首先要判斷兩個(gè)字符串的大小，決定是否輸出負(fù)號(hào)，然后就是按位減法，注意處理借位。八、高精度乘法#include#includeusing namespace std;int main() string str1,str2; int a250,b250,c500,len; /250位以內(nèi)的兩個(gè)數(shù)相乘 int i,j; memset(a,0,sizeof(a); memset(b,0,sizeof(b); cinstr1str2; a0=str1.length(); for(i=

11、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+) /做按位乘法同時(shí)處理進(jìn)位，注意循環(huán)內(nèi)語(yǔ)句的寫(xiě)法。 for(j=1;j1) len-; /為什么此處要len1? for(i=len;i=1;i-) coutci; return 0;注意：兩個(gè)數(shù)相乘，結(jié)果的位數(shù)應(yīng)該是這兩個(gè)數(shù)的位數(shù)和減1。優(yōu)化：萬(wàn)進(jìn)制#include#includeusing namespace std;void num1(int s,string s

12、t1);int a2501,b2501,c5002;/此處可以進(jìn)行2500位萬(wàn)進(jìn)制乘法，即10000位十進(jìn)制乘法。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從最低位開(kāi)始，每4位存放在數(shù)組a中 num1(b,str2); /把str2從最低位開(kāi)始，每4位存放在數(shù)組b中 for(int i=1;i=a0;i+) /作按位乘法并處理進(jìn)位，此處是萬(wàn)進(jìn)制進(jìn)位 for(int

13、j=1;j1) len-;/去掉高位的0，并輸出最高位 cout=1;i-)/把剩下來(lái)的每一位還原成4位輸出 if (ci1000) cout0; if (ci100) cout0; if (ci10) cout0; coutci; cout=0;i-) /從最低位開(kāi)始，處理每一位 if (count%4=0) sk+=(st1i-0)*1000; if(i!=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; /存放數(shù)

14、組的位數(shù)，就是按4位處理后的萬(wàn)進(jìn)制數(shù)的位數(shù)。 Return;九、高精度除法（沒(méi)講）十、篩選法建立素?cái)?shù)表void maketable(int x)/建立X以內(nèi)的素?cái)?shù)表prim，primi為0，表示i為素?cái)?shù)，為1表示不是質(zhì)數(shù)memset(prim,0,sizeof(prim);/初始化質(zhì)數(shù)表prim0=1;prim1=1;prim2=0;/用篩選法求X以內(nèi)的質(zhì)數(shù)表for(int i=2;i=x;i+) if (primi=0) int j=2*i; while(j=x) primj=1;j=j+i;對(duì)于那些算法中，經(jīng)常要判斷素?cái)?shù)的問(wèn)題，建立一個(gè)素?cái)?shù)表，可以達(dá)到一勞永逸的目的。十一、深度優(yōu)先搜索vo

15、id dfs(int x) 以圖的深度優(yōu)先遍歷為例。 coutx ; 訪問(wèn)x頂點(diǎn) visitedx=1; 作已訪問(wèn)的標(biāo)記 for(int k=1;k=n;k+) 對(duì)與頂點(diǎn)x相鄰而又沒(méi)訪問(wèn)過(guò)的結(jié)點(diǎn)k進(jìn)行深度優(yōu)先搜索。 if(axk=1)&(visitedk=0) dfs(k); 十二、廣度優(yōu)先搜索void bfs(void) /按廣度優(yōu)先非遞歸遍歷圖G，n個(gè)頂點(diǎn)，編號(hào)為1.n。注：圖不一定是連通的/使用輔助隊(duì)列Q和訪問(wèn)標(biāo)記數(shù)組visited。 for(v=1;v=n;v+) visitedv=0；/標(biāo)記數(shù)組初始化 for(v=1; v=n; v+) if(visitedv=0 ) /v尚未訪問(wèn)

16、int h=1,r=1; /置空的輔助隊(duì)列q visitedv=1；/頂點(diǎn)v,作訪問(wèn)標(biāo)記 coutv ; /訪問(wèn)頂點(diǎn)v qr=v； /v入隊(duì)列 while(h=r) /當(dāng)隊(duì)列非空時(shí)循環(huán) int tmp=qh; /隊(duì)頭元素出隊(duì)，并賦值給tmp for(int j=1;j=n;j+) if(visitedj=0)&(atmpj=1)/j為tmp的尚未訪問(wèn)的鄰接頂點(diǎn) visitedj=1; 對(duì)j作訪問(wèn)標(biāo)記 coutj ; 訪問(wèn)j r+; /隊(duì)尾指針加1qr=j; /j入隊(duì) /end-if h+; /end -while十三、二叉樹(shù)的前序、中序和后序遍歷void preorder(int x)/二叉樹(shù)

17、的先序遍歷 if(x=0) return; coutx;/先訪問(wèn)根 preorder(ax.ld);/再先序遍歷根的左子樹(shù) preorder(ax.rd);/最后先序遍歷根的右子樹(shù)void inorder(int x)/二叉樹(shù)的中序遍歷 if(x=0) return; preorder(ax.ld);/先中序遍歷根的左子樹(shù) coutx;/再訪問(wèn)根 preorder(ax.rd);/最后中序遍歷根的右子樹(shù)void reorder(int x)/二叉樹(shù)的后序遍歷 if(x=0) return; preorder(ax.ld);/先后序遍歷根的左子樹(shù) preorder(ax.rd);/再后序遍歷根的

18、右子樹(shù) coutx;/最后訪問(wèn)根十四、樹(shù)轉(zhuǎn)換為二叉樹(shù)算法十五、二叉排序樹(shù)十六、哈夫曼樹(shù)void haff(void) /構(gòu)建哈夫曼樹(shù) for(int i=n+1;i=2*n-1;i+) /依次生成n-1個(gè)結(jié)點(diǎn) int l=fmin(i-1); /查找權(quán)值最小的結(jié)點(diǎn)的編號(hào)l ai.lchild=l; /把l作為結(jié)點(diǎn)i的左孩子 al.father=i; /把l的父結(jié)點(diǎn)修改為i int r=fmin(i-1); /查找次小權(quán)值的編號(hào)r ai.rchild=r; /把l作為結(jié)點(diǎn)i的右孩子 ar.father=i; /把r的父結(jié)點(diǎn)修改為i ai.da=al.da+ar.da; /合并l,j結(jié)點(diǎn)，生成新結(jié)

19、點(diǎn)i int fmin(int k)/在1到K中尋找最小的權(quán)值的編號(hào) int mins=0; for(int s=1;sas.da)&(as.father=0) /as.father=0,說(shuō)明這個(gè)結(jié)點(diǎn)還不是別個(gè)結(jié)點(diǎn)mins=s; /的孩子，不等于0說(shuō)明這個(gè)結(jié)點(diǎn)已經(jīng)用過(guò)。 return mins; void inorder(int x)/遞歸生成哈夫曼編碼 if(ax.father=0) ax.code=”“;/根結(jié)點(diǎn) if(aax.father.lchild=x) ax.code=aax.father.code+0; if(aax.father.rchild=x) ax.code=aax.fa

20、ther.code+1; if(ax.lchild!=0) inorder(ax.lchild);/遞歸生成左子樹(shù) if(ax.lchild=0)&(ax.rchild=0)/輸出葉子結(jié)點(diǎn) coutax.da:ax.codeendl; if(ax.rchild!=0) inorder(ax.rchild);/遞歸生成右子樹(shù)十七、并查集int getfather(int x)/非遞歸求X結(jié)點(diǎn)的根結(jié)點(diǎn)的編號(hào)while(x!=fatherx) x=fatherx;return x;int getfather(int x)/遞歸求X結(jié)點(diǎn)的根結(jié)點(diǎn)的編號(hào)if(x=fatherx) return x;els

21、e return getfather(fatherx);int getfather(int x)/非遞歸求X結(jié)點(diǎn)的根結(jié)點(diǎn)編號(hào)同時(shí)進(jìn)行路徑壓縮int p=x;while(p!=fatherp)/循環(huán)結(jié)束后，P即為根結(jié)點(diǎn) p=fatherp;while(x!=fatherx)/從X結(jié)點(diǎn)沿X的父結(jié)點(diǎn)進(jìn)行路徑壓縮 int temp=fatherx;/暫存X沒(méi)有修改前的父結(jié)點(diǎn)fatherx=p;/把X的父結(jié)點(diǎn)指向Px=temp; return p;int getfather(int x)/遞歸求X結(jié)點(diǎn)的根結(jié)點(diǎn)編號(hào)同時(shí)進(jìn)行路徑壓縮if(x=fatherx) return x;else int temp=g

22、etfather(fatherx); fatherx=temp; return temp;void merge(int x,int y)/合并x,y兩個(gè)結(jié)點(diǎn)int x1,x2; x1=getfather(x);/取得X的父結(jié)點(diǎn) x2=getfather(y);/取得Y的父結(jié)點(diǎn) if(x1!=x2) fatherx1=x2; /兩個(gè)父結(jié)點(diǎn)不同的話就合并，注意：合并的是X，Y兩個(gè)結(jié)點(diǎn)的根。十八、Prime算法void prime(void) /prim算法求最小生成樹(shù)，elisti是邊集數(shù)組，aij為的權(quán)值。edge為結(jié)構(gòu)體類型。for (int i=1;i=n-1;i+)/初始化結(jié)點(diǎn)1到其它n-

23、1個(gè)結(jié)點(diǎn)形成的邊集 elisti.from=1;elisti.to=i+1;elisti.w=a1i+1; for (int i=1;i=n-1;i+)/依次確定n-1條邊 int m=i; for(int j=i+1;j=n-1;j+)/確定第i條邊時(shí)，依次在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.toeli

24、stj.to;for(int i=1;i=n-1;i+)/求最小生成樹(shù)的值ans=ans+elisti.w; 如果要求出哪些邊構(gòu)成最小生成樹(shù)，在更新第i+1至n-1條邊到已經(jīng)生成的樹(shù)中最小距離時(shí)(上面代碼中加粗的部分)，還要加上elistj.from=elisti.to;語(yǔ)句，即在更新權(quán)值時(shí)，還應(yīng)該更新起點(diǎn)。Prime算法適用于頂點(diǎn)不是太多的稠密圖，如果對(duì)于頂點(diǎn)數(shù)較多的稀疏圖，就不太適用了。十九、Dijkstra算法void dijkstra(int x) /求結(jié)點(diǎn)x到各個(gè)結(jié)點(diǎn)的最短路徑memset(vis,0,sizeof(vis); /初始化，visi0表示源點(diǎn)到結(jié)點(diǎn)i未求，否則已求vis

25、x=1;prex=0; /初始化源點(diǎn)。for(int i=1;i=n;i+) /對(duì)其它各點(diǎn)初始化。 if(i!=x)disi=gxi;prei=x;for(int i=1;i=n-1;i+) /對(duì)于n個(gè)結(jié)點(diǎn)的圖，要求x到其它n-1個(gè)結(jié)點(diǎn)的最短距離 int m=big; /虛擬一個(gè)最大的數(shù)big=99999999;int k=x; for(int j=1;jdisj)m=disj;k=j; visk=1; /思考：如果k=X說(shuō)明什么？說(shuō)明后面的點(diǎn)，無(wú)解。 for(int j=1;j=n;j+) /用當(dāng)前找的結(jié)點(diǎn)更新未求結(jié)點(diǎn)到X的最短路徑 if(visj=0)&(disk+gkj1.w;while

26、(hr) while(elisth.wm) 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)/找根結(jié)點(diǎn)，并壓縮路徑，此處用遞歸實(shí)現(xiàn)的。if(x=fatherx) return x;else int f=getfather(fatherx); fatherx=f; return f; void merge(int x,int y)/合并x,y結(jié)點(diǎn)，在此題中的x,y為兩個(gè)根結(jié)點(diǎn)。fatherx=y;void krus

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

28、來(lái)表示圖的鄰接矩陣，對(duì)于10000個(gè)點(diǎn)的數(shù)據(jù)，顯然在空間上是無(wú)法容忍的。二十一、Floyed算法void floyed(void)/ aij表示結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑長(zhǎng)度，初始時(shí)值為的權(quán)值。for(int k=1;k=n;k+) /枚舉中間加入的結(jié)點(diǎn)不超過(guò)K時(shí)fij最短路徑長(zhǎng)度，K相當(dāng)DP中的階段 for(int i=1;i=n;i+) /i，j是結(jié)點(diǎn)i到結(jié)點(diǎn)J，相當(dāng)于DP中的狀態(tài)for(int j=1;jaik+akj) aij=aik+akj;/這是決策，加和不加中間點(diǎn)，取最小的值弗洛伊德算法適合于求沒(méi)有負(fù)權(quán)回路的圖的最短路徑長(zhǎng)度，利用FLOYED算法，可寫(xiě)出判斷結(jié)點(diǎn)i和結(jié)點(diǎn)J是否連通的算法。二十二、01背包問(wèn)題n為物品的數(shù)量，wi表示第i個(gè)物品的重量，ci表示第i個(gè)物品的價(jià)值，v為背包的最大重量。有狀態(tài)轉(zhuǎn)移方程fij=maxfi-1j,fi-1j-wi+ci。fij表示前i個(gè)物品，在背包載重為j時(shí)獲得的最大價(jià)值。顯然fnv即