常用算法經(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; /取中間的那個位置的值   while(h<r)while (ah<m) h+; /比中間那個位置的值小，循環(huán)直到找一個比中間那個值大的      while (ar>m) r-; /比中間那個位置的值大，循環(huán)直到找一個比中間那個值小的      if(h

2、<=r)int temp=ah;/如果此時h<=r，交換ah和ar         ah=ar;         ar=temp;         h+;r-; /這兩句必不可少哦     if(r>x) qsort(x,r);/注意此處，尾指針跑到前半部分了    &#

3、160;if(h<y) qsort(h,y); /注意此處，頭指針跑到后半部分了調(diào)用：qsort(1,n)即可實現(xiàn)數(shù)組a中元素有序。適用于n比較大的排序 二、冒泡排序void paopao(void) /待排序的數(shù)據(jù)存放在a1.an數(shù)組中for(int i=1;i<n;i+)  /控制循環(huán)（冒泡）的次數(shù)，n個數(shù)，需要n-1次冒泡  for(int j=1;j<=n-i;j+) /相鄰的兩兩比較    if(aj<aj+1) int temp=aj;aj=aj+1;aj+1=temp;或者void paopao(

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

5、初始化for(int i=1;i<=n;i+)/讀入n個數(shù)    int acin>>a;tonga+;/相應(yīng)的桶號計數(shù)器加1  for(int i=1;i<=cmax;i+)  if(tongi>0) /當(dāng)桶中裝的樹大于0，說明i出現(xiàn)過tongi次，否則沒出現(xiàn)過i     while (tongi!=0)       tongi-;cout<<i<< ; 桶排序適用于那些待排序的關(guān)

6、鍵字的值在已知范圍的排序。 四、合（歸）并排序void merge(int l,int m,int r)/合并l,m和m+1,r兩個已經(jīng)有序的區(qū)間 int b101;/借助一個新的數(shù)組B，使兩個有序的子區(qū)間合并成一個有序的區(qū)間，b數(shù)組的大小要注意  int h,t,k;  k=0;/用于新數(shù)組B的指針  h=l;t=m+1;/讓h指向第一個區(qū)間的第一個元素，t指向第二個區(qū)間的第一個元素。  while(h<=m)&&(t<=r)/在指針h和t沒有到區(qū)間尾時，把兩個區(qū)間的元素抄在新數(shù)組中  

7、0; k+;       /新數(shù)組指針加1     if (ah<at)bk=ah;h+;       /抄第一個區(qū)間元素到新數(shù)組     elsebk=at;t+;   /抄第二個區(qū)間元素到新數(shù)組      while(h<=m)k+;bk=ah;h+;  /如果第一個區(qū)間沒有抄結(jié)束，把剩下的抄在新數(shù)組中 

8、; while(t<=r)k+;bk=at;t+;   /如果第二個區(qū)間沒有抄結(jié)束，把剩下的抄在新數(shù)組中  for(int o=1;o<=k;o+)/把新數(shù)組中的元素，再抄回原來的區(qū)間，這兩個連續(xù)的區(qū)間變?yōu)橛行虻膮^(qū)間。al+o-1=bo;void mergesort(int x,int y)/對區(qū)間x,y進行二路歸并排序  int mid;  if(x>=y) return;  mid=(x+y)/2;/求x,y區(qū)間，中間的那個點mid,mid把x,y區(qū)間一分為二  mergesort(x,mid);/對前

9、一段進行二路歸并  mergesort(mid+1,y);/對后一段進行二路歸并  merge(x,mid,y);/把已經(jīng)有序的前后兩段進行合并 歸并排序應(yīng)用了分治思想，把一個大問題，變成兩個小問題。二分是分治的思想。 五、二分查找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;/如果中間元素值為m返回中間元素下標(biāo)mid 

10、; if(head>tail) return 0;/如果x>y，查找失敗，返回0  if(m>amid)  /如果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<iostream>#include<cstring>using namespace s

11、td;int main()  string str1,str2;  int a250,b250,len;   /數(shù)組的大小決定了計算的高精度最大位數(shù)  int i;  memset(a,0,sizeof(a);  memset(b,0,sizeof(b);  cin>>str1>>str2;   /輸入兩個字符串  a0=str1.length();  /取得第一個字符串的長度  for(i=1;i<=a0;i+)  /把第一

12、個字符串轉(zhuǎn)換為整數(shù)，存放在數(shù)組a中    ai=str1a0-i-'0'  b0=str2.length();   /取得第二個字符串長度  for(i=1;i<=b0;i+)   /把第二個字符串中的每一位轉(zhuǎn)換為整數(shù)，存放在數(shù)組B中    bi=str2b0-i-'0'  len=(a0>b0?a0:b0);   /取兩個字符串最大的長度  for(i=1;i<=len;i+)

13、0;  /做按位加法，同時處理進位      ai+=bi;    ai+1+=ai/10;    ai%=10;       len+;    /下面是去掉最高位的0，然后輸出。  while(alen=0)&&(len>1) len-;  for(i=len;i>=1;i-)    cout<<ai; 

14、return 0;  注意：兩個數(shù)相加，結(jié)果的位數(shù)，應(yīng)該比兩個數(shù)中大的那個數(shù)多一位。 七、高精度減法#include<iostream>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);  cin>>str1>>

15、str2;  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)  /大于等于，做按位減，并處理借位。      for(i=1;i<=a0;i+) &#

16、160;    ai-=bi;       if (ai<0) ai+1-;ai+=10;          a0+;    while(aa0=0)&&(a0>1) a0-;    for(i=a0;i>=1;i-)      cout<<ai;  &

17、#160; cout<<endl;                               else      cout<<'-'  /小于就輸出負(fù)號    for(i=1;i<=b0;i+

18、)  /做按位減，大的減小的      bi-=ai;       if (bi<0) bi+1-;bi+=10;          b0+;    while(bb0=0)&&(b0>1) b0-;    for(i=b0;i>=1;i-)      c

19、out<<bi;    cout<<endl;            return 0; int compare(string s1,string s2)  /比較字符串（兩個數(shù)）數(shù)字的大小，大于等于返回0，小于返回1。  if(s1.length()>s2.length() return 0;  /先比較長度，哪個字符串長，對應(yīng)的那個數(shù)就大  if(s1.length()<s2.

20、length() return 1;  for(int i=0;i<=s1.length();i+)  /長度相同時，就一位一位比較。      if(s1i>s2i) return 0;    if(s1i<s2i) return 1;                     &

21、#160;        return 0;   /如果長度相同，每一位也一樣，就返回0，說明相等 做減法時，首先要判斷兩個字符串的大小，決定是否輸出負(fù)號，然后就是按位減法，注意處理借位。 八、高精度乘法#include<iostream>#include<cstring>using namespace std;int main()  string str1,str2;  int a250,b250,c500,len;   

22、0;/250位以內(nèi)的兩個數(shù)相乘  int i,j;  memset(a,0,sizeof(a);  memset(b,0,sizeof(b);  cin>>str1>>str2;  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-'

23、;0'  memset(c,0,sizeof(c);  for(i=1;i<=a0;i+)   /做按位乘法同時處理進位，注意循環(huán)內(nèi)語句的寫法。    for(j=1;j<=b0;j+)        ci+j-1+=ai*bj;    ci+j+=ci+j-1/10;    ci+j-1%=10;         l

24、en=a0+b0+1;  /去掉最高位的0，然后輸出  while(clen=0)&&(len>1) len-;   /為什么此處要len>1?  for(i=len;i>=1;i-)    cout<<ci;  return 0;  注意：兩個數(shù)相乘，結(jié)果的位數(shù)應(yīng)該是這兩個數(shù)的位數(shù)和減1。優(yōu)化：萬進制#include<iostream>#include<cstring>using namespace std;voi

25、d num1(int s,string st1);int a2501,b2501,c5002;/此處可以進行2500位萬進制乘法，即10000位十進制乘法。Int main()      string str1,str2;    int len;    cin>>str1>>str2;    memset(a,0,sizeof(a);    memset(b,0,sizeof(b); 

26、0;  memset(c,0,sizeof(c);    num1(a,str1); /把str1從最低位開始，每4位存放在數(shù)組a中    num1(b,str2); /把str2從最低位開始，每4位存放在數(shù)組b中    for(int i=1;i<=a0;i+) /作按位乘法并處理進位，此處是萬進制進位      for(int j=1;j<=b0;j+)      

27、60;           ci+j-1+=ai*bj;          ci+j+=ci+j-1/10000;          ci+j-1%=10000;            len=a0+b0;/a0和b0存放的是每個

28、數(shù)按4位處理的位數(shù)    while (clen=0)&&(len>1) len-;/去掉高位的0，并輸出最高位      cout<<clen;    for(int i=len-1;i>=1;i-)/把剩下來的每一位還原成4位輸出              if (ci<1000) cout<<0;

29、0;       if (ci<100) cout<<0;        if (ci<10) cout<<0;                cout<<ci;          cout<&l

30、t;endl;    return 0;void num1(int s,string st1)/此函數(shù)的作用就是把字符串st1，按4位一組存放在數(shù)組s中   int k=1,count=1;    s0=st1.length();/存放st1的長度，省去一長度變量    for(int i=s0-1;i>=0;i-) /從最低位開始，處理每一位    if (count%4=0) sk+=(st1i-0)*1000; if(i!=0) k+;

31、0;     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ù)組的位數(shù)，就是按4位處理后的萬進制數(shù)的位數(shù)。  &

32、#160;   Return; 九、高精度除法（沒講） 十、篩選法建立素數(shù)表void maketable(int x)/建立X以內(nèi)的素數(shù)表prim，primi為0，表示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; 

33、;     while(j<=x)       primj=1;j=j+i; 對于那些算法中，經(jīng)常要判斷素數(shù)的問題，建立一個素數(shù)表，可以達到一勞永逸的目的。 十一、深度優(yōu)先搜索void dfs(int x)  以圖的深度優(yōu)先遍歷為例。           cout<<x<< ; 訪問x頂點     

34、 visitedx=1; 作已訪問的標(biāo)記      for(int k=1;k<=n;k+) 對與頂點x相鄰而又沒訪問過的結(jié)點k進行深度優(yōu)先搜索。        if(axk=1)&&(visitedk=0)         dfs(k);    十二、廣度優(yōu)先搜索void  bfs(void) /按廣度優(yōu)先非遞歸遍歷圖G，n個頂點，編

35、號為1.n。注：圖不一定是連通的/使用輔助隊列Q和訪問標(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尚未訪問         int h=1,r=1;

36、    /置空的輔助隊列q         visitedv=1；/頂點v,作訪問標(biāo)記         cout<<v<< ; /訪問頂點v         qr=v；    /v入隊列       

37、60; while(h<=r) /當(dāng)隊列非空時循環(huán)              int tmp=qh;  /隊頭元素出隊，并賦值給tmp             for(int j=1;j<=n;j+)          

38、0;    if(visitedj=0)&&(atmpj=1)/j為tmp的尚未訪問的鄰接頂點                    visitedj=1;  對j作訪問標(biāo)記               

39、     cout<<j<< ; 訪問j                    r+; /隊尾指針加1qr=j; /j入隊  /end-if             h+;   

40、0;       /end -while十三、二叉樹的前序、中序和后序遍歷void preorder(int x)/二叉樹的先序遍歷    if(x=0) return;   cout<<x;/先訪問根   preorder(ax.ld);/再先序遍歷根的左子樹   preorder(ax.rd);/最后先序遍歷根的右子樹 void inorder(int x)/二叉樹的中序遍歷    if(x

41、=0) return;   preorder(ax.ld);/先中序遍歷根的左子樹   cout<<x;/再訪問根   preorder(ax.rd);/最后中序遍歷根的右子樹 void reorder(int x)/二叉樹的后序遍歷    if(x=0) return;   preorder(ax.ld);/先后序遍歷根的左子樹   preorder(ax.rd);/再后序遍歷根的右子樹   cout<<x;/

42、最后訪問根  十四、樹轉(zhuǎn)換為二叉樹算法 十五、二叉排序樹 十六、哈夫曼樹void haff(void) /構(gòu)建哈夫曼樹   for(int i=n+1;i<=2*n-1;i+) /依次生成n-1個結(jié)點     int l=fmin(i-1); /查找權(quán)值最小的結(jié)點的編號l       ai.lchild=l; /把l作為結(jié)點i的左孩子       al.father=i;

43、 /把l的父結(jié)點修改為i       int r=fmin(i-1); /查找次小權(quán)值的編號r       ai.rchild=r; /把l作為結(jié)點i的右孩子       ar.father=i; /把r的父結(jié)點修改為i       ai.da=al.da+ar.da; /合并l,j結(jié)點，生成新結(jié)點i     int

44、fmin(int k)/在1到K中尋找最小的權(quán)值的編號                int mins=0;         for(int s=1;s<=k;s+)           if(amins.da>as.da)&&(as.father=0) /as.father=0,

45、說明這個結(jié)點還不是別個結(jié)點mins=s;                           /的孩子，不等于0說明這個結(jié)點已經(jīng)用過。         return mins;       void inord

46、er(int x)/遞歸生成哈夫曼編碼  if(ax.father=0) ax.code=”“;/根結(jié)點  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)/輸出

47、葉子結(jié)點     cout<<ax.da<<':'<<ax.code<<endl;  if(ax.rchild!=0) inorder(ax.rchild);/遞歸生成右子樹十七、并查集int getfather(int x)/非遞歸求X結(jié)點的根結(jié)點的編號while(x!=fatherx)  x=fatherx; return x; int getfather(int x)/遞歸求X結(jié)點的根結(jié)點的編號if(x=fatherx) return x;

48、60;else return getfather(fatherx);  int getfather(int x)/非遞歸求X結(jié)點的根結(jié)點編號同時進行路徑壓縮int p=x;while(p!=fatherp)/循環(huán)結(jié)束后，P即為根結(jié)點   p=fatherp; while(x!=fatherx)/從X結(jié)點沿X的父結(jié)點進行路徑壓縮   int temp=fatherx;/暫存X沒有修改前的父結(jié)點fatherx=p;/把X的父結(jié)點指向Px=temp;    return p; int get

49、father(int x)/遞歸求X結(jié)點的根結(jié)點編號同時進行路徑壓縮if(x=fatherx) return x; else        int temp=getfather(fatherx);       fatherx=temp;       return temp; void merge(int x,int y)/合并x,y兩個結(jié)點 int x1,x2;  x1=get

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

51、+1;    for (int i=1;i<=n-1;i+)/依次確定n-1條邊  int m=i;   for(int j=i+1;j<=n-1;j+)/確定第i條邊時，依次在i+1至n-1條邊中找最小的那條邊     if(elistj.w<elistm.w) m=j;   if(m!=i) /如果最小的邊不是第i條邊就交換edge tmp=elisti;elisti=elistm;elistm=tmp;   for(int j=i+

52、1;j<=n-1;j+)/更新第i+1至n-1條邊的最小距離。     if(elistj.w>aelisti.toelistj.to) elistj.w=aelisti.toelistj.to;                            for(int

53、i=1;i<=n-1;i+)/求最小生成樹的值ans=ans+elisti.w;                        如果要求出哪些邊構(gòu)成最小生成樹，在更新第i+1至n-1條邊到已經(jīng)生成的樹中最小距離時(上面代碼中加粗的部分)，還要加上elistj.from=elisti.to;語句，即在更新權(quán)值時，還應(yīng)該更新起點。Prime算法適用于頂點不是太多的稠

54、密圖，如果對于頂點數(shù)較多的稀疏圖，就不太適用了。 十九、Dijkstra算法void dijkstra(int x)  /求結(jié)點x到各個結(jié)點的最短路徑memset(vis,0,sizeof(vis); /初始化，visi0表示源點到結(jié)點i未求，否則已求visx=1;prex=0; /初始化源點。for(int i=1;i<=n;i+)   /對其它各點初始化。    if(i!=x)disi=gxi;prei=x;for(int i=1;i<=n-1;i+)   /對于n個結(jié)點的圖，要求x到其

55、它n-1個結(jié)點的最短距離    int m=big; /虛擬一個最大的數(shù)big=99999999;int k=x;      for(int j=1;j<=n;j+)   /在未求出的結(jié)點中找一個源點到其距離最小的點        if(visj=0&&m>disj)m=disj;k=j;      visk=1;   /思考：如

56、果k=X說明什么？說明后面的點，無解。      for(int j=1;j<=n;j+)   /用當(dāng)前找的結(jié)點更新未求結(jié)點到X的最短路徑      if(visj=0)&&(disk+gkj<disj)                    disj=disk+gkj;

57、  /更新         prej=k;  /保存前趨結(jié)點，以便后面求路徑            說明：disi表示x到i的最短距離，prei表示i結(jié)點的前趨結(jié)點。二十、Kruscal算法void qsort(int x,int y)/對邊集數(shù)組進行快速排序int h=x,r=y,m=elist(h+r)>>1.w; while(h<r)  while(el

58、isth.w<m) h+;   while(elistr.w>m) r-;   if(h<=r)    edge tmp=elisth;elisth=elistr;elistr=tmp;h+;r-;   if(x<r) qsort(x,r); if(h<y) qsort(h,y); int getfather(int x)/找根結(jié)點，并壓縮路徑，此處用遞歸實現(xiàn)的。if(x=fatherx) return x; else   &

59、#160;     int f=getfather(fatherx);        fatherx=f;        return f;       void merge(int x,int y)/合并x,y結(jié)點，在此題中的x,y為兩個根結(jié)點。fatherx=y; void kruscal(void)int sum=0,ans=0;qsort(

60、1,t);/對t條邊按權(quán)值大小按從小到大的次序進行快速排序   for(int i=1;i<=t;i+)     int x1=getfather(elisti.from);/取第i條邊的起點所在的樹的根int x2=getfather(elisti.to);/ 取第i條邊的終點所在的樹的根if(x1!=x2)sum+;merge(x1,x2);ans+=elisti.w;/不在同一個集合，合并，即第i條邊可以選取。if(sum>n-1)break;/已經(jīng)確定了n-1條邊了，最小生成樹已經(jīng)生成了，可以提前退出循環(huán)了

61、0;  if(sum<n-1)cout<<"Impossible"<<endl; /從t條邊中無法確定n-1條邊，說明無法生成最小生成樹   else  cout<<ans<<endl;   克魯斯卡爾算法，只用了邊集數(shù)組，沒有用到圖的鄰接矩陣，因此當(dāng)圖的結(jié)點數(shù)比較多的時候，輸入數(shù)據(jù)又是邊的信息時，就要考慮用Kruscal算法。對于島國問題，我們就要選擇此算法，如果用Prim算法，還要開一個二維的數(shù)組來表示圖的鄰接矩陣，對于10000個點的數(shù)據(jù)，顯然在空間上是無

62、法容忍的。 二十一、Floyed算法void floyed(void)/ aij表示結(jié)點i到結(jié)點j的最短路徑長度，初始時值為<I,J>的權(quán)值。for(int k=1;k<=n;k+) /枚舉中間加入的結(jié)點不超過K時fij最短路徑長度，K相當(dāng)DP中的階段        for(int i=1;i<=n;i+) /i，j是結(jié)點i到結(jié)點J，相當(dāng)于DP中的狀態(tài)for(int j=1;j<=n;j+)      if (aij>aik+akj) aij=aik+akj;/這是決策，加和不加中間點，取最